Research map / Bandits and online learning / Contextual bandits and Thompson sampling
On the Optimality of Batch Policy Optimization Algorithms
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use any confidence adjustment α within [-βδ, βδ], including optimistic, neutral, or pessimistic adjustment | Confidence-adjusted index algorithms · Finite-armed stochastic bandits, fixed counts | worst-case simple regret: 12 \sqrt{\frac{\log(k/\delta)}{\min_i n_i}} | No clear effect |
| Use a pessimistic index rather than an optimistic or neutral index | Confidence-adjusted index algorithms · Individual bandit instances | simple regret | Mixed |
| Use LCB rather than UCB | Finite-armed stochastic bandits · Instances where heavily sampled arms include a good arm | simple regret | Helped |
| Use UCB rather than LCB | Finite-armed stochastic bandits · Instances where heavily sampled arms include all worse arms | simple regret | Helped |
| Use LCB rather than UCB | Finite-armed stochastic bandits · Uniformly sampled subsets of m heavily sampled arms, m < k | upper-bound regret: 1 - \frac{(k-m)!m!}{k!} | Helped |
| Use LCB rather than greedy | Finite-armed stochastic bandits · Uniformly sampled subsets of m heavily sampled arms, m < k | upper-bound regret: 1 - \frac{(k-m)!m!}{k!} | Helped |
| Seek an algorithm that is instance-optimal up to a constant multiplicative factor | Batch policy optimization · Two-armed Gaussian bandits | regret ratio to the instance-dependent lower bound: \limsup_{n\to\infty} \sup_{\theta\in \Theta_{\mathbf{n}}} \frac{\cR(\cA, \theta)}{\cR^*_{\cM_{\mathbf{n}, c}}(\theta)} = | Hurt |
| Weight each instance by optimal-value prediction difficulty | LCB · Finite-armed Gaussian bandits | regret divided by optimal-value estimation difficulty: c\sqrt{\log |\mathbf{n}|} | Helped |
| Use UCB instead of LCB under optimal-value-difficulty weighting | Finite-armed Gaussian bandits · A sequence of fixed-count settings | regret divided by optimal-value estimation difficulty: \limsup_{j\rightarrow\infty} \sup_{\theta\in\Theta_{\mathbf{n}_j}}{\frac{\cR(\textnormal{UCB},\theta)}{\sqrt{\log |\math | Hurt |
| Use greedy instead of LCB under optimal-value-difficulty weighting | Finite-armed Gaussian bandits · A sequence of fixed-count settings | regret divided by optimal-value estimation difficulty: \limsup_{j\rightarrow\infty}\sup_{\theta\in\Theta_{\mathbf{n}_j}} {\frac{\cR(\textnormal{greedy},\theta)}{\sqrt{\log |\m | Hurt |
| Concentrate logged data on a best or near-best arm | LCB, UCB, and greedy · Synthetic 100-arm bandits | simple regret | Helped |
| Give best and near-best arms very few samples while sampling the remaining arms more | LCB, UCB, and greedy · Synthetic 100-arm bandits | simple regret | Helped |
Closest papers by meaning
- Optimal Batched Linear Bandits (ICML 2024 · similarity 0.91)
- Batched Stochastic Linear Bandits with 1-Bit Communication Constraints (NeurIPS 2026 · similarity 0.90)
- Optimal and Practical Batched Linear Bandit Algorithm (ICML 2025 · similarity 0.90)
- Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints (ICML 2025 · similarity 0.89)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.89)
- Rate-Optimal Policy Optimization for Linear Markov Decision Processes (ICML 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.