Research map / Bandits and online learning / RL theory and MDPs
Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Gives a computationally inefficient policy-search-free algorithm achieving Õ(√K) regret and a computationally efficient logdet-FTRL policy optimization algorithm achieving Õ(K^{3/4}) regret for adversarial linear MDPs with bandit feedback and unknown transitions.
Problem
Online RL in linear MDPs with adversarial losses, bandit feedback, unknown transitions and no simulator; prior best regrets were K^{4/5} (inefficient) and K^{6/7} (efficient), with the minimax rate √K open.
Approach
An on-the-fly, model-free occupancy-measure estimator constrained to be a valid occupancy measure, combined with state-space discretization and exponential weights over linear policies (inefficient); and logdet-barrier FTRL policy optimization with an initial exploration phase, optimistic least-squares bonus and dilated bonuses (efficient).
Key results
- Inefficient exponential-weights algorithm achieves Õ(√K) regret (stated as Õ(√(d^7H^7K)) in the theorem), the first optimal K dependence in this setting.
- Efficient logdet-FTRL algorithm achieves Õ(d^{3/2}H^3K^{3/4}) regret, improving the prior K^{6/7} efficient bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Exponential Weights with on-the-fly estimation of valid occupancy measures | Adversarial linear MDP learning with bandit feedback and unknown transitions · Adversarial linear MDPs, bandit feedback, unknown transitions | regret: \(\widetilde{\mathcal{O}}(K^{\nicefrac{4}{5}}+\poly(\nicefrac{1}{\lambda_{\min}}))\) -> \(\widetilde{\mathcal{O}}(\sqrt{ | Helped |
| Use logdet-barrier FTRL with initial exploration | Computationally efficient policy optimization for adversarial linear MDPs · Adversarial linear MDPs, bandit feedback, unknown transitions | regret: \(\widetilde{\mathcal{O}}(K^{\nicefrac{6}{7}})\) -> \(\widetilde{\mathcal{O}}(K^{\nicefrac{3}{4}})\) | Helped |
| Use an improved matrix concentration bound so that \(\tau = \frac{1}{\gamma}\) episodes suffice | Logdet FTRL with initial exploration · Adversarial linear MDPs, bandit feedback, unknown transitions | regret: \(\tau = \frac{1}{\gamma}\) -> \(\tau = \frac{1}{\gamma^2}\); \(\tau = \frac{1}{\gamma^3}\) | Helped |
| Use logdet-barrier FTRL instead of exponential weights for policy updates | Computationally efficient policy optimization · Adversarial linear MDPs, bandit feedback, unknown transitions | regret | Helped |
Limitations
- The √K algorithm is computationally inefficient, requiring enumeration over exponentially large policy sets.
- The efficient algorithm's K^{3/4} rate is not optimal; closing the gap to √K with an efficient method is open.
- Results are stated in the paper with polylogarithmic and dimension/horizon-dependent factors that are large.
Experimental setup
Metrics: regret
Baselines: K^{4/5} inefficient algorithm (Sherman et al.) K^{6/7} efficient policy optimization (Luo et al.) K^{8/9} efficient algorithm K^{14/15} algorithm (Cai et al.)
Builds on: policy optimization with dilated bonus exponential weights for linear bandits logdet-barrier FTRL for adversarial linear bandits
Closest papers by meaning
- Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback (ICML 2025 · similarity 0.93)
- Rate-Optimal Policy Optimization for Linear Markov Decision Processes (ICML 2024 · similarity 0.93)
- Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback (NeurIPS 2024 · similarity 0.92)
- Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints (ICML 2025 · similarity 0.91)
- Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback (NeurIPS 2025 · similarity 0.90)
- Learning Adversarial MDPs with Stochastic Hard Constraints (ICML 2025 · similarity 0.90)
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.