# Learning Markov Decision Processes under Fully Bandit Feedback

arXiv: https://arxiv.org/abs/2602.02260 · HTML: https://mlsanity.com/paper/2602.02260/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 15 of its 32 references that are in the map.
- First posted on arXiv 2 Feb 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 15 of 15)

- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Deep Reinforcement Learning for Robotics: A Survey of Real-World Successes](https://mlsanity.com/paper/2408.03539/) (2024)
- [Reinforcement Learning with Trajectory Feedback](https://mlsanity.com/paper/2008.06036/) (2020)
- [On the Theory of Reinforcement Learning with Once-per-Episode Feedback](https://mlsanity.com/paper/2105.14363/) (2021)
- [Generalizing Complex Hypotheses on Product Distributions: Auctions, Prophet Inequalities, and Pandora's Problem](https://mlsanity.com/paper/1911.11936/) (2019)
- [Deep Reinforcement Learning for Automated Stock Trading: An Ensemble Strategy](https://mlsanity.com/paper/2511.12120/) (2025)
- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [Online Markov Decision Processes with Aggregate Bandit Feedback](https://mlsanity.com/paper/2102.00490/) (2021)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Bandit Sequential Posted Pricing via Half-Concavity](https://mlsanity.com/paper/2312.12794/) (2023)
- [Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality](https://mlsanity.com/paper/2505.18828/) (2025)
- [Reinforcement Learning with Segment Feedback](https://mlsanity.com/paper/2502.01876/) (2025)

## Built on by (most cited first, 1 of 1)

- [Reinforcement Learning with Segment Reward Feedback under Linear Function Approximation](https://mlsanity.com/paper/2610.08271/) (2026)

## Abstract (arXiv)

A standard assumption in Reinforcement Learning is that the agent observes every visited state-action pair in the associated Markov Decision Process (MDP), along with the per-step rewards. Strong theoretical results are known in this setting, achieving nearly-tight Theta(√T)-regret bounds. However, such detailed feedback can be unrealistic, and recent research has investigated more restricted settings such as trajectory feedback, where the agent observes all the visited state-action pairs, but only a single aggregate reward. In this paper, we consider a far more restrictive ``fully bandit'' feedback model for episodic MDPs, where the agent does not even observe the visited state-action pairs -- it only learns the aggregate reward. We provide the first efficient bandit learning algorithm for episodic MDPs with widetildeO(√T) regret. Our regret has an exponential dependence on the horizon length H, which we show is necessary. We also obtain improved nearly-tight regret bounds for ``ordered'' MDPs; these can be used to model classical stochastic optimization problems such as k-item prophet inequality and sequential posted pricing. Finally, we evaluate the empirical performance of our algorithm for the setting of k-item prophet inequalities; despite the highly restricted feedback, our algorithm's performance is comparable to that of a state-of-art learning algorithm (UCB-VI) with detailed state-action feedback.