mlsanityData to 7 Oct 2026

Online Markov Decision Processes with Aggregate Bandit Feedback

arXiv 2102.00490 ↗First posted 31 Jan 2021cs.LG stat.MLcited by 10

Not on the map. Why?

Abstract (arXiv)

We study a novel variant of online finite-horizon Markov Decision Processes with adversarially changing loss functions and initially unknown dynamics. In each episode, the learner suffers the loss accumulated along the trajectory realized by the policy chosen for the episode, and observes aggregate bandit feedback: the trajectory is revealed along with the cumulative loss suffered, rather than the individual losses encountered along the trajectory. Our main result is a computationally efficient algorithm with O(√K) regret for this setting, where K is the number of episodes. We establish this result via an efficient reduction to a novel bandit learning setting we call Distorted Linear Bandits (DLB), which is a variant of bandit linear optimization where actions chosen by the learner are adversarially distorted before they are committed. We then develop a computationally-efficient online algorithm for DLB for which we prove an O(√T) regret bound, where T is the number of time steps. Our algorithm is based on online mirror descent with a self-concordant barrier regularization that employs a novel increasing learning rate schedule.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 12 of its 30 references that are in the map. First posted on arXiv 31 Jan 2021.

Builds on

12 of 30 references.

References · 12

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  3. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  4. 2016Corralling a Band of Bandit Algorithmscited by 99
  5. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  6. 2016Kernel-based methods for bandit convex optimizationcited by 63
  7. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
  8. 2017Misspecified Linear Banditscited by 41
  9. 2020Reinforcement Learning with Trajectory Feedbackcited by 40
  10. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 39
  11. 2013Volumetric Spanners: an Efficient Exploration Basis for Learningcited by 23
  12. 2013Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributionscited by 18

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 3; 2023: 1; 2024: 2; 2025: 2; 2026: 1.

10 papers.

  1. 2024Multi-turn Reinforcement Learning from Preference Human Feedbackcited by 65
  2. 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
  3. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  4. 2022Dynamic Regret of Online Markov Decision Processescited by 13
  5. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
  6. 2022Reinforcement Learning with a Terminatorcited by 4
  7. 2025Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedbackcited by 2
  8. 2023Online Resource Allocation in Episodic Markov Decision Processescited by 1
  9. 2025Online Episodic Convex Reinforcement Learningcited by 0
  10. 2026Learning Markov Decision Processes under Fully Bandit Feedbackcited by 0