Research map / Bandits and online learning / RL theory and MDPs
Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate 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.
Introduces policy optimization algorithms for adversarial finite-horizon MDPs with aggregate (full-bandit) trajectory loss feedback, using a new U-function, achieving near-optimal regret under known dynamics and improved regret under unknown dynamics.
Problem
Online episodic MDPs with adversarially changing losses where the learner only observes the total trajectory loss (aggregate bandit feedback); prior methods were either computationally heavy or had suboptimal regret.
Approach
Decompose regret with respect to a U-function (expected total trajectory loss conditioned on visiting a state-action pair at a step), which can be estimated from the aggregate loss alone; combine with an occupancy-based importance-weighted estimator, a bonus term, and entropy-regularized policy mirror descent with closed-form updates.
Key results
- Known dynamics: regret Õ(H^2 sqrt(SAK)) + Õ(H^3 sqrt K), matching a new Ω(H^2 sqrt(SAK)) lower bound up to logs when sqrt(SA) ≥ H.
- Unknown dynamics: regret Õ(H^3 S sqrt(AK)), improving the best known DBOLO-based bound of Õ(H^5 S^6 A^{5/2} sqrt K) by a factor of H^2 S^5 A^2.
- Unknown dynamics bound matches the best known policy optimization regret under semi-bandit feedback, Õ(H^3 S sqrt(AK)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Policy Optimization instead of the reduction to Efficient Linear Bandits | Online MDPs with known dynamics and aggregate bandit feedback · Online MDPs, known dynamics | regret bound: $\tilde O(H^2 S A \sqrt{K})$ -> $\tilde O (H^{2}\sqrt{SAK} + H^{3}\sqrt{K})$ | Helped |
| Use Policy Optimization instead of the reduction to DBOLO | Online MDPs with unknown dynamics and aggregate bandit feedback · Online MDPs, unknown dynamics | regret bound: $\tilde O(H^5 S^6 A^{5/2} \sqrt{K})$ -> $\tilde O (H^{3}S\sqrt{AK} + H^{4}S^{3}A)$ | Helped |
| Use Policy Optimization rather than the prior DBOLO reduction | Online MDPs with unknown dynamics and aggregate bandit feedback · Online MDPs, unknown dynamics | regret bound: $H^2 S^5 A^2$ | Helped |
| Use the proposed known-dynamics algorithm rather than the prior efficient linear-bandit reduction | Online MDPs with known dynamics and aggregate bandit feedback · Online MDPs, known dynamics | computational efficiency | Helped |
| Use the proposed unknown-dynamics algorithm rather than the prior DBOLO reduction | Online MDPs with unknown dynamics and aggregate bandit feedback · Online MDPs, unknown dynamics | computational efficiency | Helped |
Surprising findings
- Policy optimization with aggregate-only feedback matches the best known policy optimization regret under semi-bandit feedback in the unknown-dynamics case.
Limitations
- Gap to lower bound of H*sqrt(S) in the unknown-dynamics case
- Analysis restricted to tabular MDPs; U-function is not linear so extension to linear MDPs / function approximation is open
Experimental setup
Metrics: regret upper bound regret lower bound
Baselines: Reduction to efficient linear bandits Reduction to DBOLO (Cohen et al. 2021) UCBVI-TS REPO
Builds on: policy optimization (Shani et al. 2020) value difference lemma distorted bandit online linear optimization (Cohen et al. 2021) SCRIBLE
Closest papers by meaning
- Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback (ICLR 2024 · similarity 0.93)
- Rate-Optimal Policy Optimization for Linear Markov Decision Processes (ICML 2024 · similarity 0.93)
- Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback (NeurIPS 2025 · similarity 0.93)
- Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints (ICML 2025 · similarity 0.91)
- Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback (ICML 2024 · similarity 0.91)
- Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback (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.