# Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 56 references that are in the map.
- First posted on arXiv 5 Jun 2023.

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

- [(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)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Queueing Network Controls via Deep Reinforcement Learning](https://mlsanity.com/paper/2008.01644/) (2020)
- [Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory management](https://mlsanity.com/paper/1905.04337/) (2019)
- [Learning Unknown Service Rates in Queues: A Multi-Armed Bandit Approach](https://mlsanity.com/paper/1604.06377/) (2016)
- [Online Learning for Unknown Partially Observable MDPs](https://mlsanity.com/paper/2102.12661/) (2021)
- [Job Dispatching Policies for Queueing Systems with Unknown Service Rates](https://mlsanity.com/paper/2106.04707/) (2021)
- [Bayesian Optimal Control of Smoothly Parameterized Systems: The Lazy Posterior Sampling Algorithm](https://mlsanity.com/paper/1406.3926/) (2014)
- [On Learning the cμ Rule in Single and Parallel Server Networks](https://mlsanity.com/paper/1802.06723/) (2018)
- [On learning Whittle index policy for restless bandits with scalable regret](https://mlsanity.com/paper/2202.03463/) (2022)
- [Augmenting Max-Weight with Explicit Learning for Wireless Scheduling with Switching Costs](https://mlsanity.com/paper/1808.01618/) (2018)
- [Learning and Information in Stochastic Networks and Queues](https://mlsanity.com/paper/2105.08769/) (2021)
- [Learning While Scheduling in Multi-Server Systems with Unknown Statistics: MaxWeight with Discounted UCB](https://mlsanity.com/paper/2209.01126/) (2022)
- [Posterior Sampling for Large Scale Reinforcement Learning](https://mlsanity.com/paper/1711.07979/) (2017)
- [Learning-based Optimal Admission Control in a Single Server Queuing System](https://mlsanity.com/paper/2212.11316/) (2022)
- [Learning to Admit Optimally in an M/M/k/k+N Queueing System with Unknown Service Rate](https://mlsanity.com/paper/2202.02419/) (2022)

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

- [Convergence of Natural Policy Gradient for a Family of Infinite-State Queueing MDPs](https://mlsanity.com/paper/2402.05274/) (2024)
- [Bayesian learning for the stochastic shortest path problem](https://mlsanity.com/paper/2606.04845/) (2026)

## Abstract (arXiv)

Models of many real-life applications, such as queuing models of communication networks or computing systems, have a countably infinite state-space. Algorithmic and learning procedures that have been developed to produce optimal policies mainly focus on finite state settings, and do not directly apply to these models. To overcome this lacuna, in this work we study the problem of optimal control of a family of discrete-time countable state-space Markov Decision Processes (MDPs) governed by an unknown parameter θ∈Theta, and defined on a countably-infinite state space mathcal X=mathbbZ_+d, with finite action space mathcal A, and an unbounded cost function. We take a Bayesian perspective with the random unknown parameter boldsymbolθ^* generated via a given fixed prior distribution on Theta. To optimally control the unknown MDP, we propose an algorithm based on Thompson sampling with dynamically-sized episodes: at the beginning of each episode, the posterior distribution formed via Bayes' rule is used to produce a parameter estimate, which then decides the policy applied during the episode. To ensure the stability of the Markov chain obtained by following the policy chosen for each parameter, we impose ergodicity assumptions. From this condition and using the solution of the average cost Bellman equation, we establish an tilde O(dhd√|mathcal A|T) upper bound on the Bayesian regret of our algorithm, where T is the time-horizon. Finally, to elucidate the applicability of our algorithm, we consider two different queuing models with unknown dynamics, and show that our algorithm can be applied to develop approximately optimal control algorithms.