Introduction
In a contextual bandit problem, the learner observes a context on each of T T T rounds, chooses one of K K K actions, and observes only the loss of that action. Regret is measured against the best policy in hindsight from a class of N N N policies. The classical E x p 4 \mathrm{Exp4} Exp4 algorithm achieves expected regret O ( K T log N ) O\left(\sqrt{KT\log N}\right) O ( K T log N ) 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 T 2 / 3 T^{2/3} T 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 ( T 3 / 4 K 1 / 2 ( log N ) 1 / 4 ) O\left(T^{3/4}K^{1/2}(\log N)^{1/4}\right) O ( T 3/4 K 1/2 ( log N ) 1/4 ) . Syrgkanis et al. Syrgkanis et al. [8 ] improved the dependence on the horizon to T 2 / 3 T^{2/3} T 2/3 , with regret O ( ( K T ) 2 / 3 ( log N ) 1 / 3 ) O\left((KT)^{2/3}(\log N)^{1/3}\right) O ( ( K T ) 2/3 ( log N ) 1/3 ) . Banihashem et al. Banihashem et al. [4 ] then improved the dependence on the number of actions, obtaining O ( T 2 / 3 ( K log N ) 1 / 3 ) O\left(T^{2/3}(K\log N)^{1/3}\right) O ( T 2/3 ( K log N ) 1/3 ) regret. More recently, Buzaglo and Hazan Buzaglo and Hazan [3 ] obtained O ~ ( T 2 / 3 ) \widetilde{O}(T^{2/3}) O ( T 2/3 ) dependence on the horizon without requiring auxiliary context samples. Despite these advances, achieving the optimal T \sqrt{T} 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 ( K T log ( 2 N ) log ( 2 K T ) ) . O\left(\sqrt{KT\log(2N)}\log(2KT)\right). O ( K T log ( 2 N ) log ( 2 K T ) ) .
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 T T T , K K K , and log ( 2 N ) \log(2N) log ( 2 N ) (Theorem 1 ).
Model and Main Result
Let T ≥ 1 T \ge1 T ≥ 1 , K ≥ 2 K \ge2 K ≥ 2 , and let Π \Pi Π be a nonempty finite class of N N N measurable policies π : X → [ K ] \pi: \mathcal{X} \to[K] π : X → [ K ] . Before play the adversary fixes measurable losses c t : X → [ 0 , 1 ] K c_t : \mathcal{X} \to[0,1]^K c t : X → [ 0 , 1 ] K . The actual contexts x t x_t x t are independent draws from D D D . After observing x t x_t x t , the learner chooses q t q_t q t , draws A t ∼ q t A_t \sim q_t A t ∼ q t with fresh randomness, and observes only c t ( x t , A t ) c_t(x_t,A_t) c t ( x t , A t ) . Independent auxiliary samples from D D D are available. Given a list of contexts and real cost vectors, the value oracle returns
Val ( ( y i , v i ) i ) = min π ∈ Π ∑ i v i ( π ( y i ) ) . \operatorname{Val}((y_i,v_i)_i)=\min_{\pi\in\Pi}\sum_i v_i(\pi(y_i)). Val (( y i , v i ) i ) = π ∈ Π min i ∑ v i ( π ( 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 ( 2 N ) L=\log(2N) L = log ( 2 N ) or an upper bound L 0 ≥ log ( 2 N ) L_0 \ge\log(2N) L 0 ≥ log ( 2 N ) . Each logarithm and square root used during initialization counts as one exact real-arithmetic operation.
Theorem 1. Let L = log ( 2 N ) L=\log(2N) L = log ( 2 N ) . Algorithm 2, tuned with L L L , satisfies
EReg T : = E [ ∑ t = 1 T c t ( x t , A t ) − min π ∈ Π ∑ t = 1 T c t ( x t , π ( x t ) ) ] ≤ C K T L log ( 2 K T ) \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) EReg T := E [ t = 1 ∑ T c t ( x t , A t ) − π ∈ Π min t = 1 ∑ T c t ( x t , π ( x t )) ] ≤ C K T L log ( 2 K T ) for a universal constant C C C . Its number of oracle calls, query sizes, auxiliary context samples, storage and real-arithmetic operations are polynomial in T T T , K K K , L L L . A supplied upper bound L 0 ≥ L L_0 \ge L L 0 ≥ L may replace L L L 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 ( e K / γ ) , n = ℓ − 1 T L / K , λ = 4 n ℓ . (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)} γ = ( T + 1 ) − 1 , B = K / γ , ℓ = log ( eK / γ ) , n = ℓ − 1 T L / K , λ = 4 n ℓ . (1)
At the start of round t t t the score of π \pi π is S ( π ) = S t − 1 ( π ) = − ∑ i < t c ^ i ( π ( x i ) ) S(\pi)=S_{t-1}(\pi)=-\sum_{i<t}\widehat{c}_i(\pi(x_i)) S ( π ) = S t − 1 ( π ) = − ∑ i < t c i ( π ( x i )) , where S 0 = 0 S_0=0 S 0 = 0 and
c ^ t = e A t c t ( x t , A t ) q t ( A t ) . (2) \widehat{c}_t=\frac{e_{A_t}c_t(x_t,A_t)}{q_t(A_t)}. \tag*{(2)} c t = q t ( A t ) e A t c t ( x t , A t ) . (2)
A pool consists of M ∼ Pois ( n ) M \sim\operatorname{Pois}(n) M ∼ Pois ( n ) contexts X i ∼ D X_i \sim D X i ∼ D and vectors Z i ∼ μ = Lap ( 1 ) ⊗ K Z_i \sim\mu= \operatorname{Lap}(1)^{\otimes K} Z i ∼ μ = Lap ( 1 ) ⊗ K , all independent conditional on M M M . The one-dimensional density is e − ∣ z ∣ / 2 e^{-|z|}/2 e − ∣ z ∣ /2 . For a measurable scale σ : X → [ 1 , B ] K \sigma:\mathcal{X}\to[1,B]^K σ : X → [ 1 , B ] K define
P π ( σ ) = ∑ i = 1 M σ π ( X i ) ( X i ) Z i , π ( X i ) , P_\pi(\sigma)=\sum_{i=1}^{M}\sigma_{\pi(X_i)}(X_i)Z_{i,\pi(X_i)}, P π ( σ ) = i = 1 ∑ M σ π ( X i ) ( X i ) Z i , π ( X i ) ,
F ( S , σ ) = E max π ∈ Π [ S ( π ) + P π ( σ ) ] , F(S,\sigma)=\mathbb{E}\max_{\pi\in\Pi}[S(\pi)+P_\pi(\sigma)], F ( S , σ ) = E π ∈ Π max [ S ( π ) + P π ( σ )] ,
J S ( σ ) = F ( S , σ ) + λ E X ∼ D ∑ a = 1 K log B σ a ( X ) , R ( S ) = inf σ J S ( σ ) . 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). J S ( σ ) = F ( S , σ ) + λ E X ∼ D a = 1 ∑ K log σ a ( X ) B , R ( S ) = σ inf J S ( σ ) .
Choose a minimizing scale σ \sigma σ before observing x = x t x=x_t x = x t (Lemma 6). With an independent Z ∼ μ Z\sim\mu Z ∼ μ , let
W x = 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)} W x = π arg max { S ( π ) + P π ( σ ) + σ π ( x ) ( x ) Z π ( x ) } . (3)
A fixed order breaks ties. Conditional on S , x S,x S , x define
p a ( x ) = Pr ( W x ( x ) = a ) , q a ∗ ( x ) = ( 1 − γ ) p a ( x ) + γ / K . (4) p_a(x)=\Pr(W_x(x)=a),\qquad q_a^*(x)=(1-\gamma)p_a(x)+\gamma/K. \tag*{(4)} p a ( x ) = Pr ( W x ( x ) = a ) , q a ∗ ( x ) = ( 1 − γ ) p a ( x ) + γ / K . (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
Set S 0 ( π ) = 0 S_0(\pi)=0 S 0 ( π ) = 0 for every π ∈ Π \pi\in\Pi π ∈ Π . Use the parameters in (1).
For t = 1 , … , T t=1,\ldots,T t = 1 , … , T : (a) Choose σ ∈ arg min σ J S t − 1 ( σ ) \sigma\in\underset{\sigma}{\operatorname{arg\,min}}\,J_{S_{t-1}}(\sigma) σ ∈ σ arg min J S t − 1 ( σ ) . (b) Receive x = x t x=x_t x = x t . For each a ∈ [ K ] a\in[K] a ∈ [ K ] , compute
p a ( x ) = Pr [ ( arg max π ∈ Π { S t − 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]. p a ( x ) = Pr [ ( π ∈ Π arg max { S t − 1 ( π ) + P π ( σ ) + σ π ( x ) ( x ) Z π ( x ) } ) ( x ) = a ] .
The probability averages over the auxiliary pool defining P π ( σ ) P_\pi(\sigma) P π ( σ ) and the independent vector Z ∼ μ Z\sim\mu Z ∼ μ , holding S t − 1 , σ , x S_{t-1},\sigma,x S t − 1 , σ , x fixed.
(c) Set q t ( a ) = ( 1 − γ ) p a ( x ) + γ / K q_t(a)=(1-\gamma)p_a(x)+\gamma/K q t ( a ) = ( 1 − γ ) p a ( x ) + γ / K for each a a a . Draw A t ∼ q t A_t\sim q_t A t ∼ q t and observe c t ( x , A t ) c_t(x,A_t) c t ( x , A t ) . (d) Update the policy scores by
S t ( π ) = S t − 1 ( π ) − c t ( x , A t ) q t ( A t ) 1 { π ( x ) = A t } , π ∈ Π . S_t(\pi)=S_{t-1}(\pi)-\frac{c_t(x,A_t)}{q_t(A_t)}\mathbf{1}\{\pi(x)=A_t\},\qquad\pi\in\Pi. S t ( π ) = S t − 1 ( π ) − q t ( A t ) c t ( x , A t ) 1 { π ( x ) = A t } , π ∈ Π.
Define for any distribution q q q with full support, with c a = c t ( x , a ) c_a=c_t(x,a) c a = c t ( x , a ) and f a ( π ) = 1 { π ( x ) = a } f_a(\pi)=\mathbf{1}\{\pi(x)=a\} f a ( π ) = 1 { π ( x ) = a } ,
Φ S , x ( q ) = ∑ a q a [ c a + R ( S − c a q a f a ) − R ( S ) ] . \Phi_{S,x}(q)=\sum_a q_a\left[c_a+R\left(S-\frac{c_a}{q_a}f_a\right)-R(S)\right]. Φ S , x ( q ) = a ∑ q a [ c a + R ( S − q a c a f a ) − R ( S ) ] .
This is the conditional mean of the played loss plus the change in R R R .
Theorem 2 (Ideal one-round bound). At every score S S S and for every fixed measurable current loss function,
E x ∼ D Φ S , x ( q ∗ ( x ) ) ≤ u : = γ + 6 log ( N ) / n + 3 K / B . \mathbb{E}_{x\sim D}\Phi_{S,x}(q^*(x)) \le u := \gamma+ 6\log(N)/n + 3K/B. E x ∼ D Φ S , x ( q ∗ ( x )) ≤ u := γ + 6 log ( N ) / n + 3 K / B .
The only stability estimate needed for this theorem is Lemma 3. For q = q ∗ ( x ) q=q^*(x) q = q ∗ ( x ) set b a = c a / q a b_a=c_a/q_a b a = c a / q a and define
W a − = arg max π [ S ( π ) + P π ( σ ) − b a f a ( π ) ] , p a − = Pr ( W a − ( x ) = a ) . W_a^-=\underset{\pi}{\arg\max}\,[S(\pi)+P_\pi(\sigma)-b_af_a(\pi)], \qquad p_a^-=\Pr(W_a^-(x)=a). W a − = π arg max [ S ( π ) + P π ( σ ) − b a f a ( π )] , p a − = Pr ( W a − ( x ) = a ) .
Lemma 3 (One-round stability). Fix a round t t t and an incoming score S = S t − 1 S=S_{t-1} S = S t − 1 . Let σ \sigma σ be the minimizing scale chosen by the ideal strategy at S S S . There exist nonnegative functions D a : X → [ 0 , ∞ ) D_a:\mathcal{X}\to[0,\infty) D a : X → [ 0 , ∞ ) , a ∈ [ K ] a\in[K] a ∈ [ K ] , depending on S S S and σ \sigma σ , such that
E x ∼ D [ ∑ a = 1 K D a ( x ) ] ≤ log N n . \mathbb{E}_{x\sim D}\left[\sum_{a=1}^{K}D_a(x)\right]\le\frac{\log N}{n}. E x ∼ D [ a = 1 ∑ K D a ( x ) ] ≤ n log N . For every fixed measurable loss function c t : X → [ 0 , 1 ] K c_t:\mathcal{X}\to[0,1]^K c t : X → [ 0 , 1 ] K , let p a ( x ) p_a(x) p a ( x ) be defined as above with b a = c t ( x , a ) / q a ∗ ( x ) b_a=c_t(x,a)/q_a^*(x) b a = c t ( x , a ) / q a ∗ ( x ) . Then, for D D D -almost every x x x , all a ∈ [ K ] a\in[K] a ∈ [ K ] satisfy
p a ( x ) − p a − ( x ) ≤ 6 D a ( x ) + 3 B . p_a(x)-p_a^-(x)\le6D_a(x)+\frac{3}{B}. p a ( x ) − p a − ( x ) ≤ 6 D a ( x ) + B 3 .
Proof of Theorem 2 given Lemma 3. If A t = a A_t=a A t = a , then S t = S − b a f a S_t=S-b_af_a S t = S − b a f a . At the realized W a − W_a^- W a − ,
max π [ S ( π ) + P π ( σ ) ] ≥ S ( W a − ) + P W a − ( σ ) = max π [ S ( π ) + P π ( σ ) − b a f a ( π ) ] + b a f a ( W a − ) . \begin{aligned}
\max_{\pi}[S(\pi)+P_\pi(\sigma)]\ge S(W_a^-)+P_{W_a^-}(\sigma) \\
&=\max_{\pi}[S(\pi)+P_\pi(\sigma)-b_af_a(\pi)]+b_af_a(W_a^-).
\end{aligned} π max [ S ( π ) + P π ( σ )] ≥ S ( W a − ) + P W a − ( σ ) = π max [ S ( π ) + P π ( σ ) − b a f a ( π )] + b a f a ( W a − ) .
Here W a − W_a^- W a − and both maxima use the same pool realization. The same scale is feasible after the update. Its penalty cancels on subtraction, giving
R ( S − b a f a ) − R ( S ) ≤ J S − b a f a ( σ ) − J S ( σ ) = F ( S − b a f a , σ ) − F ( S , σ ) ≤ − b a E f a ( W a − ) = − b a p a − . \begin{aligned}
R(S-b_af_a)-R(S)\le J_{S-b_af_a}(\sigma)-J_S(\sigma) \\
&=F(S-b_af_a,\sigma)-F(S,\sigma) \\
&\le-b_a\mathbb{E}f_a(W_a^-)=-b_ap_a^-.
\end{aligned} R ( S − b a f a ) − R ( S ) ≤ J S − b a f a ( σ ) − J S ( σ ) = F ( S − b a f a , σ ) − F ( S , σ ) ≤ − b a E f a ( W a − ) = − b a p a − .
Use q a b a = c a q_ab_a=c_a q a b a = c a and then c a ∈ [ 0 , 1 ] c_a\in[0,1] c a ∈ [ 0 , 1 ] to obtain
Φ S , x ( q ) ≤ ∑ a q a ( c a − b a p a − ) = ( q − p ) ⋅ c + ∑ a c a ( p a − p a − ) ≤ γ ( K − 1 ∑ a c a − p ⋅ c ) + 6 ∑ a D a ( x ) + 3 K / B . \begin{aligned}
\Phi_{S,x}(q)\le\sum_aq_a(c_a-b_ap_a^-)
=(q-p)\cdot c+\sum_ac_a(p_a-p_a^-) \\
&\le\gamma\left(K^{-1}\sum_ac_a-p\cdot c\right)+6\sum_aD_a(x)+3K/B.
\end{aligned} Φ S , x ( q ) ≤ a ∑ q a ( c a − b a p a − ) = ( q − p ) ⋅ c + a ∑ c a ( p a − p a − ) ≤ γ ( K − 1 a ∑ c a − p ⋅ c ) + 6 a ∑ D a ( x ) + 3 K / B .
The first term is at most γ \gamma γ . Averaging over x x x and applying Lemma 3 gives
E x Φ S , x ( q ∗ ( x ) ) ≤ γ + 6 E x ∑ a D a ( x ) + 3 K / B ≤ γ + 6 log ( N ) / n + 3 K / B . \mathbb{E}_x\Phi_{S,x}(q^*(x))
\le\gamma+6\mathbb{E}_x\sum_aD_a(x)+3K/B
\le\gamma+6\log(N)/n+3K/B. E x Φ S , x ( q ∗ ( x )) ≤ γ + 6 E x a ∑ D a ( x ) + 3 K / B ≤ γ + 6 log ( N ) / n + 3 K / B .
Lemma 4 (Accumulation of one-round error). Suppose the actually played vector q t q_t q t satisfies E [ Φ S t − 1 , x t ( q t ) ∣ H t − 1 ] ≤ u + ξ \mathbb{E}[\Phi_{S_{t-1},x_t}(q_t)\mid\mathcal{H}_{t-1}]\le u+\xi E [ Φ S t − 1 , x t ( q t ) ∣ H t − 1 ] ≤ u + ξ at every round. Here H t − 1 \mathcal{H}_{t-1} H t − 1 is the past before observing x t x_t x t . Then
E Reg T ≤ K n + K λ log B + T ( u + ξ ) . \mathbb{E}\operatorname{Reg}_T\le Kn+K\lambda\log B+T(u+\xi). E Reg T ≤ K n + K λ log B + T ( u + ξ ) .
Proof. At scale σ = 1 \sigma= 1 σ = 1 , P π ( 1 ) ≤ ∑ i , a ∣ Z i , a ∣ P_{\pi}(1) \le\sum_{i,a} |Z_{i,a}| P π ( 1 ) ≤ ∑ i , a ∣ Z i , a ∣ for every π \pi π , so R ( 0 ) ≤ K n + K λ log B R(0) \le K n + K \lambda\log B R ( 0 ) ≤ K n + K λ log B . At any score S S S , the penalty is nonnegative, and E P π ( σ ) = 0 \mathbb{E}P_{\pi}(\sigma) = 0 E P π ( σ ) = 0 at fixed π , σ \pi,\sigma π , σ . Hence R ( S ) ≥ max π S ( π ) R(S) \ge\max_{\pi} S(\pi) R ( S ) ≥ max π S ( π ) . Since the loss functions are fixed before play and the action uses fresh randomness,
E [ c ^ t ( a ) ∣ x 1 : T , H t − 1 , q t ] = q t ( a ) c t ( x t , a ) q t ( a ) = c t ( x t , a ) . \mathbb{E}[\widehat{c}_t(a) \mid x_{1:T}, \mathcal{H}_{t-1},q_t] = \frac{q_t(a)c_t(x_t,a)}{q_t(a)} = c_t(x_t,a). E [ c t ( a ) ∣ x 1 : T , H t − 1 , q t ] = q t ( a ) q t ( a ) c t ( x t , a ) = c t ( x t , a ) .
Consequently,
E [ R ( S T ) ∣ x 1 : T ] ≥ max π E [ S T ( π ) ∣ x 1 : T ] = − min π ∑ t c t ( x t , π ( x t ) ) . \mathbb{E}[R(S_T) \mid x_{1:T}] \ge\max_{\pi} \mathbb{E}[S_T(\pi) \mid x_{1:T}] = -\min_{\pi} \sum_t c_t(x_t,\pi(x_t)). E [ R ( S T ) ∣ x 1 : T ] ≥ π max E [ S T ( π ) ∣ x 1 : T ] = − π min t ∑ c t ( x t , π ( x t )) .
Telescoping the potential along the realized scores gives
E Reg T ≤ E [ ∑ t c t ( x t , A t ) + R ( S T ) ] = R ( 0 ) + ∑ t E Φ S t − 1 , x t ( q t ) ≤ R ( 0 ) + T ( u + ξ ) . \mathbb{E}\operatorname{Reg}_T \le\mathbb{E}\left[\sum_t c_t(x_t,A_t) + R(S_T)\right]
= R(0) + \sum_t \mathbb{E}\Phi_{S_{t-1},x_t}(q_t) \le R(0) + T(u+\xi). E Reg T ≤ E [ t ∑ c t ( x t , A t ) + R ( S T ) ] = R ( 0 ) + t ∑ E Φ S t − 1 , x t ( q t ) ≤ R ( 0 ) + T ( u + ξ ) .
Put A = K T L A = \sqrt{KTL} A = K T L . Under (1), K n = A / ℓ Kn = A/\ell K n = A / ℓ , K λ = 4 A K\lambda= 4A K λ = 4 A , T L / n = A ℓ TL/n = A\ell T L / n = A ℓ , and T γ = T K / B ≤ 1 T\gamma= TK/B \le1 T γ = T K / B ≤ 1 . Thus the lemma gives O ( A log ( 2 K T ) ) + T ξ O(A\log(2KT)) + T\xi O ( A log ( 2 K T )) + T ξ . Theorem 2 gives ξ = 0 \xi= 0 ξ = 0 for ideal play; Theorem 11 below gives ξ = 1 / T \xi= 1/T ξ = 1/ T for oracle play.
Proof of One-round Stability
Lemma 3 requires two estimates. First, we define D a ( x ) D_a(x) D a ( x ) and prove
E x ∼ D ∑ a = 1 K D a ( x ) ≤ log N n . \mathbb{E}_{x\sim D}\sum_{a=1}^{K} D_a(x) \le\frac{\log N}{n}. E x ∼ D a = 1 ∑ K D a ( x ) ≤ n log N .
We then use the optimality of the scale σ \sigma σ to prove that, for D D D -almost every x x x and each a ∈ [ K ] a \in[K] a ∈ [ K ] ,
p a ( x ) − p a − ( x ) ≤ 6 D a ( x ) + 3 B . p_a(x)-p_a^-(x) \le6D_a(x)+\frac{3}{B}. p a ( x ) − p a − ( x ) ≤ 6 D a ( x ) + B 3 .
Information in the inserted context
Lemma 5 (Information carried by one inserted vector). Fix the score S S S and the scale σ \sigma σ . For each context x x x , let C = ( M , X 1 : M ) C=(M,X_{1:M}) C = ( M , X 1 : M ) be the auxiliary pool locations, let Z ∼ μ Z\sim\mu Z ∼ μ be the independent Laplace vector inserted at x x x , and let W x W_x W x be the winning policy in (3).
For each π ∈ Π \pi\in\Pi π ∈ Π , write w π = Pr ( W x = π ∣ C ) w_\pi=\Pr(W_x=\pi\mid C) w π = Pr ( W x = π ∣ C ) . When w π > 0 w_\pi>0 w π > 0 , define the conditional distribution ν π \nu_\pi ν π by
ν π ( A ) = Pr ( Z ∈ A ∣ C , W x = π ) \nu_\pi(A)=\Pr(Z\in A\mid C,W_x=\pi) ν π ( A ) = Pr ( Z ∈ A ∣ C , W x = π ) for every measurable A ⊆ R K A\subseteq\mathbb{R}^{K} A ⊆ R K .
For each action a ∈ [ K ] a\in[K] a ∈ [ K ] , set
D a ( x ) = E C [ ∑ π ∈ Π : π ( x ) = a w π > 0 w π KL ( ν π ∥ μ ) ] . D_a(x)=\mathbb{E}_C\left[\sum_{\substack{\pi\in\Pi:\ \pi(x)=a\\ w_\pi>0}}w_\pi\,\operatorname{KL}(\nu_\pi\Vert\mu)\right]. D a ( x ) = E C π ∈ Π : π ( x ) = a w π > 0 ∑ w π KL ( ν π ∥ μ ) . Then
E x ∼ D [ ∑ a = 1 K D a ( x ) ] ≤ log N n . \mathbb{E}_{x\sim D}\left[\sum_{a=1}^{K}D_a(x)\right]\le\frac{\log N}{n}. E x ∼ D [ a = 1 ∑ K D a ( x ) ] ≤ n log N .
Proof. For each m ≥ 1 m \ge1 m ≥ 1 , let ( X 1 , Z 1 ) , … , ( X m , Z m ) (X_1,Z_1),\ldots,(X_m,Z_m) ( X 1 , Z 1 ) , … , ( X m , Z m ) be independent pairs with law D ⊗ μ D \otimes\mu D ⊗ μ , and define
W m = arg max π ∈ Π { S ( π ) + ∑ i = 1 m σ π ( X i ) ( X i ) Z i , π ( X i ) } . W_m = \operatorname*{arg\,max}_{\pi\in\Pi} \left\{ S(\pi) + \sum_{i=1}^{m} \sigma_{\pi(X_i)}(X_i) Z_{i,\pi(X_i)} \right\}. W m = π ∈ Π arg max { S ( π ) + i = 1 ∑ m σ π ( X i ) ( X i ) Z i , π ( X i ) } .
using the same tie-breaking rule as in (3) . Write ρ m = Pr ( M = m ) = e − n n m / m ! \rho_m = \Pr(M=m) = e^{-n}n^m/m! ρ m = Pr ( M = m ) = e − n n m / m ! .
Claim 5.1.
n E x ∼ D [ ∑ a = 1 K D a ( x ) ] = ∑ m ≥ 1 ρ m ∑ i = 1 m I ( Z i ; W m ∣ X 1 : m ) . n \mathbb{E}_{x \sim D}\left[\sum_{a=1}^{K} D_a(x)\right] = \sum_{m \ge1} \rho_m \sum_{i=1}^{m} I(Z_i;W_m \mid X_{1:m}). n E x ∼ D [ a = 1 ∑ K D a ( x ) ] = m ≥ 1 ∑ ρ m i = 1 ∑ m I ( Z i ; W m ∣ X 1 : m ) .
Proof of Claim 5.1. Fix x x x and the pool locations C C C . Write I x , C ( Z ; W x ) I_{x,C}(Z;W_x) I x , C ( Z ; W x ) for the mutual information under these fixed locations. The inserted vector Z Z Z has law μ \mu μ . Conditional on W x = π W_x=\pi W x = π , it has law ν π \nu_\pi ν π . Thus
I x , C ( Z ; W x ) = ∑ π : w π > 0 w π KL ( ν π ∥ μ ) . I_{x,C}(Z;W_x) = \sum_{\pi:w_\pi>0} w_\pi\operatorname{KL}(\nu_\pi\mathbin\Vert\mu). I x , C ( Z ; W x ) = π : w π > 0 ∑ w π KL ( ν π ∥ μ ) .
Grouping the policies by their action at x x x and averaging over C C C gives
E C [ I x , C ( Z ; W x ) ] = ∑ a = 1 K D a ( x ) . \mathbb{E}_C[I_{x,C}(Z;W_x)] = \sum_{a=1}^{K} D_a(x). E C [ I x , C ( Z ; W x )] = a = 1 ∑ K D a ( x ) .
Now average over an independent x ∼ D x \sim D x ∼ D and condition on M = k M=k M = k . Since C = ( k , X 1 : k ) C=(k,X_{1:k}) C = ( k , X 1 : k ) on this event,
E x ∼ D [ ∑ a = 1 K D a ( x ) ] = ∑ k ≥ 0 ρ k E x , X 1 : k [ I x , ( k , X 1 : k ) ( Z ; W x ) ] . (5) \mathbb{E}_{x \sim D}\left[\sum_{a=1}^{K}D_a(x)\right] = \sum_{k \ge0}\rho_k \mathbb{E}_{x,X_{1:k}}\left[I_{x,(k,X_{1:k})}(Z;W_x)\right]. \tag*{(5)} E x ∼ D [ a = 1 ∑ K D a ( x ) ] = k ≥ 0 ∑ ρ k E x , X 1 : k [ I x , ( k , X 1 : k ) ( Z ; W x ) ] . (5)
Fix k k k . Label the inserted pair ( X k + 1 , Z k + 1 ) = ( x , Z ) (X_{k+1},Z_{k+1})=(x,Z) ( X k + 1 , Z k + 1 ) = ( x , Z ) . The resulting k + 1 k+1 k + 1 pairs are independent with law D ⊗ μ D \otimes\mu D ⊗ μ . For every policy π \pi π , its score in the inserted experiment is
S ( π ) + ∑ i = 1 k σ π ( X i ) ( X i ) Z i , π ( X i ) + σ π ( x ) ( x ) Z π ( x ) = S ( π ) + ∑ i = 1 k + 1 σ π ( X i ) ( X i ) Z i , π ( X i ) . \begin{aligned}
S(\pi) + \sum_{i=1}^{k}\sigma_{\pi(X_i)}(X_i)Z_{i,\pi(X_i)} + \sigma_{\pi(x)}(x)Z_{\pi(x)} \\
&= S(\pi) + \sum_{i=1}^{k+1}\sigma_{\pi(X_i)}(X_i)Z_{i,\pi(X_i)}.
\end{aligned} S ( π ) + i = 1 ∑ k σ π ( X i ) ( X i ) Z i , π ( X i ) + σ π ( x ) ( x ) Z π ( x ) = S ( π ) + i = 1 ∑ k + 1 σ π ( X i ) ( X i ) Z i , π ( X i ) .
Hence W x = W k + 1 W_x=W_{k+1} W x = W k + 1 under this labeling. In particular, at fixed locations u 1 , … , u k + 1 u_1,\ldots,u_{k+1} u 1 , … , u k + 1 ,
I u k + 1 , ( k , u 1 : k ) ( Z ; W u k + 1 ) = I ( Z k + 1 ; W k + 1 ∣ X 1 : k + 1 = u 1 : k + 1 ) . I_{u_{k+1},(k,u_{1:k})}(Z;W_{u_{k+1}}) = I(Z_{k+1};W_{k+1} \mid X_{1:k+1}=u_{1:k+1}). I u k + 1 , ( k , u 1 : k ) ( Z ; W u k + 1 ) = I ( Z k + 1 ; W k + 1 ∣ X 1 : k + 1 = u 1 : k + 1 ) .
By definition, averaging the right-hand side over the locations gives conditional mutual information. Therefore
E x , X 1 : k [ I x , ( k , X 1 : k ) ( Z ; W x ) ] = ∫ I ( Z k + 1 ; W k + 1 ∣ X 1 : k + 1 = u 1 : k + 1 ) D ⊗ ( k + 1 ) ( d u 1 : k + 1 ) = I ( Z k + 1 ; W k + 1 ∣ X 1 : k + 1 ) . \begin{aligned}
\mathbb{E}_{x,X_{1:k}}\left[I_{x,(k,X_{1:k})}(Z;W_x)\right] = \int I(Z_{k+1};W_{k+1} \mid X_{1:k+1}=u_{1:k+1})\,D^{\otimes(k+1)}(du_{1:k+1}) \\
&= I(Z_{k+1};W_{k+1} \mid X_{1:k+1}).
\end{aligned} E x , X 1 : k [ I x , ( k , X 1 : k ) ( Z ; W x ) ] = ∫ I ( Z k + 1 ; W k + 1 ∣ X 1 : k + 1 = u 1 : k + 1 ) D ⊗ ( k + 1 ) ( d u 1 : k + 1 ) = I ( Z k + 1 ; W k + 1 ∣ X 1 : k + 1 ) .
Substitute into (5), multiply by n n n , and set m = k + 1 m = k + 1 m = k + 1 . The Poisson probabilities satisfy n ρ m − 1 = m ρ m n\rho_{m-1} = m\rho_m n ρ m − 1 = m ρ m , so
n E x ∼ D [ ∑ a = 1 K D a ( x ) ] = ∑ k ≥ 0 n ρ k I ( Z k + 1 ; W k + 1 ∣ X 1 : k + 1 ) = ∑ m ≥ 1 n ρ m − 1 I ( Z m ; W m ∣ X 1 : m ) = ∑ m ≥ 1 ρ m m I ( Z m ; W m ∣ X 1 : m ) . n \mathbb{E}_{x\sim D}\left[\sum_{a=1}^{K} D_a(x)\right] = \sum_{k\geq0} n\rho_k I(Z_{k+1};W_{k+1}\mid X_{1:k+1})
= \sum_{m\geq1} n\rho_{m-1} I(Z_m;W_m\mid X_{1:m})
= \sum_{m\geq1} \rho_m m I(Z_m;W_m\mid X_{1:m}). n E x ∼ D [ a = 1 ∑ K D a ( x ) ] = k ≥ 0 ∑ n ρ k I ( Z k + 1 ; W k + 1 ∣ X 1 : k + 1 ) = m ≥ 1 ∑ n ρ m − 1 I ( Z m ; W m ∣ X 1 : m ) = m ≥ 1 ∑ ρ m m I ( Z m ; W m ∣ X 1 : m ) .
Finally, fix m m m and i ∈ [ m ] i \in[m] i ∈ [ m ] . Swapping pairs i i i and m m m preserves their joint law. It also preserves W m W_m W m , since it only reorders the summands in every policy’s score. The swap exchanges Z i Z_i Z i and Z m Z_m Z m and reorders the conditioning vector X 1 : m X_{1:m} X 1 : m . This reordering is invertible, so it preserves the conditioning information. Consequently,
I ( Z m ; W m ∣ X 1 : m ) = I ( Z i ; W m ∣ X 1 : m ) , i ∈ [ m ] . I(Z_m;W_m\mid X_{1:m}) = I(Z_i;W_m\mid X_{1:m}), \qquad i\in[m]. I ( Z m ; W m ∣ X 1 : m ) = I ( Z i ; W m ∣ X 1 : m ) , i ∈ [ m ] .
Summing over i i i gives
m I ( Z m ; W m ∣ X 1 : m ) = ∑ i = 1 m I ( Z i ; W m ∣ X 1 : m ) , m I(Z_m;W_m\mid X_{1:m}) = \sum_{i=1}^{m} I(Z_i;W_m\mid X_{1:m}), m I ( Z m ; W m ∣ X 1 : m ) = i = 1 ∑ m I ( Z i ; W m ∣ X 1 : m ) ,
which proves the claim.
It remains to bound the inner sum in Claim 5.1 . Fix m ≥ 1 m \geq1 m ≥ 1 , write X = X 1 : m X = X_{1:m} X = X 1 : m , and let Z < i = ( Z 1 , … , Z i − 1 ) Z_{<i} = (Z_1,\ldots,Z_{i-1}) Z < i = ( Z 1 , … , Z i − 1 ) . The noise vectors are independent conditional on X X X , so I ( Z i ; Z < i ∣ X ) = 0 I(Z_i;Z_{<i}\mid X) = 0 I ( Z i ; Z < i ∣ X ) = 0 . For each i i i , the chain rule gives
I ( Z i ; W m ∣ X ) ≤ I ( Z i ; Z < i , W m ∣ X ) = I ( Z i ; Z < i ∣ X ) + I ( Z i ; W m ∣ X , Z < i ) = I ( Z i ; W m ∣ X , Z < i ) . I(Z_i;W_m\mid X) \leq I(Z_i;Z_{<i},W_m\mid X)
= I(Z_i;Z_{<i}\mid X) + I(Z_i;W_m\mid X,Z_{<i})
= I(Z_i;W_m\mid X,Z_{<i}). I ( Z i ; W m ∣ X ) ≤ I ( Z i ; Z < i , W m ∣ X ) = I ( Z i ; Z < i ∣ X ) + I ( Z i ; W m ∣ X , Z < i ) = I ( Z i ; W m ∣ X , Z < i ) .
Summing and applying the chain rule once more yields
∑ i = 1 m I ( Z i ; W m ∣ X ) ≤ ∑ i = 1 m I ( Z i ; W m ∣ X , Z < i ) = I ( Z 1 : m ; W m ∣ X ) ≤ H ( W m ∣ X ) ≤ log N , \sum_{i=1}^{m} I(Z_i;W_m\mid X) \leq\sum_{i=1}^{m} I(Z_i;W_m\mid X,Z_{<i})
= I(Z_{1:m};W_m\mid X)
\leq H(W_m\mid X) \leq\log N, i = 1 ∑ m I ( Z i ; W m ∣ X ) ≤ i = 1 ∑ m I ( Z i ; W m ∣ X , Z < i ) = I ( Z 1 : m ; W m ∣ X ) ≤ H ( W m ∣ X ) ≤ log N ,
since W m W_m W m takes values in the N N N -element class Π \Pi Π . Substituting this bound into Claim 5.1 gives
E x ∼ D [ ∑ a = 1 K D a ( x ) ] ≤ 1 n ∑ m ≥ 1 ρ m log N ≤ log N n . \mathbb{E}_{x\sim D}\left[\sum_{a=1}^{K} D_a(x)\right] \leq\frac{1}{n}\sum_{m\geq1}\rho_m\log N \leq\frac{\log N}{n}. E x ∼ D [ a = 1 ∑ K D a ( x ) ] ≤ n 1 m ≥ 1 ∑ ρ m log N ≤ n log N .
The minimizing scale
For each context x x x , let g ( x ) = ( π ( x ) ) π ∈ Π g(x) = (\pi(x))_{\pi\in\Pi} g ( x ) = ( π ( x ) ) π ∈ Π denote its prediction signature. Write s = ( s g , a ) s = (s_{g,a}) s = ( s g , a ) for a table with one row per prediction signature g g g and one column per action a ∈ [ K ] a \in[K] a ∈ [ K ] . Each entry s g , a ∈ [ 1 , B ] s_{g,a} \in[1,B] s g , a ∈ [ 1 , B ] specifies the scale for action a a a at every context with signature g g g . Thus the scale defined by s s s is
σ a ( x ) = s g ( x ) , a . \sigma_a(x) = s_{g(x),a}. σ a ( x ) = s g ( x ) , a .
For each prediction signature g g g , let ω g \omega_g ω g be its probability under the context distribution D D D , and let Γ + \Gamma_+ Γ + be the set of signatures with positive probability:
ω g = Pr X ∼ D ( g ( X ) = g ) , Γ + = { g : ω g > 0 } . \omega_g = \Pr_{X\sim D}(g(X)=g), \qquad\Gamma_+ = \{g:\omega_g>0\}. ω g = X ∼ D Pr ( g ( X ) = g ) , Γ + = { g : ω g > 0 } .
Lemma 6 (Scale minimization on prediction signatures). There is a minimizing scale of the form σ a ( x ) = s g ( x ) , a ∗ \sigma_a(x)=s^*_{g(x),a} σ a ( x ) = s g ( x ) , a ∗ , where g ( x ) = ( π ( x ) ) π ∈ Π g(x)=(\pi(x))_{\pi\in\Pi} g ( x ) = ( π ( x ) ) π ∈ Π . The table can be chosen measurably in S S S .
Proof. Fix a feasible scale σ \sigma σ . Define
s g , a = { E [ σ a ( X ) ∣ g ( X ) = g ] , g ∈ Γ + , 1 , g ∉ Γ + , σ ˉ a ( x ) = s g ( x ) , a . s_{g,a} =
\begin{cases}
\mathbb{E}[\sigma_a(X)\mid g(X)=g], & g\in\Gamma_+,\\
1, & g\notin\Gamma_+,
\end{cases}
\qquad
\bar{\sigma}_a(x)=s_{g(x),a}. s g , a = { E [ σ a ( X ) ∣ g ( X ) = g ] , 1 , g ∈ Γ + , g ∈ / Γ + , σ ˉ a ( x ) = s g ( x ) , a . Condition on G = ( M , ( g ( X i ) , Z i ) i = 1 M ) \mathcal{G}=(M,(g(X_i),Z_i)_{i=1}^M) G = ( M , ( g ( X i ) , Z i ) i = 1 M ) . The signature g ( X i ) g(X_i) g ( X i ) determines π ( X i ) \pi(X_i) π ( X i ) , and the noise is independent of the contexts. Hence
E [ P π ( σ ) ∣ G ] = ∑ i = 1 M s g ( X i ) , π ( X i ) Z i , π ( X i ) = P π ( σ ˉ ) . \mathbb{E}[P_\pi(\sigma)\mid\mathcal{G}]
=\sum_{i=1}^{M}s_{g(X_i),\pi(X_i)}Z_{i,\pi(X_i)}
=P_\pi(\bar{\sigma}). E [ P π ( σ ) ∣ G ] = i = 1 ∑ M s g ( X i ) , π ( X i ) Z i , π ( X i ) = P π ( σ ˉ ) . Conditional Jensen for the maximum and for u ↦ log ( B / u ) u\mapsto\log(B/u) u ↦ log ( B / u ) gives
max π [ S ( π ) + P π ( σ ˉ ) ] ≤ E [ max π [ S ( π ) + P π ( σ ) ] ∣ G ] , \max_\pi[S(\pi)+P_\pi(\bar{\sigma})]
\leq
\mathbb{E}\left[\max_\pi[S(\pi)+P_\pi(\sigma)]\mid\mathcal{G}\right], π max [ S ( π ) + P π ( σ ˉ )] ≤ E [ π max [ S ( π ) + P π ( σ )] ∣ G ] , log ( B / s g , a ) ≤ E [ log ( B / σ a ( X ) ) ∣ g ( X ) = g ] ( g ∈ Γ + ) . \log(B/s_{g,a})\leq\mathbb{E}[\log(B/\sigma_a(X))\mid g(X)=g]
\qquad(g\in\Gamma_+). log ( B / s g , a ) ≤ E [ log ( B / σ a ( X )) ∣ g ( X ) = g ] ( g ∈ Γ + ) . Take expectations in the first line. In the second, multiply by λ ω g \lambda\omega_g λ ω g and sum over g , a g,a g , a . Adding yields
J S ( σ ˉ ) ≤ J S ( σ ) . J_S(\bar{\sigma})\leq J_S(\sigma). J S ( σ ˉ ) ≤ J S ( σ ) . Conversely, every table s ∈ [ 1 , B ] K ∣ Γ + ∣ s\in[1,B]^{K|\Gamma_+|} s ∈ [ 1 , B ] K ∣ Γ + ∣ defines a feasible scale by setting its entries on zero-mass signatures to one. Thus
inf σ J S ( σ ) = inf s ∈ [ 1 , B ] K ∣ Γ + ∣ J S ( s ) , J S ( s ) = F ( S , s ) + λ ∑ g ∈ Γ + ω g ∑ a = 1 K log ( B / s g , a ) . \inf_\sigma J_S(\sigma)
=
\inf_{s\in[1,B]^{K|\Gamma_+|}}J_S(s),
\qquad
J_S(s)=F(S,s)+\lambda\sum_{g\in\Gamma_+}\omega_g\sum_{a=1}^{K}\log(B/s_{g,a}). σ inf J S ( σ ) = s ∈ [ 1 , B ] K ∣ Γ + ∣ inf J S ( s ) , J S ( s ) = F ( S , s ) + λ g ∈ Γ + ∑ ω g a = 1 ∑ K log ( B / s g , a ) . The pool term F ( S , s ) F(S,s) F ( S , s ) is convex in s s s as an expected maximum of affine functions. It is jointly continuous in ( S , s ) (S,s) ( S , s ) since
∣ F ( S , s ) − F ( S ′ , s ′ ) ∣ ≤ ∥ S − S ′ ∥ ∞ + ∥ s − s ′ ∥ ∞ E ∑ i = 1 M ∑ a = 1 K ∣ Z i , a ∣ = ∥ S − S ′ ∥ ∞ + K n ∥ s − s ′ ∥ ∞ . |F(S,s)-F(S',s')|
\leq\lVert S-S'\rVert_\infty+\lVert s-s'\rVert_\infty\mathbb{E}\sum_{i=1}^{M}\sum_{a=1}^{K}|Z_{i,a}|
=\lVert S-S'\rVert_\infty+Kn\lVert s-s'\rVert_\infty. ∣ F ( S , s ) − F ( S ′ , s ′ ) ∣ ≤ ∥ S − S ′ ∥ ∞ + ∥ s − s ′ ∥ ∞ E i = 1 ∑ M a = 1 ∑ K ∣ Z i , a ∣ = ∥ S − S ′ ∥ ∞ + K n ∥ s − s ′ ∥ ∞ . The penalty is strictly convex on the table because each coordinate has second derivative λ ω g / s g , a 2 > 0 \lambda\omega_g/s_{g,a}^2>0 λ ω g / s g , a 2 > 0 . Hence J S J_S J S attains a unique minimum s ∗ ( S ) s^*(S) s ∗ ( S ) on the compact box.
Finally, if S j → S S_j\to S S j → S and a subsequence s ∗ ( S j k ) → t s^*(S_{j_k})\to t s ∗ ( S j k ) → t , then for every feasible table u u u , joint continuity gives
J S ( t ) = lim k J S j k ( s ∗ ( S j k ) ) ≤ lim k J S j k ( u ) = J S ( u ) . J_S(t)=\lim_{k}J_{S_{j_k}}(s^*(S_{j_k}))
\leq\lim_{k}J_{S_{j_k}}(u)=J_S(u). J S ( t ) = k lim J S j k ( s ∗ ( S j k )) ≤ k lim J S j k ( u ) = J S ( u ) . Uniqueness gives t = s ∗ ( S ) t=s^*(S) t = s ∗ ( S ) . By compactness, s ∗ ( S j ) → s ∗ ( S ) s^*(S_j)\to s^*(S) s ∗ ( S j ) → s ∗ ( S ) , so the minimizing table is continuous, hence measurable, in S S S .
Use the scale from Lemma 6 in the ideal strategy. For any feasible table s s s , let W x ( s ) W_x(s) W x ( s ) denote the argmax in (3) evaluated at s s s , and write
α a ( x ; s ) = E [ Z a 1 { W x ( s ) ( x ) = a } ] . \alpha_a(x;s)=\mathbb{E}[Z_a\mathbf{1}\{W_x(s)(x)=a\}]. α a ( x ; s ) = E [ Z a 1 { W x ( s ) ( x ) = a }] .
For g ( x ) = g ( y ) g(x)=g(y) g ( x ) = g ( y ) , every policy has π ( x ) = π ( y ) \pi(x)=\pi(y) π ( x ) = π ( y ) and the added score is identical at x , y x,y x , y for the same noise. Thus α a ( x ; s ) = α a ( y ; s ) \alpha_a(x;s)=\alpha_a(y;s) α a ( x ; s ) = α a ( y ; s ) .
Lemma 7 (Derivative of one scale entry). For g ( x ) = g ∈ Γ + g(x)=g\in\Gamma_+ g ( x ) = g ∈ Γ + , the derivative in entry ( g , a ) (g,a) ( g , a ) equals
∂ J S ( s ) ∂ s g , a = ω g ( n α a ( x ; s ) − λ s g , a ) . \frac{\partial J_S(s)}{\partial s_{g,a}}=\omega_g\left(n\alpha_a(x;s)-\frac{\lambda}{s_{g,a}}\right). ∂ s g , a ∂ J S ( s ) = ω g ( n α a ( x ; s ) − s g , a λ ) . At the boundary use the derivative of the same formula for J S J_S J S extended to positive scales. In particular at s = s ∗ s=s^* s = s ∗ , writing α a ( x ) = α a ( x ; s ∗ ) \alpha_a(x)=\alpha_a(x;s^*) α a ( x ) = α a ( x ; s ∗ ) ,
s g , a ∗ < B ⟹ α a ( x ) ≥ λ n s g , a ∗ . (6) s^*_{g,a}<B\quad\Longrightarrow\quad\alpha_a(x)\geq\frac{\lambda}{n s^*_{g,a}}. \tag*{(6)} s g , a ∗ < B ⟹ α a ( x ) ≥ n s g , a ∗ λ . (6)
Proof. Let s ′ s' s ′ be the table obtained by increasing s g , a s_{g,a} s g , a by ϵ \epsilon ϵ . In the sum defining P π ( s ) P_\pi(s) P π ( s ) , the i i i th term changes only if g ( X i ) = g g(X_i)=g g ( X i ) = g and π ( X i ) = a \pi(X_i)=a π ( X i ) = a . In that case it changes from s g , a Z i , a s_{g,a}Z_{i,a} s g , a Z i , a to ( s g , a + ϵ ) Z i , a (s_{g,a}+\epsilon)Z_{i,a} ( s g , a + ϵ ) Z i , a . Hence
[ S ( π ) + P π ( s ′ ) ] − [ S ( π ) + P π ( s ) ] = ϵ ∑ i = 1 M 1 { g ( X i ) = g , π ( X i ) = a } Z i , a . [S(\pi)+P_\pi(s')]-[S(\pi)+P_\pi(s)]=\epsilon\sum_{i=1}^{M}\mathbf{1}\{g(X_i)=g,\ \pi(X_i)=a\}Z_{i,a}. [ S ( π ) + P π ( s ′ )] − [ S ( π ) + P π ( s )] = ϵ i = 1 ∑ M 1 { g ( X i ) = g , π ( X i ) = a } Z i , a .
Let W m W_m W m be the policy maximizing S ( π ) + P π ( s ) S(\pi)+P_\pi(s) S ( π ) + P π ( s ) for a pool of m m m samples, with the fixed tie-breaking rule. We claim that
∂ F ( S , s ) ∂ s g , a = E [ ∑ i = 1 M 1 { g ( X i ) = g , W M ( X i ) = a } Z i , a ] . (7) \frac{\partial F(S,s)}{\partial s_{g,a}}=\mathbb{E}\left[\sum_{i=1}^{M}\mathbf{1}\{g(X_i)=g,\ W_M(X_i)=a\}Z_{i,a}\right]. \tag*{(7)} ∂ s g , a ∂ F ( S , s ) = E [ i = 1 ∑ M 1 { g ( X i ) = g , W M ( X i ) = a } Z i , a ] . (7)
To see this, fix the pool. Each policy’s score is affine in s g , a s_{g,a} s g , a , with slope
∑ i = 1 M 1 { g ( X i ) = g , π ( X i ) = a } Z i , a . \sum_{i=1}^{M}\mathbf{1}\{g(X_i)=g,\ \pi(X_i)=a\}Z_{i,a}. i = 1 ∑ M 1 { g ( X i ) = g , π ( X i ) = a } Z i , a .
If two policies differ at X i X_i X i , condition on the locations and all noise coordinates except Z i , π ( X i ) Z_{i,\pi(X_i)} Z i , π ( X i ) . Their score difference is a constant plus a nonzero multiple of this continuous variable, so they tie with probability zero. Since Π \Pi Π is finite, almost surely all tied maximizers agree at every sampled location and therefore have the same slope. The derivative of the maximum is thus the slope displayed above with π = W M \pi=W_M π = W M .
Every policy’s absolute slope is at most ∑ i = 1 M ∣ Z i , a ∣ \sum_{i=1}^{M}|Z_{i,a}| ∑ i = 1 M ∣ Z i , a ∣ . The same bound holds for the absolute difference quotient of the maximum, and its expectation is n n n . Dominated convergence therefore gives (7).
Expanding the right-hand side of (7) by conditioning on M = m M=m M = m , all m m m summands have the same expectation by symmetry. Writing ρ m = Pr ( M = m ) \rho_m=\Pr(M=m) ρ m = Pr ( M = m ) , we obtain
∂ F ( S , s ) ∂ s g , a = ∑ m ≥ 1 m ρ m E [ 1 { g ( X m ) = g , W m ( X m ) = a } Z m , a ] = n ∑ k ≥ 0 ρ k E [ 1 { g ( X k + 1 ) = g , W k + 1 ( X k + 1 ) = a } Z k + 1 , a ] = n E X ∼ D [ 1 { g ( X ) = g } α a ( X ; s ) ] = n ω g α a ( x ; s ) . \begin{aligned}
\frac{\partial F(S,s)}{\partial s_{g,a}}=\sum_{m\geq1}m\rho_m\mathbb{E}[\mathbf{1}\{g(X_m)=g,\ W_m(X_m)=a\}Z_{m,a}] \\
&=n\sum_{k\geq0}\rho_k\mathbb{E}[\mathbf{1}\{g(X_{k+1})=g,\ W_{k+1}(X_{k+1})=a\}Z_{k+1,a}] \\
&=n\mathbb{E}_{X\sim D}[\mathbf{1}\{g(X)=g\}\alpha_a(X;s)]=n\omega_g\alpha_a(x;s).
\end{aligned} ∂ s g , a ∂ F ( S , s ) = m ≥ 1 ∑ m ρ m E [ 1 { g ( X m ) = g , W m ( X m ) = a } Z m , a ] = n k ≥ 0 ∑ ρ k E [ 1 { g ( X k + 1 ) = g , W k + 1 ( X k + 1 ) = a } Z k + 1 , a ] = n E X ∼ D [ 1 { g ( X ) = g } α a ( X ; s )] = n ω g α a ( x ; s ) .
The second line uses m = k + 1 m=k+1 m = k + 1 and m ρ m = n ρ m − 1 m\rho_m=n\rho_{m-1} m ρ m = n ρ m − 1 . In the third line, the first k k k pairs form the pool and the last pair is the independent inserted pair ( X , Z ) (X,Z) ( X , Z ) . Averaging over k ∼ Pois ( n ) k\sim\operatorname{Pois}(n) k ∼ Pois ( n ) and the noise at fixed X X X gives α a ( X ; s ) = E [ Z a 1 { W X ( s ) ( X ) = a } ∣ X ] \alpha_a(X;s)=\mathbb{E}[Z_a\mathbf{1}\{W_X(s)(X)=a\}\mid X] α a ( X ; s ) = E [ Z a 1 { W X ( s ) ( X ) = a } ∣ X ] . The last equality uses Pr ( g ( X ) = g ) = ω g \Pr(g(X)=g)=\omega_g Pr ( g ( X ) = g ) = ω g and α a ( X ; s ) = α a ( x ; s ) \alpha_a(X;s)=\alpha_a(x;s) α a ( X ; s ) = α a ( x ; s ) whenever g ( X ) = g ( x ) = g g(X)=g(x)=g g ( X ) = g ( x ) = g . Only the term λ ω g log ( B / s g , a ) \lambda\omega_g\log(B/s_{g,a}) λ ω g log ( B / s g , a ) in the penalty depends on s g , a s_{g,a} s g , a . Adding its derivative to the pool derivative gives
∂ J S ( s ) ∂ s g , a = n ω g α a ( x ; s ) − λ ω g s g , a . \frac{\partial J_S(s)}{\partial s_{g,a}}=n\omega_g\alpha_a(x;s)-\frac{\lambda\omega_g}{s_{g,a}}. ∂ s g , a ∂ J S ( s ) = n ω g α a ( x ; s ) − s g , a λ ω g .
If s g , a ∗ < B s^*_{g,a}<B s g , a ∗ < B , increasing this entry by a sufficiently small amount is feasible. Since s ∗ s^* s ∗ minimizes J S J_S J S , the right derivative is nonnegative. Thus, writing α a ( x ) = α a ( x ; s ∗ ) \alpha_a(x)=\alpha_a(x;s^*) α a ( x ) = α a ( x ; s ∗ ) ,
0 ≤ n ω g α a ( x ) − λ ω g s g , a ∗ ⟹ α a ( x ) ≥ λ n s g , a ∗ , 0\le n\omega_g\alpha_a(x)-\frac{\lambda\omega_g}{s^*_{g,a}}\quad\Longrightarrow\quad\alpha_a(x)\ge\frac{\lambda}{ns^*_{g,a}}, 0 ≤ n ω g α a ( x ) − s g , a ∗ λ ω g ⟹ α a ( x ) ≥ n s g , a ∗ λ ,
where we used n ω g > 0 n\omega_g>0 n ω g > 0 .
Comparing the two action probabilities
For the next two lemmas, write r π ( z ) r_\pi(z) r π ( z ) for the winning probability when the inserted vector is fixed at z z z . Explicitly, at C = ( m , x 1 : m ) C=(m,x_{1:m}) C = ( m , x 1 : m ) set
B π ( u , z ) = S ( π ) + ∑ i = 1 m σ π ( x i ) ( x i ) u i , π ( x i ) + σ π ( x ) ( x ) z π ( x ) , B_\pi(u,z)=S(\pi)+\sum_{i=1}^{m}\sigma_{\pi(x_i)}(x_i)u_{i,\pi(x_i)}+\sigma_{\pi(x)}(x)z_{\pi(x)}, B π ( u , z ) = S ( π ) + i = 1 ∑ m σ π ( x i ) ( x i ) u i , π ( x i ) + σ π ( x ) ( x ) z π ( x ) ,
r π ( z ) = ∫ 1 { π = arg max π ′ B π ′ ( u , z ) } μ m ( d u ) . r_\pi(z)=\int\mathbf{1}\{\pi=\underset{\pi'}{\operatorname{arg\,max}}\,B_{\pi'}(u,z)\}\,\mu^m(du). r π ( z ) = ∫ 1 { π = π ′ arg max B π ′ ( u , z )} μ m ( d u ) .
Here μ ( d z ) = 2 − K e − ∥ z ∥ 1 d z \mu(dz)=2^{-K}e^{-\lVert z\rVert_1}\,dz μ ( d z ) = 2 − K e − ∥ z ∥ 1 d z . The law defined in Lemma 5 satisfies w π ν π ( d z ) = r π ( z ) μ ( d z ) w_\pi\nu_\pi(dz)=r_\pi(z)\mu(dz) w π ν π ( d z ) = r π ( z ) μ ( d z ) , since both sides equal Pr ( Z ∈ d z , W x = π ∣ C ) \Pr(Z\in dz,W_x=\pi\mid C) Pr ( Z ∈ d z , W x = π ∣ C ) .
Lemma 8 (Midpoint inequality for a winning policy). Fix x x x , C C C , π \pi π . For every pair z , z ′ ∈ R K z,z'\in\mathbb{R}^K z , z ′ ∈ R K ,
r π ( ( z + z ′ ) / 2 ) ≥ r π ( z ) r π ( z ′ ) . r_\pi\left((z+z')/2\right)\ge\sqrt{r_\pi(z)r_\pi(z')}. r π ( ( z + z ′ ) /2 ) ≥ r π ( z ) r π ( z ′ ) .
Proof. Fix the context x x x , the pool locations C = ( m , x 1 : m ) C=(m,x_{1:m}) C = ( m , x 1 : m ) , and the policy π \pi π . Write u = ( u i , b ) i ∈ [ m ] , b ∈ [ K ] u=(u_{i,b})_{i\in[m],\,b\in[K]} u = ( u i , b ) i ∈ [ m ] , b ∈ [ K ] for the noise at the pool locations and z ∈ R K z\in\mathbb{R}^K z ∈ R K for the noise at x x x . For each policy τ \tau τ , its score is
B τ ( u , z ) = S ( τ ) + ∑ i = 1 m σ τ ( x i ) ( x i ) u i , τ ( x i ) + σ τ ( x ) ( x ) z τ ( x ) . B_\tau(u,z)=S(\tau)+\sum_{i=1}^{m}\sigma_{\tau(x_i)}(x_i)u_{i,\tau(x_i)}+\sigma_{\tau(x)}(x)z_{\tau(x)}. B τ ( u , z ) = S ( τ ) + i = 1 ∑ m σ τ ( x i ) ( x i ) u i , τ ( x i ) + σ τ ( x ) ( x ) z τ ( x ) .
Let A π A_\pi A π be the set of pairs ( u , z ) (u,z) ( u , z ) for which π \pi π wins. For each competitor τ \tau τ , membership in A π A_\pi A π requires
{ B π ( u , z ) > B τ ( u , z ) , if τ has priority over π in a tie , B π ( u , z ) ≥ B τ ( u , z ) , if π has priority over τ in a tie . \begin{cases}
B_\pi(u,z)>B_\tau(u,z), & \text{if } \tau\text{ has priority over } \pi\text{ in a tie},\\
B_\pi(u,z)\ge B_\tau(u,z), & \text{if } \pi\text{ has priority over } \tau\text{ in a tie}.
\end{cases} { B π ( u , z ) > B τ ( u , z ) , B π ( u , z ) ≥ B τ ( u , z ) , if τ has priority over π in a tie , if π has priority over τ in a tie .
Each score difference B π − B τ B_\pi-B_\tau B π − B τ is affine in ( u , z ) (u,z) ( u , z ) . Thus each comparison defines a half-space, and their intersection A π A_\pi A π is convex. Now hold z z z fixed. The only randomness left is the pool noise u u u , whose density is 2 − m K e − ∥ u ∥ 1 2^{-mK}e^{-\lVert u\rVert_1} 2 − m K e − ∥ u ∥ 1 . Hence
r π ( z ) = ∫ R m K f ( u , z ) d u , f ( u , z ) = 1 { ( u , z ) ∈ A π } 2 − m K e − ∥ u ∥ 1 . r_\pi(z)=\int_{\mathbb{R}^{mK}}f(u,z)\,du,\qquad f(u,z)=\mathbf{1}\{(u,z)\in A_\pi\}\,2^{-mK}e^{-\lVert u\rVert_1}. r π ( z ) = ∫ R m K f ( u , z ) d u , f ( u , z ) = 1 {( u , z ) ∈ A π } 2 − m K e − ∥ u ∥ 1 .
We verify that f f f is jointly log-concave. Fix 0 < t < 1 0 < t < 1 0 < t < 1 and set
u t = ( 1 − t ) u 0 + t u 1 , z t = ( 1 − t ) z 0 + t z 1 . u_t = (1-t)u_0 + tu_1,\qquad z_t = (1-t)z_0 + tz_1. u t = ( 1 − t ) u 0 + t u 1 , z t = ( 1 − t ) z 0 + t z 1 .
If both ( u 0 , z 0 ) (u_0,z_0) ( u 0 , z 0 ) and ( u 1 , z 1 ) (u_1,z_1) ( u 1 , z 1 ) belong to A π A_\pi A π , convexity gives ( u t , z t ) ∈ A π (u_t,z_t) \in A_\pi ( u t , z t ) ∈ A π . Since ∥ u t ∥ 1 ≤ ( 1 − t ) ∥ u 0 ∥ 1 + t ∥ u 1 ∥ 1 \lVert u_t\rVert_1 \le(1-t)\lVert u_0\rVert_1 + t\lVert u_1\rVert_1 ∥ u t ∥ 1 ≤ ( 1 − t ) ∥ u 0 ∥ 1 + t ∥ u 1 ∥ 1 , we obtain
f ( u t , z t ) = 2 − m K e − ∥ u t ∥ 1 ≥ f ( u 0 , z 0 ) 1 − t f ( u 1 , z 1 ) t . f(u_t,z_t) = 2^{-m}K_e^{-\lVert u_t\rVert_1} \ge f(u_0,z_0)^{1-t}f(u_1,z_1)^t. f ( u t , z t ) = 2 − m K e − ∥ u t ∥ 1 ≥ f ( u 0 , z 0 ) 1 − t f ( u 1 , z 1 ) t .
If either endpoint lies outside A π A_\pi A π , the right-hand side is zero, so the same inequality holds. Prékopa [Pré73]'s marginalization theorem now gives log-concavity of r π ( z ) = ∫ f ( u , z ) d u r_\pi(z) = \int f(u,z)\,du r π ( z ) = ∫ f ( u , z ) d u in z z z . Taking t = 1 / 2 t=1/2 t = 1/2 gives
r π ( z 0 + z 1 2 ) ≥ r π ( z 0 ) r π ( z 1 ) . r_\pi\left(\frac{z_0+z_1}{2}\right) \ge\sqrt{r_\pi(z_0)r_\pi(z_1)}. r π ( 2 z 0 + z 1 ) ≥ r π ( z 0 ) r π ( z 1 ) .
Lemma 9 (Comparison at a fixed penalty). Fix x x x , a a a and put v = b a / σ a ( x ) v=b_a/\sigma_a(x) v = b a / σ a ( x ) . Then
p a − p a − ≤ 3 D a ( x ) + 3 2 p a min { v , 1 } 2 . (8) p_a-p_a^- \le3D_a(x)+\frac{3}{2}p_a\min\{v,1\}^2. \tag*{(8)} p a − p a − ≤ 3 D a ( x ) + 2 3 p a min { v , 1 } 2 . (8)
Proof. For the a a a th standard basis vector e a e_a e a ,
σ π ( x ) ( x ) ( − v e a ) π ( x ) = − v σ a ( x ) 1 { π ( x ) = a } = − b a 1 { π ( x ) = a } . \sigma_{\pi(x)}(x)(-ve_a)_{\pi(x)}=-v\sigma_a(x)\mathbf{1}\{\pi(x)=a\}=-b_a\mathbf{1}\{\pi(x)=a\}. σ π ( x ) ( x ) ( − v e a ) π ( x ) = − v σ a ( x ) 1 { π ( x ) = a } = − b a 1 { π ( x ) = a } .
Consequently the two probabilities being compared are
p a = E C ∑ π ( x ) = a ∫ r π ( z ) μ ( d z ) = E C ∑ π ( x ) = a w π , p_a=\mathbb{E}_C\sum_{\pi(x)=a}\int r_\pi(z)\,\mu(dz)=\mathbb{E}_C\sum_{\pi(x)=a}w_\pi, p a = E C π ( x ) = a ∑ ∫ r π ( z ) μ ( d z ) = E C π ( x ) = a ∑ w π ,
p a − = Pr { ( arg max π [ S ( π ) + P π ( σ ) − b a 1 { π ( x ) = a } ] ) ( x ) = a } = E C ∑ π ( x ) = a r π ( − v e a ) . p_a^-=\Pr\left\{\left(\underset{\pi}{\arg\max}\left[S(\pi)+P_\pi(\sigma)-b_a\mathbf{1}\{\pi(x)=a\}\right]\right)(x)=a\right\}=\mathbb{E}_C\sum_{\pi(x)=a}r_\pi(-ve_a). p a − = Pr { ( π arg max [ S ( π ) + P π ( σ ) − b a 1 { π ( x ) = a } ] ) ( x ) = a } = E C π ( x ) = a ∑ r π ( − v e a ) .
Write r = r π r=r_\pi r = r π , w = w π w=w_\pi w = w π , ν = ν π \nu=\nu_\pi ν = ν π , and J ( z ) = − 2 v e a − z J(z)=-2ve_a-z J ( z ) = − 2 v e a − z . The midpoint of z z z , J ( z ) J(z) J ( z ) is − v e a -ve_a − v e a , so Lemma 8 gives r ( − v e a ) ≥ r ( z ) r ( J ( z ) ) r(-ve_a)\ge\sqrt{r(z)r(J(z))} r ( − v e a ) ≥ r ( z ) r ( J ( z )) . For any density Q Q Q , the reflected density is ( J Q ) ( z ) = Q ( J ( z ) ) (JQ)(z)=Q(J(z)) ( J Q ) ( z ) = Q ( J ( z )) since J − 1 = J J^{-1}=J J − 1 = J and ∣ det D J ∣ = 1 |\det DJ|=1 ∣ det D J ∣ = 1 . Put h ( P , Q ) 2 = ∫ ( P − Q ) 2 = 2 − 2 ∫ P Q h(P,Q)^2=\int(\sqrt{P}-\sqrt{Q})^2=2-2\int\sqrt{PQ} h ( P , Q ) 2 = ∫ ( P − Q ) 2 = 2 − 2 ∫ P Q . For w > 0 w>0 w > 0 , use ν ( z ) = r ( z ) μ ( z ) / w \nu(z)=r(z)\mu(z)/w ν ( z ) = r ( z ) μ ( z ) / w :
∫ μ ( z ) μ ( J z ) d z ≤ ( ∫ μ ( z ) d z ∫ μ ( J z ) d z ) 1 / 2 = 1 , \int\sqrt{\mu(z)\mu(Jz)}\,dz\le\left(\int\mu(z)\,dz\int\mu(Jz)\,dz\right)^{1/2}=1, ∫ μ ( z ) μ ( J z ) d z ≤ ( ∫ μ ( z ) d z ∫ μ ( J z ) d z ) 1/2 = 1 ,
r ( − v e a ) ≥ r ( − v e a ) ∫ μ ( z ) μ ( J z ) d z ≥ ∫ r ( z ) r ( J z ) μ ( z ) μ ( J z ) d z = w ∫ ν ( z ) ( J ν ) ( z ) d z = w ( 1 − 1 2 h ( ν , J ν ) 2 ) . \begin{aligned}
r(-ve_a)\ge r(-ve_a)\int\sqrt{\mu(z)\mu(Jz)}\,dz \\
&\ge\int\sqrt{r(z)r(Jz)\mu(z)\mu(Jz)}\,dz \\
&=w\int\sqrt{\nu(z)(J\nu)(z)}\,dz=w\left(1-\frac{1}{2}h(\nu,J\nu)^2\right).
\end{aligned} r ( − v e a ) ≥ r ( − v e a ) ∫ μ ( z ) μ ( J z ) d z ≥ ∫ r ( z ) r ( J z ) μ ( z ) μ ( J z ) d z = w ∫ ν ( z ) ( J ν ) ( z ) d z = w ( 1 − 2 1 h ( ν , J ν ) 2 ) .
When w = 0 w=0 w = 0 , w − r ( − v e a ) ≤ 0 w-r(-ve_a)\le0 w − r ( − v e a ) ≤ 0 and this policy can be dropped from the upper bound. For w > 0 w>0 w > 0 , the triangle inequality along ν \nu ν , μ \mu μ , J μ J\mu J μ , J ν J\nu J ν and a change of variables give
h ( ν , J ν ) ≤ h ( ν , μ ) + h ( μ , J μ ) + h ( J μ , J ν ) , h ( J μ , J ν ) = h ( μ , ν ) . h(\nu,J\nu)\le h(\nu,\mu)+h(\mu,J\mu)+h(J\mu,J\nu),\qquad h(J\mu,J\nu)=h(\mu,\nu). h ( ν , J ν ) ≤ h ( ν , μ ) + h ( μ , J μ ) + h ( J μ , J ν ) , h ( J μ , J ν ) = h ( μ , ν ) .
Also
h ( ν , μ ) 2 = 2 ∫ { ν > 0 } ν ( 1 − μ ν ) ≤ 2 ∫ { ν > 0 } ν ( − log μ ν ) = KL ( ν ∥ μ ) . h(\nu,\mu)^2=2\int_{\{\nu>0\}}\nu\left(1-\sqrt{\frac{\mu}{\nu}}\right)\le2\int_{\{\nu>0\}}\nu\left(-\log\sqrt{\frac{\mu}{\nu}}\right)=\operatorname{KL}(\nu\mathbin\Vert\mu). h ( ν , μ ) 2 = 2 ∫ { ν > 0 } ν ( 1 − ν μ ) ≤ 2 ∫ { ν > 0 } ν ( − log ν μ ) = KL ( ν ∥ μ ) .
::: Let φ ( t ) = 1 2 e − ∣ t ∣ \varphi(t) = \frac{1}{2}e^{-|t|} φ ( t ) = 2 1 e − ∣ t ∣ denote the standard Laplace density. Since μ ( z ) = ∏ b = 1 K φ ( z b ) \mu(z) = \prod_{b=1}^{K} \varphi(z_b) μ ( z ) = ∏ b = 1 K φ ( z b ) , J ( z ) = − 2 v e a − z J(z) = -2v e_a-z J ( z ) = − 2 v e a − z , and φ \varphi φ is even, we have
( J μ ) ( z ) = μ ( J ( z ) ) = φ ( z a + 2 v ) ∏ b ≠ a φ ( z b ) . (J\mu)(z) = \mu(J(z)) = \varphi(z_a+2v)\prod_{b\ne a}\varphi(z_b). ( J μ ) ( z ) = μ ( J ( z )) = φ ( z a + 2 v ) b = a ∏ φ ( z b ) .
Put g 0 ( t ) = φ ( t ) g_0(t) = \sqrt{\varphi(t)} g 0 ( t ) = φ ( t ) . Integrating out the other K − 1 K-1 K − 1 coordinates and using Cauchy–Schwarz gives
h ( μ , J μ ) 2 = ∫ [ g 0 ( t + 2 v ) − g 0 ( t ) ] 2 d t h(\mu,J\mu)^2 = \int[g_0(t+2v)-g_0(t)]^2\,dt h ( μ , J μ ) 2 = ∫ [ g 0 ( t + 2 v ) − g 0 ( t ) ] 2 d t
≤ 2 v ∫ 0 2 v ∫ ∣ g 0 ′ ( t + s ) ∣ 2 d t d s = ( 2 v ) 2 / 4 = v 2 , \le2v\int_0^{2v}\int|g_0'(t+s)|^2\,dt\,ds=(2v)^2/4=v^2, ≤ 2 v ∫ 0 2 v ∫ ∣ g 0 ′ ( t + s ) ∣ 2 d t d s = ( 2 v ) 2 /4 = v 2 ,
since ∣ g 0 ′ ∣ = g 0 / 2 |g_0'|=g_0/2 ∣ g 0 ′ ∣ = g 0 /2 almost everywhere and ∫ g 0 2 = 1 \int g_0^2=1 ∫ g 0 2 = 1 . Using ( A + B + C ) 2 ≤ 3 ( A 2 + B 2 + C 2 ) (A+B+C)^2\le3(A^2+B^2+C^2) ( A + B + C ) 2 ≤ 3 ( A 2 + B 2 + C 2 ) now gives
w − r π ( − v e a ) ≤ 3 2 w [ h ( ν , μ ) 2 + h ( μ , J μ ) 2 + h ( J μ , J ν ) 2 ] w-r_\pi(-ve_a)\le\frac{3}{2}w\left[h(\nu,\mu)^2+h(\mu,J\mu)^2+h(J\mu,J\nu)^2\right] w − r π ( − v e a ) ≤ 2 3 w [ h ( ν , μ ) 2 + h ( μ , J μ ) 2 + h ( J μ , J ν ) 2 ]
≤ 3 w KL ( ν ∥ μ ) + 3 2 w v 2 , \le3w\operatorname{KL}(\nu\Vert\mu)+\frac{3}{2}wv^2, ≤ 3 w KL ( ν ∥ μ ) + 2 3 w v 2 ,
p a − p a − = E C π ( x ) = a ( w π − r π ( − v e a ) ) ≤ 3 D a ( x ) + 3 2 p a v 2 . p_a-p_a^-=\mathbb{E}_{C\atop\pi(x)=a}\left(w_\pi-r_\pi(-ve_a)\right)\le3D_a(x)+\frac{3}{2}p_av^2. p a − p a − = E π ( x ) = a C ( w π − r π ( − v e a ) ) ≤ 3 D a ( x ) + 2 3 p a v 2 .
For v > 1 v>1 v > 1 , p a − p a − ≤ p a ≤ 3 D a ( x ) + 3 2 p a p_a-p_a^-\le p_a\le3D_a(x)+\frac{3}{2}p_a p a − p a − ≤ p a ≤ 3 D a ( x ) + 2 3 p a . The two ranges therefore give the square of min { v , 1 } \min\{v,1\} min { v , 1 } in (8).
Lemma 10 (Cost of the shift). At a minimizing scale, for g ( x ) ∈ Γ + g(x)\in\Gamma_+ g ( x ) ∈ Γ + and d = min { b a / σ a ( x ) , 1 } d=\min\{b_a/\sigma_a(x),1\} d = min { b a / σ a ( x ) , 1 } ,
p a d 2 ≤ { 2 / B , σ a ( x ) = B , 3 2 D a ( x ) , σ a ( x ) < B . p_a d^2\le
\begin{cases}
2/B, & \sigma_a(x)=B,\\
\frac{3}{2}D_a(x), & \sigma_a(x)<B.
\end{cases} p a d 2 ≤ { 2/ B , 2 3 D a ( x ) , σ a ( x ) = B , σ a ( x ) < B .
Proof. Since γ ≤ 1 / 2 \gamma\le1/2 γ ≤ 1/2 , (4) gives p a ≤ 2 q a p_a\le2q_a p a ≤ 2 q a . Write v = b a / σ a ( x ) v=b_a/\sigma_a(x) v = b a / σ a ( x ) , so q a v = c a / σ a ( x ) q_av=c_a/\sigma_a(x) q a v = c a / σ a ( x ) . When σ a ( x ) = B \sigma_a(x)=B σ a ( x ) = B , we have p a d 2 ≤ 2 q a v ≤ 2 / B p_ad^2\le2q_av\le2/B p a d 2 ≤ 2 q a v ≤ 2/ B . Suppose σ a ( x ) < B \sigma_a(x)<B σ a ( x ) < B . By Lemma 7 and the parameter choice λ = 4 n ℓ \lambda=4n\ell λ = 4 n ℓ with ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 , we have
α a ( x ) ≥ λ n σ a ( x ) ≥ 4 σ a ( x ) . \alpha_a(x)\ge\frac{\lambda}{n\sigma_a(x)}\ge\frac{4}{\sigma_a(x)}. α a ( x ) ≥ n σ a ( x ) λ ≥ σ a ( x ) 4 .
Since q a v = c a / σ a ( x ) q_av=c_a/\sigma_a(x) q a v = c a / σ a ( x ) and c a ≤ 1 c_a\le1 c a ≤ 1 , it follows that
α a ( x ) ≥ 4 σ a ( x ) ≥ 4 q a v ≥ 2 p a d , \alpha_a(x)\ge\frac{4}{\sigma_a(x)}\ge4q_av\ge2p_ad, α a ( x ) ≥ σ a ( x ) 4 ≥ 4 q a v ≥ 2 p a d ,
where the last inequality uses p a ≤ 2 q a p_a\le2q_a p a ≤ 2 q a and d = min { v , 1 } ≤ v d=\min\{v,1\}\le v d = min { v , 1 } ≤ v .
It remains to turn the lower bound on α a ( x ) \alpha_a(x) α a ( x ) into a lower bound on D a ( x ) D_a(x) D a ( x ) . Set θ = d / 2 \theta=d/2 θ = d /2 . We will show that
D a ( x ) ≥ θ α a ( x ) + p a log ( 1 − θ 2 ) . D_a(x)\ge\theta\alpha_a(x)+p_a\log(1-\theta^2). D a ( x ) ≥ θ α a ( x ) + p a log ( 1 − θ 2 ) .
Fix the pool locations C C C and a policy π \pi π with w π > 0 w_\pi>0 w π > 0 . Recall that μ \mu μ is the law of the inserted noise vector Z Z Z , and ν π \nu_\pi ν π is its conditional law given C C C and W x = π W_x=\pi W x = π . To relate KL ( ν π ∥ μ ) \operatorname{KL}(\nu_\pi\Vert\mu) KL ( ν π ∥ μ ) to E ν π [ Z a ] \mathbb{E}_{\nu_\pi}[Z_a] E ν π [ Z a ] , define an auxiliary law μ θ \mu_\theta μ θ for the same vector by giving each z z z weight e θ z a e^{\theta z_a} e θ z a relative to μ \mu μ . Dividing by the total weight gives
μ θ ( d z ) = e θ z a M θ μ ( d z ) , M θ = ∫ e θ z a μ ( d z ) . \mu_\theta(dz)=\frac{e^{\theta z_a}}{M_\theta}\,\mu(dz),\qquad M_\theta=\int e^{\theta z_a}\,\mu(dz). μ θ ( d z ) = M θ e θ z a μ ( d z ) , M θ = ∫ e θ z a μ ( d z ) .
Since Z a Z_a Z a has density e − ∣ t ∣ / 2 e^{-\lvert t\rvert/2} e − ∣ t ∣ /2 and 0 ≤ θ ≤ 1 / 2 0 \le\theta\le1/2 0 ≤ θ ≤ 1/2 ,
M θ = 1 2 ∫ 0 ∞ e − ( 1 − θ ) t d t + 1 2 ∫ 0 ∞ e − ( 1 + θ ) t d t = 1 1 − θ 2 . M_\theta= \frac{1}{2}\int_0^\infty e^{-(1-\theta)t}\,\mathrm{d}t+\frac{1}{2}\int_0^\infty e^{-(1+\theta)t}\,\mathrm{d}t=\frac{1}{1-\theta^2}. M θ = 2 1 ∫ 0 ∞ e − ( 1 − θ ) t d t + 2 1 ∫ 0 ∞ e − ( 1 + θ ) t d t = 1 − θ 2 1 .
By construction, log ( d μ θ / d μ ) ( z ) = θ z a − log M θ \log(\mathrm{d}\mu_\theta/\mathrm{d}\mu)(z)=\theta z_a-\log M_\theta log ( d μ θ / d μ ) ( z ) = θ z a − log M θ . Hence
KL ( ν π ∥ μ ) = KL ( ν π ∥ μ θ ) + E ν π [ log d μ θ d μ ( Z ) ] ≥ θ E ν π [ Z a ] − log M θ . \begin{aligned}
\operatorname{KL}(\nu_\pi\mathbin\Vert\mu)=\operatorname{KL}(\nu_\pi\mathbin\Vert\mu_\theta)+\mathbb{E}_{\nu_\pi}\left[\log\frac{\mathrm{d}\mu_\theta}{\mathrm{d}\mu}(Z)\right] \\
&\geq\theta\mathbb{E}_{\nu_\pi}[Z_a]-\log M_\theta.
\end{aligned} KL ( ν π ∥ μ ) = KL ( ν π ∥ μ θ ) + E ν π [ log d μ d μ θ ( Z ) ] ≥ θ E ν π [ Z a ] − log M θ .
Multiply by w π w_\pi w π , sum over policies with π ( x ) = a \pi(x)=a π ( x ) = a and w π > 0 w_\pi>0 w π > 0 , and average over C C C . By the definition of ν π \nu_\pi ν π ,
E C ∑ π ( x ) = a w π > 0 w π E ν π [ Z a ] = E [ Z a 1 { W x ( x ) = a } ] = α a ( x ) , \mathbb{E}_C\sum_{\substack{\pi(x)=a\\w_\pi>0}}w_\pi\mathbb{E}_{\nu_\pi}[Z_a]=\mathbb{E}[Z_a\mathbf{1}\{W_x(x)=a\}]=\alpha_a(x), E C π ( x ) = a w π > 0 ∑ w π E ν π [ Z a ] = E [ Z a 1 { W x ( x ) = a }] = α a ( x ) ,
E C ∑ π ( x ) = a w π = Pr ( W x ( x ) = a ) = p a . \mathbb{E}_C\sum_{\pi(x)=a}w_\pi=\Pr(W_x(x)=a)=p_a. E C π ( x ) = a ∑ w π = Pr ( W x ( x ) = a ) = p a .
The weighted sum of the KL terms is D a ( x ) D_a(x) D a ( x ) , so
D a ( x ) ≥ θ α a ( x ) − p a log M θ = θ α a ( x ) + p a log ( 1 − θ 2 ) . D_a(x)\geq\theta\alpha_a(x)-p_a\log M_\theta=\theta\alpha_a(x)+p_a\log(1-\theta^2). D a ( x ) ≥ θ α a ( x ) − p a log M θ = θ α a ( x ) + p a log ( 1 − θ 2 ) .
Finally, θ = d / 2 \theta=d/2 θ = d /2 gives θ 2 = d 2 / 4 ≤ 1 / 4 \theta^2=d^2/4\leq1/4 θ 2 = d 2 /4 ≤ 1/4 , so
− log ( 1 − θ 2 ) = ∫ 0 θ 2 d t 1 − t ≤ θ 2 1 − θ 2 ≤ d 2 3 . -\log(1-\theta^2)=\int_0^{\theta^2}\frac{\mathrm{d}t}{1-t}\leq\frac{\theta^2}{1-\theta^2}\leq\frac{d^2}{3}. − log ( 1 − θ 2 ) = ∫ 0 θ 2 1 − t d t ≤ 1 − θ 2 θ 2 ≤ 3 d 2 .
Using α a ( x ) ≥ 2 p a d \alpha_a(x)\geq2p_a d α a ( x ) ≥ 2 p a d from above, we conclude that
D a ( x ) ≥ d 2 α a ( x ) − 1 3 p a d 2 ≥ d 2 ( 2 p a d ) − 1 3 p a d 2 = 2 3 p a d 2 . D_a(x)\geq\frac{d}{2}\alpha_a(x)-\frac{1}{3}p_a d^2\geq\frac{d}{2}(2p_a d)-\frac{1}{3}p_a d^2=\frac{2}{3}p_a d^2. D a ( x ) ≥ 2 d α a ( x ) − 3 1 p a d 2 ≥ 2 d ( 2 p a d ) − 3 1 p a d 2 = 3 2 p a d 2 .
Proof of Lemma 3. Lemma 5 gives the expectation bound. For a positive-mass signature, put d = min { b a / σ a ( x ) , 1 } d=\min\{b_a/\sigma_a(x),1\} d = min { b a / σ a ( x ) , 1 } and apply Lemmas 9 and 10 to obtain
p a − p a − ≤ 3 D a ( x ) + 3 2 p a d 2 ≤ { ( 3 + 3 2 ⋅ 3 2 ) D a ( x ) = 21 4 D a ( x ) , σ a ( x ) < B , 3 D a ( x ) + 3 2 ⋅ 2 / B = 3 D a ( x ) + 3 / B , σ a ( x ) = B . p_a-p_a^- \leq3D_a(x)+\frac{3}{2}p_a d^2\leq
\begin{cases}
\left(3+\frac{3}{2}\cdot\frac{3}{2}\right)D_a(x)=\frac{21}{4}D_a(x), & \sigma_a(x)<B,\\
3D_a(x)+\frac{3}{2}\cdot2/B=3D_a(x)+3/B, & \sigma_a(x)=B.
\end{cases} p a − p a − ≤ 3 D a ( x ) + 2 3 p a d 2 ≤ { ( 3 + 2 3 ⋅ 2 3 ) D a ( x ) = 4 21 D a ( x ) , 3 D a ( x ) + 2 3 ⋅ 2/ B = 3 D a ( x ) + 3/ B , σ a ( x ) < B , σ a ( x ) = B .
Both bounds are at most 6 D a ( x ) + 3 / B 6D_a(x)+3/B 6 D a ( x ) + 3/ B . This proves Lemma 3, since the positive-mass signatures have total probability one.
Oracle Implementation
Fix the past H = ( ( x i , c ^ i ) ) i < t H=((x_i,\hat{c}_i))_{i<t} H = (( x i , c ^ i ) ) i < t and its score S S S . The algorithm uses projected stochastic gradient descent to approximate the minimizer of J S J_S J S . Its random iterates are functions of a context. A stored list of draws lets us evaluate those functions only where they are needed. After x t x_t x t arrives, independent playouts estimate the winning probabilities at that context.
Theorem 11 (Oracle round). On each round Algorithm 2 uses polynomial resources in T , K , L T,K,L T , K , L and satisfies
E [ Φ S , x t ( q t ) ∣ H t − 1 ] ≤ E x ∼ D Φ S , x ( q ∗ ( x ) ) + 1 T . \mathbb{E}[\Phi_{S,x_t}(q_t)\mid H_{t-1}]\leq\mathbb{E}_{x\sim D}\Phi_{S,x}(q^*(x))+\frac{1}{T}. E [ Φ S , x t ( q t ) ∣ H t − 1 ] ≤ E x ∼ D Φ S , x ( q ∗ ( x )) + T 1 .
Together with Theorem 2 and Lemma 4, this proves Theorem 1 . We give the algorithm first and then prove its accuracy and cost.
Sampling and evaluation
Use n n n , λ \lambda λ , B B B , γ \gamma γ from (1) . The following choices fix the precision, iteration count, number of probability samples, and pool cap:
δ = 1 T ( 1 + K / γ ) , ε = λ δ 2 32 B 2 ( n + 1 ) , m = ⌈ 16 K δ 2 ⌉ , \delta= \frac{1}{T(1+K/\gamma)}, \qquad
\varepsilon= \frac{\lambda\delta^{2}}{32B^{2}(n+1)}, \qquad
m = \left\lceil\frac{16K}{\delta^{2}} \right\rceil, δ = T ( 1 + K / γ ) 1 , ε = 32 B 2 ( n + 1 ) λ δ 2 , m = ⌈ δ 2 16 K ⌉ ,
D 0 = B K , G 2 = K ( 4 n 2 + 2 λ 2 ) , J = max { 1 , ⌈ D 0 2 G 2 ε 2 ⌉ } , D_{0} = B\sqrt{K}, \qquad
G^{2} = K(4n^{2}+2\lambda^{2}), \qquad
J = \max\left\{1,\left\lceil\frac{D_{0}^{2}G^{2}}{\varepsilon^{2}}\right\rceil\right\}, D 0 = B K , G 2 = K ( 4 n 2 + 2 λ 2 ) , J = max { 1 , ⌈ ε 2 D 0 2 G 2 ⌉ } ,
η = D 0 G J , M max = ⌈ ( e − 1 ) n + log ( 4 ( J + m ) δ ) ⌉ . \eta= \frac{D_{0}}{G\sqrt{J}}, \qquad
M_{\max} = \left\lceil(e-1)n+\log\left(\frac{4(J+m)}{\delta}\right)\right\rceil. η = G J D 0 , M m a x = ⌈ ( e − 1 ) n + log ( δ 4 ( J + m ) ) ⌉ .
Here D 0 D_{0} D 0 bounds the diameter of the feasible scales, and G 2 G^{2} G 2 bounds the expected squared norm of one stochastic gradient (Lemma 14). A pool U U U consists of pairs ( Y , Z ) (Y,Z) ( Y , Z ) with Y ∼ D Y\sim D Y ∼ D , Z ∼ μ Z\sim\mu Z ∼ μ . Products d ⊙ Z d\odot Z d ⊙ Z are coordinatewise. All fresh draws in the algorithms are independent. Write 1 \mathbf{1} 1 for the all-ones vector of the required dimension.
Algorithm 2 One bandit round given history H H H
Draw J + m J+m J + m capped Poisson counts. If any exceeds M max M_{\max} M m a x , receive x t x_t x t , set q = 1 / K q=1/K q = 1/ K , and continue at line 5. Otherwise use these counts in order.
Start with an empty list of training records. For j = 0 , … , J − 1 j=0,\ldots,J-1 j = 0 , … , J − 1 : (a) Draw a pool U j U_j U j of the specified size. For every ( Y , Z ) ∈ U j (Y,Z)\in U_j ( Y , Z ) ∈ U j , call Algorithm 4 at Y Y Y on the first j j j records, obtaining ( d , u ) (d,u) ( d , u ) . Store ( Y , d ⊙ Z ) (Y,d\odot Z) ( Y , d ⊙ Z ) in the list P j P_j P j . (b) Draw one Z j ′ ∼ μ Z_j'\sim\mu Z j ′ ∼ μ and append ( P j , Z j ′ ) (P_j,Z_j') ( P j , Z j ′ ) to the records.
Receive x = x t x=x_t x = x t . Call Algorithm 4 at x x x on all J J J records and set s ˉ ( x ) = u / J \bar{s}(x)=u/J s ˉ ( x ) = u / J from its second output.
For k = 1 , … , m k=1,\ldots,m k = 1 , … , m , draw a fresh pool. At each of its locations Y Y Y , evaluate s ˉ ( Y ) = u / J \bar{s}(Y)=u/J s ˉ ( Y ) = u / J in the same way. Form the list P k ′ = ( ( Y , s ˉ ( Y ) ⊙ Z ) : ( Y , Z ) in this pool ) P_k'=((Y,\bar{s}(Y)\odot Z):(Y,Z)\text{ in this pool}) P k ′ = (( Y , s ˉ ( Y ) ⊙ Z ) : ( Y , Z ) in this pool ) . Draw Z k ′ ∼ μ Z_k'\sim\mu Z k ′ ∼ μ and set
A k ′ = Winner ( H , P k ′ , x , s ˉ ( x ) ⊙ Z k ′ ) . A_k'=\operatorname{Winner}(H,P_k',x,\bar{s}(x)\odot Z_k'). A k ′ = Winner ( H , P k ′ , x , s ˉ ( x ) ⊙ Z k ′ ) . After all m m m draws, compute for each a ∈ [ K ] a\in[K] a ∈ [ K ]
p ^ a = 1 m ∑ k = 1 m 1 { A k ′ = a } , q a = ( 1 − γ ) p ^ a + γ / K . \hat{p}_a=\frac{1}{m}\sum_{k=1}^{m}\mathbf{1}\{A_k'=a\},\qquad q_a=(1-\gamma)\hat{p}_a+\gamma/K. p ^ a = m 1 k = 1 ∑ m 1 { A k ′ = a } , q a = ( 1 − γ ) p ^ a + γ / K . Draw A t ∼ q A_t\sim q A t ∼ q , observe c t ( x t , A t ) c_t(x_t,A_t) c t ( x t , A t ) , and append ( x t , e A t c t ( x t , A t ) / q A t ) (x_t,e_{A_t}c_t(x_t,A_t)/q_{A_t}) ( x t , e A t c t ( x t , A t ) / q A t ) to H H H .
Algorithm 3 Winner ( H , P , y , v ) \operatorname{Winner}(H,P,y,v) Winner ( H , P , y , v )
For each a ∈ [ K ] a\in[K] a ∈ [ K ] obtain V a V_a V a by querying Val \operatorname{Val} Val on the concatenation H H H , ( ( Y , − u ) : ( Y , u ) ∈ P ) ((Y,-u):(Y,u)\in P) (( Y , − u ) : ( Y , u ) ∈ P ) , ( y , − v − e a ) (y,-v-e_a) ( y , − v − e a ) .
Return the smallest a a a attaining min b V b \min_b V_b min b V b .
Algorithm 4 Evaluate a scale at context y y y using records ( P i , Z i ) 0 ≤ i < j (P_i,Z^i)_{0\le i<j} ( P i , Z i ) 0 ≤ i < j and history H H H
Initialize d = 1 d=1 d = 1 and u = 0 u=0 u = 0 in R K \mathbb{R}^K R K .
For i = 0 , … , j − 1 i=0,\ldots,j-1 i = 0 , … , j − 1 : (a) Set u ← u + d u\leftarrow u+d u ← u + d and A ← Winner ( H , P i , y , d ⊙ Z i ) A\leftarrow\operatorname{Winner}(H,P_i,y,d\odot Z^i) A ← Winner ( H , P i , y , d ⊙ Z i ) . (b) For every a ∈ [ K ] a\in[K] a ∈ [ K ] set d a ← clip [ 1 , B ] ( d a − η [ n Z a i 1 { A = a } − λ / d a ] ) d_a\leftarrow\operatorname{clip}_{[1,B]}\left(d_a-\eta[nZ^i_a\mathbf{1}\{A=a\}-\lambda/d_a]\right) d a ← clip [ 1 , B ] ( d a − η [ n Z a i 1 { A = a } − λ / d a ] ) .
Return ( d , u ) (d,u) ( d , u ) , the current iterate s j ( y ) s^j(y) s j ( y ) and the sum ∑ i < j s i ( y ) \sum_{i<j}s^i(y) ∑ i < j s i ( y ) .
Lemma 12 (Replay computes the explicit SGD iterates). Fix the history H H H and the training draws ( U j , Z j ) 0 ≤ j < J (U_j,Z^j)_{0\le j<J} ( U j , Z j ) 0 ≤ j < J . Consider explicit projected SGD starting from s 0 ( y ) = 1 s^0(y)=1 s 0 ( y ) = 1 and applying the update in Algorithm 4 at every context y y y in every step. For each 0 ≤ j ≤ J 0\le j\le J 0 ≤ j ≤ J and every y y y , Algorithm 4 on the first j j j records of Algorithm 2 returns
( d , u ) = ( s j ( y ) , ∑ i = 0 j − 1 s i ( y ) ) . (d,u)=\left(s^j(y),\sum_{i=0}^{j-1}s^i(y)\right). ( d , u ) = ( s j ( y ) , i = 0 ∑ j − 1 s i ( y ) ) . Proof. We induct on j j j . With no records, replay returns ( 1 , 0 ) = ( s 0 ( y ) , 0 ) (1,0)=(s^0(y),0) ( 1 , 0 ) = ( s 0 ( y ) , 0 ) for every y y y .
Suppose the claim holds after j j j records. To build record j j j , Algorithm 2 calls replay at each location Y Y Y in the new pool U j U_j U j . By induction, the returned scale is s j ( Y ) s^j(Y) s j ( Y ) . Thus the stored pool is exactly the one explicit SGD constructs:
P j = [ ( Y , s j ( Y ) ⊙ Z ) : ( Y , Z ) ∈ U j ] . P_j=\left[(Y,s^j(Y)\odot Z):(Y,Z)\in U_j\right]. P j = [ ( Y , s j ( Y ) ⊙ Z ) : ( Y , Z ) ∈ U j ] . Now fix any query context y y y . After the first j j j records, replay has d = s j ( y ) d=s^j(y) d = s j ( y ) . On record j j j , replay and explicit SGD therefore compute the same action
A j ( y ) = Winner ( H , P j , y , s j ( y ) ⊙ Z j ) . A_j(y)=\operatorname{Winner}(H,P_j,y,s^j(y)\odot Z^j). A j ( y ) = Winner ( H , P j , y , s j ( y ) ⊙ Z j ) . For each a ∈ [ K ] a\in[K] a ∈ [ K ] , both update the scale to
s a j + 1 ( y ) = clip [ 1 , B ] ( s a j ( y ) − η [ n Z a j 1 { A j ( y ) = a } − λ s a j ( y ) ] ) . s_a^{j+1}(y)=\operatorname{clip}_{[1,B]}\left(s_a^j(y)-\eta\left[nZ_a^j\mathbf{1}\{A_j(y)=a\}-\frac{\lambda}{s_a^j(y)}\right]\right). s a j + 1 ( y ) = clip [ 1 , B ] ( s a j ( y ) − η [ n Z a j 1 { A j ( y ) = a } − s a j ( y ) λ ] ) . Replay also adds the pre-update value s j ( y ) s^j(y) s j ( y ) to u u u , giving u = ∑ i = 0 j s i ( y ) u=\sum_{i=0}^{j}s^i(y) u = ∑ i = 0 j s i ( y ) . This proves the claim for j + 1 j+1 j + 1 .
Lemma 13 (Oracle access and cost). Algorithm 3 returns the winning action in each queried playout almost surely. Per round, Algorithm 2 makes at most
O ( K [ M max J 2 + m ( M max + 1 ) ( J + 1 ) ] ) O\left(K\left[M_{\max}J^2+m(M_{\max}+1)(J+1)\right]\right) O ( K [ M m a x J 2 + m ( M m a x + 1 ) ( J + 1 ) ] ) value calls, each on at most T + M max + 1 T+M_{\max}+1 T + M m a x + 1 contexts.
Proof. Write H π = S ( π ) + ∑ ( Y , u ) ∈ P u π ( Y ) + v π ( y ) H_\pi=S(\pi)+\sum_{(Y,u)\in P}u\pi(Y)+v_\pi(y) H π = S ( π ) + ∑ ( Y , u ) ∈ P u π ( Y ) + v π ( y ) . Then
− V a = max π [ H π + 1 { π ( y ) = a } ] , − V a = 1 + max π H π ⟺ ∃ π ∈ arg max H : π ( y ) = a . -V_a=\max_\pi[H_\pi+\mathbf{1}\{\pi(y)=a\}],\qquad-V_a=1+\max_\pi H_\pi\iff\exists\pi\in\arg\max H:\pi(y)=a. − V a = π max [ H π + 1 { π ( y ) = a }] , − V a = 1 + π max H π ⟺ ∃ π ∈ arg max H : π ( y ) = a . Conditional on the other draws, the highest scores of distinct nonempty action groups are constants plus independent continuous shifts s b ( y ) Z b s_b(y)Z_b s b ( y ) Z b . They tie with probability zero. Within a training step
this holds jointly for every prediction signature by a finite union: inductively the input scales depend on y y y only through its signature. Thus reusing that step at later query locations preserves its winning action almost surely.
Building record j j j takes at most j M max jM_{\max} j M m a x winner calls. Evaluating s ˉ ( x ) \bar{s}(x) s ˉ ( x ) costs J J J calls, and each probability trial needs at most J M max + 1 JM_{\max}+1 J M m a x + 1 . Multiplying by K K K proves the stated bound. The storage of scaled training records is O ( K J ( M max + 1 ) ) O(KJ(M_{\max}+1)) O ( K J ( M m a x + 1 )) in addition to the history and working lists. At most ( J + m ) M max (J+m)M_{\max} ( J + m ) M m a x auxiliary contexts are drawn. Each list construction and coordinate update costs polynomially many operations in the dimensions shown. A capped count can be sampled with at most M max + 1 M_{\max}+1 M m a x + 1 independent exponential waiting times of mean one: stop when their sum exceeds n n n or M max + 1 M_{\max}+1 M m a x + 1 arrivals occur by n n n . For k ≤ M max k\le M_{\max} k ≤ M m a x the probability of k k k arrivals is the integral of e − n e^{-n} e − n over 0 < t 1 < ⋯ < t k < n 0<t_1<\cdots<t_k<n 0 < t 1 < ⋯ < t k < n , namely e − n n k / k ! e^{-n}n^k/k! e − n n k / k ! . All displayed parameters and the reciprocals of γ , λ , δ , ε \gamma,\lambda,\delta,\varepsilon γ , λ , δ , ε are polynomially bounded in T , K , L T,K,L T , K , L since L ≥ log 2 L\ge\log2 L ≥ log 2 .
Accuracy of the played distribution
For the next two lemmas allow full Poisson counts. Write s ˉ = J − 1 ∑ j < J s j \bar{s}=J^{-1}\sum_{j<J}s^j s ˉ = J − 1 ∑ j < J s j and ∥ h ∥ D 2 = E Y ∼ D ∑ a h a ( Y ) 2 \lVert h\rVert_D^2=\mathbb{E}_{Y\sim D}\sum_a h_a(Y)^2 ∥ h ∥ D 2 = E Y ∼ D ∑ a h a ( Y ) 2 . At each y y y the stochastic gradient used in Algorithm 4 is
v a j ( y ) = n Z a j 1 { WINNER ( H , P j , y , s j ( y ) ⊙ Z j ) = a } − λ s g , a j . (9) v_a^j(y)=nZ_a^j\mathbf{1}\{\operatorname{WINNER}(H,P_j,y,s^j(y)\odot Z^j)=a\}-\frac{\lambda}{s_{g,a}^j}. \tag*{(9)} v a j ( y ) = n Z a j 1 { WINNER ( H , P j , y , s j ( y ) ⊙ Z j ) = a } − s g , a j λ . (9)
Lemma 14 (Optimization error). With the parameters of Algorithm 2, if s ∗ s^* s ∗ is the scale minimizer at S S S , then
E [ J S ( s ˉ ) − R ( S ) ] ≤ ε , E ∥ s ˉ − s ∗ ∥ D 2 ≤ 2 B 2 ε / λ . (10) \mathbb{E}[J_S(\bar{s})-R(S)]\le\varepsilon,\qquad\mathbb{E}\lVert\bar{s}-s^*\rVert_D^2\le2B^2\varepsilon/\lambda. \tag*{(10)} E [ J S ( s ˉ ) − R ( S )] ≤ ε , E ∥ s ˉ − s ∗ ∥ D 2 ≤ 2 B 2 ε / λ . (10)
Proof. Fix the incoming score S S S and use uncapped Poisson pools. By Lemma 12 , replay evaluates the explicit projected SGD iterates for the same training draws. Thus the scale used by the algorithm is s ˉ = J − 1 ∑ j = 0 J − 1 s j \bar{s}=J^{-1}\sum_{j=0}^{J-1}s^j s ˉ = J − 1 ∑ j = 0 J − 1 s j .
We first identify the conditional mean of one SGD update. Let H j \mathcal{H}_j H j be the history of the first j j j training steps, and write E j [ ⋅ ] = E [ ⋅ ∣ H j ] \mathbb{E}_j[\cdot]=\mathbb{E}[\cdot\mid\mathcal{H}_j] E j [ ⋅ ] = E [ ⋅ ∣ H j ] . Conditional on H j \mathcal{H}_j H j , the current scale s j s^j s j is fixed. At a fixed context y y y , the action used in (9) is
A j ( y ) = WINNER ( H , P j , y , s j ( y ) ⊙ Z j ) . A_j(y)=\operatorname{WINNER}(H,P_j,y,s^j(y)\odot Z^j). A j ( y ) = WINNER ( H , P j , y , s j ( y ) ⊙ Z j ) .
The pool P j P_j P j is a fresh ordinary pool scaled by s j s^j s j , and Z j Z^j Z j is the independent noise vector inserted at y y y . Thus A j ( y ) A_j(y) A j ( y ) is the action of the inserted winner in the experiment defining α a ( y ; s j ) \alpha_a(y;s^j) α a ( y ; s j ) . In particular,
E j [ Z a j 1 { A j ( y ) = a } ] = α a ( y ; s j ) . \mathbb{E}_j[Z_a^j\mathbf{1}\{A_j(y)=a\}]=\alpha_a(y;s^j). E j [ Z a j 1 { A j ( y ) = a }] = α a ( y ; s j ) .
For each g ∈ Γ + g\in\Gamma_+ g ∈ Γ + , choose a context y g y_g y g with g ( y g ) = g g(y_g)=g g ( y g ) = g . Substituting the preceding identity into (9) and applying Lemma 7 gives
ω g E j [ v a j ( y g ) ] = ω g ( n α a ( y g ; s j ) − λ s g , a j ) = ∂ J S ( s j ) ∂ s g , a . \omega_g\mathbb{E}_j[v_a^j(y_g)]
=\omega_g\left(n\alpha_a(y_g;s^j)-\frac{\lambda}{s_{g,a}^j}\right)
=\frac{\partial J_S(s^j)}{\partial s_{g,a}}. ω g E j [ v a j ( y g )] = ω g ( n α a ( y g ; s j ) − s g , a j λ ) = ∂ s g , a ∂ J S ( s j ) .
Consequently, with ⟨ h , k ⟩ D = E Y ∼ D ∑ a h a ( Y ) k a ( Y ) \langle h,k\rangle_D=\mathbb{E}_{Y\sim D}\sum_a h_a(Y)k_a(Y) ⟨ h , k ⟩ D = E Y ∼ D ∑ a h a ( Y ) k a ( Y ) , convexity of J S J_S J S gives
J S ( s j ) − R ( S ) = J S ( s j ) − J S ( s ∗ ) ≤ ∑ g ∈ Γ + ∑ a = 1 K ∂ J S ( s j ) ∂ s g , a ( s g , a j − s g , a ∗ ) = ∑ g ∈ Γ + ω g ∑ a = 1 K E j [ v a j ( y g ) ] ( s g , a j − s g , a ∗ ) = ⟨ E j [ v j ] , s j − s ∗ ⟩ D . \begin{aligned}
J_S(s^j)-R(S)&=J_S(s^j)-J_S(s^*)\\
&\le\sum_{g\in\Gamma_+}\sum_{a=1}^{K}\frac{\partial J_S(s^j)}{\partial s_{g,a}}(s_{g,a}^j-s_{g,a}^*)\\
&=\sum_{g\in\Gamma_+}\omega_g\sum_{a=1}^{K}\mathbb{E}_j[v_a^j(y_g)](s_{g,a}^j-s_{g,a}^*)=\langle\mathbb{E}_j[v^j],s^j-s^*\rangle_D.
\end{aligned} J S ( s j ) − R ( S ) = J S ( s j ) − J S ( s ∗ ) ≤ g ∈ Γ + ∑ a = 1 ∑ K ∂ s g , a ∂ J S ( s j ) ( s g , a j − s g , a ∗ ) = g ∈ Γ + ∑ ω g a = 1 ∑ K E j [ v a j ( y g )] ( s g , a j − s g , a ∗ ) = ⟨ E j [ v j ] , s j − s ∗ ⟩ D .
To bound the squared size of the update, use s a j ( y ) ≥ 1 s_a^j(y) \ge1 s a j ( y ) ≥ 1 and E j [ ( Z a j ) 2 ] = 2 \mathbb{E}_j[(Z_a^j)^2] = 2 E j [( Z a j ) 2 ] = 2 . For every y , a y,a y , a ,
E j [ ( v a j ( y ) ) 2 ] ≤ 2 n 2 E j [ ( Z a j ) 2 1 { A j ( y ) = a } ] + 2 λ 2 ( s a j ( y ) ) 2 ≤ 4 n 2 + 2 λ 2 . \mathbb{E}_j[(v_a^j(y))^2] \le2n^2\mathbb{E}_j[(Z_a^j)^2\mathbf{1}\{A_j(y)=a\}] + \frac{2\lambda^2}{(s_a^j(y))^2}
\le4n^2 + 2\lambda^2. E j [( v a j ( y ) ) 2 ] ≤ 2 n 2 E j [( Z a j ) 2 1 { A j ( y ) = a }] + ( s a j ( y ) ) 2 2 λ 2 ≤ 4 n 2 + 2 λ 2 .
Hence
E j [ ∥ v j ∥ D 2 ] = E Y ∼ D ∑ a = 1 K E j [ ( v a j ( Y ) ) 2 ] ≤ K ( 4 n 2 + 2 λ 2 ) = G 2 , \mathbb{E}_j[\lVert v^j\rVert_D^2] = \mathbb{E}_{Y\sim D}\sum_{a=1}^{K}\mathbb{E}_j[(v_a^j(Y))^2] \le K(4n^2+2\lambda^2)=G^2, E j [∥ v j ∥ D 2 ] = E Y ∼ D a = 1 ∑ K E j [( v a j ( Y ) ) 2 ] ≤ K ( 4 n 2 + 2 λ 2 ) = G 2 ,
where Y Y Y is an independent draw from D D D .
Since every coordinate of s ∗ s^* s ∗ lies in [ 1 , B ] [1,B] [ 1 , B ] , clipping the update can only decrease its distance to s ∗ s^* s ∗ . Expanding the square gives
∥ s j + 1 − s ∗ ∥ D 2 ≤ ∥ s j − η v j − s ∗ ∥ D 2 = ∥ s j − s ∗ ∥ D 2 − 2 η ⟨ v j , s j − s ∗ ⟩ D + η 2 ∥ v j ∥ D 2 . \lVert s^{j+1}-s^*\rVert_D^2 \le\lVert s^j-\eta v^j-s^*\rVert_D^2
= \lVert s^j-s^*\rVert_D^2-2\eta\langle v^j,s^j-s^*\rangle_D+\eta^2\lVert v^j\rVert_D^2. ∥ s j + 1 − s ∗ ∥ D 2 ≤ ∥ s j − η v j − s ∗ ∥ D 2 = ∥ s j − s ∗ ∥ D 2 − 2 η ⟨ v j , s j − s ∗ ⟩ D + η 2 ∥ v j ∥ D 2 .
Taking E j \mathbb{E}_j E j and using the two bounds above yields
2 η ( J S ( s j ) − R ( S ) ) ≤ ∥ s j − s ∗ ∥ D 2 − E j [ ∥ s j + 1 − s ∗ ∥ D 2 ] + η 2 G 2 . 2\eta(J_S(s^j)-R(S))\le\lVert s^j-s^*\rVert_D^2-\mathbb{E}_j[\lVert s^{j+1}-s^*\rVert_D^2]+\eta^2G^2. 2 η ( J S ( s j ) − R ( S )) ≤ ∥ s j − s ∗ ∥ D 2 − E j [∥ s j + 1 − s ∗ ∥ D 2 ] + η 2 G 2 .
Taking expectations and summing from j = 0 j=0 j = 0 to J − 1 J-1 J − 1 now gives
2 η ∑ j = 0 J − 1 E [ J S ( s j ) − R ( S ) ] ≤ ∑ j = 0 J − 1 ( E ∥ s j − s ∗ ∥ D 2 − E ∥ s j + 1 − s ∗ ∥ D 2 ) + J η 2 G 2 = ∥ s 0 − s ∗ ∥ D 2 − E ∥ s J − s ∗ ∥ D 2 + J η 2 G 2 ≤ D 0 2 + J η 2 G 2 . \begin{aligned}
2\eta\sum_{j=0}^{J-1}\mathbb{E}[J_S(s^j)-R(S)]\le\sum_{j=0}^{J-1}\left(\mathbb{E}\lVert s^j-s^*\rVert_D^2-\mathbb{E}\lVert s^{j+1}-s^*\rVert_D^2\right)+J\eta^2G^2 \\
&=\lVert s^0-s^*\rVert_D^2-\mathbb{E}\lVert s^J-s^*\rVert_D^2+J\eta^2G^2 \\
&\le D_0^2+J\eta^2G^2.
\end{aligned} 2 η j = 0 ∑ J − 1 E [ J S ( s j ) − R ( S )] ≤ j = 0 ∑ J − 1 ( E ∥ s j − s ∗ ∥ D 2 − E ∥ s j + 1 − s ∗ ∥ D 2 ) + J η 2 G 2 = ∥ s 0 − s ∗ ∥ D 2 − E ∥ s J − s ∗ ∥ D 2 + J η 2 G 2 ≤ D 0 2 + J η 2 G 2 .
By convexity at s ˉ \bar{s} s ˉ and the choices η = D 0 / ( G J ) \eta=D_0/(G\sqrt{J}) η = D 0 / ( G J ) and J ≥ D 0 2 G 2 / ε 2 J\ge D_0^2G^2/\varepsilon^2 J ≥ D 0 2 G 2 / ε 2 ,
E [ J S ( s ˉ ) − R ( S ) ] ≤ 1 J ∑ j = 0 J − 1 E [ J S ( s j ) − R ( S ) ] ≤ D 0 2 + J η 2 G 2 2 η J = D 0 G 2 J + D 0 G 2 J = D 0 G J ≤ ε . \begin{aligned}
\mathbb{E}[J_S(\bar{s})-R(S)]\le\frac{1}{J}\sum_{j=0}^{J-1}\mathbb{E}[J_S(s^j)-R(S)] \\
&\le\frac{D_0^2+J\eta^2G^2}{2\eta J}=\frac{D_0G}{2\sqrt{J}}+\frac{D_0G}{2\sqrt{J}}=\frac{D_0G}{\sqrt{J}}\le\varepsilon.
\end{aligned} E [ J S ( s ˉ ) − R ( S )] ≤ J 1 j = 0 ∑ J − 1 E [ J S ( s j ) − R ( S )] ≤ 2 η J D 0 2 + J η 2 G 2 = 2 J D 0 G + 2 J D 0 G = J D 0 G ≤ ε .
It remains to bound the distance from s ˉ \bar{s} s ˉ to s ∗ s^* s ∗ . For f ( z ) = λ log ( B / z ) f(z)=\lambda\log(B/z) f ( z ) = λ log ( B / z ) and 1 ≤ z ≤ B 1\le z\le B 1 ≤ z ≤ B , we have
f ′ ′ ( z ) = λ / z 2 ≥ λ / B 2 . f''(z)=\lambda/z^2\ge\lambda/B^2. f ′′ ( z ) = λ / z 2 ≥ λ / B 2 .
Thus, for u , v ∈ [ 1 , B ] u,v\in[1,B] u , v ∈ [ 1 , B ] and 0 < t < 1 0<t<1 0 < t < 1 ,
f ( ( 1 − t ) u + t v ) ≤ ( 1 − t ) f ( u ) + t f ( v ) − λ 2 B 2 t ( 1 − t ) ( u − v ) 2 . f((1-t)u+tv)\le(1-t)f(u)+tf(v)-\frac{\lambda}{2B^2}t(1-t)(u-v)^2. f (( 1 − t ) u + t v ) ≤ ( 1 − t ) f ( u ) + t f ( v ) − 2 B 2 λ t ( 1 − t ) ( u − v ) 2 .
Apply this inequality to u = s a ∗ ( Y ) u=s_a^*(Y) u = s a ∗ ( Y ) and v = s a ( Y ) v=s_a(Y) v = s a ( Y ) for any feasible scale s s s . Summing over a a a and averaging over Y Y Y gives the squared distance E Y ∑ a ( s a ( Y ) − s a ∗ ( Y ) ) 2 = ∥ s − s ∗ ∥ D 2 \mathbb{E}_Y\sum_a(s_a(Y)-s_a^*(Y))^2=\lVert s-s^*\rVert_D^2 E Y ∑ a ( s a ( Y ) − s a ∗ ( Y ) ) 2 = ∥ s − s ∗ ∥ D 2 . Adding the convex pool term and using the optimality of s ∗ s^* s ∗ gives
R ( S ) ≤ J S ( ( 1 − t ) s ∗ + t s ) ≤ ( 1 − t ) R ( S ) + t J S ( s ) − λ 2 B 2 t ( 1 − t ) ∥ s − s ∗ ∥ D 2 . R(S)\le J_S((1-t)s^*+ts)\le(1-t)R(S)+tJ_S(s)-\frac{\lambda}{2B^2}t(1-t)\lVert s-s^*\rVert_D^2. R ( S ) ≤ J S (( 1 − t ) s ∗ + t s ) ≤ ( 1 − t ) R ( S ) + t J S ( s ) − 2 B 2 λ t ( 1 − t ) ∥ s − s ∗ ∥ D 2 .
In particular,
0 ≤ t ( J S ( s ) − R ( S ) ) − λ 2 B 2 t ( 1 − t ) ∥ s − s ∗ ∥ D 2 . 0 \le t\bigl(J_S(s)-R(S)\bigr)-\frac{\lambda}{2B^2}t(1-t)\lVert s-s^*\rVert_D^2. 0 ≤ t ( J S ( s ) − R ( S ) ) − 2 B 2 λ t ( 1 − t ) ∥ s − s ∗ ∥ D 2 .
J S ( s ) − R ( S ) ≥ λ 2 B 2 ( 1 − t ) ∥ s − s ∗ ∥ D 2 . J_S(s)-R(S)\ge\frac{\lambda}{2B^2}(1-t)\lVert s-s^*\rVert_D^2. J S ( s ) − R ( S ) ≥ 2 B 2 λ ( 1 − t ) ∥ s − s ∗ ∥ D 2 .
Letting t ↓ 0 t \downarrow0 t ↓ 0 and applying the result to s = s ˉ s=\bar{s} s = s ˉ yields
E ∥ s ˉ − s ∗ ∥ D 2 ≤ 2 B 2 λ E [ J S ( s ˉ ) − R ( S ) ] ≤ 2 B 2 ε λ . \mathbb{E}\lVert\bar{s}-s^*\rVert_D^2\le\frac{2B^2}{\lambda}\mathbb{E}\bigl[J_S(\bar{s})-R(S)\bigr]\le\frac{2B^2\varepsilon}{\lambda}. E ∥ s ˉ − s ∗ ∥ D 2 ≤ λ 2 B 2 E [ J S ( s ˉ ) − R ( S ) ] ≤ λ 2 B 2 ε .
Fix the score vector S S S at the start of the round. For a scale s s s and a context x x x , let p a s ( x ) p_a^s(x) p a s ( x ) be the probability that the winning policy predicts action a a a at x x x :
p a s ( x ) = Pr ( W x ( s ) ( x ) = a ) . p_a^s(x)=\Pr\bigl(W_x(s)(x)=a\bigr). p a s ( x ) = Pr ( W x ( s ) ( x ) = a ) .
Here S S S , s s s , and x x x are fixed. The probability is over a fresh Poisson pool and an independent noise vector inserted at x x x . The scale s s s determines the noise multipliers at every pool location and at x x x . Let s ∗ s^* s ∗ minimize J S J_S J S . The ideal strategy plays action a a a at x x x with probability
q a ∗ ( x ) = ( 1 − γ ) p a s ∗ ( x ) + γ K . q_a^*(x)=(1-\gamma)p_a^{s^*}(x)+\frac{\gamma}{K}. q a ∗ ( x ) = ( 1 − γ ) p a s ∗ ( x ) + K γ .
The algorithm instead uses the scale s ˉ \bar{s} s ˉ computed by SGD. After receiving x x x , it holds s ˉ \bar{s} s ˉ and x x x fixed and runs m m m independent trials, each with a fresh pool and a fresh noise vector at x x x . If A k ′ A_k' A k ′ is the winning policy’s action at x x x in trial k k k , then the fraction of trials won by action a a a and its resulting play probability are
p ^ a ( x ) = 1 m ∑ k = 1 m 1 { A k ′ = a } , q ^ a ( x ) = ( 1 − γ ) p ^ a ( x ) + γ K . \hat{p}_a(x)=\frac{1}{m}\sum_{k=1}^{m}\mathbf{1}\{A_k'=a\},\qquad\hat{q}_a(x)=(1-\gamma)\hat{p}_a(x)+\frac{\gamma}{K}. p ^ a ( x ) = m 1 k = 1 ∑ m 1 { A k ′ = a } , q ^ a ( x ) = ( 1 − γ ) p ^ a ( x ) + K γ .
Lemma 15 (Accuracy of the action probabilities before capping). Suppose the algorithm runs with the pool-size cap disabled. For a fresh context x ∼ D x\sim D x ∼ D , its play probabilities satisfy
E [ ∑ a = 1 K ∣ q ^ a ( x ) − q a ∗ ( x ) ∣ ] ≤ 2 B ( n + 1 ) ε 2 λ ⏟ error from using s ˉ + K m ⏟ error from estimating win probabilities . (11) \mathbb{E}\left[\sum_{a=1}^{K}\left|\hat{q}_a(x)-q_a^*(x)\right|\right]\le2B\underbrace{\sqrt{\frac{(n+1)\varepsilon}{2\lambda}}}_{\text{error from using }\bar{s}}+\underbrace{\sqrt{\frac{K}{m}}}_{\text{error from estimating win probabilities}}. \tag*{(11)} E [ a = 1 ∑ K ∣ q ^ a ( x ) − q a ∗ ( x ) ∣ ] ≤ 2 B error from using s ˉ 2 λ ( n + 1 ) ε + error from estimating win probabilities m K . (11) The expectation is over the draws used by SGD to compute s ˉ \bar{s} s ˉ , the independent context x x x , and the m m m trials at that context.
Proof. Fix the incoming score S S S and use uncapped Poisson pools.
Claim 15.1. For any two fixed feasible scales s , t s,t s , t ,
E x ∼ D ∥ p s ( x ) − p t ( x ) ∥ 1 ≤ n + 1 ∥ s − t ∥ D . \mathbb{E}_{x\sim D}\lVert p^s(x)-p^t(x)\rVert_1\le\sqrt{n+1}\lVert s-t\rVert_D. E x ∼ D ∥ p s ( x ) − p t ( x ) ∥ 1 ≤ n + 1 ∥ s − t ∥ D .
Proof. Write X 0 = x X_0=x X 0 = x for the inserted context and X 1 , … , X M X_1,\ldots,X_M X 1 , … , X M for the ordinary pool contexts. Let Q s Q_s Q s be the joint law of M M M , these locations, and the scaled noise coefficients V i , a = s a ( X i ) Z i , a V_{i,a}=s_a(X_i)Z_{i,a} V i , a = s a ( X i ) Z i , a for 0 ≤ i ≤ M 0\le i\le M 0 ≤ i ≤ M and a ∈ [ K ] a\in[K] a ∈ [ K ] . Define Q t Q_t Q t analogously.
We first compare one coefficient. If V ∼ Lap ( u ) V \sim\operatorname{Lap}(u) V ∼ Lap ( u ) , then E ∣ V ∣ = u \mathbb{E}|V| = u E ∣ V ∣ = u , so
KL ( Lap ( u ) ∥ Lap ( v ) ) = E [ log v u + ∣ V ∣ ( 1 v − 1 u ) ] = log ( v / u ) + u / v − 1 ≤ ( u − v ) 2 2 . \operatorname{KL}(\operatorname{Lap}(u)\Vert\operatorname{Lap}(v)) = \mathbb{E}\left[\log\frac{v}{u} + |V|\left(\frac{1}{v} - \frac{1}{u}\right)\right] = \log(v/u) + u/v - 1 \le\frac{(u-v)^2}{2}. KL ( Lap ( u ) ∥ Lap ( v )) = E [ log u v + ∣ V ∣ ( v 1 − u 1 ) ] = log ( v / u ) + u / v − 1 ≤ 2 ( u − v ) 2 .
For the inequality, the expression as a function of u u u has value and derivative zero at u = v u = v u = v , and second derivative 1 / u 2 ≤ 1 1/u^2 \le1 1/ u 2 ≤ 1 on the feasible interval [ 1 , B ] [1,B] [ 1 , B ] .
Under Q s Q_s Q s and Q t Q_t Q t , the count and locations have the same law. Conditional on them, the coefficients are independent. The chain rule for relative entropy therefore gives
KL ( Q s ∥ Q t ) = E ∑ i = 0 M ∑ a = 1 K KL ( Lap ( s a ( X i ) ) ∥ Lap ( t a ( X i ) ) ) ≤ 1 2 E ∑ i = 0 M ∑ a = 1 K ( s a ( X i ) − t a ( X i ) ) 2 = 1 2 ∑ k ≥ 0 Pr ( M = k ) ( k + 1 ) ∥ s − t ∥ D 2 = n + 1 2 ∥ s − t ∥ D 2 . \begin{aligned}
\operatorname{KL}(Q_s\Vert Q_t) = \mathbb{E}\sum_{i=0}^{M}\sum_{a=1}^{K}\operatorname{KL}(\operatorname{Lap}(s_a(X_i))\Vert\operatorname{Lap}(t_a(X_i))) \\
&\le\frac{1}{2}\mathbb{E}\sum_{i=0}^{M}\sum_{a=1}^{K}(s_a(X_i)-t_a(X_i))^2 \\
&= \frac{1}{2}\sum_{k\ge0}\Pr(M=k)(k+1)\lVert s-t\rVert_D^2 = \frac{n+1}{2}\lVert s-t\rVert_D^2.
\end{aligned} KL ( Q s ∥ Q t ) = E i = 0 ∑ M a = 1 ∑ K KL ( Lap ( s a ( X i )) ∥ Lap ( t a ( X i ))) ≤ 2 1 E i = 0 ∑ M a = 1 ∑ K ( s a ( X i ) − t a ( X i ) ) 2 = 2 1 k ≥ 0 ∑ Pr ( M = k ) ( k + 1 ) ∥ s − t ∥ D 2 = 2 n + 1 ∥ s − t ∥ D 2 .
The factor k + 1 k+1 k + 1 counts the inserted context and the k k k ordinary contexts, each drawn from D D D .
Given the locations and coefficients, the same rule under either scale returns ( x , A ) (x,A) ( x , A ) : it maximizes S ( π ) + ∑ i = 0 M V i , π ( X i ) S(\pi) + \sum_{i=0}^{M} V_{i,\pi(X_i)} S ( π ) + ∑ i = 0 M V i , π ( X i ) with the fixed tie-breaking order and returns the winner’s action at x = X 0 x=X_0 x = X 0 . The context marginal is D D D under both scales. Thus, writing Q s x , A Q_s^{x,A} Q s x , A and Q t x , A Q_t^{x,A} Q t x , A for the two resulting laws, the chain rule and data processing give
E x KL ( p s ( x ) ∥ p t ( x ) ) = KL ( Q s x , A ∥ Q t x , A ) ≤ KL ( Q s ∥ Q t ) . \mathbb{E}_x\operatorname{KL}(p^s(x)\Vert p^t(x)) = \operatorname{KL}(Q_s^{x,A}\Vert Q_t^{x,A}) \le\operatorname{KL}(Q_s\Vert Q_t). E x KL ( p s ( x ) ∥ p t ( x )) = KL ( Q s x , A ∥ Q t x , A ) ≤ KL ( Q s ∥ Q t ) .
Applying Pinsker’s inequality at each x x x yields
E x ∥ p s ( x ) − p t ( x ) ∥ 1 ≤ E x ∥ p s ( x ) − p t ( x ) ∥ 1 2 ≤ 2 E x KL ( p s ( x ) ∥ p t ( x ) ) ≤ n + 1 ∥ s − t ∥ D . \mathbb{E}_x\lVert p^s(x)-p^t(x)\rVert_1 \le\sqrt{\mathbb{E}_x\lVert p^s(x)-p^t(x)\rVert_1^2} \le\sqrt{2\mathbb{E}_x\operatorname{KL}(p^s(x)\Vert p^t(x))} \le\sqrt{n+1}\lVert s-t\rVert_D. E x ∥ p s ( x ) − p t ( x ) ∥ 1 ≤ E x ∥ p s ( x ) − p t ( x ) ∥ 1 2 ≤ 2 E x KL ( p s ( x ) ∥ p t ( x )) ≤ n + 1 ∥ s − t ∥ D .
Claim 15.2. Conditional on the learned scale s ˉ \bar{s} s ˉ and the context x x x , the m m m fresh trials satisfy
E [ ∥ p ^ ( x ) − p s ˉ ( x ) ∥ 1 ∣ s ˉ , x ] ≤ K / m . \mathbb{E}\left[\lVert\widehat{p}(x)-p^{\bar{s}}(x)\rVert_1\mid\bar{s},x\right]\le\sqrt{K/m}. E [ ∥ p ( x ) − p s ˉ ( x ) ∥ 1 ∣ s ˉ , x ] ≤ K / m . Proof. Write p a = p a s ˉ ( x ) p_a=p^{\bar{s}}_a(x) p a = p a s ˉ ( x ) . For each a a a , the m m m indicators 1 { A k ′ = a } \mathbf{1}\{A'_k=a\} 1 { A k ′ = a } are conditionally independent Bernoulli variables with mean p a p_a p a . Their average p ^ a ( x ) \widehat{p}_a(x) p a ( x ) therefore satisfies
E [ ( p ^ a ( x ) − p a ) 2 ∣ s ˉ , x ] = p a ( 1 − p a ) m . \mathbb{E}\left[(\widehat{p}_a(x)-p_a)^2\mid\bar{s},x\right]=\frac{p_a(1-p_a)}{m}. E [ ( p a ( x ) − p a ) 2 ∣ s ˉ , x ] = m p a ( 1 − p a ) . By Cauchy–Schwarz and Jensen’s inequality,
E [ ∥ p ^ ( x ) − p ∥ 1 ∣ s ˉ , x ] ≤ K ∑ a = 1 K E [ ( p ^ a ( x ) − p a ) 2 ∣ s ˉ , x ] \mathbb{E}\left[\lVert\widehat{p}(x)-p\rVert_1\mid\bar{s},x\right]\le\sqrt{K\sum_{a=1}^{K}\mathbb{E}\left[(\widehat{p}_a(x)-p_a)^2\mid\bar{s},x\right]} E [ ∥ p ( x ) − p ∥ 1 ∣ s ˉ , x ] ≤ K a = 1 ∑ K E [ ( p a ( x ) − p a ) 2 ∣ s ˉ , x ] = K m ( 1 − ∑ a = 1 K p a 2 ) ≤ K / m . =\sqrt{\frac{K}{m}\left(1-\sum_{a=1}^{K}p_a^2\right)}\le\sqrt{K/m}. = m K ( 1 − a = 1 ∑ K p a 2 ) ≤ K / m .
Since x ∼ D x \sim D x ∼ D is independent of the training draws, we may apply Claim 15.1 conditional on s ˉ \bar{s} s ˉ . Averaging over s ˉ \bar{s} s ˉ and using (10) gives
E ∥ p ˉ s ˉ ( x ) − p s ∗ ( x ) ∥ 1 ≤ ( n + 1 ) E ∥ s ˉ − s ∗ ∥ D 2 ≤ B 2 ( n + 1 ) ε λ . \mathbb{E}\lVert\bar{p}^{\bar{s}}(x)-p^{s^*}(x)\rVert_1 \le\sqrt{(n+1)\mathbb{E}\lVert\bar{s}-s^*\rVert_D^2} \le B\sqrt{\frac{2(n+1)\varepsilon}{\lambda}}. E ∥ p ˉ s ˉ ( x ) − p s ∗ ( x ) ∥ 1 ≤ ( n + 1 ) E ∥ s ˉ − s ∗ ∥ D 2 ≤ B λ 2 ( n + 1 ) ε .
Finally, q ˉ ( x ) − q ∗ ( x ) = ( 1 − γ ) ( p ˉ ( x ) − p s ∗ ( x ) ) \bar{q}(x)-q^*(x)=(1-\gamma)(\bar{p}(x)-p^{s^*}(x)) q ˉ ( x ) − q ∗ ( x ) = ( 1 − γ ) ( p ˉ ( x ) − p s ∗ ( x )) . Inserting p ˉ s ˉ ( x ) \bar{p}^{\bar{s}}(x) p ˉ s ˉ ( x ) and applying Claim 15.2 yields
E ∥ q ˉ ( x ) − q ∗ ( x ) ∥ 1 ≤ ( 1 − γ ) ( E ∥ p ˉ ( x ) − p ˉ s ˉ ( x ) ∥ 1 + E ∥ p ˉ s ˉ ( x ) − p s ∗ ( x ) ∥ 1 ) ≤ K m + 2 B ( n + 1 ) ε 2 λ . \begin{aligned}
\mathbb{E}\lVert\bar{q}(x)-q^*(x)\rVert_1 \le(1-\gamma)\left(\mathbb{E}\lVert\bar{p}(x)-\bar{p}^{\bar{s}}(x)\rVert_1+\mathbb{E}\lVert\bar{p}^{\bar{s}}(x)-p^{s^*}(x)\rVert_1\right) \\
&\le\sqrt{\frac{K}{m}}+2B\sqrt{\frac{(n+1)\varepsilon}{2\lambda}}.
\end{aligned} E ∥ q ˉ ( x ) − q ∗ ( x ) ∥ 1 ≤ ( 1 − γ ) ( E ∥ p ˉ ( x ) − p ˉ s ˉ ( x ) ∥ 1 + E ∥ p ˉ s ˉ ( x ) − p s ∗ ( x ) ∥ 1 ) ≤ m K + 2 B 2 λ ( n + 1 ) ε .
Regret at the actual score
Lemma 16 (Sensitivity to the played probabilities). If q a , r a ≥ γ / K q_a,r_a \ge\gamma/K q a , r a ≥ γ / K for all a a a , then ∣ Φ S , x ( q ) − Φ S , x ( r ) ∣ ≤ ( 1 + K / γ ) ∥ q − r ∥ 1 \lvert\Phi_{S,x}(q)-\Phi_{S,x}(r)\rvert\le(1+K/\gamma)\lVert q-r\rVert_1 ∣ Φ S , x ( q ) − Φ S , x ( r )∣ ≤ ( 1 + K / γ ) ∥ q − r ∥ 1 .
Proof. Fix S S S and x x x . For each action a a a , write f a ( π ) = 1 { π ( x ) = a } f_a(\pi)=1\{\pi(x)=a\} f a ( π ) = 1 { π ( x ) = a } and define
g a ( b ) = R ( S ) − R ( S − b f a ) , b ≥ 0. g_a(b)=R(S)-R(S-bf_a), \qquad b\ge0. g a ( b ) = R ( S ) − R ( S − b f a ) , b ≥ 0.
Thus g a ( b ) g_a(b) g a ( b ) is the decrease in the potential when every policy predicting a a a at x x x receives a score penalty of b b b . We will bound how much the term q a g a ( c a / q a ) q_ag_a(c_a/q_a) q a g a ( c a / q a ) changes when q a q_a q a is replaced by r a r_a r a .
We first verify the properties of g a g_a g a used in this bound. Let s 0 , s 1 s_0,s_1 s 0 , s 1 be minimizing tables at scores S 0 , S 1 S_0,S_1 S 0 , S 1 , respectively. For 0 ≤ t ≤ 1 0\le t\le1 0 ≤ t ≤ 1 , put S t = ( 1 − t ) S 0 + t S 1 S_t=(1-t)S_0+tS_1 S t = ( 1 − t ) S 0 + t S 1 and s t = ( 1 − t ) s 0 + t s 1 s_t=(1-t)s_0+ts_1 s t = ( 1 − t ) s 0 + t s 1 . The table s t s_t s t is feasible. For every fixed pool, linearity of P π P_\pi P π in the table gives
max π [ S t ( π ) + P π ( s t ) ] = max π ( ( 1 − t ) [ S 0 ( π ) + P π ( s 0 ) ] + t [ S 1 ( π ) + P π ( s 1 ) ] ) ≤ ( 1 − t ) max π [ S 0 ( π ) + P π ( s 0 ) ] + t max π [ S 1 ( π ) + P π ( s 1 ) ] . \begin{aligned}
\max_\pi[S_t(\pi)+P_\pi(s_t)]=\max_\pi\left((1-t)[S_0(\pi)+P_\pi(s_0)]+t[S_1(\pi)+P_\pi(s_1)]\right) \\
&\le(1-t)\max_\pi[S_0(\pi)+P_\pi(s_0)]+t\max_\pi[S_1(\pi)+P_\pi(s_1)].
\end{aligned} π max [ S t ( π ) + P π ( s t )] = π max ( ( 1 − t ) [ S 0 ( π ) + P π ( s 0 )] + t [ S 1 ( π ) + P π ( s 1 )] ) ≤ ( 1 − t ) π max [ S 0 ( π ) + P π ( s 0 )] + t π max [ S 1 ( π ) + P π ( s 1 )] .
Taking expectations and using convexity of the log penalty gives
R ( S t ) ≤ J S t ( s t ) ≤ ( 1 − t ) J S 0 ( s 0 ) + t J S 1 ( s 1 ) = ( 1 − t ) R ( S 0 ) + t R ( S 1 ) . R(S_t)\le J_{S_t}(s_t)\le(1-t)J_{S_0}(s_0)+tJ_{S_1}(s_1)=(1-t)R(S_0)+tR(S_1). R ( S t ) ≤ J S t ( s t ) ≤ ( 1 − t ) J S 0 ( s 0 ) + t J S 1 ( s 1 ) = ( 1 − t ) R ( S 0 ) + tR ( S 1 ) .
Thus R R R is convex. Applying this inequality to the scores S − b 0 f a S-b_0f_a S − b 0 f a and S − b 1 f a S-b_1f_a S − b 1 f a gives
g a ( ( 1 − t ) b 0 + t b 1 ) = R ( S ) − R ( ( 1 − t ) ( S − b 0 f a ) + t ( S − b 1 f a ) ) ≥ ( 1 − t ) g a ( b 0 ) + t g a ( b 1 ) . \begin{aligned}
g_a((1-t)b_0+tb_1)=R(S)-R((1-t)(S-b_0f_a)+t(S-b_1f_a)) \\
&\ge(1-t)g_a(b_0)+tg_a(b_1).
\end{aligned} g a (( 1 − t ) b 0 + t b 1 ) = R ( S ) − R (( 1 − t ) ( S − b 0 f a ) + t ( S − b 1 f a )) ≥ ( 1 − t ) g a ( b 0 ) + t g a ( b 1 ) .
The potential is also nondecreasing in each score entry, since increasing a score can only increase the maximum at each fixed table. Adding the same constant to every score shifts every maximum by that constant, so R ( S − b 1 ) = R ( S ) − b R(S-b\mathbf{1})=R(S)-b R ( S − b 1 ) = R ( S ) − b . Since 0 ≤ f a ≤ 1 0\le f_a\le1 0 ≤ f a ≤ 1 ,
R ( S ) − b = R ( S − b 1 ) ≤ R ( S − b f a ) ≤ R ( S ) . R(S)-b=R(S-b\mathbf{1})\le R(S-bf_a)\le R(S). R ( S ) − b = R ( S − b 1 ) ≤ R ( S − b f a ) ≤ R ( S ) .
Hence 0 ≤ g a ( b ) ≤ b 0\le g_a(b)\le b 0 ≤ g a ( b ) ≤ b and g a ( 0 ) = 0 g_a(0)=0 g a ( 0 ) = 0 . Moreover, if b 0 ≤ b 1 b_0\le b_1 b 0 ≤ b 1 , then R ( S − b 1 f a ) ≤ R ( S − b 0 f a ) R(S-b_1f_a)\le R(S-b_0f_a) R ( S − b 1 f a ) ≤ R ( S − b 0 f a ) , so g a ( b 0 ) ≤ g a ( b 1 ) g_a(b_0)\le g_a(b_1) g a ( b 0 ) ≤ g a ( b 1 ) . Now fix one action a a a and two possible probabilities γ / K ≤ s ≤ t \gamma/K \le s \le t γ / K ≤ s ≤ t . Since
c a t = s t c a s + ( 1 − s t ) 0 , \frac{c_a}{t}=\frac{s}{t}\frac{c_a}{s}+\left(1-\frac{s}{t}\right)0, t c a = t s s c a + ( 1 − t s ) 0 ,
concavity and g a ( 0 ) = 0 g_a(0)=0 g a ( 0 ) = 0 give t g a ( c a / t ) ≥ s g a ( c a / s ) t g_a(c_a/t) \ge s g_a(c_a/s) t g a ( c a / t ) ≥ s g a ( c a / s ) . For the reverse bound on their difference, use c a / t ≤ c a / s c_a/t \le c_a/s c a / t ≤ c a / s and monotonicity of g a g_a g a :
0 ≤ t g a ( c a / t ) − s g a ( c a / s ) = ( t − s ) g a ( c a / t ) + s ( g a ( c a / t ) − g a ( c a / s ) ) ≤ ( t − s ) g a ( c a / t ) ≤ ( t − s ) c a t ≤ K γ ( t − s ) . \begin{aligned}
0 &\le t g_a(c_a/t)-s g_a(c_a/s)=(t-s)g_a(c_a/t)+s\bigl(g_a(c_a/t)-g_a(c_a/s)\bigr)\\
&\le(t-s)g_a(c_a/t)\\
&\le(t-s)\frac{c_a}{t}\le\frac{K}{\gamma}(t-s).
\end{aligned} 0 ≤ t g a ( c a / t ) − s g a ( c a / s ) = ( t − s ) g a ( c a / t ) + s ( g a ( c a / t ) − g a ( c a / s ) ) ≤ ( t − s ) g a ( c a / t ) ≤ ( t − s ) t c a ≤ γ K ( t − s ) .
The last inequality uses c a ≤ 1 c_a \le1 c a ≤ 1 and t ≥ γ / K t \ge\gamma/K t ≥ γ / K . Taking s = min { q a , r a } s=\min\{q_a,r_a\} s = min { q a , r a } and t = max { q a , r a } t=\max\{q_a,r_a\} t = max { q a , r a } therefore yields, for every a ∈ [ K ] a \in[K] a ∈ [ K ] ,
∣ q a g a ( c a / q a ) − r a g a ( c a / r a ) ∣ ≤ K γ ∣ q a − r a ∣ . \left|q_a g_a(c_a/q_a)-r_a g_a(c_a/r_a)\right|\le\frac{K}{\gamma}|q_a-r_a|. ∣ q a g a ( c a / q a ) − r a g a ( c a / r a ) ∣ ≤ γ K ∣ q a − r a ∣.
Finally, expand the difference of the two one-round quantities. From Φ S , x ( q ) = q ⋅ c − ∑ a q a g a ( c a / q a ) \Phi_{S,x}(q)=q\cdot c-\sum_a q_a g_a(c_a/q_a) Φ S , x ( q ) = q ⋅ c − ∑ a q a g a ( c a / q a ) , we obtain
∣ Φ S , x ( q ) − Φ S , x ( r ) ∣ = ∣ ∑ a = 1 K ( q a − r a ) c a − ∑ a = 1 K ( q a g a ( c a / q a ) − r a g a ( c a / r a ) ) ∣ ≤ ∑ a = 1 K ∣ q a − r a ∣ c a + ∑ a = 1 K ∣ q a g a ( c a / q a ) − r a g a ( c a / r a ) ∣ ≤ ∑ a = 1 K ∣ q a − r a ∣ + K γ ∑ a = 1 K ∣ q a − r a ∣ = ( 1 + K γ ) ∥ q − r ∥ 1 . \begin{aligned}
\left|\Phi_{S,x}(q)-\Phi_{S,x}(r)\right|
&=\left|\sum_{a=1}^{K}(q_a-r_a)c_a-\sum_{a=1}^{K}\left(q_a g_a(c_a/q_a)-r_a g_a(c_a/r_a)\right)\right|\\
&\le\sum_{a=1}^{K}|q_a-r_a|c_a+\sum_{a=1}^{K}\left|q_a g_a(c_a/q_a)-r_a g_a(c_a/r_a)\right|\\
&\le\sum_{a=1}^{K}|q_a-r_a|+\frac{K}{\gamma}\sum_{a=1}^{K}|q_a-r_a|\\
&=\left(1+\frac{K}{\gamma}\right)\lVert q-r\rVert_1.
\end{aligned} ∣ Φ S , x ( q ) − Φ S , x ( r ) ∣ = a = 1 ∑ K ( q a − r a ) c a − a = 1 ∑ K ( q a g a ( c a / q a ) − r a g a ( c a / r a ) ) ≤ a = 1 ∑ K ∣ q a − r a ∣ c a + a = 1 ∑ K ∣ q a g a ( c a / q a ) − r a g a ( c a / r a ) ∣ ≤ a = 1 ∑ K ∣ q a − r a ∣ + γ K a = 1 ∑ K ∣ q a − r a ∣ = ( 1 + γ K ) ∥ q − r ∥ 1 .
Proof of Theorem 11. Condition on the actual history H t − 1 \mathcal{H}_{t-1} H t − 1 , so the incoming score S S S is fixed. Write Pr t \Pr_t Pr t and E t \mathbb{E}_t E t for probability and expectation conditional on this history. Run the capped and uncapped algorithms with the same context x t x_t x t , pool counts, pool samples, and inserted noise vectors. Let q t q_t q t and q ^ t \widehat{q}_t q t be their respective play probabilities at x t x_t x t .
Let M 1 , … , M J + m M_1,\ldots,M_{J+m} M 1 , … , M J + m be the uncapped pool counts and let E = { max i M i > M max } E=\{\max_i M_i>M_{\max}\} E = { max i M i > M m a x } be the event that the cap is exceeded. For each M i ∼ Poisson ( n ) M_i\sim\operatorname{Poisson}(n) M i ∼ Poisson ( n ) ,
E t [ e M i ] = e − n ∑ k = 0 ∞ ( e n ) k k ! = exp ( ( e − 1 ) n ) . \mathbb{E}_t[e^{M_i}]=e^{-n}\sum_{k=0}^{\infty}\frac{(en)^k}{k!}=\exp((e-1)n). E t [ e M i ] = e − n k = 0 ∑ ∞ k ! ( e n ) k = exp (( e − 1 ) n ) .
By the union bound and Markov’s inequality,
Pr t ( E ) ≤ ∑ i = 1 J + m Pr t ( M i > e M max ) ≤ ( J + m ) exp ( ( e − 1 ) n − M max ) ≤ ( J + m ) exp ( − log 4 ( J + m ) δ ) = δ 4 . \begin{aligned}
\Pr_t(E)&\le\sum_{i=1}^{J+m}\Pr_t(M_i>e^{M_{\max}})\\
&\le(J+m)\exp((e-1)n-M_{\max})\\
&\le(J+m)\exp\left(-\log\frac{4(J+m)}{\delta}\right)=\frac{\delta}{4}.
\end{aligned} t Pr ( E ) ≤ i = 1 ∑ J + m t Pr ( M i > e M m a x ) ≤ ( J + m ) exp (( e − 1 ) n − M m a x ) ≤ ( J + m ) exp ( − log δ 4 ( J + m ) ) = 4 δ .
On E c E^c E c , the two algorithms use exactly the same draws and hence q t = q ^ t q_t = \hat{q}_t q t = q ^ t . On E E E , both outputs are probability vectors, so
∥ q t − q ^ t ∥ 1 ≤ ∑ a = 1 K ( q t , a + q ^ t , a ) = 2. \lVert q_t - \hat{q}_t \rVert_1 \le\sum_{a=1}^{K}(q_{t,a}+\hat{q}_{t,a})=2. ∥ q t − q ^ t ∥ 1 ≤ a = 1 ∑ K ( q t , a + q ^ t , a ) = 2.
Thus the expected error introduced by the cap is
E t ∥ q t − q ^ t ∥ 1 = E t [ 1 { E } ∥ q t − q ^ t ∥ 1 ] ≤ 2 Pr t ( E ) ≤ δ 2 . \mathbb{E}_t\lVert q_t-\hat{q}_t\rVert_1=\mathbb{E}_t[1\{E\}\lVert q_t-\hat{q}_t\rVert_1]\le2\Pr_t(E)\le\frac{\delta}{2}. E t ∥ q t − q ^ t ∥ 1 = E t [ 1 { E } ∥ q t − q ^ t ∥ 1 ] ≤ 2 t Pr ( E ) ≤ 2 δ .
For the uncapped output q ^ t \hat{q}_t q ^ t , Lemma 15 applies under the full Poisson law, including draws on which E E E occurs. Using ε = λ δ 2 / [ 32 B 2 ( n + 1 ) ] \varepsilon=\lambda\delta^2/[32B^2(n+1)] ε = λ δ 2 / [ 32 B 2 ( n + 1 )] and m ≥ 16 K / δ 2 m\ge16K/\delta^2 m ≥ 16 K / δ 2 , we obtain
E t ∥ q ^ t − q ∗ ( x t ) ∥ 1 ≤ 2 B ( n + 1 ) ε 2 λ + K m \mathbb{E}_t\lVert\hat{q}_t-q^*(x_t)\rVert_1\le2B\sqrt{\frac{(n+1)\varepsilon}{2\lambda}}+\sqrt{\frac{K}{m}} E t ∥ q ^ t − q ∗ ( x t ) ∥ 1 ≤ 2 B 2 λ ( n + 1 ) ε + m K
≤ 2 B δ 2 64 B 2 + δ 2 16 = δ 2 . \le2B\sqrt{\frac{\delta^2}{64B^2}}+\sqrt{\frac{\delta^2}{16}}=\frac{\delta}{2}. ≤ 2 B 64 B 2 δ 2 + 16 δ 2 = 2 δ .
Inserting q ^ t \hat{q}_t q ^ t between the actual and ideal play probabilities therefore gives
E t ∥ q t − q ∗ ( x t ) ∥ 1 ≤ E t ∥ q t − q ^ t ∥ 1 + E t ∥ q ^ t − q ∗ ( x t ) ∥ 1 ≤ δ 2 + δ 2 = δ . \mathbb{E}_t\lVert q_t-q^*(x_t)\rVert_1\le\mathbb{E}_t\lVert q_t-\hat{q}_t\rVert_1+\mathbb{E}_t\lVert\hat{q}_t-q^*(x_t)\rVert_1\le\frac{\delta}{2}+\frac{\delta}{2}=\delta. E t ∥ q t − q ∗ ( x t ) ∥ 1 ≤ E t ∥ q t − q ^ t ∥ 1 + E t ∥ q ^ t − q ∗ ( x t ) ∥ 1 ≤ 2 δ + 2 δ = δ .
Every coordinate of q t q_t q t and q ∗ ( x t ) q^*(x_t) q ∗ ( x t ) is at least γ / K \gamma/K γ / K , including on overflow, when q t , a = 1 / K q_{t,a}=1/K q t , a = 1/ K . Applying Lemma 16 at the same context x t x_t x t gives
E t [ Φ S , x t ( q t ) ] ≤ E t [ Φ S , x t ( q ∗ ( x t ) ) ] + ( 1 + K γ ) E t ∥ q t − q ∗ ( x t ) ∥ 1 ≤ E x ∼ D [ Φ S , x ( q ∗ ( x ) ) ] + ( 1 + K γ ) δ = E x ∼ D [ Φ S , x ( q ∗ ( x ) ) ] + 1 T . \begin{aligned}
\mathbb{E}_t[\Phi_{S,x_t}(q_t)]\le\mathbb{E}_t[\Phi_{S,x_t}(q^*(x_t))]+\left(1+\frac{K}{\gamma}\right)\mathbb{E}_t\lVert q_t-q^*(x_t)\rVert_1 \\
&\le\mathbb{E}_{x\sim D}[\Phi_{S,x}(q^*(x))]+\left(1+\frac{K}{\gamma}\right)\delta\\
&=\mathbb{E}_{x\sim D}[\Phi_{S,x}(q^*(x))]+\frac{1}{T}.
\end{aligned} E t [ Φ S , x t ( q t )] ≤ E t [ Φ S , x t ( q ∗ ( x t ))] + ( 1 + γ K ) E t ∥ q t − q ∗ ( x t ) ∥ 1 ≤ E x ∼ D [ Φ S , x ( q ∗ ( x ))] + ( 1 + γ K ) δ = E x ∼ D [ Φ S , x ( q ∗ ( x ))] + T 1 .
The second line uses that x t x_t x t has law D D D conditional on H t − 1 \mathcal{H}_{t-1} H t − 1 , and the last line uses δ = 1 / [ T ( 1 + K / γ ) ] \delta=1/[T(1+K/\gamma)] δ = 1/ [ T ( 1 + K / γ )] . Lemma 13 gives the claimed per-round resource bound. □
Acknowledgments and AI Usage
This work resulted from extensive interaction between the authors and OpenAI Astra, with the authors providing suggestions and critically checking Astra’s responses through iterative exchanges. OpenAI Astra was also used in writing and revising the manuscript through detailed prompts from the authors, with Gemini Argon assisting in some parts. The authors directed the process and evaluated the proposed ideas and arguments. Lean files formalizing the main theorem are available on https://github.com/kbanihashem/bandit-oracle-lean .
The authors thank Suho Shin and Max Springer for their collaboration on earlier work on this problem, which led to the publication of [4 ] and Alex Slivkins for originally suggesting the problem.