# Problem Dependent Reinforcement Learning Bounds Which Can Identify Bandit Structure in MDPs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2019.

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

- [Towards Instance-Optimal Offline Reinforcement Learning with Pessimism](https://mlsanity.com/paper/2110.08695/) (2021)
- [NeurWIN: Neural Whittle Index Network For Restless Bandits Via Deep RL](https://mlsanity.com/paper/2110.02128/) (2021)
- [Truncated Variance Reduced Value Iteration](https://mlsanity.com/paper/2405.12952/) (2024)
- [The Unintended Consequences of Discount Regularization: Improving Regularization in Certainty Equivalence Reinforcement Learning](https://mlsanity.com/paper/2306.11208/) (2023)
- [A Bayesian Approach to Learning Bandit Structure in Markov Decision Processes](https://mlsanity.com/paper/2208.00250/) (2022)
- [An Option-Dependent Analysis of Regret Minimization Algorithms in Finite-Horizon Semi-Markov Decision Processes](https://mlsanity.com/paper/2305.06936/) (2023)

## Abstract (arXiv)

In order to make good decision under uncertainty an agent must learn from observations. To do so, two of the most common frameworks are Contextual Bandits and Markov Decision Processes (MDPs). In this paper, we study whether there exist algorithms for the more general framework (MDP) which automatically provide the best performance bounds for the specific problem at hand without user intervention and without modifying the algorithm. In particular, it is found that a very minor variant of a recently proposed reinforcement learning algorithm for MDPs already matches the best possible regret bound tilde O (√SAT) in the dominant term if deployed on a tabular Contextual Bandit problem despite the agent being agnostic to such setting.