Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
Not on the map. Why?
Abstract (arXiv)
We study online finite-horizon Markov Decision Processes with adversarially changing loss and aggregate bandit feedback (a.k.a full-bandit). Under this type of feedback, the agent observes only the total loss incurred over the entire trajectory, rather than the individual losses at each intermediate step within the trajectory. We introduce the first Policy Optimization algorithms for this setting. In the known-dynamics case, we achieve the first textitoptimal regret bound of tilde Theta(H2√SAK), where K is the number of episodes, H is the episode horizon, S is the number of states, and A is the number of actions. In the unknown dynamics case we establish regret bound of tilde O(H3 S √AK), significantly improving the best known result by a factor of H2 S5 A2.
Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Feb 2025.
Builds on
0 of 0 references.
No references here yet.
Built on by
Citing papers per year: 2025: 3; 2026: 3.
6 papers.
- 2025Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspectivecited by 16
- 2025Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limitscited by 7
- 2025Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedbackcited by 2
- 2026Optimal Regret for Policy Optimization in Contextual Banditscited by 1
- 2026Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximationcited by 0
- 2026When Does Trajectory-Level Supervision Permit Efficient Offline Reinforcement Learning?cited by 0
- 2026When Does Trajectory-Level Supervision Permit Efficient Offline Reinforcement Learning?16 Jun 2026
- 2026Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximation14 Feb 2026
- 2026Optimal Regret for Policy Optimization in Contextual Bandits14 Feb 2026
- 2025Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback20 Oct 2025
- 2025Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits26 May 2025
- 2025Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspective14 Feb 2025