Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback
Not on the map. Why?
Abstract (arXiv)
We study online learning in finite-horizon episodic Markov decision processes (MDPs) under the challenging aggregate bandit feedback model, where the learner observes only the cumulative loss incurred in each episode, rather than individual losses at each state-action pair. While prior work in this setting has focused exclusively on worst-case analysis, we initiate the study of best-of-both-worlds (BOBW) algorithms that achieve low regret in both stochastic and adversarial environments. We propose the first BOBW algorithms for episodic tabular MDPs with aggregate bandit feedback. In the case of known transitions, our algorithms achieve O(log T) regret in stochastic settings and O(√T) regret in adversarial ones. Importantly, we also establish matching lower bounds, showing the optimality of our algorithms in this setting. We further extend our approach to unknown-transition settings by incorporating confidence-based techniques. Our results rely on a combination of FTRL over occupancy measures, self-bounding techniques, and new loss estimators inspired by recent advances in online shortest path problems. Along the way, we also provide the first individual-gap-dependent lower bounds and demonstrate near-optimal BOBW algorithms for shortest path problems with bandit feedback.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 27 of its 33 references that are in the map. First posted on arXiv 20 Oct 2025.
Builds on
27 of 33 references.
References · 27
- 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 123
- 2015Explore no more: Improved high-probability regret bounds for non-stochastic banditscited by 120
- 2018More Adaptive Algorithms for Adversarial Banditscited by 114
- 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
- 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
- 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
- 2016The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Banditscited by 48
- 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
- 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
- 2019An Optimal Algorithm for Adversarial Bandits with Arbitrary Delayscited by 44
- 2020Reinforcement Learning with Trajectory Feedbackcited by 40
- 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
15 more
- 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
- 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
- 2020Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transitioncited by 27
- 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
- 2017Sparsity, variance and curvature in multi-armed banditscited by 24
- 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
- 2023Best of Both Worlds Policy Optimizationcited by 17
- 2023Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worldscited by 15
- 2023No-Regret Online Reinforcement Learning with Adversarial Losses and Transitionscited by 13
- 2023A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delayscited by 11
- 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
- 2021Online Markov Decision Processes with Aggregate Bandit Feedbackcited by 10
- 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
- 2025Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedbackcited by 6
- 2025Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversariescited by 5
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.