Learning from a Bandit Learner

Michela Petriconi; Nicolas Menet; Claire Vernade

cs.LGOct 19, 2026

Learning from a Bandit Learner

Authors: Michela Petriconi, Nicolas Menet, Claire Vernade

Organizations: University of Tübingen · University of Technology Nuremberg · ETH Zurich

Abstract

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 $\Psi$ -LS for $n\in\{500,1000,2000\}$ , over $100$ trajectories. Here, $\eta$ is the realized uniform error of the within-batch frequency estimator. Panel (a) compares $c_{\gamma}$ with $c_{\gamma-2\eta}$ , and Panel (b) reports the stability factor $c_{\gamma-2\eta}\eta$ . Panel (c) shows the conditional and coverage-weighted inversion errors, $\widehat{L}_{T}^{\gamma-\eta}$ and $\widehat{\mathcal{E}}_{T}^{\gamma-\eta}$ , computed on the practical relevance set $\widehat{\mathcal{M}}_{T}^{\gamma-\eta}$ . Panel (d) reports the excess coverage $|\widehat{\mathcal{M}}_{T}^{\gamma-\eta}\setminus\mathcal{M}_{T}^{\gamma}|/T$ . Quantities are reported only for trajectories satisfying $2\eta<\gamma$ ; shaded regions in Panels (c)–(d) are pointwise $95\%$ confidence intervals.

Figure 2: End-to-end inversion for

v=\Psi

K=4

T=2000

, and

\gamma=0.4

. The panels show conditional inversion error

L_{t}^{\gamma}

, the fractions of non-reference and relevant rounds, and coverage-weighted error

\mathcal{E}_{t}^{\gamma}

. Here

B_{t}=\sum_{s=1}^{t}\mathbbm{1}\{A_{s}=\widehat{a}^{*}\}

counts pulls of the estimated best, or reference, arm. Solid and dotted curves in the middle panel denote

1-B_{t}/t

and

|\mathcal{M}_{t}^{\gamma}|/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=\Phi

(Gaussian) and

v=\Psi

. The same estimation error

|\hat{q}-q|<\eta

is harmless inside the relevant interval

(\gamma,1-\gamma)

but produces unbounded gap errors outside it.

Panel of Figure 4 — Figure 4: Conservative non-batched inversion for $\Phi$ -LS with $K\in\{2,4,8\}$ (left to right) and $m\in\{100,200,500\}$ . Panel (a) compares the intrinsic inverse-CDF slope $c_{\gamma}$ with the median effective slope $c_{\gamma-2\eta}$ . Panel (b) reports the median stability factor $c_{\gamma-2\eta}\eta$ . Panel (c) reports the practical conditional and coverage-weighted inversion errors, $\widehat{L}_{T}^{\gamma-\eta}$ and $\widehat{\mathcal{E}}_{T}^{\gamma-\eta}$ , computed on $\widehat{\mathcal{M}}_{T}^{\gamma-\eta}$ . Panel (d) reports the excess coverage $|\widehat{\mathcal{M}}_{T}^{\gamma-\eta}\setminus\mathcal{M}_{T}^{\gamma}|/T$ . Curves are shown only when at least ten of the $100$ trajectories satisfy $2\eta<\gamma$ ; shaded regions in Panels (c)–(d) are pointwise $95\%$ confidence intervals.

Panel of Figure 5 — Figure 5: Conservative non-batched inversion for $\Psi$ -LS with $K\in\{2,4,8\}$ (left to right) and $m\in\{100,200,500\}$ . Panels (a)–(d) report, respectively, $c_{\gamma}$ and the median $c_{\gamma-2\eta}$ , the median stability factor $c_{\gamma-2\eta}\eta$ , the practical inversion errors $\widehat{L}_{T}^{\gamma-\eta}$ and $\widehat{\mathcal{E}}_{T}^{\gamma-\eta}$ on $\widehat{\mathcal{M}}_{T}^{\gamma-\eta}$ , and the excess coverage $|\widehat{\mathcal{M}}_{T}^{\gamma-\eta}\setminus\mathcal{M}_{T}^{\gamma}|/T$ . Curves are shown only when at least ten trajectories satisfy $2\eta<\gamma$ ; shaded regions in Panels (c)–(d) are pointwise $95\%$ confidence intervals over the valid trajectories.

Panel of Figure 6 — Figure 6: Batched iLITE- $\Phi$ conditioning and inversion results for $K\in\{2,4,8\}$ (left to right), $T=20000$ , and batch sizes $n\in\{500,1000,2000\}$ . Panel (a) compares $c_{\gamma}$ with $c_{\gamma-2\eta}$ , and Panel (b) reports the stability factor $c_{\gamma-2\eta}\eta$ . Panel (c) shows the conditional and coverage-weighted inversion errors, $\widehat{L}_{T}^{\gamma-\eta}$ and $\widehat{\mathcal{E}}_{T}^{\gamma-\eta}$ , computed on the practical relevance set $\widehat{\mathcal{M}}_{T}^{\gamma-\eta}$ . Panel (d) reports the excess coverage $|\widehat{\mathcal{M}}_{T}^{\gamma-\eta}\setminus\mathcal{M}_{T}^{\gamma}|/T$ . Quantities are reported only for trajectories satisfying $2\eta<\gamma$ ; shaded regions in Panels (c)–(d) are pointwise $95\%$ confidence intervals.

Panel of Figure 7 — Figure 7: Batched $\Psi$ -LS conditioning experiment for $K\in\{2,4,8\}$ (left to right), $T=20000$ , and batch sizes $n\in\{500,1000,2000\}$ . Panel (a) compares $c_{\gamma}$ with $c_{\gamma-2\eta}$ , and Panel (b) reports the stability factor $c_{\gamma-2\eta}\eta$ . Panel (c) shows the conditional and coverage-weighted inversion errors, $\widehat{L}_{T}^{\gamma-\eta}$ and $\widehat{\mathcal{E}}_{T}^{\gamma-\eta}$ , computed on the practical relevance set $\widehat{\mathcal{M}}_{T}^{\gamma-\eta}$ . Panel (d) reports the excess coverage $|\widehat{\mathcal{M}}_{T}^{\gamma-\eta}\setminus\mathcal{M}_{T}^{\gamma}|/T$ . Quantities are reported only for trajectories satisfying $2\eta<\gamma$ ; shaded regions in Panels (c)–(d) are pointwise $95\%$ confidence intervals.

Figure 8: Sliding-window inversion for

\Phi

-LS with

K=2

T=20{,}000

\gamma=0.20

, and

n\in\{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

\Phi

-LS with

K=4

. The remaining settings and panels are the same as in Figure 8 .

Figure 10: Sliding-window inversion for

\Phi

-LS with

K=8

. The remaining settings and panels are the same as in Figure 8 .

Figure 11: Sliding-window inversion for

\Psi

-LS with

K=2

T=20{,}000

\gamma=0.20

, and

n\in\{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

\Psi

-LS with

K=4

. The remaining settings and panels are the same as in Figure 11 .

Figure 13: Sliding-window inversion for

\Psi

-LS with

K=8

. The remaining settings and panels are the same as in Figure 11 .

Panel of Figure 14 — Figure 14: Same-history discrepancies relative to the $\Phi$ -LS reference (left) and the $\Psi$ -LS reference (right), for $K\in\{2,4,8\}$ and $T=2000$ . The upper panels report the played-arm gap discrepancy $|\Delta^{\mathrm{ref}}_{a_{t},t}-\Delta^{\mathcal{A}}_{a_{t},t}|$ , while the lower panels report the maximum sampling-policy discrepancy $\max_{a\in[K]}|p^{\mathcal{A}}_{a,t}-q^{\mathrm{ref}}_{a,t}|$ . 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=\Psi

for

K=2

T=2000

, and

\gamma=0.4

. We invert TS, MS, BGE, and a

\Phi

-LS demonstrator using the exact sampling probabilities. The panels report the conditional inversion error

L_{t}^{\gamma}

, the non-reference pull fraction

1-B_{t}/t

and relevant-round fraction

|\mathcal{M}_{t}^{\gamma}|/t

, and the coverage-weighted error

\mathcal{E}_{t}^{\gamma}

. Curves are restricted to trajectories satisfying

2\varepsilon<\gamma

; shaded regions are pointwise

95\%

confidence intervals.

Figure 16: Fixed-threshold inversion with

v=\Psi

for

K=4

T=2000

, and

\gamma=0.4

. The panels respectively report

L_{t}^{\gamma}

, the fractions of non-reference and relevant rounds, and

\mathcal{E}_{t}^{\gamma}

. The blue curve corresponds to a

\Phi

-LS demonstrator inverted using

\Psi^{-1}

and therefore isolates inverse-CDF misspecification. Exact sampling probabilities are used, and only trajectories satisfying

2\varepsilon<\gamma

contribute. Shaded regions are pointwise

95\%

confidence intervals.

Figure 17: Fixed-threshold inversion with

v=\Psi

for

K=8

T=2000

, and

\gamma=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

\Phi

-LS curve illustrates inversion using a misspecified inverse CDF. Results use exact sampling probabilities and are restricted to trajectories satisfying

2\varepsilon<\gamma

. Shaded regions are pointwise

95\%

confidence intervals.

Figure 18: Fixed-threshold inversion with

v=\Phi

for

K=2

T=2000

, and

\gamma=0.4

. We invert TS, MS, BGE, and a

\Psi

-LS demonstrator using the exact sampling probabilities. The left panel reports the conditional inversion error

L_{t}^{\gamma}

. The central panel shows the fraction of non-reference pulls,

1-B_{t}/t

, together with the relevant-round fraction

|\mathcal{M}_{t}^{\gamma}|/t

. The right panel reports the coverage-weighted error

\mathcal{E}_{t}^{\gamma}

. Curves are computed over trajectories satisfying

2\varepsilon<\gamma

; shaded regions are pointwise

95\%

confidence intervals.

Figure 19: Fixed-threshold inversion with

v=\Phi

for

K=4

T=2000

, and

\gamma=0.4

. The panels respectively report the conditional inversion error

L_{t}^{\gamma}

, the non-reference and relevant-round fractions, and the coverage-weighted error

\mathcal{E}_{t}^{\gamma}

. The blue curve corresponds to a

\Psi

-LS demonstrator inverted using

\Phi^{-1}

. Exact sampling probabilities are used, and only trajectories satisfying

2\varepsilon<\gamma

contribute to each curve. Shaded regions are pointwise

95\%

confidence intervals.

Figure 20: Fixed-threshold inversion with

v=\Phi

for

K=8

T=2000

, and

\gamma=0.4

. The three panels show

L_{t}^{\gamma}

, the fractions of non-reference and relevant rounds, and

\mathcal{E}_{t}^{\gamma}

. The

\Psi

-LS curve illustrates inversion under inverse-CDF misspecification. Results use exact sampling probabilities and are restricted to trajectories satisfying

2\varepsilon<\gamma

. 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 $\Phi$ -LS. Each panel perturbs the inverse learner’s prior variance for the indicated arm; $\rho$ denotes the multiplier in $\widetilde{\sigma}_{a,0}^{2}=\rho\sigma_{a,0}^{2}$ . The dashed curve is the correctly specified prior baseline.

Figure 22: Running conditional inversion error under prior-variance misspecification for $\Psi$ -LS. The setup and conventions are the same as in Figure 21 .

Multi-Armed Bandits

Multi-Armed Bandits study how to choose among uncertain actions over time while balancing immediate rewards with learning.

See all 341 papers

Tight Generalization Bounds for Noiseless Inverse Optimization
May 9, 2026Pouria Fatemi, Hoomaan Maskan, Suvrit Sra +1Parameter Estimation Learning to Optimize
Technical University of Munich, Germany · Uppsala University, Sweden · University of Toronto, Canada
Bandit Simulation for Average Reward Inference
May 30, 2026Samya Praharaj, Chih-Yu Chang, Koulik Khamaru +1Multi-Armed Bandits Simulation-Based Inference
Rutgers University · Imperial College London
Stabilizing Bandits using Regularization: Precise Regret and A Quantitative Central Limit Theorem
Mar 10, 2026Budhaditya Halder, Ishan Sengupta, Koustav Chowdhury +2Multi-Armed Bandits Algorithmic Stability
Department of Statistics, Rutgers University · Indian Statistical Institute, Kolkata

May 9, 2026J/K move · Enter open · S save

Tight Generalization Bounds for Noiseless Inverse Optimization

Pouria Fatemi, Hoomaan Maskan, Suvrit Sra, Peyman Mohajerin Esfahani

Technical University of Munich, Germany · Uppsala University, Sweden · University of Toronto, Canada

Parameter Estimation Learning to Optimize Regret Minimization Generalization Bounds

Open paper AskPDF arXiv

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}(\frac{d}{T})

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}(\frac{d}{T})

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.

Abstract

Multi-Armed Bandits

Explore similar work

Tight Generalization Bounds for Noiseless Inverse Optimization

Bandit Simulation for Average Reward Inference

Stabilizing Bandits using Regularization: Precise Regret and A Quantitative Central Limit Theorem