Introduction
Imagine going to the casino with a friend. As they decide to try their luck on the slot machines, you sit back and watch, observing them progressively allocate their coins to the machines. Suppose your friend (the learner ) has recently read Bandit Algorithms (Lattimore and Szepesvári, [18 ] ) and can perform a no-regret learning strategy, but you (the observer ) do not know exactly which one. Can you infer their belief on the average rewards of the machines?
We study the problem of learning from a learner (Jacq et al., [15 ] ) in the bandit setting, a variation of the Inverse Bandits (IB) problem (Guo et al., [12 ] ; Guha et al. [11 ] ) that we address under different assumptions and observation models. Guo et al. [12 ] study a white-box setting in which the observer knows the learner’s internal decision mechanism exactly and uses it explicitly to form estimates of the true mean rewards, that are recoverable only up to a constant due to the unidentifiability of inverse problems (Russell, [28 ] ). In contrast, we propose a formulation that relaxes the white-box assumption. Specifically, we assume that the demonstrator belongs to a broad family of randomized, no-regret bandit algorithms, and that the observer has access to the realized action sequence, with neither knowledge of the exact policy that generated it nor of the rewards associated with the played actions. However, we assume that the observer can form an estimate of the demonstrator’s sampling probability. Under this structured grey-box assumption we target the learner’s internal beliefs about the means, which may not coincide with the true means (Halder et al., [13 ] ). This shift is deliberate: these beliefs govern the behavior of a demonstrator that is still learning and, without additional information, are the only reward-related quantities that can be learned from its actions. Even if the beliefs on the rewards are biased, a second learner can leverage them to construct a better policy for the same task, in the spirit of “better than the demonstrator” approaches (Brown et al., [4 ] ).
We focus on randomized algorithms, which implicitly or explicitly sample arms at each round from a distribution that depends on an internal estimate of the mean rewards and the learner’s uncertainty. The most prominent such algorithm is Thompson Sampling (TS) (Thompson, [32 ] ; Russo et al. [29 ] ), which pulls arms according to the probability that their mean reward is larger than all others, what Menet et al. [22 ] call Probability of Maximality (PoM). In TS, the sampling probability is implicit via an indirect posterior sampling mechanism, making it difficult to recover the belief parameter in closed form from the sampling distribution.
Our first contribution is a general class of randomized bandit algorithms whose sampling probabilities admit a closed-form relationship with their internal mean estimates. Building on the Linear-Time Independence-based Estimator (LITE) of Menet et al. [22 ] , in Section 2.2 we introduce v-LITE Sampling (v-LS), which turns the LITE estimator into a sampling rule. Under suitable assumptions, we provide regret bounds for v v v
Our second contribution is an inversion method for this class of learners. In Section 4, we show how the demonstrator’s sampling probabilities can be inverted to recover its internal gap estimates. We derive inversion-error bounds when the sampling probabilities are available only through estimates, including under batched observations. To move beyond exactly specified v v v v v v
Preliminaries
A stochastic bandit instance (Lattimore and Szepesvári [18 ] ) is defined as a collection of reward distributions ν = ( ν a : a ∈ [ K ] ) \nu= (\nu_a : a \in[K]) ν = ( ν a : a ∈ [ K ]) [ K ] : = { 1 , 2 , … , K } [K] := \{1, 2, \ldots, K\} [ K ] := { 1 , 2 , … , K } α 2 \alpha^2 α 2 ν a = N ( θ a , α 2 ) \nu_a = \mathcal{N}(\theta_a, \alpha^2) ν a = N ( θ a , α 2 ) θ a : = E R ∼ ν a [ R ] \theta_a := \mathbb{E}_{R\sim\nu_a}[R] θ a := E R ∼ ν a [ R ] θ = ( θ 1 , … , θ K ) \theta= (\theta_1, \ldots, \theta_K) θ = ( θ 1 , … , θ K ) θ \theta θ
The learner interacts with the environment over a horizon of T T T t t t a t ∈ [ K ] a_t \in[K] a t ∈ [ K ] r t ∼ ν a t r_t \sim\nu_{a_t} r t ∼ ν a t
Define N a ( t ) : = ∑ j = 1 t 1 { a j = a } N_a(t) := \sum_{j=1}^{t} \mathbb{1}\{a_j = a\} N a ( t ) := ∑ j = 1 t 1 { a j = a } a a a t t t a ∗ : = arg max a ∈ [ K ] θ a a^* := \arg\max_{a\in[K]} \theta_a a ∗ := arg max a ∈ [ K ] θ a
A learning algorithm is said to be no-regret if its cumulative regret, E [ ∑ t = 1 T θ a ∗ − θ a t ] \mathbb{E}[\sum_{t=1}^{T}\theta_{a^*}-\theta_{a_t}] E [ ∑ t = 1 T θ a ∗ − θ a t ] T T T Upper Confidence Bound (UCB) ([2 , 30 ] ) and TS ([32 , 29 ] ).
Throughout the paper, we use the terms learner and demonstrator interchangeably to refer to the online learning algorithm that sequentially selects actions, observes their rewards, and aims to minimize regret relative to the best arm. The observer , by contrast, has access only to the resulting action trajectory { a t } t = 1 T \{a_t\}_{t=1}^{T} { a t } t = 1 T
TS and the Probability of Maximality
TS ([32 , 1 , 29 ] ) is a Bayesian algorithm for sequential decision-making that balances exploration and exploitation through posterior sampling. While being arguably the oldest strategy for bandit play, it has remained popular, e.g., enabling analysis of coding agents ([23 ] ) or improving robustness of LLM post-training ([24 ] ). In TS, the learner maintains a posterior distribution p t p_t p t ( θ a ) a ∈ [ K ] (\theta_a)_{a\in[K]} ( θ a ) a ∈ [ K ] t t t Z t ∼ p t Z_t \sim p_t Z t ∼ p t
a t = arg max a ∈ [ K ] Z a , t (1) a_t = \arg\max_{a\in[K]} Z_{a,t} \tag*{(1)} a t = arg a ∈ [ K ] max Z a , t (1) observes the associated reward r t ∼ ν a t r_t \sim\nu_{a_t} r t ∼ ν a t θ ∼ N ( μ 0 , Σ 0 ) \theta\sim\mathcal{N}(\mu_0,\Sigma_0) θ ∼ N ( μ 0 , Σ 0 ) α 2 \alpha^2 α 2 a t = a a_t = a a t = a N ( μ t + 1 , Σ t + 1 ) \mathcal{N}(\mu_{t+1},\Sigma_{t+1}) N ( μ t + 1 , Σ t + 1 ) H t ∈ R K × K H_t \in\mathbb{R}^{K\times K} H t ∈ R K × K [ H t ] a , a = N a ( t ) [H_t]_{a,a} = N_a(t) [ H t ] a , a = N a ( t )
Σ t + 1 = ( Σ 0 − 1 + α − 2 H t ) − 1 , (2) \Sigma_{t+1} = \left(\Sigma_0^{-1} + \alpha^{-2}H_t\right)^{-1}, \tag*{(2)} Σ t + 1 = ( Σ 0 − 1 + α − 2 H t ) − 1 , (2) μ t + 1 = Σ t + 1 ( Σ 0 − 1 μ 0 + α − 2 ∑ s = 1 t r s e a s ) , (3) \mu_{t+1} = \Sigma_{t+1}\left(\Sigma_0^{-1}\mu_0 + \alpha^{-2}\sum_{s=1}^{t} r_s e_{a_s}\right), \tag*{(3)} μ t + 1 = Σ t + 1 ( Σ 0 − 1 μ 0 + α − 2 s = 1 ∑ t r s e a s ) , (3) where e a e_a e a s s s N ( μ a , t , σ a , t 2 ) \mathcal{N}(\mu_{a,t},\sigma_{a,t}^2) N ( μ a , t , σ a , t 2 ) μ a , t = [ μ t ] a \mu_{a,t} = [\mu_t]_a μ a , t = [ μ t ] a σ a , t 2 = [ Σ t ] a , a \sigma_{a,t}^2 = [\Sigma_t]_{a,a} σ a , t 2 = [ Σ t ] a , a Σ t \Sigma_t Σ t σ a , t \sigma_{a,t} σ a , t (2) ). In contrast, μ t \mu_t μ t r s r_s r s (3) ), which is observable to the learner but not to the inverse learner.
The randomized mechanism of (1) was originally designed by Thompson [32 ] to approximate the likelihood that one arm’s mean reward is larger than those of all other arms, the so called Probability of Maximality (PoM). Indeed, it can be shown1 identity of the optimal arm coincides exactly with that of the action chosen by TS:
P ( arg max b ∈ [ K ] θ b = ⋅ ∣ F t − 1 ) = P ( a t = ⋅ ∣ F t − 1 ) \mathbb{P}\left(\arg\max_{b\in[K]}\theta_b = \mathord{\cdot}\mid\mathcal{F}_{t-1}\right) = \mathbb{P}\left(a_t = \mathord{\cdot}\mid\mathcal{F}_{t-1}\right) P ( arg b ∈ [ K ] max θ b = ⋅ ∣ F t − 1 ) = P ( a t = ⋅ ∣ F t − 1 ) where F t − 1 \mathcal{F}_{t-1} F t − 1 t − 1 t-1 t − 1
LITE sampling
Although the TS mechanism already provides samples from the PoM, direct access to it opens up new possibilities such as Entropy Search [14 , 22 ] , Bayes-optimal batch selection [7 , 22 ] , policies for zero-sum two-player games [26 ] , and scaling up Thompson sampling via fine-tuning of LLMs [25 ] .
Therefore, we introduce a family of algorithms whose sampling probability is directly connected to the PoM.
Definition 2.1 (v v v v : R → ( 0 , 1 ) v:\mathbb{R}\to(0,1) v : R → ( 0 , 1 ) μ a ∈ R , σ a > 0 \mu_a\in\mathbb{R},\sigma_a>0 μ a ∈ R , σ a > 0 a ∈ [ K ] a\in[K] a ∈ [ K ] v v v q q q
q a : = v ( μ a − κ ∗ σ a ) ∀ a ∈ [ K ] , (4) q_a := v\left(\frac{\mu_a-\kappa^*}{\sigma_a}\right)\quad\forall a\in[K], \tag*{(4)} q a := v ( σ a μ a − κ ∗ ) ∀ a ∈ [ K ] , (4) where the threshold κ ∗ ∈ R \kappa^*\in\mathbb{R} κ ∗ ∈ R ∑ a = 1 K q a = 1 \sum_{a=1}^{K}q_a=1 ∑ a = 1 K q a = 1
Given that this approximate PoM (q t q_t q t κ ∗ \kappa^* κ ∗ [22 ] , a natural approximation to TS is a randomized algorithm that samples arms directly according to v v v
Definition 2.2 (v v v v v v t t t v v v q a , t q_{a,t} q a , t ( μ a , t , σ a , t ) (\mu_{a,t},\sigma_{a,t}) ( μ a , t , σ a , t ) θ a \theta_a θ a v v v a t ∼ Cat ( q t ) a_t\sim\operatorname{Cat}(q_t) a t ∼ Cat ( q t )
The v v v
VBOS: Setting v ( x ) = Ψ ( x ) : = exp ( − ( x 2 + 4 − x ) 2 / 8 ) v(x)=\Psi(x):=\exp\left(-(\sqrt{x^2+4}-x)^2/8\right) v ( x ) = Ψ ( x ) := exp ( − ( x 2 + 4 − x ) 2 /8 ) [26 , 31 , 25 ] .
F-LITE: Setting v = Φ v=\Phi v = Φ Φ \Phi Φ [22 ] . F-LITE is a highly accurate TS approximation derived using extreme value theory, though no-regret guarantees are not established for bandit play under Φ \Phi Φ
v v v θ \theta θ v ( x ) = Ψ ( x ) v(x)=\Psi(x) v ( x ) = Ψ ( x ) O ~ ( T K ) \widetilde{O}(\sqrt{TK}) O ( T K ) [31 ] .
In the correlated Gaussian setting, this improves to O ~ ( T γ T ) \widetilde{O}(\sqrt{T\gamma_T}) O ( T γ T ) [25 ] , where γ T \gamma_T γ T [30 ] and scales as O ( d log T ) O(d\log T) O ( d log T ) d d d v v v v v v
Problem Formulation
We consider a randomized no-regret algorithm A \mathcal{A} A t t t A \mathcal{A} A a t ∼ p t a_t\sim p_t a t ∼ p t F t − 1 \mathcal{F}_{t-1} F t − 1
The observer has access to the complete action trajectory { a t } t = 1 T \{a_t\}_{t=1}^{T} { a t } t = 1 T p ^ t \hat{p}_t p ^ t p t p_t p t p ^ t \hat{p}_t p ^ t
Access to p ^ t \hat{p}_t p ^ t p t p_t p t
Objective. Our goal is to recover the internal gap estimates that drive the demonstrator’s behavior, focusing on the rounds during which it is still actively exploring. Because the observer does not observe rewards, it cannot identify the true optimal arm. We therefore use the empirically most-pulled arm as an observable reference: a ^ ∗ : = arg max a N a ( T ) \hat{a}^*:=\arg\max_a N_a(T) a ^ ∗ := arg max a N a ( T ) a ∈ [ K ] a\in[K] a ∈ [ K ] t ≤ T t\leq T t ≤ T a ^ ∗ \hat{a}^* a ^ ∗
Δ a , t A = μ a ^ ∗ , t − μ a , t , (5) \Delta^A_{a,t}=\mu_{\hat{a}^*,t}-\mu_{a,t}, \tag*{(5)} Δ a , t A = μ a ^ ∗ , t − μ a , t , (5) where μ a , t \mu_{a,t} μ a , t a a a t t t a ^ ∗ \hat{a}^* a ^ ∗
Once the demonstrator concentrates its play on a single arm, its behavior becomes near-deterministic and therefore contains little information about the magnitude of the remaining gaps: many different internal gap values induce essentially the same near-deterministic behavior. In that regime, continued inversion is neither statistically stable nor necessary for explaining the demonstrator’s decisions. To reflect this, we restrict inversion to a set of relevant rounds, M T γ M_T^\gamma M T γ
Definition 3.1 (Relevant Rounds). For a fixed threshold γ ∈ ( 0 , 1 / 2 ) \gamma\in(0,1/2) γ ∈ ( 0 , 1/2 ) t ≤ T t \le T t ≤ T M T γ M_T^\gamma M T γ a t ≠ a ^ ∗ a_t \ne\hat{a}^* a t = a ^ ∗ p a t , t ≥ γ p_{a_t,t} \ge\gamma p a t , t ≥ γ p a ^ ∗ , t ≥ γ p_{\hat{a}^*,t} \ge\gamma p a ^ ∗ , t ≥ γ a t a_t a t a ^ ∗ \hat{a}^* a ^ ∗
This set depends on the demonstrator and the generated trajectory, with more details in § 4.2 and Appendix § 8 .§ 1 . Using the concept of relevant rounds for inversion, we define the trajectory-level inversion error as follows:
Definition 3.2 (Trajectory-Level Inversion Error). The trajectory-level decision-relevant inversion error is defined as the average gap reconstruction error on relevant rounds over the entire time horizon:
E T γ : = 1 T ∑ t = 1 T 1 { t ∈ M T γ } ∣ Δ ^ a t , t − Δ a t , t A ∣ . (6) \mathcal{E}_T^\gamma:= \frac{1}{T}\sum_{t=1}^{T} \mathbf{1}\{t \in M_T^\gamma\} \left|\widehat{\Delta}_{a_t,t} - \Delta^A_{a_t,t}\right|. \tag*{(6)} E T γ := T 1 t = 1 ∑ T 1 { t ∈ M T γ } Δ a t , t − Δ a t , t A . (6) where Δ ^ a t , t \widehat{\Delta}_{a_t,t} Δ a t , t a t a_t a t t t t
This objective can be interpreted as follows. Define the realized relevant coverage as
C T γ : = ∣ M T γ ∣ T , (7) C_T^\gamma:= \frac{|M_T^\gamma|}{T}, \tag*{(7)} C T γ := T ∣ M T γ ∣ , (7) and the average reconstruction error over relevant rounds as
L T γ : = 1 max { ∣ M T γ ∣ , 1 } ∑ t = 1 T 1 { t ∈ M T γ } ∣ Δ ^ a t , t − Δ a t , t A ∣ . (8) L_T^\gamma:= \frac{1}{\max\{|M_T^\gamma|,1\}}\sum_{t=1}^{T} \mathbf{1}\{t \in M_T^\gamma\}\left|\widehat{\Delta}_{a_t,t} - \Delta^A_{a_t,t}\right|. \tag*{(8)} L T γ := max { ∣ M T γ ∣ , 1 } 1 t = 1 ∑ T 1 { t ∈ M T γ } Δ a t , t − Δ a t , t A . (8) Hence,
E T γ = C T γ L T γ , \mathcal{E}_T^\gamma= C_T^\gamma L_T^\gamma, E T γ = C T γ L T γ , is a coverage-weighted error. Importantly, C T γ C_T^\gamma C T γ E T γ \mathcal{E}_T^\gamma E T γ
Coverage may decrease as the demonstrator concentrates on a ^ ∗ \hat{a}^* a ^ ∗ a t = a ^ ∗ a_t = \hat{a}^* a t = a ^ ∗ a ^ ∗ \hat{a}^* a ^ ∗
Related work Our demonstrator-focused metric (6) deliberately departs from standard Inverse Bandits (IB) ([12 ] ), which seek to recover the true underlying means θ ^ a \hat{\theta}_a θ ^ a [12 ] , reconstructing θ ^ a \hat{\theta}_a θ ^ a
E [ ∣ θ ^ a − θ a ∣ ] ≥ 1 16 min { 1 E [ N a ( T ) ] , 1 } . \mathbb{E}[|\hat{\theta}_a-\theta_a|] \ge\frac{1}{16}\min\left\{\frac{1}{\sqrt{\mathbb{E}[N_a(T)]}},1\right\}. E [ ∣ θ ^ a − θ a ∣ ] ≥ 16 1 min { E [ N a ( T )] 1 , 1 } . For standard no-regret demonstrators, where a suboptimal arm is pulled only O ( log T ) O(\log T) O ( log T ) Ω ( 1 / log T ) \Omega(1/\sqrt{\log T}) Ω ( 1/ log T ) [12 ] provide nearly matching estimators for parameterized UCB ([2 , 30 ] ) and successive-arm-elimination ([6 ] ) demonstrators. Although the logarithmic-regret case remains consistent, achieving a polynomially decreasing estimation error requires deliberately inflated exploration, resulting in O ( T α ) O(T^\alpha) O ( T α ) α > 0 \alpha> 0 α > 0 § 4.2 ).
iLITE: Inverting LS
We start by illustrating the idea of our method in an idealized setting to build intuition.
Inversion in an idealized setting
We define ν \nu ν Definition 2.2 ) as our reference demonstrator . Under the additional assumptions below, we show that it can be perfectly inverted; we relax these assumptions in subsequent sections.
Assumption 4.1. The demonstrator is exactly ν \nu ν
Assumption 4.2. At each time t t t q t q_t q t (4) ) of the demonstrator, i.e., a t ∼ Cat ( q t ) a_t \sim\operatorname{Cat}(q_t) a t ∼ Cat ( q t )
Assumption 4.3. The observer knows the initial prior covariance Σ 0 \Sigma_0 Σ 0 α 2 \alpha^2 α 2
The sampling probability q t q_t q t
z a , t : = ν − 1 ( q a , t ) = μ a , t − κ t ∗ σ a , t . (9) z_{a,t} := \nu^{-1}(q_{a,t}) = \frac{\mu_{a,t}-\kappa^*_{t}}{\sigma_{a,t}}. \tag*{(9)} z a , t := ν − 1 ( q a , t ) = σ a , t μ a , t − κ t ∗ . (9) As a result, it holds that
μ a , t = z a , t σ a , t + κ t ∗ , (10) \mu_{a,t}=z_{a,t}\sigma_{a,t}+\kappa^*_{t}, \tag*{(10)} μ a , t = z a , t σ a , t + κ t ∗ , (10) where σ a , t 2 \sigma_{a,t}^2 σ a , t 2 a a a t t t t t t (2) . Even if κ t ∗ \kappa^*_t κ t ∗ q t q_t q t Δ a , t A \Delta^A_{a,t} Δ a , t A (5) ) w.r.t. the most-pulled arm a ^ ∗ : = arg max a N a ( T ) \hat{a}^* := \arg\max_a N_a(T) a ^ ∗ := arg max a N a ( T )
Δ ^ a , t = Δ a , t A : = z a ^ ∗ , t σ a ^ ∗ , t − z a , t σ a , t . (11) \widehat{\Delta}_{a,t}=\Delta^A_{a,t}:=z_{\hat{a}^*,t}\sigma_{\hat{a}^*,t}-z_{a,t}\sigma_{a,t}. \tag*{(11)} Δ a , t = Δ a , t A := z a ^ ∗ , t σ a ^ ∗ , t − z a , t σ a , t . (11) In this idealized setting, E T γ = 0 ∀ γ ∈ ( 0 , 1 ) \mathcal{E}^{\gamma}_{T}=0\ \forall\ \gamma\in(0,1) E T γ = 0 ∀ γ ∈ ( 0 , 1 )
Approximate iLITE
This perfect inversion relies on two major assumptions: the learner is exactly the reference demonstrator (Assumption 4.1), and its sampling probabilities are known without approximations (Assumption 4.2). In the following subsections, we relax these two assumptions. The proofs of this section are deferred to Appendix § 10 .
PoM estimated
We first retain Assumption 4.1 but relax Assumption 4.2. The observer now has access only to estimates q ^ t \hat{q}_t q ^ t ν \nu ν q t q_t q t η > 0 \eta>0 η > 0
G η : = { max t ∈ [ T ] max a ∈ [ K ] ∣ q ^ a , t − q a , t ∣ ≤ η } . (12) \mathcal{G}_{\eta}:=\left\{\max_{t\in[T]}\max_{a\in[K]}\left|\hat{q}_{a,t}-q_{a,t}\right|\leq\eta\right\}. \tag*{(12)} G η := { t ∈ [ T ] max a ∈ [ K ] max ∣ q ^ a , t − q a , t ∣ ≤ η } . (12) Conditioned on this event occuring, we bound the inversion error E T γ \mathcal{E}^{\gamma}_{T} E T γ (6) in terms of η \eta η q ^ t \hat{q}_t q ^ t P ( G η ) ≥ 1 − δ \mathbb{P}(\mathcal{G}_{\eta})\geq1-\delta P ( G η ) ≥ 1 − δ
On G η \mathcal{G}_{\eta} G η
Δ ^ a , t = z ^ a ∗ , t σ a ∗ , t − z ^ a , t σ a , t , z ^ a , t : = ν − 1 ( q ^ a , t ) . (13) \hat{\Delta}_{a,t}=\hat{z}_{a^{*},t}\sigma_{a^{*},t}-\hat{z}_{a,t}\sigma_{a,t},\qquad\hat{z}_{a,t}:=\nu^{-1}(\hat{q}_{a,t}). \tag*{(13)} Δ ^ a , t = z ^ a ∗ , t σ a ∗ , t − z ^ a , t σ a , t , z ^ a , t := ν − 1 ( q ^ a , t ) . (13) where the variances σ a , t 2 \sigma^2_{a,t} σ a , t 2
The oracle relevance set M T γ M^{\gamma}_{T} M T γ Definition 3.1 depends on the unknown probabilities q t q_t q t ρ > 0 \rho>0 ρ > 0
M ^ T ρ : = { t ∈ [ T ] : a t ≠ a ^ ∗ , q ^ a t , t ≥ ρ , q ^ a ^ ∗ , t ≥ ρ } . (14) \widehat{M}^{\rho}_{T}:=\{t\in[T]:a_t\ne\hat{a}^{*},\ \hat{q}_{a_t,t}\geq\rho,\ \hat{q}_{\hat{a}^{*},t}\geq\rho\}. \tag*{(14)} M T ρ := { t ∈ [ T ] : a t = a ^ ∗ , q ^ a t , t ≥ ρ , q ^ a ^ ∗ , t ≥ ρ } . (14) On G η \mathcal{G}_{\eta} G η
M ^ T γ + η ⊆ M T γ ⊆ M ^ T γ − η . (15) \widehat{M}^{\gamma+\eta}_{T}\subseteq M^{\gamma}_{T}\subseteq\widehat{M}^{\gamma-\eta}_{T}. \tag*{(15)} M T γ + η ⊆ M T γ ⊆ M T γ − η . (15) Thus, by computing gap estimates on M ^ T γ − η \widehat{M}^{\gamma-\eta}_{T} M T γ − η E T γ \mathcal{E}^{\gamma}_{T} E T γ M T γ M^{\gamma}_{T} M T γ
Restricting inversion to relevant rounds is necessary because ν − 1 \nu^{-1} ν − 1 ( 0 , 1 ) (0,1) ( 0 , 1 ) ∣ ( ν − 1 ) ′ ( u ) ∣ \left|(\nu^{-1})'(u)\right| ( ν − 1 ) ′ ( u ) u u u 0 0 0 1 1 1 § 8 .§ 1 for a detailed illustration of this non-Lipschitz behavior.
Therefore, we restrict gap recovery to a domain where ν − 1 \nu^{-1} ν − 1
c β : = sup u ∈ [ β , 1 − β ] ∣ ( ν − 1 ) ′ ( u ) ∣ , where β ∈ ( 0 , 1 / 2 ) . (16) c_{\beta}:=\sup_{u\in[\beta,1-\beta]}\left|(\nu^{-1})'(u)\right|,\qquad\text{where }\beta\in(0,1/2). \tag*{(16)} c β := u ∈ [ β , 1 − β ] sup ( ν − 1 ) ′ ( u ) , where β ∈ ( 0 , 1/2 ) . (16) In particular, if t ∈ M ^ T γ − η t\in\widehat{M}^{\gamma-\eta}_{T} t ∈ M T γ − η j ∈ { a t , a ^ ∗ } j\in\{a_t,\hat{a}^{*}\} j ∈ { a t , a ^ ∗ } q ^ j , t ∈ [ γ − η , 1 − γ + η ] \hat{q}_{j,t}\in[\gamma-\eta,1-\gamma+\eta] q ^ j , t ∈ [ γ − η , 1 − γ + η ] G η \mathcal{G}_{\eta} G η q j , t , q ^ j , t ∈ [ γ − 2 η , 1 − γ + 2 η ] q_{j,t},\hat{q}_{j,t}\in[\gamma-2\eta,1-\gamma+2\eta] q j , t , q ^ j , t ∈ [ γ − 2 η , 1 − γ + 2 η ] β = γ − 2 η \beta=\gamma-2\eta β = γ − 2 η
In Algorithm 1, we set ρ = γ − η \rho=\gamma-\eta ρ = γ − η M ^ T ρ \widehat{M}^{\rho}_{T} M T ρ M T γ M^{\gamma}_{T} M T γ G η \mathcal{G}_{\eta} G η
Table 1.
The following lemma quantifies how an error in the estimated sampling probabilities propagates through the inverse map ν − 1 \nu^{-1} ν − 1
Lemma 4.1. Let 0 < η < ρ ≤ 1 / 2 0<\eta<\rho\leq1/2 0 < η < ρ ≤ 1/2 t ∈ M ^ T ρ t\in\widehat{M}^{\rho}_{T} t ∈ M T ρ G η \mathcal{G}_{\eta} G η
∣ Δ ^ a t , t − Δ a t , t γ ∣ ≤ ( ∣ σ a ∗ , t ∣ + ∣ σ a t , t ∣ ) c ρ − η η . (17) \left|\hat{\Delta}_{a_t,t}-\Delta^{\gamma}_{a_t,t}\right|\leq\left(|\sigma_{a^{*},t}|+|\sigma_{a_t,t}|\right)c_{\rho-\eta}\eta. \tag*{(17)} Δ ^ a t , t − Δ a t , t γ ≤ ( ∣ σ a ∗ , t ∣ + ∣ σ a t , t ∣ ) c ρ − η η . (17) where c ρ − η c_{\rho-\eta} c ρ − η ν − 1 \nu^{-1} ν − 1 [ ρ − η , 1 − ρ + η ] [\rho-\eta,1-\rho+\eta] [ ρ − η , 1 − ρ + η ] (16) .
Aggregating the local error over the relevant rounds gives the following trajectory-level guarantee:
Theorem 4.1. Assume that A A A σ a , 0 2 ≤ 1 \sigma^2_{a,0}\leq1 σ a , 0 2 ≤ 1 a ∈ [ K ] a\in[K] a ∈ [ K ] 0 < 2 η < γ ≤ 1 / 2 0<2\eta<\gamma\leq1/2 0 < 2 η < γ ≤ 1/2 G η \mathcal{G}_{\eta} G η
E T γ ≤ c γ − 2 η ⋅ η ( ( α 2 + 1 ) γ T + 2 α T + t ∗ + 1 T ) . (18) \mathcal{E}^{\gamma}_{T}\leq c_{\gamma-2\eta}\cdot\eta\left(\frac{(\alpha\sqrt{2}+1)\sqrt{\gamma^{T}}+2\alpha}{\sqrt{T}}+\frac{t^{*}+1}{T}\right). \tag*{(18)} E T γ ≤ c γ − 2 η ⋅ η ( T ( α 2 + 1 ) γ T + 2 α + T t ∗ + 1 ) . (18) Here, c γ − 2 η c_{\gamma-2\eta} c γ − 2 η ν − 1 \nu^{-1} ν − 1 [ γ − 2 η , 1 − γ + 2 η ] [\gamma-2\eta,1-\gamma+2\eta] [ γ − 2 η , 1 − γ + 2 η ] (16) , γ T \gamma^{T} γ T 2 ^{2} 2 t ∗ : = ∑ a ≠ a ∗ N a ( T ) t^{*}:=\sum_{a\ne a^{*}}N_a(T) t ∗ := ∑ a = a ∗ N a ( T )
Consequently, if P ( G η ) ≥ 1 − δ \mathbb{P}(\mathcal{G}_{\eta}) \ge1-\delta P ( G η ) ≥ 1 − δ (29) holds with probability at least 1 − δ 1-\delta 1 − δ G η \mathcal{G}_{\eta} G η
Corollary 4.1. Under the assumptions of Theorem 4.1, if G η \mathcal{G}_{\eta} G η
E [ E T γ ] ≤ c γ − 2 η ⋅ η ( ( α 2 + 1 ) γ T + 2 α T + E [ t ∗ ] + 1 T ) . \mathbb{E}[\mathcal{E}^{\gamma}_{T}] \le c_{\gamma-2\eta}\cdot\eta\left(\frac{(\alpha\sqrt{2}+1)\sqrt{\gamma_T}+2\alpha}{\sqrt{T}}+\frac{\mathbb{E}[t^*]+1}{T}\right). E [ E T γ ] ≤ c γ − 2 η ⋅ η ( T ( α 2 + 1 ) γ T + 2 α + T E [ t ∗ ] + 1 ) . The bound separates two sources of error. The factor c γ − 2 η η c_{\gamma-2\eta}\eta c γ − 2 η η v − 1 v^{-1} v − 1 γ T / T \sqrt{\gamma_T/T} γ T / T t ∗ / T t^*/T t ∗ / T γ T ∈ O ( d log T ) \gamma_T \in O(d\log T) γ T ∈ O ( d log T ) d d d
To relate E [ t ∗ ] / T \mathbb{E}[t^*]/T E [ t ∗ ] / T a ∗ a^* a ∗ Δ min : = min a ≠ a ∗ ( θ a ∗ − θ a ) > 0 \Delta_{\min}:=\min_{a\ne a^*}(\theta_{a^*}-\theta_a)>0 Δ m i n := min a = a ∗ ( θ a ∗ − θ a ) > 0
S T : = ∑ a ≠ a ∗ N a ( T ) S_T := \sum_{a\ne a^*}N_a(T) S T := a = a ∗ ∑ N a ( T ) be the total number of suboptimal pulls. Then t ∗ ≤ S T t^*\le S_T t ∗ ≤ S T a ^ ∗ = a ∗ \hat{a}^*=a^* a ^ ∗ = a ∗ N a ^ ∗ ( T ) ≥ N a ∗ ( T ) N_{\hat{a}^*}(T)\ge N_{a^*}(T) N a ^ ∗ ( T ) ≥ N a ∗ ( T ) a ^ ∗ \hat{a}^* a ^ ∗
t ∗ = N a ∗ ( T ) + S T − N a ^ ∗ ( T ) ≤ S T . t^*=N_{a^*}(T)+S_T-N_{\hat{a}^*}(T)\le S_T. t ∗ = N a ∗ ( T ) + S T − N a ^ ∗ ( T ) ≤ S T . Therefore, if the demonstrator has expected regret bounded by R ( T ) R(T) R ( T )
E [ t ∗ ] ≤ E [ S T ] ≤ R ( T ) Δ min . (19) \mathbb{E}[t^*]\le\mathbb{E}[S_T]\le\frac{R(T)}{\Delta_{\min}}. \tag*{(19)} E [ t ∗ ] ≤ E [ S T ] ≤ Δ m i n R ( T ) . (19) Thus, for any v v v v v v R ( T ) ∈ o ( T ) R(T)\in o(T) R ( T ) ∈ o ( T ) E [ t ∗ ] / T \mathbb{E}[t^*]/T E [ t ∗ ] / T
Batched Bandit Inversion The preceding result is agnostic to how q ^ t \hat{q}_t q ^ t q t ( ϕ ) q_t(\phi) q t ( ϕ ) ϕ \phi ϕ q t q_t q t
A simpler and widely used in practice alternative arises under batched play, where the sampling distribution remains fixed within each batch and can therefore be estimated directly from empirical action frequencies (Kalkanli and Ozgur, 2021). We focus on this setting.
We introduce a batched version of v v v
Suppose that n n n T T T B = T / n B=T/n B = T / n n n n b ∈ [ B ] b\in[B] b ∈ [ B ] v v v q b q_b q b
a b , 1 , … , a b , n ∣ F ( b − 1 ) n ∼ i . i . d . Cat ( q b ) , a_{b,1},\ldots,a_{b,n}\mid\mathcal{F}_{(b-1)n}\mathrel{\overset{\mathrm{i.i.d.}}{\sim}}\operatorname{Cat}(q_b), a b , 1 , … , a b , n ∣ F ( b − 1 ) n ∼ i.i.d. Cat ( q b ) , and updates its posterior using the n n n q b q_b q b b b b n n n Cat ( q b ) \operatorname{Cat}(q_b) Cat ( q b )
q ^ a , b : = 1 n ∑ j = 1 n 1 { a b , j = a } , a ∈ [ K ] . (20) \hat{q}_{a,b}:=\frac{1}{n}\sum_{j=1}^{n}\mathbf{1}\{a_{b,j}=a\},\qquad a\in[K]. \tag*{(20)} q ^ a , b := n 1 j = 1 ∑ n 1 { a b , j = a } , a ∈ [ K ] . (20) After the batch has been observed, the same estimate q ^ b \hat{q}_b q ^ b q ^ t \hat{q}_t q ^ t t t t b b b
Using Hoeffding’s inequality together with a union bound, the next result provides an approximation guarantee that holds uniformly over all arms and batches.
Lemma 4.2. For any δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 )
η n , δ : = log ( 2 K B / δ ) 2 n . (21) \eta_{n,\delta}:=\sqrt{\frac{\log(2KB/\delta)}{2n}}. \tag*{(21)} η n , δ := 2 n log ( 2 K B / δ ) . (21) Then
P ( max b ∈ [ B ] max a ∈ [ K ] ∣ q ^ a , b − q a , b ∣ ≤ η n , δ ) ≥ 1 − δ . (22) \mathbb{P}\left(\max_{b\in[B]}\max_{a\in[K]}|\hat{q}_{a,b}-q_{a,b}|\le\eta_{n,\delta}\right)\ge1-\delta. \tag*{(22)} P ( b ∈ [ B ] max a ∈ [ K ] max ∣ q ^ a , b − q a , b ∣ ≤ η n , δ ) ≥ 1 − δ . (22) Define the uniform approximation event
G n , δ : = { max b ∈ [ B ] max a ∈ [ K ] ∣ q ^ a , b − q a , b ∣ ≤ η n , δ } . (23) \mathcal{G}_{n,\delta}:=\left\{\max_{b\in[B]}\max_{a\in[K]}|\hat{q}_{a,b}-q_{a,b}|\le\eta_{n,\delta}\right\}. \tag*{(23)} G n , δ := { b ∈ [ B ] max a ∈ [ K ] max ∣ q ^ a , b − q a , b ∣ ≤ η n , δ } . (23) Combining Lemma 4.2 with the local stability of the inverse map gives a trajectory-level guarantee.
Theorem 4.2. Let A A A v v v σ a , 0 2 ≤ 1 \sigma_{a,0}^{2}\le1 σ a , 0 2 ≤ 1 a ∈ [ K ] a\in[K] a ∈ [ K ] α 2 \alpha^2 α 2 0 < 2 η n , δ < γ ≤ 1 / 2 0<2\eta_{n,\delta}<\gamma\le1/2 0 < 2 η n , δ < γ ≤ 1/2 G n , δ \mathcal{G}_{n,\delta} G n , δ
E T γ ≤ c γ − 2 η n , δ ⋅ η n , δ [ ( α 2 + n ) γ B + 2 α T + t ∗ + n ( 1 + B α ) T ] . (24) \mathcal{E}^{\gamma}_{T}\le c_{\gamma-2\eta_{n,\delta}}\cdot\eta_{n,\delta}\left[\frac{(\alpha\sqrt{2}+\sqrt{n})\sqrt{\gamma B}+2\alpha}{\sqrt{T}}+\frac{t^*+n(1+B\alpha)}{T}\right]. \tag*{(24)} E T γ ≤ c γ − 2 η n , δ ⋅ η n , δ [ T ( α 2 + n ) γ B + 2 α + T t ∗ + n ( 1 + B α ) ] . (24) Here, B α : = min { 1 , α } B_\alpha:= \min\{1,\alpha\} B α := min { 1 , α } γ B \gamma_B γ B c γ − 2 η n , δ c_{\gamma-2\eta_{n,\delta}} c γ − 2 η n , δ (16) , and t ∗ : = ∑ a ≠ a ^ ∗ N a ( T ) t^* := \sum_{a\ne\hat{a}^*}N_a(T) t ∗ := ∑ a = a ^ ∗ N a ( T ) 1 − δ 1-\delta 1 − δ
The bound reveals a trade-off in the batch size n n n η n , δ ∈ O ( n − 1 / 2 ) \eta_{n,\delta} \in O(n^{-1/2}) η n , δ ∈ O ( n − 1/2 ) n \sqrt{n} n n / T n/T n / T
(,)-LS-family
We relax Assumption 4.1 to allow demonstrators that differ from the reference v v v t ∈ M T t \in\mathcal{M}_T t ∈ M T
∣ Δ ^ a t , t − Δ a t , t A ∣ ≤ ∣ Δ ^ a t , t − Δ a t , t L S ∣ + ∣ Δ a t , t L S − Δ a t , t A ∣ . (25) \left|\widehat{\Delta}_{a_t,t}-\Delta^A_{a_t,t}\right| \le\left|\widehat{\Delta}_{a_t,t}-\Delta^{LS}_{a_t,t}\right|+\left|\Delta^{LS}_{a_t,t}-\Delta^A_{a_t,t}\right|. \tag*{(25)} Δ a t , t − Δ a t , t A ≤ Δ a t , t − Δ a t , t L S + Δ a t , t L S − Δ a t , t A . (25) The two terms capture, respectively, inversion error relative to the reference and discrepancy between the internal gaps of the reference and actual demonstrators. To quantify these discrepancies we introduce the following definitions.
Definition 4.1 (Gap mismatch). Let A \mathcal{A} A F t − 1 \mathcal{F}_{t-1} F t − 1
ε g a p ( A ; T ) : = max t ∈ [ T ] ∣ Δ a t , t L S − Δ a t , t A ∣ . \varepsilon_{\mathrm{gap}}(\mathcal{A};T):=\max_{t\in[T]}\left|\Delta^{LS}_{a_t,t}-\Delta^A_{a_t,t}\right|. ε gap ( A ; T ) := t ∈ [ T ] max Δ a t , t L S − Δ a t , t A . Definition 4.2 (Sampling-policy mismatch). Let p t p_t p t A \mathcal{A} A q t q_t q t F t − 1 \mathcal{F}_{t-1} F t − 1
ε p o l ( A ; T ) : = max t ≤ T max a ∈ [ K ] ∣ p a , t − q a , t ∣ . \varepsilon_{\mathrm{pol}}(\mathcal{A};T):=\max_{t\le T}\max_{a\in[K]}|p_{a,t}-q_{a,t}|. ε pol ( A ; T ) := t ≤ T max a ∈ [ K ] max ∣ p a , t − q a , t ∣. Since p a , t , q a , t ∈ [ 0 , 1 ] p_{a,t},q_{a,t}\in[0,1] p a , t , q a , t ∈ [ 0 , 1 ] ε p o l ( A ; T ) ∈ [ 0 , 1 ] \varepsilon_{\mathrm{pol}}(\mathcal{A};T)\in[0,1] ε pol ( A ; T ) ∈ [ 0 , 1 ] A \mathcal{A} A
Definition 4.3 ((ε , ε ~ \varepsilon,\tilde{\varepsilon} ε , ε ~ A \mathcal{A} A ( ε , ε ~ ) (\varepsilon,\tilde{\varepsilon}) ( ε , ε ~ )
ε p o l ( A ; T ) ≤ ε and ε g a p ( A ; T ) ≤ ε ~ . \varepsilon_{\mathrm{pol}}(\mathcal{A};T)\le\varepsilon
\qquad\text{and}\qquad
\varepsilon_{\mathrm{gap}}(\mathcal{A};T)\le\tilde{\varepsilon}. ε pol ( A ; T ) ≤ ε and ε gap ( A ; T ) ≤ ε ~ . These families are nested in both tolerances. The choices ε = 0 \varepsilon=0 ε = 0 ε ~ = 0 \tilde{\varepsilon}=0 ε ~ = 0 ε = 1 \varepsilon=1 ε = 1
Conditional on the same realized history, the gap mismatch ε ~ \tilde{\varepsilon} ε ~
Gaussian prior and posterior-update rule as the reference learner. This includes TS and other posterior-based acquisition rules such as EI [16 ] , ES [21 ] , and MES [33 ] . Consequently, TS belongs to an ( ε , 0 ) (\varepsilon,0) ( ε , 0 ) ε \varepsilon ε v v v
Theorem 4.3. Assume that A \mathcal{A} A ( ε , ε ~ ) (\varepsilon,\tilde{\varepsilon}) ( ε , ε ~ ) 0 < 2 ε < γ ≤ 1 / 2 0<2\varepsilon<\gamma\le1/2 0 < 2 ε < γ ≤ 1/2 v v v
ε T γ ≤ c γ − 2 ε ε ( ( α 2 + 1 ) γ T + 2 α T + t ∗ + 1 T ) + ε ~ . (26) \varepsilon_T^\gamma\le c_{\gamma-2\varepsilon}\varepsilon\left(\frac{(\alpha\sqrt{2}+1)\sqrt{\gamma_T}+2\alpha}{\sqrt{T}}+\frac{t^*+1}{T}\right)+\tilde{\varepsilon}. \tag*{(26)} ε T γ ≤ c γ − 2 ε ε ( T ( α 2 + 1 ) γ T + 2 α + T t ∗ + 1 ) + ε ~ . (26) Here, c γ − 2 ε c_{\gamma-2\varepsilon} c γ − 2 ε (16) , evaluated at γ − 2 ε \gamma-2\varepsilon γ − 2 ε γ T \gamma_T γ T t ∗ : = ∑ a ≠ a ^ ∗ N a ( T ) t^*:=\sum_{a\ne\hat{a}^*}N_a(T) t ∗ := ∑ a = a ^ ∗ N a ( T )
When only estimates { p ^ t } t = 1 T \{\hat{p}_t\}_{t=1}^T { p ^ t } t = 1 T
Experiments We empirically investigate the two sources of inversion error predicted by our analysis: the sampling probability estimation and the reference policy misspecification. Additional experiments are deferred to Appendix D, where we also analyze misspecification of the prior Σ 0 \Sigma_0 Σ 0
We use K = 4 K=4 K = 4 ( 0 , 1 / 3 , 2 / 3 , 1 ) (0,1/3,2/3,1) ( 0 , 1/3 , 2/3 , 1 ) α 2 = 1 \alpha^2=1 α 2 = 1 N ( 0 , 1 ) \mathcal{N}(0,1) N ( 0 , 1 )
Batched probability estimation. We use batched Ψ \Psi Ψ q q q q q q T = 20000 T=20000 T = 20000
Figure 1 illustrates the two effects predicted by our analysis. Increasing γ \gamma γ n n n c γ − 2 η c_{\gamma-2\eta} c γ − 2 η c γ c_\gamma c γ c γ − 2 η η c_{\gamma-2\eta}\eta c γ − 2 η η n n n
Figure 1. Batched Ψ \Psi Ψ n ∈ { 500 , 1000 , 2000 } n \in\{500,1000,2000\} n ∈ { 500 , 1000 , 2000 } η \eta η c γ c_\gamma c γ c γ − 2 η c_{\gamma-2\eta} c γ − 2 η c γ − 2 η η c_{\gamma-2\eta}\eta c γ − 2 η η L ^ T γ − η \widehat{L}^{\gamma-\eta}_T L T γ − η E ^ T γ − η \widehat{E}^{\gamma-\eta}_T E T γ − η M ^ T γ − η \widehat{M}^{\gamma-\eta}_T M T γ − η ∣ M ^ T γ − η ∖ M ^ T γ ∣ / T |\widehat{M}^{\gamma-\eta}_T \setminus\widehat{M}^{\gamma}_T|/T ∣ M T γ − η ∖ M T γ ∣/ T 2 η < γ 2\eta< \gamma 2 η < γ
Figure 2. End-to-end inversion for v = Ψ v=\Psi v = Ψ K = 4 K=4 K = 4 T = 2000 T=2000 T = 2000 γ = 0.4 \gamma=0.4 γ = 0.4 L t γ L^\gamma_t L t γ E t γ E^\gamma_t E t γ B t = ∑ s = 1 t 1 { A s = a ^ ∗ } B_t=\sum_{s=1}^{t}\mathbb{1}\{A_s=\hat{a}^*\} B t = ∑ s = 1 t 1 { A s = a ^ ∗ } 1 − B t / t 1-B_t/t 1 − B t / t ∣ M t γ ∣ / t |M^\gamma_t|/t ∣ M t γ ∣/ t
End-to-end inversion. Finally, we invert TS, Maillard sampling (MS) [20 , 3 ] , and Boltzmann-Gumbel exploration (BGE) [5 ] using their exact sampling probabilities at γ = 0.4 \gamma=0.4 γ = 0.4 T = 2000 T=2000 T = 2000 Ψ \Psi Ψ 2 ε < γ 2\varepsilon<\gamma 2 ε < γ Φ \Phi Φ Ψ − 1 \Psi^{-1} Ψ − 1
The middle panel displays the start-learn-converge behavior described by Garivier et al. [9 ] . Initially, the algorithms distribute pulls across the arms; during learning, alternative pulls remain frequent and the relevance set grows; finally, the algorithms concentrate on a ^ ∗ \hat{a}^* a ^ ∗ 1 − B t / t 1-B_t/t 1 − B t / t ∣ M t γ ∣ / t |M^\gamma_t|/t ∣ M t γ ∣/ t E t γ E^\gamma_t E t γ Φ \Phi Φ v v v ε \varepsilon ε ε ^ \hat{\varepsilon} ε ^
Conclusion
We introduce an inverse-bandit framework for recovering a demonstrator’s internal suboptimality gaps rather than the environment’s true rewards. We define the invertible v v v ( ε , ε ^ ) (\varepsilon,\hat{\varepsilon}) ( ε , ε ^ )
Our results expose an intrinsic exploration-inversion trade-off. While the demonstrator explores, its sampling probabilities reveal its internal gaps; as its policy concentrates, different gap magnitudes produce nearly identical behavior, making stable inversion impossible. This limitation is inherent to the information contained in the action trajectory and reflected in the coverage C T γ C^\gamma_T C T γ
Limitations and future work. Future work includes exploiting temporal continuity between rounds, which could enable probability estimation under weaker observation protocols. We empirically show one possibility in Appendix D.3. Other directions include extending the framework to other structured policies, such as KL-UCB variants [8 ] , and studying its privacy implications. In particular, recovered gaps may reveal sensitive preferences of the users, connecting algorithm inversion to differential privacy [27 ] remains an open question.
Acknowledgments
C. Vernade is funded by the Deutsche Forschungsgemeinschaft (DFG) under both the project 468806714 of the Emmy Noether Programme and under Germany’s Excellence Strategy – EXC number 2064/1 – Project number 390727645. CV also gratefully acknowledges funding from the European Union (ERC, ConSequen-tIAL, 101165883). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them). CV and M. Petriconi also thank the international Max Planck Research School for Intelligent Systems (IMPRS-IS).
Appendix
Stability of inverting v v v
Because v v v v − 1 ( q ) → − ∞ v^{-1}(q) \to-\infty v − 1 ( q ) → − ∞ q ↓ 0 q \downarrow0 q ↓ 0 v − 1 ( q ) → ∞ v^{-1}(q) \to\infty v − 1 ( q ) → ∞ q ↑ 1 q \uparrow1 q ↑ 1 v − 1 v^{-1} v − 1 ( 0 , 1 ) (0,1) ( 0 , 1 ) v v v v ′ ( x ) > 0 v'(x) > 0 v ′ ( x ) > 0 v ′ ( x ) → 0 v'(x) \to0 v ′ ( x ) → 0 x → ± ∞ x \to\pm\infty x → ± ∞
( v − 1 ) ′ ( q ) = 1 v ′ ( v − 1 ( q ) ) , (v^{-1})'(q) = \frac{1}{v'(v^{-1}(q))}, ( v − 1 ) ′ ( q ) = v ′ ( v − 1 ( q )) 1 , and therefore ∣ ( v − 1 ) ′ ( q ) ∣ → ∞ |(v^{-1})'(q)| \to\infty ∣ ( v − 1 ) ′ ( q ) ∣ → ∞ q ↓ 0 q \downarrow0 q ↓ 0 q ↑ 1 q \uparrow1 q ↑ 1
In the context of inverse bandits, the external observer only has access to an empirical estimate q ^ \hat q q ^ q q q q ^ \hat q q ^ q q q q q q v − 1 ( q ) v^{-1}(q) v − 1 ( q ) Figure 3 . The inverse mapping is
Figure 3. Error amplification under inversion for two reference CDFs, v = Φ v = \Phi v = Φ v = Ψ v = \Psi v = Ψ ∣ q ^ − q ∣ < η |\hat q-q| < \eta ∣ q ^ − q ∣ < η ( γ , 1 − γ ) (\gamma,1-\gamma) ( γ , 1 − γ )
nevertheless well-conditioned on every compact subinterval of ( 0 , 1 ) (0,1) ( 0 , 1 ) γ ∈ ( 0 , 1 ) \gamma\in(0,1) γ ∈ ( 0 , 1 ) v − 1 v^{-1} v − 1 η \eta η
c γ − 2 η : = sup q ∈ [ γ − 2 η , 1 − γ + 2 η ] ∣ ( v − 1 ) ′ ( q ) ∣ < ∞ . (27) c_{\gamma-2\eta} := \sup_{q \in[\gamma-2\eta,1-\gamma+2\eta]} |(v^{-1})'(q)| < \infty. \tag*{(27)} c γ − 2 η := q ∈ [ γ − 2 η , 1 − γ + 2 η ] sup ∣ ( v − 1 ) ′ ( q ) ∣ < ∞. (27) By the mean value theorem, the inversion error is then bounded linearly by the estimation error:
∣ v − 1 ( q ^ ) − v − 1 ( q ) ∣ ≤ c γ − 2 η ∣ q ^ − q ∣ . |v^{-1}(\hat q)-v^{-1}(q)| \le c_{\gamma-2\eta}|\hat q-q|. ∣ v − 1 ( q ^ ) − v − 1 ( q ) ∣ ≤ c γ − 2 η ∣ q ^ − q ∣. This Lipschitz-type control motivates restricting the inversion to the set of relevant rounds M T γ M^\gamma_T M T γ [ γ , 1 − γ ] [\gamma,1-\gamma] [ γ , 1 − γ ] ∣ M T γ ∣ |M^\gamma_T| ∣ M T γ ∣ M T γ M^\gamma_T M T γ
It suffices to verify the lower bounds q a t , t , q a ^ ∗ , t ≥ γ q_{a_t,t},q_{\hat a^*,t} \ge\gamma q a t , t , q a ^ ∗ , t ≥ γ a t ≠ a ^ ∗ a_t \ne\hat a^* a t = a ^ ∗ q a t , t , q a ^ ∗ , t ≤ 1 − γ q_{a_t,t},q_{\hat a^*,t} \le1-\gamma q a t , t , q a ^ ∗ , t ≤ 1 − γ γ ∈ ( 0 , 1 / 2 ) \gamma\in(0,1/2) γ ∈ ( 0 , 1/2 ) q a t , t , q a ^ ∗ , t ≥ γ q_{a_t,t},q_{\hat a^*,t} \ge\gamma q a t , t , q a ^ ∗ , t ≥ γ γ > 1 / 2 \gamma> 1/2 γ > 1/2
Generalized LITE sampling
While the main text focuses on the Gaussian reward setting, where the posterior uncertainties σ \sigma σ [22 ] to arbitrary arm distributions is a central secondary contribution of this paper. Many real-world applications rely on reward distributions that are non-Gaussian: click-through rates are Bernoulli, waiting times are Exponential, and clinical outcomes can follow heavy-tailed distributions. To invert demonstrators operating in these settings, we first formalize a generic sampling strategy that is both no-regret and invertible for arbitrary reward posteriors. The key idea is to characterize the tail behavior of the marginal reward posteriors through a reference CDF v v v
To this end, let v v v conditional tail expectation functional g v : ( 0 , 1 ) → R g_v : (0,1) \to\mathbb{R} g v : ( 0 , 1 ) → R
g v ( p ) : = E [ Z ∣ Z > v − 1 ( p ) ] ⋅ P [ Z > v − 1 ( p ) ] = ∫ p 1 v − 1 ( r ) d r g_v(p) := \mathbb{E}[Z \mid Z > v^{-1}(p)] \cdot\mathbb{P}[Z > v^{-1}(p)] = \int_p^1 v^{-1}(r)\,dr g v ( p ) := E [ Z ∣ Z > v − 1 ( p )] ⋅ P [ Z > v − 1 ( p )] = ∫ p 1 v − 1 ( r ) d r Moreover, for E [ Z ] ∈ [ 0 , ∞ ) \mathbb{E}[Z] \in[0,\infty) E [ Z ] ∈ [ 0 , ∞ ) g v ( p ) ∈ [ 0 , ∞ ) ∀ p g_v(p) \in[0,\infty) \ \forall p g v ( p ) ∈ [ 0 , ∞ ) ∀ p
The associated quasi-surprisal i v : ( 0 , 1 ) → [ 0 , ∞ ) i_v : (0,1) \to[0,\infty) i v : ( 0 , 1 ) → [ 0 , ∞ )
i v ( p ) : = 1 2 ( g v ( p ) p ) 2 . i_v(p) := \frac{1}{2}\left(\frac{g_v(p)}{p}\right)^2. i v ( p ) := 2 1 ( p g v ( p ) ) 2 . The quasi-surprisal measures how aggressively the tail of v v v i v i_v i v p p p v v v θ \theta θ v v v
The following proposition makes this precise. It shows that if the posterior’s Cramér rate function dominates the quasi-surprisal induced by v v v H v ( q ) : = ∑ a q a i v ( q a ) H_v(q) := \sum_a q_a i_v(q_a) H v ( q ) := ∑ a q a i v ( q a ) adapted quasi-entropy , which bounds the total exploration penalty of the randomized policy.
Definition B.1. The (Cramér) rate function Λ ∗ \Lambda^* Λ ∗ X : Ω → R X : \Omega\to\mathbb{R} X : Ω → R Λ \Lambda Λ
Λ ∗ ( α ) : = sup β > 0 α β − Λ ( β ) where Λ ( β ) : = log E [ e β ( X − E [ X ] ) ] . \Lambda^*(\alpha) := \sup_{\beta>0} \alpha\beta- \Lambda(\beta) \quad\text{where} \quad\Lambda(\beta) := \log\mathbb{E}\left[e^{\beta(X-\mathbb{E}[X])}\right]. Λ ∗ ( α ) := β > 0 sup α β − Λ ( β ) where Λ ( β ) := log E [ e β ( X − E [ X ]) ] . Proposition B.1. Let θ t : Ω → R K \theta_t : \Omega\to\mathbb{R}^K θ t : Ω → R K ( Λ θ t ∗ ) − 1 ( − ln p ) ≤ σ a , t 2 i v ( p ) (\Lambda^*_{\theta_t})^{-1}(-\ln p) \le\sigma_{a,t}\sqrt{2i_v(p)} ( Λ θ t ∗ ) − 1 ( − ln p ) ≤ σ a , t 2 i v ( p ) p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) q t q_t q t v v v t t t a t ∼ q t a_t \sim q_t a t ∼ q t H v ( q ) : = ∑ a ∈ [ K ] q a i v ( q a ) ≤ sup q ∈ Δ K H v ( q ) = : I v ( K ) < ∞ H_v(q) := \sum_{a \in[K]} q_a i_v(q_a) \le\sup_{q \in\Delta^K} H_v(q) =: I_v(K) < \infty H v ( q ) := ∑ a ∈ [ K ] q a i v ( q a ) ≤ sup q ∈ Δ K H v ( q ) =: I v ( K ) < ∞ V T V_T V T E [ ∑ t = 1 T σ a t , t 2 ] ≤ V T \mathbb{E}\left[\sum_{t=1}^T \sigma_{a_t,t}^2\right] \le V_T E [ ∑ t = 1 T σ a t , t 2 ] ≤ V T
Reg ( T ) = ∑ t E [ max a θ a , t − θ a t , t ] ≤ ∑ t E a ∼ q t [ σ a , t 2 i v ( q a , t ) ] ≤ 2 I v ( K ) T V T . \operatorname{Reg}(T) = \sum_t \mathbb{E}[\max_a \theta_{a,t} - \theta_{a_t,t}]
\le\sum_t \mathbb{E}_{a \sim q_t}[\sigma_{a,t}\sqrt{2i_v(q_{a,t})}]
\le\sqrt{2I_v(K)T V_T}. Reg ( T ) = t ∑ E [ a max θ a , t − θ a t , t ] ≤ t ∑ E a ∼ q t [ σ a , t 2 i v ( q a , t ) ] ≤ 2 I v ( K ) T V T . Proof of Proposition B.1. The first inequality follows immediately from Lemma C.4:
∑ t = 1 T E [ max a θ a , t − θ a t , t ] ≤ ∑ t = 1 T E [ V ( q t ) − ∑ a = 1 K q a , t μ a , t ] = ∑ t = 1 T E [ ∑ a = 1 K q a , t σ a , t 2 i v ( q a , t ) ] . \sum_{t=1}^T \mathbb{E}[\max_a \theta_{a,t} - \theta_{a_t,t}]
\le\sum_{t=1}^T \mathbb{E}\left[\mathcal{V}(q_t) - \sum_{a=1}^K q_{a,t}\mu_{a,t}\right]
= \sum_{t=1}^T \mathbb{E}\left[\sum_{a=1}^K q_{a,t}\sigma_{a,t}\sqrt{2i_v(q_{a,t})}\right]. t = 1 ∑ T E [ a max θ a , t − θ a t , t ] ≤ t = 1 ∑ T E [ V ( q t ) − a = 1 ∑ K q a , t μ a , t ] = t = 1 ∑ T E [ a = 1 ∑ K q a , t σ a , t 2 i v ( q a , t ) ] . For the second inequality, we apply the Cauchy–Schwarz inequality first over the arms, then over the time steps:
∑ t = 1 T ∑ a = 1 K q a , t σ a , t 2 i v ( q a , t ) ≤ ∑ t = 1 T ∑ a = 1 K 2 q a , t i v ( q a , t ) ∑ a = 1 K q a , t σ a , t 2 ≤ 2 I v ( K ) ∑ t = 1 T ∑ a = 1 K q a , t σ a , t 2 ≤ 2 I v ( K ) T ∑ t = 1 T ∑ a = 1 K q a , t σ a , t 2 . \begin{aligned}
\sum_{t=1}^T \sum_{a=1}^K q_{a,t}\sigma_{a,t}\sqrt{2i_v(q_{a,t})}
\le\sum_{t=1}^T \sqrt{\sum_{a=1}^K 2q_{a,t}i_v(q_{a,t})}\sqrt{\sum_{a=1}^K q_{a,t}\sigma_{a,t}^2} \\
&\le\sqrt{2I_v(K)}\sum_{t=1}^T \sqrt{\sum_{a=1}^K q_{a,t}\sigma_{a,t}^2} \\
&\le\sqrt{2I_v(K)}\sqrt{T}\sqrt{\sum_{t=1}^T\sum_{a=1}^K q_{a,t}\sigma_{a,t}^2}.
\end{aligned} t = 1 ∑ T a = 1 ∑ K q a , t σ a , t 2 i v ( q a , t ) ≤ t = 1 ∑ T a = 1 ∑ K 2 q a , t i v ( q a , t ) a = 1 ∑ K q a , t σ a , t 2 ≤ 2 I v ( K ) t = 1 ∑ T a = 1 ∑ K q a , t σ a , t 2 ≤ 2 I v ( K ) T t = 1 ∑ T a = 1 ∑ K q a , t σ a , t 2 . Taking the expectation over the trajectory and applying Jensen’s inequality alongside the assumption on the cumulative variance yields:
E [ 2 I v ( K ) T ∑ t = 1 T ∑ a = 1 K q a , t σ a , t 2 ] ≤ 2 I v ( K ) T E [ ∑ t = 1 T ∑ a = 1 K q a , t σ a , t 2 ] = 2 I v ( K ) T E [ ∑ t = 1 T σ a t , t 2 ] ≤ 2 I v ( K ) T V T . \mathbb{E}\left[\sqrt{2I_v(K)T\sum_{t=1}^{T}\sum_{a=1}^{K}q_{a,t}\sigma_{a,t}^{2}}\right]\leq\sqrt{2I_v(K)T\mathbb{E}\left[\sum_{t=1}^{T}\sum_{a=1}^{K}q_{a,t}\sigma_{a,t}^{2}\right]}=\sqrt{2I_v(K)T\mathbb{E}\left[\sum_{t=1}^{T}\sigma_{a_t,t}^{2}\right]}\leq\sqrt{2I_v(K)TV_T}. E 2 I v ( K ) T t = 1 ∑ T a = 1 ∑ K q a , t σ a , t 2 ≤ 2 I v ( K ) T E [ t = 1 ∑ T a = 1 ∑ K q a , t σ a , t 2 ] = 2 I v ( K ) T E [ t = 1 ∑ T σ a t , t 2 ] ≤ 2 I v ( K ) T V T . In practical deployments, including large-scale A/B tests and federated learning systems, updating the posterior after every observation is often computationally prohibitive or impossible due to delayed feedback pipelines. Batched algorithms address this by freezing the sampling policy over windows of n n n
Theorem B.1 (Batched LS regret). Assume that v v v H v ( q ) : = ∑ a ∈ [ K ] q a v ( q a ) ≤ sup q ∈ Δ K H v ( q ) = : I v ( K ) < ∞ H_v(q) := \sum_{a\in[K]}q_av(q_a) \leq\sup_{q\in\Delta_K}H_v(q) =: I_v(K) < \infty H v ( q ) := ∑ a ∈ [ K ] q a v ( q a ) ≤ sup q ∈ Δ K H v ( q ) =: I v ( K ) < ∞ α 2 \alpha^2 α 2 v v v n n n T = n B T=nB T = n B
Reg ( T ) ≤ 2 I v ( K ) T n C ( n , α ) γ B , \operatorname{Reg}(T)\leq2\sqrt{I_v(K)T\frac{n}{C(n,\alpha)}}\gamma_B, Reg ( T ) ≤ 2 I v ( K ) T C ( n , α ) n γ B , where C ( n , α ) = ln ( 1 + n / α 2 ) C(n,\alpha)=\ln(1+n/\alpha^2) C ( n , α ) = ln ( 1 + n / α 2 ) γ B \gamma_B γ B B B B
Remark B.1. For v = Ψ v=\Psi v = Ψ I Ψ ( K ) ≤ log ( K ) I_\Psi(K)\leq\log(K) I Ψ ( K ) ≤ log ( K ) O ( T γ B n C ( n , α ) log K ) O\left(\sqrt{T\gamma_B\frac{n}{C(n,\alpha)}\log K}\right) O ( T γ B C ( n , α ) n log K ) n / ln ( 1 + n / α 2 ) n/\ln(1+n/\alpha^2) n / ln ( 1 + n / α 2 ) n n n n = 1 n=1 n = 1
Proof of Theorem B.1. Since batched v v v q b q_b q b σ a , b \sigma_{a,b} σ a , b a i , b a_{i,b} a i , b i i i b b b Lemma C.4 , applied with the posterior at the start of batch b b b
Reg ( T ) = ∑ b = 1 B ∑ i = 1 n E [ max a θ a − θ a i , b ] ≤ ∑ b = 1 B ∑ i = 1 n E a i , b ∼ q b [ σ a i , b , b 2 i v ( q b ( a i , b ) ) ] . \operatorname{Reg}(T)=\sum_{b=1}^{B}\sum_{i=1}^{n}\mathbb{E}\left[\max_a\theta_a-\theta_{a_{i,b}}\right]\leq\sum_{b=1}^{B}\sum_{i=1}^{n}\mathbb{E}_{a_{i,b}\sim q_b}\left[\sigma_{a_{i,b},b}\sqrt{2i_v(q_b(a_{i,b}))}\right]. Reg ( T ) = b = 1 ∑ B i = 1 ∑ n E [ a max θ a − θ a i , b ] ≤ b = 1 ∑ B i = 1 ∑ n E a i , b ∼ q b [ σ a i , b , b 2 i v ( q b ( a i , b )) ] . This is identical in structure to the first inequality in the proof of Proposition B.1. Applying the same double Cauchy–Schwarz argument (first over arms within each batch, then over batches) yields
Reg ( T ) ≤ 2 I v ( K ) T E [ ∑ b = 1 B ∑ i = 1 n σ a i , b , b 2 ] . \operatorname{Reg}(T)\leq\sqrt{2I_v(K)T\mathbb{E}\left[\sum_{b=1}^{B}\sum_{i=1}^{n}\sigma_{a_{i,b},b}^{2}\right]}. Reg ( T ) ≤ 2 I v ( K ) T E [ b = 1 ∑ B i = 1 ∑ n σ a i , b , b 2 ] . Under the Gaussian prior and Gaussian noise assumptions, ∑ i = 1 n σ a i , b , b 2 = tr ( Σ b ( X 1 : b ) ) \sum_{i=1}^{n}\sigma_{a_{i,b},b}^{2}=\operatorname{tr}(\Sigma_b(X_{1:b})) ∑ i = 1 n σ a i , b , b 2 = tr ( Σ b ( X 1 : b )) Σ b ( X 1 : b ) \Sigma_b(X_{1:b}) Σ b ( X 1 : b ) n × n n\times n n × n b b b X 1 : B X_{1:B} X 1 : B γ B \gamma_B γ B
E [ ∑ b = 1 B tr ( Σ b ( X 1 : b ) ) ] ≤ 2 n C ( n , α ) γ B , \mathbb{E}\left[\sum_{b=1}^{B}\operatorname{tr}(\Sigma_b(X_{1:b}))\right]\leq\frac{2n}{C(n,\alpha)}\gamma_B, E [ b = 1 ∑ B tr ( Σ b ( X 1 : b )) ] ≤ C ( n , α ) 2 n γ B , where C ( n , α ) = ln ( 1 + n / α 2 ) C(n,\alpha)=\ln(1+n/\alpha^2) C ( n , α ) = ln ( 1 + n / α 2 )
Proofs of Section 4.2
Lemma 4.1. Let 0 < η < ρ ≤ 1 / 2 0<\eta<\rho\leq1/2 0 < η < ρ ≤ 1/2 t ∈ M ^ T ρ t\in\widehat{\mathcal{M}}_T^\rho t ∈ M T ρ G η \mathcal{G}_\eta G η
∣ Δ ^ a t , t − Δ a t , t L S ∣ ≤ ( ∣ σ a ∗ , t ∣ + ∣ σ a t , t ∣ ) c ρ − η , (28) \left|\widehat{\Delta}_{a_t,t}-\Delta^{\mathrm{LS}}_{a_t,t}\right|\leq\left(|\sigma_{a^*,t}|+|\sigma_{a_t,t}|\right)c_{\rho-\eta}, \tag*{(28)} Δ a t , t − Δ a t , t LS ≤ ( ∣ σ a ∗ , t ∣ + ∣ σ a t , t ∣ ) c ρ − η , (28) where c ρ − η c_{\rho-\eta} c ρ − η v − 1 v^{-1} v − 1 [ ρ − η , 1 − ρ + η ] [\rho-\eta,1-\rho+\eta] [ ρ − η , 1 − ρ + η ] (16) .
Proof.
∣ Δ ^ a ^ t , t − Δ a ^ t , t L S ∣ : = ∣ z ^ a ^ ∗ , t σ a ^ ∗ , t − z ^ a ^ t , t σ a ^ t , t − ( z a ^ ∗ , t σ a ^ ∗ , t − z a ^ t , t σ a t , t ) ∣ ≤ ∣ z ^ a ^ ∗ , t σ a ^ ∗ , t − z a ^ ∗ , t σ a ^ ∗ , t ∣ + ∣ z a ^ t , t σ a t , t − z ^ a ^ t , t σ a t , t ∣ ≤ ∣ σ a ^ ∗ , t ∣ ∣ z ^ a ^ ∗ , t − z a ^ ∗ , t ∣ + ∣ σ a t , t ∣ ∣ z ^ a ^ t , t − z a t , t ∣ . \begin{aligned}
\left|\widehat{\Delta}_{\hat{a}_t,t}-\Delta^{LS}_{\hat{a}_t,t}\right| := \left|\widehat{z}_{\hat{a}^{*},t}\sigma_{\hat{a}^{*},t}-\widehat{z}_{\hat{a}_t,t}\sigma_{\hat{a}_t,t}-\left(z_{\hat{a}^{*},t}\sigma_{\hat{a}^{*},t}-z_{\hat{a}_t,t}\sigma_{a_t,t}\right)\right| \\
&\leq\left|\widehat{z}_{\hat{a}^{*},t}\sigma_{\hat{a}^{*},t}-z_{\hat{a}^{*},t}\sigma_{\hat{a}^{*},t}\right|+\left|z_{\hat{a}_t,t}\sigma_{a_t,t}-\widehat{z}_{\hat{a}_t,t}\sigma_{a_t,t}\right| \\
&\leq|\sigma_{\hat{a}^{*},t}|\left|\widehat{z}_{\hat{a}^{*},t}-z_{\hat{a}^{*},t}\right|+|\sigma_{a_t,t}|\left|\widehat{z}_{\hat{a}_t,t}-z_{a_t,t}\right|.
\end{aligned} Δ a ^ t , t − Δ a ^ t , t L S := ∣ z a ^ ∗ , t σ a ^ ∗ , t − z a ^ t , t σ a ^ t , t − ( z a ^ ∗ , t σ a ^ ∗ , t − z a ^ t , t σ a t , t ) ∣ ≤ ∣ z a ^ ∗ , t σ a ^ ∗ , t − z a ^ ∗ , t σ a ^ ∗ , t ∣ + ∣ z a ^ t , t σ a t , t − z a ^ t , t σ a t , t ∣ ≤ ∣ σ a ^ ∗ , t ∣ ∣ z a ^ ∗ , t − z a ^ ∗ , t ∣ + ∣ σ a t , t ∣ ∣ z a ^ t , t − z a t , t ∣ . Observe that, for t ∈ M ^ T ρ t \in\widehat{M}^{\rho}_{T} t ∈ M T ρ
∣ z ^ a t , t − z a t , t ∣ : = ∣ v − 1 ( q ^ a t , t ) − v − 1 ( q a t , t ) ∣ ≤ c ρ − η ∣ q ^ a t , t − q a t , t ∣ ≤ c ρ − η η , \left|\widehat{z}_{a_t,t}-z_{a_t,t}\right| := \left|v^{-1}(\widehat{q}_{a_t,t})-v^{-1}(q_{a_t,t})\right|\leq c_{\rho-\eta}\left|\widehat{q}_{a_t,t}-q_{a_t,t}\right|\leq c_{\rho-\eta}\eta, ∣ z a t , t − z a t , t ∣ := v − 1 ( q a t , t ) − v − 1 ( q a t , t ) ≤ c ρ − η ∣ q a t , t − q a t , t ∣ ≤ c ρ − η η , since v − 1 : [ ρ − η , 1 − ρ + η ] → R v^{-1}:[\rho-\eta,1-\rho+\eta]\to\mathbb{R} v − 1 : [ ρ − η , 1 − ρ + η ] → R c ρ − η c_{\rho-\eta} c ρ − η a ^ ∗ \hat{a}^{*} a ^ ∗
Theorem 4.1. Assume that A A A σ a , 0 2 ≤ 1 \sigma_{a,0}^{2}\leq1 σ a , 0 2 ≤ 1 a ∈ [ K ] a\in[K] a ∈ [ K ] 0 < 2 η < γ ≤ 1 / 2 0<2\eta<\gamma\leq1/2 0 < 2 η < γ ≤ 1/2 G η \mathcal{G}_{\eta} G η
E T γ ≤ c γ − 2 η ⋅ η ( ( α 2 + 1 ) γ T + 2 α T + t ∗ + 1 T ) . (29) \mathcal{E}^{\gamma}_{T}\leq c_{\gamma-2\eta}\cdot\eta\left(\frac{(\alpha\sqrt{2}+1)\sqrt{\gamma T}+2\alpha}{\sqrt{T}}+\frac{t^{*}+1}{T}\right). \tag*{(29)} E T γ ≤ c γ − 2 η ⋅ η ( T ( α 2 + 1 ) γ T + 2 α + T t ∗ + 1 ) . (29) Here, c γ − 2 η c_{\gamma-2\eta} c γ − 2 η v − 1 v^{-1} v − 1 [ γ − 2 η , 1 − γ + 2 η ] [\gamma-2\eta,1-\gamma+2\eta] [ γ − 2 η , 1 − γ + 2 η ] (16) , γ T \gamma T γ T 3 t ∗ : = ∑ a ≠ a ^ ∗ N a ( T ) t^{*}:=\sum_{a\ne\hat{a}^{*}}N_a(T) t ∗ := ∑ a = a ^ ∗ N a ( T )
Proof. Using the fact that M T γ ⊆ M ^ T γ − η M^{\gamma}_{T}\subseteq\widehat{M}^{\gamma-\eta}_{T} M T γ ⊆ M T γ − η ρ = γ − η \rho=\gamma-\eta ρ = γ − η
E T γ ≤ 1 T ∑ t = 1 T 1 { t ∈ M ^ T γ − η } ∣ Δ ^ a t , t − Δ a t , t L S ∣ \mathcal{E}^{\gamma}_{T}\leq\frac{1}{T}\sum_{t=1}^{T}\mathbb{1}\{t\in\widehat{M}^{\gamma-\eta}_{T}\}\left|\widehat{\Delta}_{a_t,t}-\Delta^{LS}_{a_t,t}\right| E T γ ≤ T 1 t = 1 ∑ T 1 { t ∈ M T γ − η } Δ a t , t − Δ a t , t L S ≤ c γ − 2 η η T ∑ t = 1 T 1 { t ∈ M ^ T γ − η } ( ∣ σ a t , t ∣ + ∣ σ a ^ ∗ , t ∣ ) . \leq\frac{c_{\gamma-2\eta}\eta}{T}\sum_{t=1}^{T}\mathbb{1}\{t\in\widehat{M}^{\gamma-\eta}_{T}\}\left(|\sigma_{a_t,t}|+|\sigma_{\hat{a}^{*},t}|\right). ≤ T c γ − 2 η η t = 1 ∑ T 1 { t ∈ M T γ − η } ( ∣ σ a t , t ∣ + ∣ σ a ^ ∗ , t ∣ ) . Using the Cauchy-Schwarz inequality for the first sum, we get:
c γ − 2 η η T ∑ t = 1 T 1 { t ∈ M ^ T γ − η } ( ∣ σ a t , t ∣ + ∣ σ a ^ ∗ , t ∣ ) (30) \frac{c_{\gamma-2\eta}\eta}{T}\sum_{t=1}^{T}\mathbb{1}\{t\in\widehat{M}^{\gamma-\eta}_{T}\}\left(|\sigma_{a_t,t}|+|\sigma_{\hat{a}^{*},t}|\right) \tag*{(30)} T c γ − 2 η η t = 1 ∑ T 1 { t ∈ M T γ − η } ( ∣ σ a t , t ∣ + ∣ σ a ^ ∗ , t ∣ ) (30) ≤ c γ − 2 η η T ( ∑ t = 1 T σ a t , t 2 × T + ∑ t = 1 T 1 { t ∈ M ^ T γ − η } σ a ^ ∗ , t ) (31) \leq\frac{c_{\gamma-2\eta}\eta}{T}\left(\sqrt{\sum_{t=1}^{T}\sigma_{a_t,t}^{2}}\times\sqrt{T}+\sum_{t=1}^{T}\mathbb{1}\{t\in\widehat{M}^{\gamma-\eta}_{T}\}\sigma_{\hat{a}^{*},t}\right) \tag*{(31)} ≤ T c γ − 2 η η t = 1 ∑ T σ a t , t 2 × T + t = 1 ∑ T 1 { t ∈ M T γ − η } σ a ^ ∗ , t (31) ≤ c γ − 2 η η T ( T C α γ T 2 + ∑ t = 1 T σ a ^ ∗ , t ) . (32) \leq\frac{c_{\gamma-2\eta}\eta}{T}\left(\sqrt{T}\sqrt{\frac{C_{\alpha}\gamma_{T}}{2}}+\sum_{t=1}^{T}\sigma_{\hat{a}^{*},t}\right). \tag*{(32)} ≤ T c γ − 2 η η ( T 2 C α γ T + t = 1 ∑ T σ a ^ ∗ , t ) . (32) Note that the last inequality applied Lemma C.5. It remains to bound
∑ t = 1 T σ a ^ ∗ , t . \sum_{t=1}^{T}\sigma_{\hat{a}^{*},t}. t = 1 ∑ T σ a ^ ∗ , t . First, observe that:
σ a ^ ∗ , t ≤ ( 1 σ a ^ ∗ , 0 2 + N a ^ ∗ ( t − 1 ) α 2 ) − 1 ≤ α N a ^ ∗ ( t − 1 ) . \sigma_{\hat{a}^{*},t}\leq\sqrt{\left(\frac{1}{\sigma_{\hat{a}^{*},0}^{2}}+\frac{N_{\hat{a}^{*}}(t-1)}{\alpha^{2}}\right)^{-1}}\leq\frac{\alpha}{\sqrt{N_{\hat{a}^{*}}(t-1)}}. σ a ^ ∗ , t ≤ ( σ a ^ ∗ , 0 2 1 + α 2 N a ^ ∗ ( t − 1 ) ) − 1 ≤ N a ^ ∗ ( t − 1 ) α . We know that,
N a ^ ∗ ( t − 1 ) = ( t − 1 ) − ∑ a ≠ a ^ ∗ N a ( t − 1 ) ≥ ( t − 1 ) − ∑ a ≠ a ^ ∗ N a ( T ) . (33) N_{\hat{a}^{*}}(t-1)=(t-1)-\sum_{a\ne\hat{a}^{*}}N_a(t-1)\geq(t-1)-\sum_{a\ne\hat{a}^{*}}N_a(T). \tag*{(33)} N a ^ ∗ ( t − 1 ) = ( t − 1 ) − a = a ^ ∗ ∑ N a ( t − 1 ) ≥ ( t − 1 ) − a = a ^ ∗ ∑ N a ( T ) . (33) here we should be careful because ( t − 1 ) − ∑ a ≠ a ^ ∗ N a ( T ) (t-1)-\sum_{a\ne\hat{a}^{*}}N_a(T) ( t − 1 ) − ∑ a = a ^ ∗ N a ( T ) t ∗ : = ∑ a ≠ a ^ ∗ N a ( T ) < T t^{*}:=\sum_{a\ne\hat{a}^{*}}N_a(T)<T t ∗ := ∑ a = a ^ ∗ N a ( T ) < T
∑ t = 1 T σ a ^ ∗ , t = ∑ t = 1 t ∗ + 1 σ a ^ ∗ , t + ∑ t = t ∗ + 2 T σ a ^ ∗ , t (34) \sum_{t=1}^{T}\sigma_{\hat{a}^{*},t}=\sum_{t=1}^{t^{*}+1}\sigma_{\hat{a}^{*},t}+\sum_{t=t^{*}+2}^{T}\sigma_{\hat{a}^{*},t} \tag*{(34)} t = 1 ∑ T σ a ^ ∗ , t = t = 1 ∑ t ∗ + 1 σ a ^ ∗ , t + t = t ∗ + 2 ∑ T σ a ^ ∗ , t (34) ≤ t ∗ + 1 + ∑ t = t ∗ + 2 T α N a ^ ∗ ( t − 1 ) (35) \le t^{*}+1+\sum_{t=t^{*}+2}^{T}\frac{\alpha}{\sqrt{N_{\hat{a}^{*}}(t-1)}} \tag*{(35)} ≤ t ∗ + 1 + t = t ∗ + 2 ∑ T N a ^ ∗ ( t − 1 ) α (35) ≤ t ∗ + 1 + α ( ∑ t = t ∗ + 2 T 1 t − 1 − t ∗ ) ≤ t ∗ + 1 + 2 α T (36) \le t^{*}+1+\alpha\left(\sum_{t=t^{*}+2}^{T}\frac{1}{\sqrt{t-1-t^{*}}}\right)\le t^{*}+1+2\alpha\sqrt{T} \tag*{(36)} ≤ t ∗ + 1 + α ( t = t ∗ + 2 ∑ T t − 1 − t ∗ 1 ) ≤ t ∗ + 1 + 2 α T (36) Remark C.1. Since a ^ ∗ \hat{a}^{*} a ^ ∗ T ≥ 1 T\ge1 T ≥ 1 N a ^ ∗ ( T ) ≥ 1 N_{\hat{a}^{*}}(T)\ge1 N a ^ ∗ ( T ) ≥ 1 t ∗ = T − N a ^ ∗ ( T ) ≤ T − 1 t^{*}=T-N_{\hat{a}^{*}}(T)\le T-1 t ∗ = T − N a ^ ∗ ( T ) ≤ T − 1 t ∗ + 1 ≤ T t^{*}+1\le T t ∗ + 1 ≤ T
Where we upper bounded σ a ^ ∗ , t ≤ σ a ^ ∗ , 0 ≤ 1 \sigma_{\hat{a}^{*},t}\le\sigma_{\hat{a}^{*},0}\le1 σ a ^ ∗ , t ≤ σ a ^ ∗ , 0 ≤ 1 (33) in the second one together with an integral comparison. Plugging this into (32) we get:
1 T ∑ t = 1 T 1 { t ∈ M T γ } ∣ Δ ^ a t , t − Δ a t , t L S ∣ ≤ C γ − 2 η η T ( T C α γ T 2 + t ∗ + 1 + 2 α T ) (37) \frac{1}{T}\sum_{t=1}^{T}\mathbb{1}\{t\in M_{T}^{\gamma}\}\left|\widehat{\Delta}_{a_t,t}-\Delta^{LS}_{a_t,t}\right|\le\frac{C_{\gamma-2\eta}\eta}{T}\left(\sqrt{T}\sqrt{\frac{C_{\alpha}\gamma T}{2}}+t^{*}+1+2\alpha\sqrt{T}\right) \tag*{(37)} T 1 t = 1 ∑ T 1 { t ∈ M T γ } Δ a t , t − Δ a t , t L S ≤ T C γ − 2 η η ( T 2 C α γ T + t ∗ + 1 + 2 α T ) (37) where C α : = 4 ln ( 1 + α − 2 ) C_{\alpha}:=\frac{4}{\ln(1+\alpha^{-2})} C α := l n ( 1 + α − 2 ) 4 2 ln ( 1 + α − 2 ) ≤ 2 α 2 + 1 \frac{2}{\ln(1+\alpha^{-2})}\le2\alpha^{2}+1 l n ( 1 + α − 2 ) 2 ≤ 2 α 2 + 1 ln ( 1 + x ) ≥ 2 x x + 2 \ln(1+x)\ge\frac{2x}{x+2} ln ( 1 + x ) ≥ x + 2 2 x x > 0 x>0 x > 0 2 α 2 + 1 ≤ α 2 + 1 \sqrt{2\alpha^{2}+1}\le\alpha\sqrt{2}+1 2 α 2 + 1 ≤ α 2 + 1
Lemma 4.2. For any δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 )
η n , δ : = log ( 2 K B / δ ) 2 n . (38) \eta_{n,\delta}:=\sqrt{\frac{\log(2KB/\delta)}{2n}}. \tag*{(38)} η n , δ := 2 n log ( 2 K B / δ ) . (38) Then
P ( max b ∈ [ B ] max a ∈ [ K ] ∣ q ^ a , b − q a , b ∣ ≤ η n , δ ) ≥ 1 − δ . (39) \mathbb{P}\left(\max_{b\in[B]}\max_{a\in[K]}|\hat{q}_{a,b}-q_{a,b}|\le\eta_{n,\delta}\right)\ge1-\delta. \tag*{(39)} P ( b ∈ [ B ] max a ∈ [ K ] max ∣ q ^ a , b − q a , b ∣ ≤ η n , δ ) ≥ 1 − δ . (39) Proof. Fix an arm a ∈ [ K ] a\in[K] a ∈ [ K ] b ∈ [ B ] b\in[B] b ∈ [ B ] F ( b − 1 ) n \mathcal{F}_{(b-1)n} F ( b − 1 ) n b b b
X b , j a : = 1 { a b , j = a } , j ∈ [ n ] . X^{a}_{b,j}:=\mathbb{1}\{a_{b,j}=a\},\qquad j\in[n]. X b , j a := 1 { a b , j = a } , j ∈ [ n ] . Because the sampling distribution remains fixed within batch b b b X b , 1 a , … , X b , n a X^{a}_{b,1},\ldots,X^{a}_{b,n} X b , 1 a , … , X b , n a q a , b q_{a,b} q a , b
q ^ a , b = 1 n ∑ j = 1 n X b , j a . \hat{q}_{a,b}=\frac{1}{n}\sum_{j=1}^{n}X^{a}_{b,j}. q ^ a , b = n 1 j = 1 ∑ n X b , j a . Therefore, Hoeffding’s inequality gives, for every x > 0 x>0 x > 0
P ( ∣ q ^ a , b − q a , b ∣ > x ∣ F b − 1 ) ≤ 2 exp ( − 2 n x 2 ) . (40) \mathbb{P}\left(|\hat{q}_{a,b}-q_{a,b}|>x\mid\mathcal{F}_{b-1}\right)\le2\exp(-2nx^{2}). \tag*{(40)} P ( ∣ q ^ a , b − q a , b ∣ > x ∣ F b − 1 ) ≤ 2 exp ( − 2 n x 2 ) . (40) Taking expectations over F b − 1 \mathcal{F}_{b-1} F b − 1
P ( ∣ q ^ a , b − q a , b ∣ > x ) ≤ 2 exp ( − 2 n x 2 ) . (41) \mathbb{P}\left(|\hat{q}_{a,b}-q_{a,b}|>x\right)\le2\exp(-2nx^{2}). \tag*{(41)} P ( ∣ q ^ a , b − q a , b ∣ > x ) ≤ 2 exp ( − 2 n x 2 ) . (41) Applying a union bound over the K B KB K B
P ( max b ∈ [ B ] max a ∈ [ K ] ∣ q ^ a , b − q a , b ∣ > x ) ≤ 2 K B exp ( − 2 n x 2 ) . (42) \mathbb{P}\left(\max_{b\in[B]}\max_{a\in[K]}|\hat{q}_{a,b}-q_{a,b}|>x\right)\le2KB\exp(-2nx^{2}). \tag*{(42)} P ( b ∈ [ B ] max a ∈ [ K ] max ∣ q ^ a , b − q a , b ∣ > x ) ≤ 2 K B exp ( − 2 n x 2 ) . (42) Setting
x = log ( 2 K B / δ ) 2 n = η n , δ x=\sqrt{\frac{\log(2KB/\delta)}{2n}}=\eta_{n,\delta} x = 2 n log ( 2 K B / δ ) = η n , δ concludes the proof.
Theorem 4.2. Let A \mathcal{A} A ν \nu ν σ a , 0 2 ≤ 1 \sigma_{a,0}^{2} \le1 σ a , 0 2 ≤ 1 a ∈ [ K ] a \in[K] a ∈ [ K ] α 2 \alpha^{2} α 2 0 < 2 η n , δ < γ ≤ 1 / 2 0 < 2\eta_{n,\delta} < \gamma\le1/2 0 < 2 η n , δ < γ ≤ 1/2 G n , δ \mathcal{G}_{n,\delta} G n , δ
E T γ ≤ c γ − 2 η n , δ ⋅ η n , δ [ ( α 2 + n ) γ B + 2 α T + t ∗ + n ( 1 + B α ) T ] . (43) \mathcal{E}_{T}^{\gamma} \le c_{\gamma-2\eta_{n,\delta}} \cdot\eta_{n,\delta} \left[\frac{(\alpha\sqrt{2}+\sqrt{n})\sqrt{\gamma_{B}}+2\alpha}{\sqrt{T}}+\frac{t^{*}+n(1+B_{\alpha})}{T}\right]. \tag*{(43)} E T γ ≤ c γ − 2 η n , δ ⋅ η n , δ [ T ( α 2 + n ) γ B + 2 α + T t ∗ + n ( 1 + B α ) ] . (43) Here, B α : = min { 1 , α } B_{\alpha} := \min\{1,\alpha\} B α := min { 1 , α } γ B \gamma_{B} γ B c γ − 2 η n , δ c_{\gamma-2\eta_{n,\delta}} c γ − 2 η n , δ (16) , and t ∗ : = ∑ a ≠ a ^ ∗ N a ( T ) t^{*} := \sum_{a\ne\hat{a}^{*}}N_{a}(T) t ∗ := ∑ a = a ^ ∗ N a ( T ) 1 − δ 1-\delta 1 − δ
Proof. On the event G n , δ \mathcal{G}_{n,\delta} G n , δ
E T γ ≤ 1 T ∑ t = 1 T 1 { t ∈ M ~ T γ − η n , δ } ∣ Δ ^ a t , t − Δ a t , t A ∣ = 1 T ∑ b = 1 B ∑ t = n ( b − 1 ) + 1 n b 1 { t ∈ M ~ T γ − η n , δ } ∣ Δ ^ a t , t − Δ a t , t A ∣ ≤ c γ − 2 η n , δ η n , δ T ∑ b = 1 B ∑ t = n ( b − 1 ) + 1 n b 1 { t ∈ M ~ T γ − η n , δ } ( ∣ σ a t , t ∣ + ∣ σ a ^ ∗ , t ∣ ) . \begin{aligned}
\mathcal{E}_{T}^{\gamma} \le\frac{1}{T}\sum_{t=1}^{T}\mathbb{1}\{t\in\widetilde{\mathcal{M}}_{T}^{\gamma-\eta_{n,\delta}}\}\lvert\widehat{\Delta}_{a_t,t}-\Delta^{\mathcal{A}}_{a_t,t}\rvert
= \frac{1}{T}\sum_{b=1}^{B}\sum_{t=n(b-1)+1}^{nb}\mathbb{1}\{t\in\widetilde{\mathcal{M}}_{T}^{\gamma-\eta_{n,\delta}}\}\lvert\widehat{\Delta}_{a_t,t}-\Delta^{\mathcal{A}}_{a_t,t}\rvert\\
&\le\frac{c_{\gamma-2\eta_{n,\delta}}\eta_{n,\delta}}{T}\sum_{b=1}^{B}\sum_{t=n(b-1)+1}^{nb}\mathbb{1}\{t\in\widetilde{\mathcal{M}}_{T}^{\gamma-\eta_{n,\delta}}\}(\lvert\sigma_{a_t,t}\rvert+\lvert\sigma_{\hat{a}^{*},t}\rvert).
\end{aligned} E T γ ≤ T 1 t = 1 ∑ T 1 { t ∈ M T γ − η n , δ } ∣ Δ a t , t − Δ a t , t A ∣ = T 1 b = 1 ∑ B t = n ( b − 1 ) + 1 ∑ nb 1 { t ∈ M T γ − η n , δ } ∣ Δ a t , t − Δ a t , t A ∣ ≤ T c γ − 2 η n , δ η n , δ b = 1 ∑ B t = n ( b − 1 ) + 1 ∑ nb 1 { t ∈ M T γ − η n , δ } (∣ σ a t , t ∣ + ∣ σ a ^ ∗ , t ∣) . Using Cauchy-Schwarz inequality we get
c γ − 2 η n , δ η n , δ T ∑ b = 1 B ∑ t = n ( b − 1 ) + 1 n b 1 { t ∈ M ~ T γ − η n , δ } ( ∣ σ a t , t ∣ + ∣ σ a ^ ∗ , t ∣ ) ≤ (44) \frac{c_{\gamma-2\eta_{n,\delta}}\eta_{n,\delta}}{T}\sum_{b=1}^{B}\sum_{t=n(b-1)+1}^{nb}\mathbb{1}\{t\in\widetilde{\mathcal{M}}_{T}^{\gamma-\eta_{n,\delta}}\}(\lvert\sigma_{a_t,t}\rvert+\lvert\sigma_{\hat{a}^{*},t}\rvert)
\le \tag*{(44)} T c γ − 2 η n , δ η n , δ b = 1 ∑ B t = n ( b − 1 ) + 1 ∑ nb 1 { t ∈ M T γ − η n , δ } (∣ σ a t , t ∣ + ∣ σ a ^ ∗ , t ∣) ≤ (44) c γ − 2 η n , δ η n , δ T ( ∑ b = 1 B ∑ t = n ( b − 1 ) + 1 n b ∣ σ a t , t ∣ 2 × n B + ∑ b = 1 B ∑ t = n ( b − 1 ) + 1 n b ∣ σ a ^ ∗ , t ∣ ) . (45) \frac{c_{\gamma-2\eta_{n,\delta}}\eta_{n,\delta}}{T}\left(\sqrt{\sum_{b=1}^{B}\sum_{t=n(b-1)+1}^{nb}\lvert\sigma_{a_t,t}\rvert^{2}\times\sqrt{nB}}+\sum_{b=1}^{B}\sum_{t=n(b-1)+1}^{nb}\lvert\sigma_{\hat{a}^{*},t}\rvert\right). \tag*{(45)} T c γ − 2 η n , δ η n , δ b = 1 ∑ B t = n ( b − 1 ) + 1 ∑ nb ∣ σ a t , t ∣ 2 × n B + b = 1 ∑ B t = n ( b − 1 ) + 1 ∑ nb ∣ σ a ^ ∗ , t ∣ . (45) Since the posterior is constant within each batch, ∑ t = n ( b − 1 ) + 1 n b σ a t , t 2 = tr ( Σ b ) \sum_{t=n(b-1)+1}^{nb}\sigma_{a_t,t}^{2}=\operatorname{tr}(\Sigma_b) ∑ t = n ( b − 1 ) + 1 nb σ a t , t 2 = tr ( Σ b ) Σ b \Sigma_b Σ b a t a_t a t
∑ b = 1 B ∑ t = n ( b − 1 ) + 1 n b ∣ σ a t , t ∣ 2 × n B = n B ∑ b = 1 B tr ( Σ b ) ≤ n B 2 n γ B C ( n , α ) , (46) \sqrt{\sum_{b=1}^{B}\sum_{t=n(b-1)+1}^{nb}\lvert\sigma_{a_t,t}\rvert^{2}\times\sqrt{nB}}
=\sqrt{nB}\sqrt{\sum_{b=1}^{B}\operatorname{tr}(\Sigma_b)}
\le\sqrt{nB}\sqrt{\frac{2n\gamma_{B}}{C(n,\alpha)}}, \tag*{(46)} b = 1 ∑ B t = n ( b − 1 ) + 1 ∑ nb ∣ σ a t , t ∣ 2 × n B = n B b = 1 ∑ B tr ( Σ b ) ≤ n B C ( n , α ) 2 n γ B , (46) where C ( n , α ) : = ln ( 1 + n / α 2 ) C(n,\alpha):=\ln(1+n/\alpha^{2}) C ( n , α ) := ln ( 1 + n / α 2 ) 2 n ln ( 1 + n / α 2 ) ≤ 2 α 2 + n \frac{2n}{\ln(1+n/\alpha^{2})}\le2\alpha^{2}+n l n ( 1 + n / α 2 ) 2 n ≤ 2 α 2 + n 2 α 2 + n ≤ α 2 + n \sqrt{2\alpha^{2}+n}\le\alpha\sqrt{2}+\sqrt{n} 2 α 2 + n ≤ α 2 + n
n B 2 n γ B C ( n , α ) ≤ n B ( α 2 + n ) γ B . (47) \sqrt{nB}\sqrt{\frac{2n\gamma_{B}}{C(n,\alpha)}}\le\sqrt{nB}(\alpha\sqrt{2}+\sqrt{n})\sqrt{\gamma_{B}}. \tag*{(47)} n B C ( n , α ) 2 n γ B ≤ n B ( α 2 + n ) γ B . (47) It remains to bound:
∑ b = 1 B ∑ t = n ( b − 1 ) + 1 n b ∣ σ a ^ ∗ , t ∣ = ∑ b = 1 B n σ a ^ ∗ , b (48) \sum_{b=1}^{B}\sum_{t=n(b-1)+1}^{nb}\lvert\sigma_{\hat{a}^{*},t}\rvert=\sum_{b=1}^{B}n\sigma_{\hat{a}^{*},b} \tag*{(48)} b = 1 ∑ B t = n ( b − 1 ) + 1 ∑ nb ∣ σ a ^ ∗ , t ∣ = b = 1 ∑ B n σ a ^ ∗ , b (48) since σ a ^ ∗ , t \sigma_{\hat{a}^{*},t} σ a ^ ∗ , t n n n
t ∗ = ∑ a ≠ a ^ ∗ N a ( T ) = ℓ n + r , ℓ : = ⌊ t ∗ n ⌋ , r : = t ∗ mod n ∈ { 0 , … , n − 1 } . t^{*}=\sum_{a\ne\hat{a}^{*}}N_{a}(T)=\ell n+r,\qquad\ell:=\left\lfloor\frac{t^{*}}{n}\right\rfloor,\qquad r:=t^{*}\mathbin{\operatorname{mod}} n\in\{0,\ldots,n-1\}. t ∗ = a = a ^ ∗ ∑ N a ( T ) = ℓ n + r , ℓ := ⌊ n t ∗ ⌋ , r := t ∗ mod n ∈ { 0 , … , n − 1 } . At the beginning of batch b b b
N a ^ ∗ ( n ( b − 1 ) ) = n ( b − 1 ) − ∑ a ≠ a ^ ∗ N a ( n ( b − 1 ) ) ≥ n ( b − 1 ) − t ∗ , N_{\hat{a}^{*}}(n(b-1))=n(b-1)-\sum_{a\ne\hat{a}^{*}}N_a(n(b-1))\ge n(b-1)-t^{*}, N a ^ ∗ ( n ( b − 1 )) = n ( b − 1 ) − a = a ^ ∗ ∑ N a ( n ( b − 1 )) ≥ n ( b − 1 ) − t ∗ , the first ℓ + 1 \ell+1 ℓ + 1 n ( ℓ + 1 ) n(\ell+1) n ( ℓ + 1 ) σ a ∗ , t ≤ 1 \sigma_{a^{*},t}\le1 σ a ∗ , t ≤ 1
If ℓ + 2 ≤ B \ell+2\le B ℓ + 2 ≤ B ℓ + 2 \ell+2 ℓ + 2
n σ a ^ ∗ , n ( ℓ + 2 ) ≤ n min { 1 , α n − r } ≤ n min { 1 , α } = : n B α . n\sigma_{\hat{a}^{*},n(\ell+2)}\le n\min\left\{1,\frac{\alpha}{\sqrt{n-r}}\right\}\le n\min\{1,\alpha\}=:nB_{\alpha}. n σ a ^ ∗ , n ( ℓ + 2 ) ≤ n min { 1 , n − r α } ≤ n min { 1 , α } =: n B α . For the remaining batches, the summand is decreasing, so an integral comparison gives
∑ b = ℓ + 3 B n α n ( b − 1 ) − t ∗ ≤ n α ∫ ℓ + 2 B d x n ( x − 1 ) − t ∗ (49) \sum_{b=\ell+3}^{B}\frac{n\alpha}{\sqrt{n(b-1)-t^{*}}}\le n\alpha\int_{\ell+2}^{B}\frac{dx}{\sqrt{n(x-1)-t^{*}}} \tag*{(49)} b = ℓ + 3 ∑ B n ( b − 1 ) − t ∗ n α ≤ n α ∫ ℓ + 2 B n ( x − 1 ) − t ∗ d x (49) = 2 α ( n ( B − 1 ) − t ∗ − n − r ) (50) =2\alpha\left(\sqrt{n(B-1)-t^{*}}-\sqrt{n-r}\right) \tag*{(50)} = 2 α ( n ( B − 1 ) − t ∗ − n − r ) (50) ≤ 2 α T . (51) \le2\alpha\sqrt{T}. \tag*{(51)} ≤ 2 α T . (51) Consequently,
∑ b = 1 B n σ a ^ ∗ , n b ≤ n ( ℓ + 1 ) + n B α + 2 α T (52) \sum_{b=1}^{B}n\sigma_{\hat{a}^{*},nb}\le n(\ell+1)+nB_{\alpha}+2\alpha\sqrt{T} \tag*{(52)} b = 1 ∑ B n σ a ^ ∗ , nb ≤ n ( ℓ + 1 ) + n B α + 2 α T (52) = t ∗ − r + n + n B α + 2 α T (53) =t^{*}-r+n+nB_{\alpha}+2\alpha\sqrt{T} \tag*{(53)} = t ∗ − r + n + n B α + 2 α T (53) ≤ t ∗ + n ( 1 + B α ) + 2 α T . (54) \le t^{*}+n(1+B_{\alpha})+2\alpha\sqrt{T}. \tag*{(54)} ≤ t ∗ + n ( 1 + B α ) + 2 α T . (54) If ℓ + 2 > B \ell+2>B ℓ + 2 > B
Plugging Equation (54) and Equation (47) into Equation (44) we get:
c γ − 2 η n , δ η n , δ T ( ∑ b = 1 B ∑ t = n ( b − 1 ) + 1 n b ∣ σ a t , t ∣ 2 × n B + ∑ b = 1 B ∑ t = n ( b − 1 ) + 1 n b ∣ σ a ^ ∗ , t ∣ ) (55) \frac{c_{\gamma-2\eta_{n,\delta}}\eta_{n,\delta}}{T}\left(\sqrt{\sum_{b=1}^{B}\sum_{t=n(b-1)+1}^{nb}|\sigma_{a_t,t}|^{2}\times\sqrt{nB}+\sum_{b=1}^{B}\sum_{t=n(b-1)+1}^{nb}|\sigma_{\hat{a}^{*},t}|}\right) \tag*{(55)} T c γ − 2 η n , δ η n , δ b = 1 ∑ B t = n ( b − 1 ) + 1 ∑ nb ∣ σ a t , t ∣ 2 × n B + b = 1 ∑ B t = n ( b − 1 ) + 1 ∑ nb ∣ σ a ^ ∗ , t ∣ (55) ≤ c γ − 2 η n , δ η n , δ T ( n B ( α 2 + n ) γ B + t ∗ + n ( 1 + min { 1 , α } ) + 2 α T ) (56) \le\frac{c_{\gamma-2\eta_{n,\delta}}\eta_{n,\delta}}{T}\left(\sqrt{nB}(\alpha\sqrt{2}+\sqrt{n})\sqrt{\gamma_B}+t^{*}+n(1+\min\{1,\alpha\})+2\alpha\sqrt{T}\right) \tag*{(56)} ≤ T c γ − 2 η n , δ η n , δ ( n B ( α 2 + n ) γ B + t ∗ + n ( 1 + min { 1 , α }) + 2 α T ) (56) Since P ( G n , δ ) ≥ 1 − δ \mathbb{P}(\mathcal{G}_{n,\delta})\ge1-\delta P ( G n , δ ) ≥ 1 − δ 1 − δ 1-\delta 1 − δ
Theorem 4.3. Assume that A A A ( ε , ε ~ ) (\varepsilon,\tilde{\varepsilon}) ( ε , ε ~ ) 0 < 2 ε < γ ≤ 1 / 2 0<2\varepsilon<\gamma\le1/2 0 < 2 ε < γ ≤ 1/2 v v v
ε T γ ≤ c γ − 2 ε ⋅ ε ( ( α 2 + 1 ) γ T + 2 α T + t ∗ + 1 T ) + ε ~ . (57) \varepsilon_T^\gamma\le c_{\gamma-2\varepsilon}\cdot\varepsilon\left(\frac{(\alpha\sqrt{2}+1)\sqrt{\gamma_T}+2\alpha}{\sqrt{T}}+\frac{t^{*}+1}{T}\right)+\tilde{\varepsilon}. \tag*{(57)} ε T γ ≤ c γ − 2 ε ⋅ ε ( T ( α 2 + 1 ) γ T + 2 α + T t ∗ + 1 ) + ε ~ . (57) Here, c γ − 2 ε c_{\gamma-2\varepsilon} c γ − 2 ε (16) , evaluated at γ − 2 ε \gamma-2\varepsilon γ − 2 ε γ T \gamma_T γ T t ∗ : = ∑ a ≠ a ^ ∗ N a ( T ) t^{*}:=\sum_{a\ne\hat{a}^{*}}N_a(T) t ∗ := ∑ a = a ^ ∗ N a ( T )
Proof.
ε T γ ≤ 1 T ∑ t = 1 T 1 { t ∈ M ^ T γ − ε } ∣ Δ ^ a t , t − Δ a t , t A ∣ (58) \varepsilon_T^\gamma\le\frac{1}{T}\sum_{t=1}^{T}\mathbb{1}\{t\in\widehat{\mathcal{M}}_T^{\gamma-\varepsilon}\}|\widehat{\Delta}_{a_t,t}-\Delta^A_{a_t,t}| \tag*{(58)} ε T γ ≤ T 1 t = 1 ∑ T 1 { t ∈ M T γ − ε } ∣ Δ a t , t − Δ a t , t A ∣ (58) ≤ 1 T ∑ t = 1 T 1 { t ∈ M ^ T γ − ε } ( ∣ Δ ^ a t , t − Δ a t , t L S ∣ + ∣ Δ a t , t L S − Δ a t , t A ∣ ) (59) \le\frac{1}{T}\sum_{t=1}^{T}\mathbb{1}\{t\in\widehat{\mathcal{M}}_T^{\gamma-\varepsilon}\}\left(|\widehat{\Delta}_{a_t,t}-\Delta^{LS}_{a_t,t}|+|\Delta^{LS}_{a_t,t}-\Delta^A_{a_t,t}|\right) \tag*{(59)} ≤ T 1 t = 1 ∑ T 1 { t ∈ M T γ − ε } ( ∣ Δ a t , t − Δ a t , t L S ∣ + ∣ Δ a t , t L S − Δ a t , t A ∣ ) (59) We first bound ∑ t = 1 T 1 { t ∈ M ^ T γ − ε } ∣ Δ ^ a t , t − Δ a t , t L S ∣ \sum_{t=1}^{T}1\{t\in\widehat{M}_{T}^{\gamma-\varepsilon}\}|\widehat{\Delta}_{a_t,t}-\Delta^{LS}_{a_t,t}| ∑ t = 1 T 1 { t ∈ M T γ − ε } ∣ Δ a t , t − Δ a t , t L S ∣ ∣ p a t , t − q a t , t ∣ ≤ ε |p_{a_t,t}-q_{a_t,t}|\le\varepsilon ∣ p a t , t − q a t , t ∣ ≤ ε η \eta η ε \varepsilon ε
∑ t = 1 T 1 { t ∈ M ^ T γ − ε } ∣ Δ ^ a t , t − Δ a t , t L S ∣ ≤ c γ − 2 ε ε ∑ t = 1 T 1 { t ∈ M ^ T γ − ε } ( ∣ σ a t , t ∣ + ∣ σ a ^ ∗ , t ∣ ) \sum_{t=1}^{T}1\{t\in\widehat{M}_{T}^{\gamma-\varepsilon}\}|\widehat{\Delta}_{a_t,t}-\Delta^{LS}_{a_t,t}|\le c_{\gamma-2\varepsilon}\varepsilon\sum_{t=1}^{T}1\{t\in\widehat{M}_{T}^{\gamma-\varepsilon}\}(|\sigma_{a_t,t}|+|\sigma_{\widehat{a}^{*},t}|) t = 1 ∑ T 1 { t ∈ M T γ − ε } ∣ Δ a t , t − Δ a t , t L S ∣ ≤ c γ − 2 ε ε t = 1 ∑ T 1 { t ∈ M T γ − ε } ( ∣ σ a t , t ∣ + ∣ σ a ∗ , t ∣ ) Then, the proof is analogous to the one of Theorem 4.1 and
1 T ∑ t = 1 T 1 { t ∈ M ^ T γ − ε } ∣ Δ ^ a t , t − Δ a t , t L S ∣ ≤ c γ − 2 ε ε ( ( α 2 + 1 ) γ T + 2 α ∗ T + t ∗ + 1 T ) . \frac{1}{T}\sum_{t=1}^{T}1\{t\in\widehat{M}_{T}^{\gamma-\varepsilon}\}|\widehat{\Delta}_{a_t,t}-\Delta^{LS}_{a_t,t}|\le c_{\gamma-2\varepsilon}\varepsilon\left(\frac{(\alpha\sqrt{2}+1)\sqrt{\gamma T}+2\alpha^{*}}{\sqrt{T}}+\frac{t^{*}+1}{T}\right). T 1 t = 1 ∑ T 1 { t ∈ M T γ − ε } ∣ Δ a t , t − Δ a t , t L S ∣ ≤ c γ − 2 ε ε ( T ( α 2 + 1 ) γ T + 2 α ∗ + T t ∗ + 1 ) . Then we bound, ∑ t = 1 T 1 { t ∈ M ^ T γ − ε } ∣ Δ a t , t L S − Δ a t , t A ∣ \sum_{t=1}^{T}1\{t\in\widehat{M}_{T}^{\gamma-\varepsilon}\}|\Delta^{LS}_{a_t,t}-\Delta^{A}_{a_t,t}| ∑ t = 1 T 1 { t ∈ M T γ − ε } ∣ Δ a t , t L S − Δ a t , t A ∣ ∣ Δ a t , t L S − Δ a t , t A ∣ ≤ ε ~ |\Delta^{LS}_{a_t,t}-\Delta^{A}_{a_t,t}|\le\widetilde{\varepsilon} ∣ Δ a t , t L S − Δ a t , t A ∣ ≤ ε
∑ t = 1 T 1 { t ∈ M ^ T γ − ε } ∣ Δ a t , t L S − Δ a t , t A ∣ ≤ ε ~ T . \sum_{t=1}^{T}1\{t\in\widehat{M}_{T}^{\gamma-\varepsilon}\}|\Delta^{LS}_{a_t,t}-\Delta^{A}_{a_t,t}|\le\widetilde{\varepsilon}T. t = 1 ∑ T 1 { t ∈ M T γ − ε } ∣ Δ a t , t L S − Δ a t , t A ∣ ≤ ε T . Combining the bounds concludes the proof.
Technical Lemmas
Lemma C.1 (Variational form of KL-divergence). Fix two probability distributions p : Σ → [ 0 , 1 ] p:\Sigma\to[0,1] p : Σ → [ 0 , 1 ] and q : Σ → [ 0 , 1 ] q:\Sigma\to[0,1] q : Σ → [ 0 , 1 ] over the measurable space ( Ω , Σ ) (\Omega,\Sigma) ( Ω , Σ ) such that p p p is absolutely continuous with respect to q q q ( p ≪ q ) (p\ll q) ( p ≪ q ) Then
D K L [ p ∥ q ] = sup X { E p [ X ] − ln E q [ exp X ] } . D_{KL}[p\|q]=\sup_X\{\mathbb{E}_p[X]-\ln\mathbb{E}_q[\exp X]\}. D K L [ p ∥ q ] = X sup { E p [ X ] − ln E q [ exp X ]} . where the supremum is taken over all measurable X : Ω → R X:\Omega\to\mathbb{R} X : Ω → R such that E p [ X ] \mathbb{E}_p[X] E p [ X ] and E q [ exp X ] \mathbb{E}_q[\exp X] E q [ exp X ] are well-defined.
Proof. The proof generalizes Gray [10 ] from discrete spaces to arbitrary probability spaces. Since p ≪ q p\ll q p ≪ q d p d q ( ω ) \frac{dp}{dq}(\omega) d q d p ( ω ) p ( A ) = ∫ A d p d q ( ω ) d q ( ω ) p(A)=\int_A\frac{dp}{dq}(\omega)\,dq(\omega) p ( A ) = ∫ A d q d p ( ω ) d q ( ω ) d p d q ( ω ) \frac{dp}{dq}(\omega) d q d p ( ω ) q q q X : Ω → R X:\Omega\to\mathbb{R} X : Ω → R E p [ X ] \mathbb{E}_p[X] E p [ X ] E q [ exp X ] \mathbb{E}_q[\exp X] E q [ exp X ]
D K L [ p ∥ q ] − ( E p [ X ] − ln ( E q [ exp X ] ) ) = E p [ ln d p d q ( ω ) ] − E p [ ln exp X E q [ exp X ] ] = E p [ ln ( d p d q ( ω ) E q [ exp X ] exp ( X ) ) ] − E p [ ln d p d λ ] = D K L [ p ∥ λ ] ≥ 0 , \begin{aligned}
D_{KL}[p\|q]-\left(\mathbb{E}_p[X]-\ln(\mathbb{E}_q[\exp X])\right)
&=\mathbb{E}_p\left[\ln\frac{dp}{dq}(\omega)\right]-\mathbb{E}_p\left[\ln\frac{\exp X}{\mathbb{E}_q[\exp X]}\right]\\
&=\mathbb{E}_p\left[\ln\left(\frac{dp}{dq}(\omega)\frac{\mathbb{E}_q[\exp X]}{\exp(X)}\right)\right]-\mathbb{E}_p\left[\ln\frac{dp}{d\lambda}\right]\\
&=D_{KL}[p\|\lambda]\ge0,
\end{aligned} D K L [ p ∥ q ] − ( E p [ X ] − ln ( E q [ exp X ]) ) = E p [ ln d q d p ( ω ) ] − E p [ ln E q [ exp X ] exp X ] = E p [ ln ( d q d p ( ω ) exp ( X ) E q [ exp X ] ) ] − E p [ ln d λ d p ] = D K L [ p ∥ λ ] ≥ 0 , where λ ( A ) : = ∫ A exp ( X ( ω ) ) E q [ exp X ] d q ( ω ) \lambda(A):=\int_A\frac{\exp(X(\omega))}{\mathbb{E}_q[\exp X]}dq(\omega) λ ( A ) := ∫ A E q [ e x p X ] e x p ( X ( ω )) d q ( ω ) E q [ exp X ] exp ( X ) = d q d λ \frac{\mathbb{E}_q[\exp X]}{\exp(X)}=\frac{dq}{d\lambda} e x p ( X ) E q [ e x p X ] = d λ d q
Lemma C.2 (Conditioned KL-divergence). Consider the probability space ( Ω , Σ , P ) (\Omega,\Sigma,\mathbb{P}) ( Ω , Σ , P ) and an event B ∈ Σ B\in\Sigma B ∈ Σ of non-zero probability, i.e. P [ B ] > 0 \mathbb{P}[B]>0 P [ B ] > 0 Then
D K L [ P [ ⋅ ∣ B ] ∥ P ] = − ln P [ B ] . D_{KL}[\mathbb{P}[\cdot\mid B]\|\mathbb{P}]=-\ln\mathbb{P}[B]. D K L [ P [ ⋅ ∣ B ] ∥ P ] = − ln P [ B ] . Proof. According to the definition of conditional expectation it holds
P [ A ∣ B ] = P [ A ∩ B ] P [ B ] = ∫ A 1 ω ∈ B P [ B ] d P ( ω ) ∀ A ∈ Σ , \mathbb{P}[A\mid B]=\frac{\mathbb{P}[A\cap B]}{\mathbb{P}[B]}=\int_A\frac{1_{\omega\in B}}{\mathbb{P}[B]}\,d\mathbb{P}(\omega)\qquad\forall A\in\Sigma, P [ A ∣ B ] = P [ B ] P [ A ∩ B ] = ∫ A P [ B ] 1 ω ∈ B d P ( ω ) ∀ A ∈ Σ , where we recognize absolute continuity P [ ⋅ ∣ B ] ≪ P \mathbb{P}[\cdot\mid B]\ll\mathbb{P} P [ ⋅ ∣ B ] ≪ P d P [ ⋅ ∣ B ] d P ( ω ) = 1 ω ∈ B P [ B ] \frac{d\mathbb{P}[\cdot\mid B]}{d\mathbb{P}}(\omega)=\frac{1_{\omega\in B}}{\mathbb{P}[B]} d P d P [ ⋅ ∣ B ] ( ω ) = P [ B ] 1 ω ∈ B
D K L [ P [ ⋅ ∣ B ] ∥ P ] : = ∫ Ω ln d P [ ⋅ ∣ B ] d P d P [ ⋅ ∣ B ] = ∫ Ω ln ( d P [ ⋅ ∣ B ] d P ) d P [ ⋅ ∣ B ] d P d P = ∫ Ω ln ( 1 ω ∈ B P [ B ] ) 1 ω ∈ B P [ B ] d P = − ln P [ B ] . \begin{aligned}
D_{KL}[\mathbb{P}[\cdot\mid B]\|\mathbb{P}]
&:=\int_{\Omega}\ln\frac{d\mathbb{P}[\cdot\mid B]}{d\mathbb{P}}\,d\mathbb{P}[\cdot\mid B]
=\int_{\Omega}\ln\left(\frac{d\mathbb{P}[\cdot\mid B]}{d\mathbb{P}}\right)\frac{d\mathbb{P}[\cdot\mid B]}{d\mathbb{P}}\,d\mathbb{P}\\
&=\int_{\Omega}\ln\left(\frac{1_{\omega\in B}}{\mathbb{P}[B]}\right)\frac{1_{\omega\in B}}{\mathbb{P}[B]}\,d\mathbb{P}
=-\ln\mathbb{P}[B].
\end{aligned} D K L [ P [ ⋅ ∣ B ] ∥ P ] := ∫ Ω ln d P d P [ ⋅ ∣ B ] d P [ ⋅ ∣ B ] = ∫ Ω ln ( d P d P [ ⋅ ∣ B ] ) d P d P [ ⋅ ∣ B ] d P = ∫ Ω ln ( P [ B ] 1 ω ∈ B ) P [ B ] 1 ω ∈ B d P = − ln P [ B ] . Lemma C.3 (Upper bound on conditional expectation). Let X : Ω → R X : \Omega\to\mathbb{R} X : Ω → R ( Ω , Σ , P ) (\Omega, \Sigma, \mathbb{P}) ( Ω , Σ , P ) Λ : R + → [ 0 , ∞ ) \Lambda: \mathbb{R}^{+} \to[0, \infty) Λ : R + → [ 0 , ∞ ) β ↦ ln E [ exp ( β ( X − E [ X ] ) ) ] \beta\mapsto\ln\mathbb{E}[\exp(\beta(X-\mathbb{E}[X]))] β ↦ ln E [ exp ( β ( X − E [ X ]))] P [ B ] > 0 \mathbb{P}[B] > 0 P [ B ] > 0 P [ ⋅ ∣ B ] \mathbb{P}[\cdot\mid B] P [ ⋅ ∣ B ] Λ ∗ \Lambda^* Λ ∗ X X X ( Λ ∗ ) − 1 ( y ) : = inf { s : Λ ∗ ( s ) ≥ y } (\Lambda^*)^{-1}(y) := \inf\{s : \Lambda^*(s) \ge y\} ( Λ ∗ ) − 1 ( y ) := inf { s : Λ ∗ ( s ) ≥ y }
E [ X ∣ B ] ≤ E [ X ] + ( Λ ∗ ) − 1 ( − ln P [ B ] ) . \mathbb{E}[X \mid B] \le\mathbb{E}[X] + (\Lambda^*)^{-1}(-\ln\mathbb{P}[B]). E [ X ∣ B ] ≤ E [ X ] + ( Λ ∗ ) − 1 ( − ln P [ B ]) . Proof. The proof adapts Lemma 11 of Tarbouriech et al. [31 ] . We apply Lemma C.1 with p ( E ) = P [ E ∣ B ] p(\mathcal{E}) = \mathbb{P}[\mathcal{E} \mid B] p ( E ) = P [ E ∣ B ] q ( E ) = P [ E ] q(\mathcal{E}) = \mathbb{P}[\mathcal{E}] q ( E ) = P [ E ] { λ ( X − E X ) } λ ∈ R + \{\lambda(X-\mathbb{E}X)\}_{\lambda\in\mathbb{R}_{+}} { λ ( X − E X ) } λ ∈ R +
D K L [ P [ ⋅ ∣ B ] ∥ P ] ≥ sup λ ∈ R + { λ E [ X − E [ X ] ∣ B ] − ln E [ exp ( λ ( X − E [ X ] ) ) ] } = sup { λ ( E [ X ∣ B ] − E [ X ] ) − Λ ( λ ) : λ ∈ R + } = Λ ∗ ( E [ X ∣ B ] − E [ X ] ) . \begin{aligned}
D_{KL}[\mathbb{P}[\cdot\mid B] \mathbin{\|} \mathbb{P}] \ge\sup_{\lambda\in\mathbb{R}_{+}} \left\{\lambda\mathbb{E}[X-\mathbb{E}[X] \mid B] - \ln\mathbb{E}[\exp(\lambda(X-\mathbb{E}[X]))]\right\} \\
&= \sup\{\lambda(\mathbb{E}[X \mid B]-\mathbb{E}[X])-\Lambda(\lambda) : \lambda\in\mathbb{R}_{+}\} \\
&= \Lambda^*(\mathbb{E}[X \mid B]-\mathbb{E}[X]).
\end{aligned} D K L [ P [ ⋅ ∣ B ] ∥ P ] ≥ λ ∈ R + sup { λ E [ X − E [ X ] ∣ B ] − ln E [ exp ( λ ( X − E [ X ]))] } = sup { λ ( E [ X ∣ B ] − E [ X ]) − Λ ( λ ) : λ ∈ R + } = Λ ∗ ( E [ X ∣ B ] − E [ X ]) . Furthermore, since the free parameter λ \lambda λ R + \mathbb{R}^{+} R + Λ ∗ \Lambda^* Λ ∗ ( Λ ∗ ) − 1 ( y ) : = inf { s : Λ ∗ ( s ) ≥ y } (\Lambda^*)^{-1}(y) := \inf\{s : \Lambda^*(s) \ge y\} ( Λ ∗ ) − 1 ( y ) := inf { s : Λ ∗ ( s ) ≥ y }
( Λ ∗ ) − 1 ( D K L [ P [ ⋅ ∣ B ] ∥ P ] ) ≥ E [ X ∣ B ] − E [ X ] . (\Lambda^*)^{-1}\left(D_{KL}[\mathbb{P}[\cdot\mid B] \mathbin{\|} \mathbb{P}]\right) \ge\mathbb{E}[X \mid B]-\mathbb{E}[X]. ( Λ ∗ ) − 1 ( D K L [ P [ ⋅ ∣ B ] ∥ P ] ) ≥ E [ X ∣ B ] − E [ X ] . As a final step, we use Lemma C.2 , which states that D K L [ P [ ⋅ ∣ B ] ∥ P ] = − ln P [ B ] D_{KL}[\mathbb{P}[\cdot\mid B] \mathbin{\|} \mathbb{P}] = -\ln\mathbb{P}[B] D K L [ P [ ⋅ ∣ B ] ∥ P ] = − ln P [ B ]
:::
Lemma C.4. Let θ : Ω → R K \theta: \Omega\to\mathbb{R}^{K} θ : Ω → R K ( Λ a ∗ ) − 1 ( − ln p ) ≤ σ a 2 i v ( p ) (\Lambda_a^*)^{-1}(-\ln p) \le\sigma_a\sqrt{2i_v(p)} ( Λ a ∗ ) − 1 ( − ln p ) ≤ σ a 2 i v ( p ) p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 ) V ( p ) : = ∑ a p a ( μ a + σ a 2 i v ( p a ) ) \mathcal{V}(p) := \sum_a p_a(\mu_a+\sigma_a\sqrt{2i_v(p_a)}) V ( p ) := ∑ a p a ( μ a + σ a 2 i v ( p a ) ) p a ∗ : = P [ a ∗ = a ] > 0 p_a^* := \mathbb{P}[a^*=a] > 0 p a ∗ := P [ a ∗ = a ] > 0 q q q v v v
E [ θ a ∗ ] ≤ V ( p ∗ ) ≤ V ( q ) . \mathbb{E}[\theta_{a^*}] \le\mathcal{V}(p^*) \le\mathcal{V}(q). E [ θ a ∗ ] ≤ V ( p ∗ ) ≤ V ( q ) . Proof. First, note that an application of Lemma C.3 gives
E [ θ a ∗ ∣ a ∗ = a ] ≤ μ a + ( Λ a ∗ ) − 1 ( − ln P [ a ∗ = a ] ) ⟹ E [ θ a ∗ ] = ∑ a p a ∗ E [ θ a ∗ ∣ a ∗ = a ] ≤ ∑ a p a ∗ ( μ a + ( Λ a ∗ ) − 1 ( − ln p a ∗ ) ) . \mathbb{E}[\theta_{a^*} \mid a^*=a] \le\mu_a+(\Lambda_a^*)^{-1}(-\ln\mathbb{P}[a^*=a]) \Longrightarrow\mathbb{E}[\theta_{a^*}] = \sum_a p_a^*\mathbb{E}[\theta_{a^*}\mid a^*=a] \le\sum_a p_a^*(\mu_a+(\Lambda_a^*)^{-1}(-\ln p_a^*)). E [ θ a ∗ ∣ a ∗ = a ] ≤ μ a + ( Λ a ∗ ) − 1 ( − ln P [ a ∗ = a ]) ⟹ E [ θ a ∗ ] = a ∑ p a ∗ E [ θ a ∗ ∣ a ∗ = a ] ≤ a ∑ p a ∗ ( μ a + ( Λ a ∗ ) − 1 ( − ln p a ∗ )) . By substituting p = p a ∗ p=p_a^* p = p a ∗ ( Λ a ∗ ) − 1 ( − ln p a ∗ ) ≤ σ a 2 i v ( p a ∗ ) (\Lambda_a^*)^{-1}(-\ln p_a^*) \le\sigma_a\sqrt{2i_v(p_a^*)} ( Λ a ∗ ) − 1 ( − ln p a ∗ ) ≤ σ a 2 i v ( p a ∗ ) E [ θ a ∗ ] ≤ V ( p ∗ ) \mathbb{E}[\theta_{a^*}] \le\mathcal{V}(p^*) E [ θ a ∗ ] ≤ V ( p ∗ ) V ( p ∗ ) ≤ max p ∈ Δ K − 1 V ( p ) = V ( q ) \mathcal{V}(p^*) \le\max_{p\in\Delta^{K-1}}\mathcal{V}(p)=\mathcal{V}(q) V ( p ∗ ) ≤ max p ∈ Δ K − 1 V ( p ) = V ( q ) v v v V \mathcal{V} V [22 ] ).
Lemma C.5 (Restatement of Lemma 4 in Menet et al. [25 ] ). Let θ ∼ N ( μ 0 , Σ 0 ) \theta\sim\mathcal{N}(\mu_0,\Sigma_0) θ ∼ N ( μ 0 , Σ 0 ) K K K σ a , 0 2 ≤ 1 \sigma_{a,0}^2 \le1 σ a , 0 2 ≤ 1 a ∈ [ K ] a \in[K] a ∈ [ K ] L T : = ( a t ) t = 1 T L_T := (a_t)_{t=1}^{T} L T := ( a t ) t = 1 T X a t = θ a t + ε a t X_{a_t}=\theta_{a_t}+\varepsilon_{a_t} X a t = θ a t + ε a t ε a t ∼ N ( 0 , α 2 ) \varepsilon_{a_t}\sim\mathcal{N}(0,\alpha^2) ε a t ∼ N ( 0 , α 2 ) γ T \gamma_T γ T σ a t , t 2 \sigma_{a_t,t}^2 σ a t , t 2
γ T : = max L T I ( X L T ; θ ) ≥ 2 C α ∑ t = 1 T σ a t , t 2 , \gamma_T := \max_{L_T} I(X_{L_T};\theta) \ge\frac{2}{C_\alpha}\sum_{t=1}^{T}\sigma_{a_t,t}^2, γ T := L T max I ( X L T ; θ ) ≥ C α 2 t = 1 ∑ T σ a t , t 2 , where 1 / C α : = ln ( 1 + α − 2 ) 4 1/C_\alpha:= \frac{\ln(1+\alpha^{-2})}{4} 1/ C α := 4 l n ( 1 + α − 2 )
Proof. We restate the proof from Menet et al. [25 ] . The right-hand side is well-defined because the predictive variances σ a t , t 2 \sigma_{a_t,t}^2 σ a t , t 2 L T L_T L T X L T ∣ θ X_{L_T}\mid\theta X L T ∣ θ α 2 \alpha^2 α 2
I ( X L T ; θ ) = H [ X L T ] − H [ X L T ∣ θ ] I(X_{L_T};\theta)=H[X_{L_T}]-H[X_{L_T}\mid\theta] I ( X L T ; θ ) = H [ X L T ] − H [ X L T ∣ θ ] = H [ X L T ] − 1 2 ∑ t = 1 T ln ( 2 π e α 2 ) . =H[X_{L_T}]-\frac{1}{2}\sum_{t=1}^{T}\ln(2\pi e\alpha^2). = H [ X L T ] − 2 1 t = 1 ∑ T ln ( 2 π e α 2 ) . Furthermore, one may decompose
H [ X L t ] = H [ X L t − 1 ] + H [ X a t ∣ X L t − 1 ] = H [ X L t − 1 ] + 1 2 ln ( 2 π e ( α 2 + σ a t , t 2 ) ) , H[X_{L_t}] = H[X_{L_{t-1}}] + H[X_{a_t}\mid X_{L_{t-1}}]
= H[X_{L_{t-1}}] + \frac{1}{2}\ln(2\pi e(\alpha^2+\sigma^2_{a_t,t})), H [ X L t ] = H [ X L t − 1 ] + H [ X a t ∣ X L t − 1 ] = H [ X L t − 1 ] + 2 1 ln ( 2 π e ( α 2 + σ a t , t 2 )) , using that X a t ∣ X L t − 1 X_{a_t}\mid X_{L_{t-1}} X a t ∣ X L t − 1 α 2 + σ a t , t 2 \alpha^2+\sigma^2_{a_t,t} α 2 + σ a t , t 2
I ( X L T ; θ ) = 1 2 ∑ t = 1 T ln ( 1 + α − 2 σ a t , t 2 ) . I(X_{L_T};\theta)=\frac{1}{2}\sum_{t=1}^{T}\ln(1+\alpha^{-2}\sigma^2_{a_t,t}). I ( X L T ; θ ) = 2 1 t = 1 ∑ T ln ( 1 + α − 2 σ a t , t 2 ) . Finally, by assumption σ a t , t 2 ∈ [ 0 , 1 ] \sigma^2_{a_t,t}\in[0,1] σ a t , t 2 ∈ [ 0 , 1 ]
σ a t , t 2 ≤ 1 2 ln ( 1 + α − 2 σ a t , t 2 ) 4 ln ( 1 + α − 2 ) = : C α . \sigma^2_{a_t,t}\leq\frac{1}{2}\ln(1+\alpha^{-2}\sigma^2_{a_t,t})\frac{4}{\ln(1+\alpha^{-2})}=:C_\alpha. σ a t , t 2 ≤ 2 1 ln ( 1 + α − 2 σ a t , t 2 ) ln ( 1 + α − 2 ) 4 =: C α . Indeed, the inequality is tight for σ a t , t 2 ∈ { 0 , 1 } \sigma^2_{a_t,t}\in\{0,1\} σ a t , t 2 ∈ { 0 , 1 }
σ a t , t 2 ↦ ln ( 1 + α − 2 σ a t , t 2 ) − σ a t , t 2 ln ( 1 + α − 2 ) . \sigma^2_{a_t,t}\mapsto\ln(1+\alpha^{-2}\sigma^2_{a_t,t})-\sigma^2_{a_t,t}\ln(1+\alpha^{-2}). σ a t , t 2 ↦ ln ( 1 + α − 2 σ a t , t 2 ) − σ a t , t 2 ln ( 1 + α − 2 ) . Lemma C.6 (Batched generalization of Lemma C.5). Let θ ∼ N ( μ 0 , Σ 0 ) \theta\sim\mathcal{N}(\mu_0,\Sigma_0) θ ∼ N ( μ 0 , Σ 0 ) K K K σ a , 0 2 ≤ 1 \sigma^2_{a,0}\leq1 σ a , 0 2 ≤ 1 a ∈ [ K ] a\in[K] a ∈ [ K ] T = n B T=nB T = n B B B B n n n
Fix a deterministic batched action sequence
x 1 : B = ( x 1 , … , x B ) , x b = ( a b , 1 , … , a b , n ) ∈ [ K ] n . x_{1:B}=(x_1,\ldots,x_B),\qquad x_b=(a_{b,1},\ldots,a_{b,n})\in[K]^n. x 1 : B = ( x 1 , … , x B ) , x b = ( a b , 1 , … , a b , n ) ∈ [ K ] n . Under this fixed design, define
Y b , i x = θ a b , i + ε b , i , ε b , i ∼ i . i . d . N ( 0 , α 2 ) , Y^x_{b,i}=\theta_{a_{b,i}}+\varepsilon_{b,i},\qquad\varepsilon_{b,i}\mathrel{\overset{\mathrm{i.i.d.}}{\sim}}\mathcal{N}(0,\alpha^2), Y b , i x = θ a b , i + ε b , i , ε b , i ∼ i.i.d. N ( 0 , α 2 ) , and let
Y b x = ( Y b , 1 x , … , Y b , n x ) , θ b x = ( θ a b , 1 , … , θ a b , n ) . Y^x_b=(Y^x_{b,1},\ldots,Y^x_{b,n}),\qquad\theta^x_b=(\theta_{a_{b,1}},\ldots,\theta_{a_{b,n}}). Y b x = ( Y b , 1 x , … , Y b , n x ) , θ b x = ( θ a b , 1 , … , θ a b , n ) . Define the posterior covariance matrix at the beginning of batch b b b
Σ b ( x 1 : b ) : = Cov ( θ b x ∣ Y 1 : b − 1 x ) . \Sigma_b(x_{1:b}):=\operatorname{Cov}(\theta^x_b\mid Y^x_{1:b-1}). Σ b ( x 1 : b ) := Cov ( θ b x ∣ Y 1 : b − 1 x ) . Let
γ B : = max x 1 : B I ( Y 1 : B x ; θ ) \gamma_B:=\max_{x_{1:B}} I(Y^x_{1:B};\theta) γ B := x 1 : B max I ( Y 1 : B x ; θ ) be the maximal information gain over B B B x 1 : B x_{1:B} x 1 : B
γ B ≥ C ( n , α ) 2 n ∑ b = 1 B tr ( Σ b ( x 1 : b ) ) , \gamma_B\geq\frac{C(n,\alpha)}{2n}\sum_{b=1}^{B}\operatorname{tr}(\Sigma_b(x_{1:b})), γ B ≥ 2 n C ( n , α ) b = 1 ∑ B tr ( Σ b ( x 1 : b )) , where
C ( n , α ) : = ln ( 1 + n α 2 ) . C(n,\alpha):=\ln\left(1+\frac{n}{\alpha^2}\right). C ( n , α ) := ln ( 1 + α 2 n ) . Proof. Fix an arbitrary deterministic design x 1 : B x_{1:B} x 1 : B
I ( Y 1 : B x ; θ ) = ∑ b = 1 B I ( Y b x ; θ ∣ Y 1 : b − 1 x ) = 1 2 ∑ b = 1 B ln det ( I n + α − 2 Σ b ( x 1 : b ) ) . (60) \begin{aligned}
I(Y^x_{1:B};\theta)=\sum_{b=1}^{B}I(Y^x_b;\theta\mid Y^x_{1:b-1}) \\
&=\frac{1}{2}\sum_{b=1}^{B}\ln\det\left(I_n+\alpha^{-2}\Sigma_b(x_{1:b})\right). \tag*{(60)}
\end{aligned} I ( Y 1 : B x ; θ ) = b = 1 ∑ B I ( Y b x ; θ ∣ Y 1 : b − 1 x ) = 2 1 b = 1 ∑ B ln det ( I n + α − 2 Σ b ( x 1 : b ) ) . (60) The second equality follows because, conditionally on Y 1 : b − 1 x Y_{1:b-1}^{x} Y 1 : b − 1 x Y b x Y_b^{x} Y b x
Σ b ( x 1 : b ) + α 2 I n , \Sigma_b(x_{1:b})+\alpha^2 I_n, Σ b ( x 1 : b ) + α 2 I n , whereas, conditionally on both θ \theta θ Y 1 : b − 1 x Y_{1:b-1}^{x} Y 1 : b − 1 x α 2 I n \alpha^2 I_n α 2 I n
Since Σ b ( x 1 : b ) \Sigma_b(x_{1:b}) Σ b ( x 1 : b )
det ( I n + α − 2 Σ b ( x 1 : b ) ) ≥ 1 + tr ( Σ b ( x 1 : b ) ) α 2 . \det\left(I_n+\alpha^{-2}\Sigma_b(x_{1:b})\right)\ge1+\frac{\operatorname{tr}(\Sigma_b(x_{1:b}))}{\alpha^2}. det ( I n + α − 2 Σ b ( x 1 : b ) ) ≥ 1 + α 2 tr ( Σ b ( x 1 : b )) . Moreover, posterior marginal variances do not exceed their corresponding prior variances, and hence
0 ≤ tr ( Σ b ( x 1 : b ) ) ≤ n . 0\le\operatorname{tr}(\Sigma_b(x_{1:b}))\le n. 0 ≤ tr ( Σ b ( x 1 : b )) ≤ n . By concavity of z ↦ ln ( 1 + z ) z\mapsto\ln(1+z) z ↦ ln ( 1 + z ) [ 0 , n / α 2 ] [0,n/\alpha^2] [ 0 , n / α 2 ]
ln det ( I n + α − 2 Σ b ( x 1 : b ) ) ≥ ln ( 1 + tr ( Σ b ( x 1 : b ) ) α 2 ) (61) \ln\det\left(I_n+\alpha^{-2}\Sigma_b(x_{1:b})\right)\ge\ln\left(1+\frac{\operatorname{tr}(\Sigma_b(x_{1:b}))}{\alpha^2}\right) \tag*{(61)} ln det ( I n + α − 2 Σ b ( x 1 : b ) ) ≥ ln ( 1 + α 2 tr ( Σ b ( x 1 : b )) ) (61) ≥ tr ( Σ b ( x 1 : b ) ) n ln ( 1 + n α 2 ) . (62) \ge\frac{\operatorname{tr}(\Sigma_b(x_{1:b}))}{n}\ln\left(1+\frac{n}{\alpha^2}\right). \tag*{(62)} ≥ n tr ( Σ b ( x 1 : b )) ln ( 1 + α 2 n ) . (62) Substituting this inequality into Equation (60) gives
I ( Y 1 : B x ; θ ) ≥ C ( n , α ) 2 n ∑ b = 1 B tr ( Σ b ( x 1 : b ) ) . I\left(Y_{1:B}^{x};\theta\right)\ge\frac{C(n,\alpha)}{2n}\sum_{b=1}^{B}\operatorname{tr}(\Sigma_b(x_{1:b})). I ( Y 1 : B x ; θ ) ≥ 2 n C ( n , α ) b = 1 ∑ B tr ( Σ b ( x 1 : b )) . Finally, since
γ B = max x 1 : B I ( Y 1 : B x ; θ ) , \gamma_B=\max_{x_{1:B}} I\left(Y_{1:B}^{x};\theta\right), γ B = x 1 : B max I ( Y 1 : B x ; θ ) , we have
γ B ≥ I ( Y 1 : B x ; θ ) \gamma_B\ge I\left(Y_{1:B}^{x};\theta\right) γ B ≥ I ( Y 1 : B x ; θ ) for every fixed design x 1 : B x_{1:B} x 1 : B □ \square □
Additional Experiments
Role of relevance threshold
Inversion for v = Φ v=\Phi v = Φ We evaluate the effect of estimating the sampling probabilities in three Gaussian bandit environments: K = 2 K=2 K = 2 μ = ( 1 / 2 , 1 ) \mu=(1/2,1) μ = ( 1/2 , 1 ) K = 4 K=4 K = 4 μ = ( 0 , 1 / 3 , 2 / 3 , 1 ) \mu=(0,1/3,2/3,1) μ = ( 0 , 1/3 , 2/3 , 1 ) K = 8 K=8 K = 8
μ a = 1 − 0.1 ( a − 1 ) , a ∈ [ K ] . \mu_a=1-0.1(a-1),\qquad a\in[K]. μ a = 1 − 0.1 ( a − 1 ) , a ∈ [ K ] . For every trajectory and round, we generate a sequence of 500 auxiliary categorical samples from the exact Φ \Phi Φ q ^ t \widehat{q}_t q t m ∈ { 100 , 200 , 500 } m\in\{100,200,500\} m ∈ { 100 , 200 , 500 }
η = max t ≤ T max a ∈ [ K ] ∣ q ^ a , t − q a , t ∣ . \eta=\max_{t\le T}\max_{a\in[K]}\left|\widehat{q}_{a,t}-q_{a,t}\right|. η = t ≤ T max a ∈ [ K ] max ∣ q a , t − q a , t ∣ . Following the formulation of Theorem 4.1, inversion is performed on the enlarged practical relevance set M ^ T γ − η \widehat{\mathcal{M}}_{T}^{\gamma-\eta} M T γ − η 2 η < γ 2\eta<\gamma 2 η < γ c γ − 2 η c_{\gamma-2\eta} c γ − 2 η
Figure 4 illustrates the resulting conditioning–coverage trade-off. Increasing m m m c γ − 2 η c_{\gamma-2\eta} c γ − 2 η c γ c_{\gamma} c γ c γ − 2 η η c_{\gamma-2\eta}\eta c γ − 2 η η 2 η < γ 2\eta<\gamma 2 η < γ K K K T = 2000 T=2000 T = 2000
Figure 4. Conservative non-batched inversion for Φ \Phi Φ K ∈ { 2 , 4 , 8 } K \in\{2, 4, 8\} K ∈ { 2 , 4 , 8 } m ∈ { 100 , 200 , 500 } m \in\{100, 200, 500\} m ∈ { 100 , 200 , 500 } c γ c_\gamma c γ c γ − 2 η c_{\gamma-2\eta} c γ − 2 η c γ − 2 η η c_{\gamma-2\eta}\eta c γ − 2 η η L ^ T γ − η \widehat{L}_T^{\gamma-\eta} L T γ − η E ^ T γ − η \widehat{E}_T^{\gamma-\eta} E T γ − η M ^ T γ − η \widehat{M}_T^{\gamma-\eta} M T γ − η ∣ M ^ T γ − η ∖ M T γ ∣ / T |\widehat{M}_T^{\gamma-\eta} \setminus M_T^\gamma|/T ∣ M T γ − η ∖ M T γ ∣/ T 2 η < γ 2\eta< \gamma 2 η < γ
Inversion for ν = Ψ \nu= \Psi ν = Ψ We repeat the same experiment using Ψ \Psi Ψ m ∈ { 100 , 200 , 500 } m \in\{100, 200, 500\} m ∈ { 100 , 200 , 500 } q ^ \widehat{q} q η \eta η M T γ M_T^\gamma M T γ
Figure 5 shows the stronger sensitivity of Ψ − 1 \Psi^{-1} Ψ − 1 c γ − 2 η c_{\gamma-2\eta} c γ − 2 η c γ − 2 η η c_{\gamma-2\eta}\eta c γ − 2 η η Φ \Phi Φ m m m Φ \Phi Φ 2 η < γ 2\eta< \gamma 2 η < γ K = 8 K = 8 K = 8 m = 100 m = 100 m = 100 Ψ \Psi Ψ
Figure 5. Conservative non-batched inversion for Ψ \Psi Ψ K ∈ { 2 , 4 , 8 } K \in\{2, 4, 8\} K ∈ { 2 , 4 , 8 } m ∈ { 100 , 200 , 500 } m \in\{100, 200, 500\} m ∈ { 100 , 200 , 500 } c γ c_\gamma c γ c γ − 2 η c_{\gamma-2\eta} c γ − 2 η c γ − 2 η η c_{\gamma-2\eta}\eta c γ − 2 η η L ^ T γ − η \widehat{L}^{\gamma-\eta}_T L T γ − η E ^ T γ − η \widehat{\mathcal{E}}^{\gamma-\eta}_T E T γ − η M ^ T γ − η \widehat{\mathcal{M}}^{\gamma-\eta}_T M T γ − η ∣ M ^ T γ − η ∖ M T γ ∣ / T |\widehat{\mathcal{M}}^{\gamma-\eta}_T \setminus\mathcal{M}^{\gamma}_T|/T ∣ M T γ − η ∖ M T γ ∣/ T 2 η < γ 2\eta< \gamma 2 η < γ
Batched algorithms
Batched Φ \Phi Φ We also evaluate the role of the threshold when the demonstrator updates its sampling policy only at batch boundaries. Within a batch of size n n n
q ^ a , b = 1 n ∑ t ∈ B b 1 { A t = a } . \widehat{q}_{a,b} = \frac{1}{n}\sum_{t \in\mathcal{B}_b} \mathbb{1}\{A_t = a\}. q a , b = n 1 t ∈ B b ∑ 1 { A t = a } . We consider n ∈ { 500 , 1000 , 2000 } n \in\{500, 1000, 2000\} n ∈ { 500 , 1000 , 2000 } q ^ \widehat{q} q q q q
η = max t , a ∣ q ^ a , t − q a , t ∣ \eta= \max_{t,a} \left|\widehat{q}_{a,t} - q_{a,t}\right| η = t , a max ∣ q a , t − q a , t ∣ and to provide an oracle coverage comparison. Figure 6 reports the resulting conditioning quantities, inversion errors, and coverage. Quantities involving c γ − 2 η c_{\gamma-2\eta} c γ − 2 η 2 η < γ 2\eta< \gamma 2 η < γ q ^ \widehat{q} q q q q T = 20000 T = 20000 T = 20000
Figure 6. Batched iLITE-Φ \Phi Φ K ∈ { 2 , 4 , 8 } K \in\{2,4,8\} K ∈ { 2 , 4 , 8 } T = 20000 T = 20000 T = 20000 n ∈ { 500 , 1000 , 2000 } n \in\{500,1000,2000\} n ∈ { 500 , 1000 , 2000 } c γ c_\gamma c γ c γ − 2 η c_{\gamma-2\eta} c γ − 2 η c γ − 2 η η c_{\gamma-2\eta}\eta c γ − 2 η η L ^ T γ − η \widehat{L}_T^{\gamma-\eta} L T γ − η E ^ T γ − η \widehat{E}_T^{\gamma-\eta} E T γ − η M ^ T γ − η \widehat{\mathcal{M}}_T^{\gamma-\eta} M T γ − η ∣ M ^ T γ − η ∖ M T γ ∣ / T \lvert\widehat{\mathcal{M}}_T^{\gamma-\eta}\setminus\mathcal{M}_T^\gamma\rvert/T ∣ M T γ − η ∖ M T γ ∣ / T 2 η < γ 2\eta< \gamma 2 η < γ
Batched Ψ \Psi Ψ Figure 7 repeats the conditioning experiment for batched Ψ \Psi Ψ
Figure 7. Batched Ψ \Psi Ψ K ∈ { 2 , 4 , 8 } K \in\{2,4,8\} K ∈ { 2 , 4 , 8 } T = 20000 T = 20000 T = 20000 n ∈ { 500 , 1000 , 2000 } n \in\{500,1000,2000\} n ∈ { 500 , 1000 , 2000 } c γ c_\gamma c γ c γ − 2 η c_{\gamma-2\eta} c γ − 2 η c γ − 2 η η c_{\gamma-2\eta}\eta c γ − 2 η η L ^ T γ − η \widehat{L}_T^{\gamma-\eta} L T γ − η E ^ T γ − η \widehat{E}_T^{\gamma-\eta} E T γ − η M ^ T γ − η \widehat{\mathcal{M}}_T^{\gamma-\eta} M T γ − η ∣ M ^ T γ − η ∖ M T γ ∣ / T \lvert\widehat{\mathcal{M}}_T^{\gamma-\eta}\setminus\mathcal{M}_T^\gamma\rvert/T ∣ M T γ − η ∖ M T γ ∣ / T 2 η < γ 2\eta< \gamma 2 η < γ
Sliding windows
We also study inversion when the observer has access only to the action trajectory and estimates the current sampling probabilities from a causal sliding window. For window length n ∈ { 20 , 50 , 100 } n \in\{20, 50, 100\} n ∈ { 20 , 50 , 100 }
q ^ a , t ( n ) = 1 n ∑ s = t − n t − 1 1 { A s = a } , t > n . \widehat{q}^{(n)}_{a,t} = \frac{1}{n}\sum_{s=t-n}^{t-1}\mathbb{1}\{A_s=a\}, \qquad t>n. q a , t ( n ) = n 1 s = t − n ∑ t − 1 1 { A s = a } , t > n . Thus, q ^ a , t ( n ) \widehat{q}^{(n)}_{a,t} q a , t ( n ) a a a n n n q ^ t \widehat{q}_t q t q t q_t q t
We evaluate all window sizes on the common interval t ≥ 101 t \ge101 t ≥ 101 T = 20,000 T = 20{,}000 T = 20 , 000 η t = max a ∈ [ K ] ∣ q ^ a , t − q a , t ∣ \eta_t = \max_{a\in[K]}|\widehat{q}_{a,t}-q_{a,t}| η t = max a ∈ [ K ] ∣ q a , t − q a , t ∣ 2 η t < γ 2\eta_t < \gamma 2 η t < γ γ = 0.20 \gamma=0.20 γ = 0.20 q ^ \widehat{q} q q q q η t \eta_t η t γ / 2 \gamma/2 γ /2 t t t 2 max 101 ≤ s ≤ t η s < γ 2\max_{101\le s\le t}\eta_s < \gamma 2 max 101 ≤ s ≤ t η s < γ q ^ \widehat{q} q q q q Φ \Phi Φ Ψ \Psi Ψ
(ε , ε ~ \varepsilon,\widetilde{\varepsilon} ε , ε
We empirically test Definition 4.3 for some common algorithms: TS, Maillard sampling (MS) [19 , 3 ] , and Boltzmann-Gumbel exploration (BGE) [5 ] with the Φ \Phi Φ Ψ \Psi Ψ ∣ Δ a , t L S − Δ a , t a ∣ |\Delta^{\mathrm{LS}}_{a,t}-\Delta^{a}_{a,t}| ∣ Δ a , t LS − Δ a , t a ∣ max a ∣ p a , t − q a , t ∣ \max_a|p_{a,t}-q_{a,t}| max a ∣ p a , t − q a , t ∣ Φ \Phi Φ Ψ \Psi Ψ K = 2 K=2 K = 2 μ = ( 1 / 2 , 1 ) \mu=(1/2,1) μ = ( 1/2 , 1 ) K = 4 K=4 K = 4 μ = ( 0 , 1 / 3 , 2 / 3 , 1 ) \mu=(0,1/3,2/3,1) μ = ( 0 , 1/3 , 2/3 , 1 ) K = 8 K = 8 K = 8
μ a = 1 − 0.1 ( a − 1 ) , a ∈ [ K ] , \mu_a = 1 - 0.1(a - 1), \qquad a \in[K], μ a = 1 − 0.1 ( a − 1 ) , a ∈ [ K ] , corresponding to μ = ( 1 , 0.9 , … , 0.3 ) \mu= (1,0.9,\ldots,0.3) μ = ( 1 , 0.9 , … , 0.3 ) α 2 = 1 \alpha^2 = 1 α 2 = 1
Figure 14 separates discrepancies in the internal gap estimates from discrepancies in the resulting sampling policies. Since TS, Φ \Phi Φ Ψ \Psi Ψ K K K K K K t = K t = K t = K Ψ \Psi Ψ K K K
Figure 14. Same-history discrepancies relative to the Φ \Phi Φ Ψ \Psi Ψ K ∈ { 2 , 4 , 8 } K \in\{2,4,8\} K ∈ { 2 , 4 , 8 } T = 2000 T = 2000 T = 2000 ∣ Δ a , t , t r e f − Δ a , t A ∣ \lvert\Delta^{\mathrm{ref}}_{a,t,t}-\Delta^{A}_{a,t}\rvert ∣ Δ a , t , t ref − Δ a , t A ∣ max a ∈ [ K ] ∣ p a , t A − q a , t r e f ∣ \max_{a\in[K]}\lvert p^{A}_{a,t}-q^{\mathrm{ref}}_{a,t}\rvert max a ∈ [ K ] ∣ p a , t A − q a , t ref ∣ t = K t=K t = K
End-to-end inversion v = Ψ v=\Psi v = Ψ We next evaluate the complete inversion procedure for TS, MS, and BGE at the fixed relevance threshold γ = 0.4 \gamma=0.4 γ = 0.4 ( ε , ε ~ ) (\varepsilon,\tilde{\varepsilon}) ( ε , ε ~ ) ε \varepsilon ε Ψ \Psi Ψ ε ~ \tilde{\varepsilon} ε ~ Ψ \Psi Ψ
Figures 15–17 show a clear dependence on the number of arms. For K = 2 K=2 K = 2 K = 4 K=4 K = 4 E t γ \mathcal{E}_t^\gamma E t γ K = 8 K=8 K = 8 γ = 0.4 \gamma=0.4 γ = 0.4
End-to-end inversion for v = Φ v=\Phi v = Φ Figures 18–20 complement the corresponding Ψ \Psi Ψ K = 2 K=2 K = 2 Ψ \Psi Ψ K = 4 K=4 K = 4 E t γ \mathcal{E}_t^\gamma E t γ Ψ − 1 \Psi^{-1} Ψ − 1 Φ \Phi Φ Φ − 1 \Phi^{-1} Φ − 1 Ψ \Psi Ψ Φ \Phi Φ Ψ − 1 \Psi^{-1} Ψ − 1
Figure 9. Sliding-window inversion for Φ \Phi Φ K = 4 K = 4 K = 4
For K = 8 K = 8 K = 8 γ = 0.4 \gamma= 0.4 γ = 0.4 v = Φ v = \Phi v = Φ 2 ϵ < γ 2\epsilon< \gamma 2 ϵ < γ Φ \Phi Φ Ψ \Psi Ψ K K K
Robustness to misspecification
We evaluate the effect of misspecifying the inverse learner’s Gaussian prior variance for K = 4 K = 4 K = 4 T = 2000 T = 2000 T = 2000 Figure 21 and Figure 22 , we multiply the prior variance of one arm by ρ ∈ { 0.25 , 0.5 , 2 , 4 } \rho\in\{0.25, 0.5, 2, 4\} ρ ∈ { 0.25 , 0.5 , 2 , 4 } σ a , 0 2 = 1 \sigma_{a,0}^{2} = 1 σ a , 0 2 = 1 σ ~ a , 0 2 = ρ σ a , 0 2 \widetilde{\sigma}_{a,0}^{2} = \rho\sigma_{a,0}^{2} σ a , 0 2 = ρ σ a , 0 2 (2) : as an arm’s pull count grows, the data-dependent term increasingly dominates the prior-variance contribution, reducing the influence of the initial misspecification. The effect is most pronounced when the best arm’s prior variance is perturbed, because the best arm enters the gap comparison at every relevant round. Results are averaged over 100 independent trajectories; shaded regions show 95% confidence intervals.
Figure 21. Running conditional inversion error under prior-variance misspecification for Φ \Phi Φ ρ \rho ρ σ ~ a , 0 2 = ρ σ a , 0 2 \widetilde{\sigma}^{2}_{a,0}=\rho\sigma^{2}_{a,0} σ a , 0 2 = ρ σ a , 0 2
Figure 22. Running conditional inversion error under prior-variance misspecification for Ψ \Psi Ψ Figure 21 .
Figure 10. Sliding-window inversion for Φ \Phi Φ K = 8 K = 8 K = 8 Figure 8 .
Figure 8. Sliding-window inversion for Φ \Phi Φ K = 2 K=2 K = 2 T = 20,000 T=20{,}000 T = 20 , 000 γ = 0.20 \gamma=0.20 γ = 0.20 n ∈ { 20 , 50 , 100 } n\in\{20,50,100\} n ∈ { 20 , 50 , 100 }
Figure 12. Sliding-window inversion for Ψ \Psi Ψ K = 4 K = 4 K = 4 Figure 11 .
Figure 11. Sliding-window inversion for Ψ \Psi Ψ K = 2 K = 2 K = 2 T = 20,000 T = 20{,}000 T = 20 , 000 γ = 0.20 \gamma= 0.20 γ = 0.20 n ∈ { 20 , 50 , 100 } n \in\{20, 50, 100\} n ∈ { 20 , 50 , 100 }
Figure 13. Sliding-window inversion for Ψ \Psi Ψ K = 8 K = 8 K = 8
Figure 15. Fixed-threshold inversion with v = Ψ v=\Psi v = Ψ K = 2 K=2 K = 2 T = 2000 T=2000 T = 2000 γ = 0.4 \gamma=0.4 γ = 0.4 Φ \Phi Φ L t γ L^\gamma_t L t γ 1 − B t / t 1-B_t/t 1 − B t / t ∣ M t γ ∣ / t \lvert\mathcal{M}^\gamma_t\rvert/t ∣ M t γ ∣ / t E t γ \mathcal{E}^\gamma_t E t γ 2 ε < γ 2\varepsilon<\gamma 2 ε < γ
Figure 16. Fixed-threshold inversion with v = Ψ v = \Psi v = Ψ K = 4 K = 4 K = 4 T = 2000 T = 2000 T = 2000 γ = 0.4 \gamma= 0.4 γ = 0.4 L t γ L_t^\gamma L t γ E t γ \mathcal{E}_t^\gamma E t γ Φ \Phi Φ Ψ − 1 \Psi^{-1} Ψ − 1 2 ϵ < γ 2\epsilon< \gamma 2 ϵ < γ
Figure 17. Fixed-threshold inversion with v = Ψ v = \Psi v = Ψ K = 8 K = 8 K = 8 T = 2000 T = 2000 T = 2000 γ = 0.4 \gamma= 0.4 γ = 0.4 Φ \Phi Φ 2 ϵ < γ 2\epsilon< \gamma 2 ϵ < γ
Figure 18. Fixed-threshold inversion with v = Φ v = \Phi v = Φ K = 2 K = 2 K = 2 T = 2000 T = 2000 T = 2000 γ = 0.4 \gamma= 0.4 γ = 0.4 Ψ \Psi Ψ L t γ L_t^\gamma L t γ 1 − B t / t 1 - B_t/t 1 − B t / t ∣ M t γ ∣ / t |M_t^\gamma|/t ∣ M t γ ∣/ t E t γ \mathcal{E}_t^\gamma E t γ 2 ϵ < γ 2\epsilon< \gamma 2 ϵ < γ
Figure 19. Fixed-threshold inversion with v = Φ v = \Phi v = Φ K = 4 K = 4 K = 4 T = 2000 T = 2000 T = 2000 γ = 0.4 \gamma= 0.4 γ = 0.4 L t γ L_t^\gamma L t γ E t γ \mathcal{E}_t^\gamma E t γ Ψ \Psi Ψ Φ − 1 \Phi^{-1} Φ − 1 2 ϵ < γ 2\epsilon< \gamma 2 ϵ < γ
Figure 20. Fixed-threshold inversion with v = Φ v = \Phi v = Φ K = 8 K = 8 K = 8 T = 2000 T = 2000 T = 2000 γ = 0.4 \gamma= 0.4 γ = 0.4 L t γ L_t^\gamma L t γ E t γ \mathcal{E}_t^\gamma E t γ Ψ \Psi Ψ 2 ε < γ 2\varepsilon< \gamma 2 ε < γ
