betaFeedback

WorksComputer Science

Near-Optimal Regret for Oracle-Efficient Adversarial Contextual Bandits

Abstract

We study contextual bandits with KK actions, a class of NN policies, and i.i.d.\ contexts from a distribution that the learner can sample. For any sequence of loss functions fixed before play, we give an oracle-efficient algorithm with expected regret O(KTlog⁡(2N) log⁡(2KT))O(\sqrt{KT\log(2N)}\,\log(2KT)) against the best policy in hindsight on the realized contexts. This improves the T2/3T^{2/3} dependence on the horizon in prior oracle-efficient bounds and achieves the optimal regret rate in this setting up to logarithmic factors. Our algorithm perturbs policy scores using a Poisson sample of auxiliary contexts. At each sampled context, the perturbation assigned to an action is a Laplace noise draw multiplied by a scale specific to that context and action. We show that choosing these scales to minimize a convex objective determined by past observations yields the stated regret bound. We further approximate the minimizing scales by projected stochastic gradient descent using only an exact offline cost-sensitive optimization oracle that returns the optimum value. Since the table of scales can be large, the algorithm represents the SGD iterates implicitly by storing the random draws that determine each update and evaluates the scales only at queried contexts. Both the oracle complexity and the remaining resource bounds are polynomial in TT, KK, and log⁡(2N)\log(2N).

Introduction

In a contextual bandit problem, the learner observes a context on each of TT rounds, chooses one of KK actions, and observes only the loss of that action. Regret is measured against the best policy in hindsight from a class of NN policies. The classical Exp4\mathrm{Exp4} algorithm achieves expected regret O(KTlog⁡N)O\left(\sqrt{KT\log N}\right) by maintaining a weight for each policy [1]. When the policy class is large, a natural question is whether one can achieve this rate using only an offline optimization oracle for the class. When contexts and loss vectors are drawn jointly i.i.d., Langford and Zhang Langford and Zhang [5] obtained a regret bound with T2/3T^{2/3} dependence on the horizon, and Agarwal et al. Agarwal et al. [2] achieved the optimal square-root rate using an offline optimization oracle.

Achieving square-root regret with an offline optimization oracle becomes much more challenging however when losses are adversarial. In this setting, Rakhlin and Sridharan Rakhlin and Sridharan [7] used auxiliary context samples to obtain expected regret O(T3/4K1/2(log⁡N)1/4)O\left(T^{3/4}K^{1/2}(\log N)^{1/4}\right). Syrgkanis et al. Syrgkanis et al. [8] improved the dependence on the horizon to T2/3T^{2/3}, with regret O((KT)2/3(log⁡N)1/3)O\left((KT)^{2/3}(\log N)^{1/3}\right). Banihashem et al. Banihashem et al. [4] then improved the dependence on the number of actions, obtaining O(T2/3(Klog⁡N)1/3)O\left(T^{2/3}(K\log N)^{1/3}\right) regret. More recently, Buzaglo and Hazan Buzaglo and Hazan [3] obtained O~(T2/3)\widetilde{O}(T^{2/3}) dependence on the horizon without requiring auxiliary context samples. Despite these advances, achieving the optimal T\sqrt{T} dependence on the horizon with an oracle-efficient algorithm has remained an outstanding open problem.

In this paper, we resolve this problem up to logarithmic factors. We give an oracle-efficient algorithm with expected regret

O(KTlog⁡(2N)log⁡(2KT)).O\left(\sqrt{KT\log(2N)}\log(2KT)\right).

Following prior work, we consider a hybrid setting in which contexts are drawn i.i.d. and the adversary fixes an arbitrary sequence of loss functions before play. The learner can draw independent auxiliary samples from the context distribution. The learner has access to independent samples from the context distribution and to an exact offline oracle that returns the minimum total cost over the policy class. Both the number and the size of the oracle queries are polynomial in TT, KK, and log⁡(2N)\log(2N) (Theorem 1).

Model and Main Result

Let T≥1T \ge1, K≥2K \ge2, and let Π\Pi be a nonempty finite class of NN measurable policies π:X→[K]\pi: \mathcal{X} \to[K]. Before play the adversary fixes measurable losses ct:X→[0,1]Kc_t : \mathcal{X} \to[0,1]^K. The actual contexts xtx_t are independent draws from DD. After observing xtx_t, the learner chooses qtq_t, draws At∼qtA_t \sim q_t with fresh randomness, and observes only ct(xt,At)c_t(x_t,A_t). Independent auxiliary samples from DD are available. Given a list of contexts and real cost vectors, the value oracle returns

Val⁡((yi,vi)i)=min⁡π∈Π∑ivi(π(yi)).\operatorname{Val}((y_i,v_i)_i)=\min_{\pi\in\Pi}\sum_i v_i(\pi(y_i)).

We count value-oracle calls, auxiliary context samples, draws from the specified elementary distributions, and exact real-arithmetic operations. The learner is given L=log⁡(2N)L=\log(2N) or an upper bound L0≥log⁡(2N)L_0 \ge\log(2N). Each logarithm and square root used during initialization counts as one exact real-arithmetic operation.

Theorem 1. Let L=log⁡(2N)L=\log(2N). Algorithm 2, tuned with LL, satisfies

EReg⁡T:=E[∑t=1Tct(xt,At)−min⁡π∈Π∑t=1Tct(xt,π(xt))]≤CKTLlog⁡(2KT)\operatorname{EReg}_T:=\mathbb{E}\left[\sum_{t=1}^{T}c_t(x_t,A_t)-\min_{\pi\in\Pi}\sum_{t=1}^{T}c_t(x_t,\pi(x_t))\right]\le C\sqrt{KTL}\log(2KT)

for a universal constant CC. Its number of oracle calls, query sizes, auxiliary context samples, storage and real-arithmetic operations are polynomial in TT, KK, LL. A supplied upper bound L0≥LL_0 \ge L may replace LL in both the tuning and the bounds.

Section 3 reduces regret to a one-round inequality for the ideal action distribution. Section 4 proves its stability estimate. Section 5 implements the distribution to sufficient accuracy to add at most one to the regret bound.

Ideal Strategy and Regret Reduction

Set

γ=(T+1)−1,B=K/γ,ℓ=log⁡(eK/γ),n=ℓ−1TL/K,λ=4nℓ.(1)\gamma=(T+1)^{-1},\qquad B=K/\gamma,\qquad\ell=\log(eK/\gamma),\qquad n=\ell^{-1}\sqrt{TL/K},\qquad\lambda=4n\ell. \tag*{(1)}

At the start of round tt the score of π\pi is S(π)=St−1(π)=−∑i<tc^i(π(xi))S(\pi)=S_{t-1}(\pi)=-\sum_{i<t}\widehat{c}_i(\pi(x_i)), where S0=0S_0=0 and

c^t=eAtct(xt,At)qt(At).(2)\widehat{c}_t=\frac{e_{A_t}c_t(x_t,A_t)}{q_t(A_t)}. \tag*{(2)}

A pool consists of M∼Pois⁡(n)M \sim\operatorname{Pois}(n) contexts Xi∼DX_i \sim D and vectors Zi∼μ=Lap⁡(1)⊗KZ_i \sim\mu= \operatorname{Lap}(1)^{\otimes K}, all independent conditional on MM. The one-dimensional density is e−∣z∣/2e^{-|z|}/2. For a measurable scale σ:X→[1,B]K\sigma:\mathcal{X}\to[1,B]^K define

Pπ(σ)=∑i=1Mσπ(Xi)(Xi)Zi,π(Xi),P_\pi(\sigma)=\sum_{i=1}^{M}\sigma_{\pi(X_i)}(X_i)Z_{i,\pi(X_i)},
F(S,σ)=Emax⁡π∈Π[S(π)+Pπ(σ)],F(S,\sigma)=\mathbb{E}\max_{\pi\in\Pi}[S(\pi)+P_\pi(\sigma)],
JS(σ)=F(S,σ)+λEX∼D∑a=1Klog⁡Bσa(X),R(S)=inf⁡σJS(σ).J_S(\sigma)=F(S,\sigma)+\lambda\mathbb{E}_{X\sim D}\sum_{a=1}^{K}\log\frac{B}{\sigma_a(X)},\qquad R(S)=\inf_{\sigma}J_S(\sigma).

Choose a minimizing scale σ\sigma before observing x=xtx=x_t (Lemma 6). With an independent Z∼μZ\sim\mu, let

Wx=arg max⁡π{S(π)+Pπ(σ)+σπ(x)(x)Zπ(x)}.(3)W_x=\underset{\pi}{\operatorname{arg\,max}}\{S(\pi)+P_\pi(\sigma)+\sigma_{\pi(x)}(x)Z_{\pi(x)}\}. \tag*{(3)}

A fixed order breaks ties. Conditional on S,xS,x define

pa(x)=Pr⁡(Wx(x)=a),qa∗(x)=(1−γ)pa(x)+γ/K.(4)p_a(x)=\Pr(W_x(x)=a),\qquad q_a^*(x)=(1-\gamma)p_a(x)+\gamma/K. \tag*{(4)}

Algorithm 1 gives the ideal strategy. Section 5 implements its scale minimization and action probabilities using a value oracle.

Algorithm 1 Poisson playout with exact action probabilities

  1. Set S0(π)=0S_0(\pi)=0 for every π∈Π\pi\in\Pi. Use the parameters in (1).

  2. For t=1,…,Tt=1,\ldots,T: (a) Choose σ∈arg min⁡σ JSt−1(σ)\sigma\in\underset{\sigma}{\operatorname{arg\,min}}\,J_{S_{t-1}}(\sigma). (b) Receive x=xtx=x_t. For each a∈[K]a\in[K], compute

pa(x)=Pr⁡[(arg max⁡π∈Π{St−1(π)+Pπ(σ)+σπ(x)(x)Zπ(x)})(x)=a].p_a(x)=\Pr\left[\left(\underset{\pi\in\Pi}{\operatorname{arg\,max}}\{S_{t-1}(\pi)+P_\pi(\sigma)+\sigma_{\pi(x)}(x)Z_{\pi(x)}\}\right)(x)=a\right].

The probability averages over the auxiliary pool defining Pπ(σ)P_\pi(\sigma) and the independent vector Z∼μZ\sim\mu, holding St−1,σ,xS_{t-1},\sigma,x fixed.

(c) Set qt(a)=(1−γ)pa(x)+γ/Kq_t(a)=(1-\gamma)p_a(x)+\gamma/K for each aa. Draw At∼qtA_t\sim q_t and observe ct(x,At)c_t(x,A_t). (d) Update the policy scores by

References

  1. [1]Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The non-stochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48–77, 2002.
  2. [2]Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert E. Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, pages 1638–1646, 2014.arxiv.org/abs/1402.0555
  3. [3]Gon Buzaglo and Elad Hazan. Oracle-efficient online classification with stochastic inputs and adversarial outputs. arXiv:2609.33760, 2026.arxiv.org/abs/2609.33760
  4. [4]Kiarash Banihashem, MohammadTaghi Hajiaghayi, Suho Shin, and Max Springer. An improved relaxation for oracle-efficient adversarial contextual bandits. In Advances in Neural Information Processing Systems, volume 36, 2023.arxiv.org/abs/2310.19025
  5. [5]John Langford and Tong Zhang. The Epoch-Greedy algorithm for multi-armed bandits with side information. In Advances in Neural Information Processing Systems, volume 20, 2007.
  6. [7]Alexander Rakhlin and Karthik Sridharan. BISTRO: An efficient relaxation-based method for contextual bandits. In Proceedings of the 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1977–1985, 2016.arxiv.org/abs/1602.02196
  7. [8]Vasilis Syrgkanis, Haipeng Luo, Akshay Krishnamurthy, and Robert E. Schapire. Improved regret bounds for oracle-based adversarial contextual bandits. In Advances in Neural Information Processing Systems, volume 29, 2016.arxiv.org/abs/1606.00313

Paper details

vlnc:W_xs8nytvm
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

OpenAI Astra, Gemini Argon

View statement
Looking for related papers…
Contents