aiqbench analysis
This paper extends Thompson sampling analysis to infinite-horizon discounted Markov decision processes with Borel state spaces, proving exponential convergence of residual regret under generalized assumptions. By rigorously connecting adaptive control theory with reinforcement learning error perspectives, it establishes conditions for complete learning in complex, continuous environments. The work advances theoretical foundations for sampling-based algorithms in high-dimensional or uncountable action space settings.
Thompson Sampling for Infinite-Horizon Discounted Decision Processes
arXiv:2405.08253v4 Announce Type: replace-cross Abstract: This paper develops a framework for learning in discounted infinite-horizon Markov decision processes (MDPs) with Borel state and action spaces, whose rewards and transitions depend on an unknown parameter.To analyze sampling-based adaptive learning algorithms in this setting, we introduce a canonical probability space that explicitly incorporates sampled parameters into the history of the process. As a performance criterion, we adopt the per-period suboptimality gap used in discounted-MDP regret analysis and specialize it to our parametrized Bayesian setting. Since this quantity captures the remaining loss in future performance from the current period onward, we refer to it as residual regret. We use the expected residual regret to connect discounted-MDP regret analysis with asymptotic discount optimality from adaptive control and the temporal-difference error perspective from reinforcement learning. We then focus on Thompson sampling (TS) in discounted infinite-horizon MDPs. Under assumptions that extend those used in prior work on finite state and action spaces to the Borel setting, we show that the expected residual regret for TS converges to zero exponentially fast. We further show that, under mild conditions ensuring the existence of the relevant limits, the ample-path residual regret converges to zero almost surely and TS achieves complete learning.
Abstract:This paper develops a framework for learning in discounted infinite-horizon Markov decision processes (MDPs) with Borel state and action spaces, whose rewards and transitions depend on an unknown this http URL analyze sampling-based adaptive learning algorithms in this setting, we introduce a canonical probability space that explicitly incorporates sampled parameters into the history of the process. As a performance criterion, we adopt the per-period suboptimality gap used in discounted-MDP regret analysis and specialize it to our parametrized Bayesian setting. Since this quantity captures the remaining loss in future performance from the current period onward, we refer to it as residual regret. We use the expected residual regret to connect discounted-MDP regret analysis with asymptotic discount optimality from adaptive control and the temporal-difference error perspective from reinforcement learning. We then focus on Thompson sampling (TS) in discounted infinite-horizon MDPs. Under assumptions that extend those used in prior work on finite state and action spaces to the Borel setting, we show that the expected residual regret for TS converges to zero exponentially fast. We further show that, under mild conditions ensuring the existence of the relevant limits, the ample-path residual regret converges to zero almost surely and TS achieves complete learning.
Machine Learning (stat.ML); Machine Learning (cs.LG); Optimization and Control (math.OC)
arXiv:2405.08253 [stat.ML]
(or arXiv:2405.08253v4 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2405.08253 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 298 words
Related coverage
Optimal Sample Complexity of Stable Discounted Markov Decision Processes
arXiv · Sep 22, 2026
A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model
arXiv · Jul 20, 2026
Improved Quantum Algorithms for Reinforcement Learning Under a Generative Model
arXiv · Aug 5, 2026
Humans Are Not Chinchillas: Revisiting “How Quick and Big Would A Software Intelligence Explosion Be?”
LessWrong · Oct 5, 2026