Online Markov Decision Processes With Aggregate Bandit Feedback

Abstract

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(\sqrt\{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(\sqrt\{T\})\) regret bound, where \(T\)

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keycohen2021online

Related papers

• Near-optimal Regret Using Policy Optimization In Online Mdps With Aggregate Bandit Feedback (2025)0.00
• Towards Optimal Regret In Adversarial Linear Mdps With Bandit Feedback (2023)0.00
• Learning Adversarial Markov Decision Processes With Delayed Feedback (2020)0.00
• Near-optimal Regret For Adversarial MDP With Delayed Bandit Feedback (2022)0.00
• Dynamic Regret Of Online Markov Decision Processes (2022)0.00
• Online Convex Optimization In Adversarial Markov Decision Processes (2019)0.00
• Rate-optimal Policy Optimization For Linear Markov Decision Processes (2023)0.00
• Online Learning In Mdps With Linear Function Approximation And Bandit Feedback (2020)0.00