# A Bayesian Approach to Learning Bandit Structure in Markov Decision Processes

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 23 references that are in the map.
- First posted on arXiv 30 Jul 2022.

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

- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Challenges of Real-World Reinforcement Learning](https://mlsanity.com/paper/1904.12901/) (2019)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Personalized HeartSteps: A Reinforcement Learning Algorithm for Optimizing Physical Activity](https://mlsanity.com/paper/1909.03539/) (2019)
- [Discovering and Removing Exogenous State Variables and Rewards for Reinforcement Learning](https://mlsanity.com/paper/1806.01584/) (2018)
- [Learning Compact Models for Planning with Exogenous Processes](https://mlsanity.com/paper/1909.13870/) (2019)
- [Mitigating Planner Overfitting in Model-Based Reinforcement Learning](https://mlsanity.com/paper/1812.01129/) (2018)
- [Problem Dependent Reinforcement Learning Bounds Which Can Identify Bandit Structure in MDPs](https://mlsanity.com/paper/1911.00954/) (2019)

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

- [Selective Uncertainty Propagation in Offline RL](https://mlsanity.com/paper/2302.00284/) (2023)

## Abstract (arXiv)

In the reinforcement learning literature, there are many algorithms developed for either Contextual Bandit (CB) or Markov Decision Processes (MDP) environments. However, when deploying reinforcement learning algorithms in the real world, even with domain expertise, it is often difficult to know whether it is appropriate to treat a sequential decision making problem as a CB or an MDP. In other words, do actions affect future states, or only the immediate rewards? Making the wrong assumption regarding the nature of the environment can lead to inefficient learning, or even prevent the algorithm from ever learning an optimal policy, even with infinite data. In this work we develop an online algorithm that uses a Bayesian hypothesis testing approach to learn the nature of the environment. Our algorithm allows practitioners to incorporate prior knowledge about whether the environment is that of a CB or an MDP, and effectively interpolate between classical CB and MDP-based algorithms to mitigate against the effects of misspecifying the environment. We perform simulations and demonstrate that in CB settings our algorithm achieves lower regret than MDP-based algorithms, while in non-bandit MDP settings our algorithm is able to learn the optimal policy, often achieving comparable regret to MDP-based algorithms.