Research map / Bandits and online learning / RL theory and MDPs
Adapting to Stochastic and Adversarial Losses in Episodic 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.
Gives the first best-of-both-worlds algorithms for episodic tabular MDPs and shortest paths with aggregate bandit feedback, using FTRL over occupancy measures with a new optimistic loss estimator and self-bounding analysis.
Problem
Online learning in finite-horizon episodic MDPs where only the aggregate episode loss is observed; prior work only gave worst-case bounds, so no algorithm achieved polylog(T) regret in stochastic settings with unknown transitions while also handling adversarial losses.
Approach
A loss estimator inspired by online shortest path bandit methods, whose second moment carries a (1 - pi(a|s)) factor, enabling self-bounding analysis without loss-shifting; for unknown transitions, an optimistic variant built from upper confidence bounds on occupancy measures is used.
Key results
- Known-transition MDPs: O(log T) regret in stochastic settings (gap-dependent) and O(sqrt(|S||A|LT)) adversarial regret with Tsallis entropy, with matching stochastic lower bound (Theorem on liminf Reg/log T).
- Unknown-transition MDPs: BOBW bound of O(U + sqrt(UC) + V) under self-bounding constraints with adversarial regret tilde O(sqrt((|A|+L)|S|^2|A|LT)).
- Shortest path with bandit feedback: log-barrier variant gives sqrt(|E|LT log T) adversarial and sum_e log T / Delta(e) stochastic regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the log-barrier regularizer instead of Tsallis entropy (ablation) | This study for known-transition episodic MDPs · Stochastic environments | regret bound: \sum_{s \neq s_L, a \neq \pi^*(s)} \frac{\log T}{\Delta(s, a)} + \frac{L|S| \log T}{\Delta_{\min}} -> \sum_{s \neq s_L, | Helped |
| Use the log-barrier regularizer instead of Tsallis entropy (ablation) | This study for known-transition episodic MDPs · Adversarial environments | regret bound: \sqrt{|S||A|L T } -> \sqrt{|S||A|L T \log T} | Hurt |
| Use the log-barrier regularizer instead of Tsallis entropy (ablation) | This study for online shortest path · Stochastic environments | regret bound: \sum_{e \in E'} \frac{\log T}{\Delta(e)} + \frac{|V|^2 \log T}{\Delta_{\min}} -> \sum_{e \in E'} \frac{\log T}{\Delta(e) | Helped |
| Use the log-barrier regularizer instead of Tsallis entropy (ablation) | This study for online shortest path · Adversarial environments | regret bound: \sqrt{|E|LT} -> \sqrt{|E|LT \log T} | Hurt |
| Use the optimistic loss estimator and avoid the loss-shifting technique | This study for unknown-transition episodic MDPs · Unknown-transition episodic MDPs | regret bound dependence on horizon L | Helped |
Surprising findings
- The optimistic loss estimator avoids the loss-shifting technique used in prior analyses, simplifying the regret proof.
Limitations
- Relies on FTRL over occupancy measures, requiring a convex optimization per round.
- Framework does not directly extend beyond tabular MDPs to linear or function approximation settings.
- Log-barrier variant incurs an extra sqrt(log T) factor in adversarial regret.
Experimental setup
Metrics: expected regret gap-dependent regret bound adversarial regret bound
Baselines: Zimmert and Seldin-style BOBW MDP algorithms with individual bandit feedback aggregate-feedback MDP algorithms (worst-case) linear bandit reductions
Builds on: FTRL over occupancy measures self-bounding regime online shortest path with bandit feedback loss estimator epoch-based UOB-REPS for unknown transitions
Closest papers by meaning
- Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback (ICML 2025 · similarity 0.93)
- Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback (NeurIPS 2024 · similarity 0.91)
- Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback (ICLR 2024 · similarity 0.90)
- Dynamic Regret of Adversarial MDPs with Unknown Transition and Linear Function Approximation (AAAI 2024 · similarity 0.90)
- Online Learning in CMDPs: Handling Stochastic and Adversarial Constraints (ICML 2024 · similarity 0.90)
- Rate-Optimal Policy Optimization for Linear Markov Decision Processes (ICML 2024 · 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.