Classical inverse bandit methods typically aim to recover true reward parameters. In contrast, we infer a demonstrator's subjective beliefs, specifically its internal estimates of suboptimality gaps. We consider no-regret demonstrators that follow randomized policies, such as Thompson sampling, and characterize a family of algorithms for which per-step inversion is possible. This enables gap estimates to be recovered directly from the arm-selection distribution. Our analysis identifies an inherent stability-coverage trade-off: inversion becomes ill-conditioned as the demonstrator concentrates its probability mass on a single arm, while the number of informative rounds depends on the rate at which its policy converges. We establish conditions under which inversion is reliable and provide theoretical guarantees on the resulting estimation error. Experiments on simulated data support the analysis and illustrate how these conditions affect gap recovery in practice.
Figures & tables
Figure 1: Batched Ψ -LS for n∈{500,1000,2000} , over 100 trajectories. Here, η is the realized uniform error of the within-batch frequency estimator. Panel (a) compares cγ with cγ−2η , and Panel (b) reports the stability factor cγ−2ηη . Panel (c) shows the conditional and coverage-weighted inversion errors, LTγ−η and ETγ−η , computed on the practical relevance set MTγ−η . Panel (d) reports the excess coverage ∣MTγ−η∖MTγ∣/T . Quantities are reported only for trajectories satisfying 2η<γ ; shaded regions in Panels (c)–(d) are pointwise 95% confidence intervals.
Figure 2: End-to-end inversion for v=Ψ , K=4 , T=2000 , and γ=0.4 . The panels show conditional inversion error Ltγ , the fractions of non-reference and relevant rounds, and coverage-weighted error Etγ . Here Bt=∑s=1t\mathbbm1{As=a∗} counts pulls of the estimated best, or reference, arm. Solid and dotted curves in the middle panel denote 1−Bt/t and ∣Mtγ∣/t , respectively. Shading gives pointwise 95% confidence intervals over theorem-valid trajectories.
Appendix figures & tables20 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Error amplification under inversion for two reference CDFs, v=Φ (Gaussian) and v=Ψ . The same estimation error ∣q^−q∣<η is harmless inside the relevant interval (γ,1−γ) but produces unbounded gap errors outside it.
Figure 4: Conservative non-batched inversion for Φ -LS with K∈{2,4,8} (left to right) and m∈{100,200,500} . Panel (a) compares the intrinsic inverse-CDF slope cγ with the median effective slope cγ−2η . Panel (b) reports the median stability factor cγ−2ηη . Panel (c) reports the practical conditional and coverage-weighted inversion errors, LTγ−η and ETγ−η , computed on MTγ−η . Panel (d) reports the excess coverage ∣MTγ−η∖MTγ∣/T . Curves are shown only when at least ten of the 100 trajectories satisfy 2η<γ ; shaded regions in Panels (c)–(d) are pointwise 95% confidence intervals.
Figure 5: Conservative non-batched inversion for Ψ -LS with K∈{2,4,8} (left to right) and m∈{100,200,500} . Panels (a)–(d) report, respectively, cγ and the median cγ−2η , the median stability factor cγ−2ηη , the practical inversion errors LTγ−η and ETγ−η on MTγ−η , and the excess coverage ∣MTγ−η∖MTγ∣/T . Curves are shown only when at least ten trajectories satisfy 2η<γ ; shaded regions in Panels (c)–(d) are pointwise 95% confidence intervals over the valid trajectories.
Figure 6: Batched iLITE- Φ conditioning and inversion results for K∈{2,4,8} (left to right), T=20000 , and batch sizes n∈{500,1000,2000} . Panel (a) compares cγ with cγ−2η , and Panel (b) reports the stability factor cγ−2ηη . Panel (c) shows the conditional and coverage-weighted inversion errors, LTγ−η and ETγ−η , computed on the practical relevance set MTγ−η . Panel (d) reports the excess coverage ∣MTγ−η∖MTγ∣/T . Quantities are reported only for trajectories satisfying 2η<γ ; shaded regions in Panels (c)–(d) are pointwise 95% confidence intervals.
Figure 7: Batched Ψ -LS conditioning experiment for K∈{2,4,8} (left to right), T=20000 , and batch sizes n∈{500,1000,2000} . Panel (a) compares cγ with cγ−2η , and Panel (b) reports the stability factor cγ−2ηη . Panel (c) shows the conditional and coverage-weighted inversion errors, LTγ−η and ETγ−η , computed on the practical relevance set MTγ−η . Panel (d) reports the excess coverage ∣MTγ−η∖MTγ∣/T . Quantities are reported only for trajectories satisfying 2η<γ ; shaded regions in Panels (c)–(d) are pointwise 95% confidence intervals.
Figure 8: Sliding-window inversion for Φ -LS with K=2 , T=20,000 , γ=0.20 , and n∈{20,50,100} , averaged over 100 trajectories. Panels (a)–(d) show pointwise probability error, local and running-uniform validity, inversion error, and empirical versus oracle relevance coverage, respectively.
Figure 9: Sliding-window inversion for Φ -LS with K=4 . The remaining settings and panels are the same as in Figure 8 .
Figure 10: Sliding-window inversion for Φ -LS with K=8 . The remaining settings and panels are the same as in Figure 8 .
Figure 11: Sliding-window inversion for Ψ -LS with K=2 , T=20,000 , γ=0.20 , and n∈{20,50,100} , averaged over 100 trajectories. Panels (a)–(d) show pointwise probability error, local and running-uniform validity, inversion error, and empirical versus oracle relevance coverage, respectively.
Figure 12: Sliding-window inversion for Ψ -LS with K=4 . The remaining settings and panels are the same as in Figure 11 .
Figure 13: Sliding-window inversion for Ψ -LS with K=8 . The remaining settings and panels are the same as in Figure 11 .
Figure 14: Same-history discrepancies relative to the Φ -LS reference (left) and the Ψ -LS reference (right), for K∈{2,4,8} and T=2000 . The upper panels report the played-arm gap discrepancy ∣Δat,tref−Δat,tA∣ , while the lower panels report the maximum sampling-policy discrepancy maxa∈[K]∣pa,tA−qa,tref∣ . For each candidate trajectory, the reference policy is evaluated on the same realized action-reward history using exact sampling probabilities. Curves show the mean over 100 simulations and shaded regions show pointwise 95% confidence intervals. The horizontal axis begins at t=K , marking the end of the forced initialization used by MS and BGE.
Figure 15: Fixed-threshold inversion with v=Ψ for K=2 , T=2000 , and γ=0.4 . We invert TS, MS, BGE, and a Φ -LS demonstrator using the exact sampling probabilities. The panels report the conditional inversion error Ltγ , the non-reference pull fraction 1−Bt/t and relevant-round fraction ∣Mtγ∣/t , and the coverage-weighted error Etγ . Curves are restricted to trajectories satisfying 2ε<γ ; shaded regions are pointwise 95% confidence intervals.
Figure 16: Fixed-threshold inversion with v=Ψ for K=4 , T=2000 , and γ=0.4 . The panels respectively report Ltγ , the fractions of non-reference and relevant rounds, and Etγ . The blue curve corresponds to a Φ -LS demonstrator inverted using Ψ−1 and therefore isolates inverse-CDF misspecification. Exact sampling probabilities are used, and only trajectories satisfying 2ε<γ contribute. Shaded regions are pointwise 95% confidence intervals.
Figure 17: Fixed-threshold inversion with v=Ψ for K=8 , T=2000 , and γ=0.4 . The three panels show the conditional inversion error, the decomposition into non-reference and relevant rounds, and the coverage-weighted inversion error. The Φ -LS curve illustrates inversion using a misspecified inverse CDF. Results use exact sampling probabilities and are restricted to trajectories satisfying 2ε<γ . Shaded regions are pointwise 95% confidence intervals.
Figure 18: Fixed-threshold inversion with v=Φ for K=2 , T=2000 , and γ=0.4 . We invert TS, MS, BGE, and a Ψ -LS demonstrator using the exact sampling probabilities. The left panel reports the conditional inversion error Ltγ . The central panel shows the fraction of non-reference pulls, 1−Bt/t , together with the relevant-round fraction ∣Mtγ∣/t . The right panel reports the coverage-weighted error Etγ . Curves are computed over trajectories satisfying 2ε<γ ; shaded regions are pointwise 95% confidence intervals.
Figure 19: Fixed-threshold inversion with v=Φ for K=4 , T=2000 , and γ=0.4 . The panels respectively report the conditional inversion error Ltγ , the non-reference and relevant-round fractions, and the coverage-weighted error Etγ . The blue curve corresponds to a Ψ -LS demonstrator inverted using Φ−1 . Exact sampling probabilities are used, and only trajectories satisfying 2ε<γ contribute to each curve. Shaded regions are pointwise 95% confidence intervals.
Figure 20: Fixed-threshold inversion with v=Φ for K=8 , T=2000 , and γ=0.4 . The three panels show Ltγ , the fractions of non-reference and relevant rounds, and Etγ . The Ψ -LS curve illustrates inversion under inverse-CDF misspecification. Results use exact sampling probabilities and are restricted to trajectories satisfying 2ε<γ . For MS, this condition holds for only a small number of trajectories. Shaded regions are pointwise 95% confidence intervals.
Figure 21: Running conditional inversion error under prior-variance misspecification for Φ -LS. Each panel perturbs the inverse learner’s prior variance for the indicated arm; ρ denotes the multiplier in σa,02=ρσa,02 . The dashed curve is the correctly specified prior baseline.
Figure 22: Running conditional inversion error under prior-variance misspecification for Ψ -LS. The setup and conventions are the same as in Figure 21 .
Inverse optimization (IO) seeks to infer the parameters of a decision-maker's objective from observed context--action data. We study noiseless IO, where demonstrations are generated by a ground-truth objective. We provide a high-probability O(Td) generalization bound for the induced action set, where d is the number of unknown parameters and T is the size of the training dataset. We strengthen these guarantees under additional conditions that ensure uniqueness of the chosen action, bringing our IO guarantees in line with best-arm identification results in the bandit literature. We further show that the O(Td) rate is tight over all consistent estimators considered here, and extend the result to both instantaneous and cumulative regret. Notably, the resulting regret lower bound matches the corresponding upper bounds in the adversarial setting, indicating that the stochastic IO setting is effectively adversarial for the class of estimators studied here. Finally, we propose a parameter-free algorithm with lower per-iteration complexity than generic solvers. Experiments validate the predicted rates and illustrate the tightness of our bounds.
Pouria Fatemi, Hoomaan Maskan, Suvrit Sra +1
Technical University of Munich, Germany · Uppsala University, Sweden · University of Toronto, Canada
Multi-arm bandit algorithms are increasingly used in online platforms, clinical trials, and social science experiments, but valid statistical inference on their performance remains an open challenge. After deploying bandits, a natural question is whether one can construct a confidence interval for its mean reward and assess whether it reliably outperforms a baseline policy. The total reward achieved in any single bandit deployment is random, and deploying a bandit twice on the same population typically yields different reward trajectories due to stochastic rewards. Standard statistical inference methods cannot be used because bandit algorithms introduce complex dependencies in the collected data, which violate the i.i.d. assumption underlying many classical approaches. Moreover, existing inference methods for adaptively collected data only apply to estimands that do not depend on the data-collection algorithm (such as the mean reward under a fixed action). We propose Bandit Simulation for Inference (BSI), a framework that fits a simulator of the bandit environment from observed data--either on-policy or off-policy--and uses it to estimate the mean reward under any evaluation policy, including adaptive blackbox algorithms. BSI formally propagates uncertainty in the estimated simulator parameters into the confidence interval construction. Furthermore, for BSI to be valid, it requires only weak exploration assumptions on the behavior policy and avoids importance weighting. We prove that BSI yields asymptotically valid confidence intervals, and demonstrate empirically that it maintains nominal coverage in settings where standard off-policy evaluation methods fail.
Statistical inference with bandit data presents fundamental challenges owing to adaptive sampling, which violates the independence assumptions underlying classical asymptotic theory. Recent work has identified stability~\citep{laiwei82} as a sufficient condition for valid inference under adaptivity. This paper first provides a refined stability condition, stated in terms of the iterates of an online algorithm, and shows that a large class of regularized stochastic-mirror-descent-style algorithms satisfy it. This refined condition allows us to strengthen the asymptotic results of~\citet{laiwei82} in several ways. First, we derive a non-asymptotic Berry--Esseen bound for the empirical reward estimates under adaptive sampling. Second, we derive matching non-asymptotic upper and lower bounds on the regret of the proposed algorithm, yielding a precise characterization of its regret. Third, we show that these regularized algorithms preserve asymptotic normality and valid inference under a prescribed level of adversarial corruption. Finally, we show that regularization is necessary rather than incidental: Lai--Wei stability is incompatible with the optimal O(T) regret rate -- the rate attained by unregularized algorithms such as EXP3 -- so that a controlled, polylogarithmic inflation in regret is the price of valid inference.