mlsanityData to 7 Oct 2026

Learning Unknown Markov Decision Processes: A Thompson Sampling Approach

arXiv 1709.04570 ↗First posted 14 Sep 2017cs.LGcited by 65

Not on the map. Why?

Abstract (arXiv)

We consider the problem of learning an unknown Markov Decision Process (MDP) that is weakly communicating in the infinite horizon setting. We propose a Thompson Sampling-based reinforcement learning algorithm with dynamic episodes (TSDE). At the beginning of each episode, the algorithm generates a sample from the posterior distribution over the unknown model parameters. It then follows the optimal stationary policy for the sampled model for the rest of the episode. The duration of each episode is dynamically determined by two stopping criteria. The first stopping criterion controls the growth rate of episode length. The second stopping criterion happens when the number of visits to any state-action pair is doubled. We establish tilde O(HS√AT) bounds on expected regret under a Bayesian setting, where S and A are the sizes of the state and action spaces, T is time, and H is the bound of the span. This regret bound matches the best available bound for weakly communicating MDPs. Numerical results show it to perform better than existing algorithms for infinite horizon MDPs.

Key facts. Cited by 65 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 Sep 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 14; 2022: 12; 2023: 10; 2024: 18; 2025: 7; 2026: 4.

65 papers.

Sort:

By area:

  1. 2021Recent Advances in Reinforcement Learning in Financecited by 102
  2. 2022Jump-Start Reinforcement Learningcited by 102
  3. 2021Reinforcement Learning, Bit by Bitcited by 59
  4. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  5. 2021Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent Statescited by 42
  6. 2022Stochastic first-order methods for average-reward Markov decision processescited by 30
  7. 2024MaxInfoRL: Boosting exploration in reinforcement learning through information gain maximizationcited by 30
  8. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 28
  9. 2023Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processescited by 22
  10. 2021Nearly Minimax Optimal Regret for Learning Infinite-horizon Average-reward MDPs with Linear Function Approximationcited by 18
  11. 2021Improved Regret Bound and Experience Replay in Regularized Policy Iterationcited by 18
  12. 2021Concave Utility Reinforcement Learning with Zero-Constraint Violationscited by 18
38 more
  1. 2021Online Learning for Unknown Partially Observable MDPscited by 17
  2. 2021Online Learning for Stochastic Shortest Path Model via Posterior Samplingcited by 16
  3. 2021Adaptive Transmission Scheduling in Wireless Networks for Asynchronous Federated Learningcited by 15
  4. 2025Toward Efficient Exploration by Large Language Model Agentscited by 15
  5. 2024Bayesian Design Principles for Offline-to-Online Reinforcement Learningcited by 14
  6. 2022Model-Based Reinforcement Learning with Multinomial Logistic Function Approximationcited by 13
  7. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 13
  8. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  9. 2022On learning Whittle index policy for restless bandits with scalable regretcited by 9
  10. 2023Social Contract AI: Aligning AI Assistants with Implicit Group Normscited by 9
  11. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
  12. 2023Safe Posterior Sampling for Constrained MDPs with Bounded Constraint Violationcited by 6
  13. 2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
  14. 2022Augmented RBMLE-UCB Approach for Adaptive Control of Linear Quadratic Systemscited by 5
  15. 2023Bridging Imitation and Online Reinforcement Learning: An Optimistic Talecited by 5
  16. 2023Langevin Thompson Sampling with Logarithmic Communication: Bandits and Reinforcement Learningcited by 5
  17. 2025The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspectivecited by 5
  18. 2021Learning Augmented Index Policy for Optimal Service Placement at the Network Edgecited by 4
  19. 2022Posterior Sampling for Continuing Environmentscited by 4
  20. 2021A Bayesian Learning Algorithm for Unknown Zero-sum Stochastic Games with an Arbitrary Opponentcited by 3
  21. 2022Efficient Algorithms for Learning to Control Bandits with Unobserved Contextscited by 3
  22. 2022Actor-Critic based Improper Reinforcement Learningcited by 3
  23. 2024NeoRL: Efficient Exploration for Nonepisodic RLcited by 3
  24. 2025Best Policy Learning from Trajectory Preference Feedbackcited by 3
  25. 2025No-Regret Thompson Sampling for Finite-Horizon Markov Decision Processes with Gaussian Processescited by 3
  26. 2022Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPscited by 2
  27. 2023Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Spacecited by 2
  28. 2024Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Samplingcited by 2
  29. 2024Robust Thompson Sampling Algorithms Against Reward Poisoning Attackscited by 2
  30. 2024Generalized Bayesian deep reinforcement learningcited by 2
  31. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2
  32. 2021Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?cited by 1
  33. 2022An Empirical Evaluation of Posterior Sampling for Constrained Reinforcement Learningcited by 1
  34. 2024Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learningcited by 1
  35. 2024A Federated Online Restless Bandit Framework for Cooperative Resource Allocationcited by 1
  36. 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Spancited by 1
  37. 2025Q-learning with Posterior Samplingcited by 1
  38. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1

50 most cited of 65 All 65 (JSON)