Improved Bayesian Regret Bounds for Thompson Sampling in Reinforcement Learning

Summary

The paper presents a refined analysis of TS in Bayesian regret reinforcement learning. Regret bounds are derived for tabular, linear, and finite mixture MDPs. The paper uses an information theoretical approach: the information ratio, representing the exploration-exploitation trade-off, is analyzed and bounded by the episode length. The paper uses discretization of the environment space defined by fixing a previous proof from the literature. The paper concludes by discussing related work and the optimality of the obtained regret bounds.

Strengths

The paper provides state-of-the-art Bayesian regret bounds for Thompson Sampling in reinforcement learning through a refined analysis of the surrogate environments and information ratio in many different settings, including tabular, linear, and finite mixtures. The obtained bound is general and independent of the dimension of transition/reward function space. Proof sketches are provided.

Weaknesses

The proposed analysis and bounds may have limited applicability to real-world RL problems beyond the considered settings. The paper does not provide experimental results or empirical validation of the derived bounds. Some assumptions and prior works are discussed without providing detailed explanations or comparisons. Overall, the paper makes significant contributions to the theoretical understanding of TS in RL by providing refined analysis and state-of-the-art Bayesian regret bounds in various settings. However, practical applicability and empirical validation of the derived bounds need further investigation.

Questions

Could you please provide more references that specifically highlight the theoretical analysis of TS in the context of RL and Bandit problems? Usually, bayesian regret is easier than frequentist to analyse. Do you know if your approach could be applicable to frequentist regret ? What is the relationship between the Kolmogorov dimension for $l_1$-distance, the "value partition for surrogate learning," and the time-inhomogeneous Bayesian RL problem? How does leveraging this relationship help in bounding the information ratio and achieving regret bounds in TS ? Can concrete estimates of the dimension be provided for linear, tabular, and finite mixtures applications? What is the significance of isolating the contributions of the information ratio and the cumulative mutual information terms? Can you clarify the specific experimental results or empirical evidence that support the conjecture regarding the optimality of the regret bound when substituting $H$ in place of the variable? Are there any specific experiments conducted with TS, assuming access to an oracle, that provide insights into the performance of the regret bound in practical scenarios? You mention related work on bounding Bayesian regret for TS, including the use of confidence regions and algorithms such as UCBVI and OPPO. How does the proposed work in this paper compare to these approaches in terms of regret bounds and optimality? Are there any notable advantages or limitations of the proposed approach compared to the existing literature?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Can you provide a motivation for using TS-based policies rather than OFU ones ? If this is about empirical performances, then it makes sense to run some experimental comparisons. I am not sure to clearly understand what evidence or rationale is provided to support the claim that the regret in surrogate environments serves as a proxy for the main problem. I think you could elaborate more on the methodology used in this analysis. How does it contribute to a better understanding of the trade-off between exploration and exploitation? Are there any limitations or assumptions associated with this analysis? minor: Lemma 11 : fix the X vs x notation

Summary

The paper shows a refined analysis of Thompson Sampling in RL. The analysis leverages the notion of Kolmogorov dimension, and results in an improved rate of the regret. The authors further presented the bounds in terms of several specific settings, which match the state-of-the-art results.

Strengths

The writing of the paper is clear and easy to follow. The paper studies an important problem in RL. The notion of Kolmogorov dimension as well as the corresponding analysis is novel. The paper also presents a complete discussion for specific settings, and makes sufficient comparisons with previous works, which shows the significance of its results.

Weaknesses

1. While the bound relies on a new notion $\lambda$, the term can still be as big as $H$ in many cases. It hard to to quantify how much improvement is made by this notion, and therefore, in the discussion of specific RL settings, the corresponds bounds only match the state-of-the-art results, but don't improve them. 2. The paper doesn't provide a lower bound in terms of the proposed notion, which weakens the significance of this notion.

Questions

1. The authors mentioned the incorrectness of [12] in terms of surrogate loss. Can the authors make some discussion on it and how did they fix the issue?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The paper has addressed it limitations.

Summary

The paper presents uniform Bayesian regret bounds for Thompson Sampling by utilizing a uniform bound of information ratio and specific bounds of the Kolmogorov dimension in different settings.

Strengths

1. The paper presents a uniform Bayesian regret bound for Thompson Sampling which yields results in a variety of settings, improving upon previous approaches in some scenarios. 2. The authors incorporate a comprehensive discussion with previous works which helps to understand the contribution of the proposed bounds.

Weaknesses

1. Potential overclaim: in the introduction, the authors state that they first define Bayesian RL with time inhomogeneous settings, which might be an overclaim since there are also previous works discussing this setting like [1]. [1]Variational Bayesian Reinforcement Learning with Regret Bounds. Brendan O'Donoghue 2. The presentation of the paper would benefit from a table that includes all the results discussed in the paper for a comprehensive comparison.

Questions

Why is time inhomogeneous specially highlighted in this work? If we consider time also as a part of the state observation, it would be homogeneous (i.e., share the same model across all timesteps). With that being considered, is it possible just to extend the time inhomogeneous bounds to this setting, and is the proposed bound also better than those?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Summary

The authors propose the novel Bayesian regret analysis for posterior sampling for reinforcement learning algorithm. The proposed regret bounds are applicable in a large variety of different RL settings, such as tabular, linear and finite mixture MDPs.

Strengths

- The novel analysis for posterior sampling algorithm in the setting of Bayesian regret; - The presented result holds not only in the setting of tabular MDPs but also in linear and finite mixture MDPs.

Weaknesses

- The weak notion of Bayesian regret is the main weakness of the presented result. Currently, there exists near-optimal results in posterior-sampling based algorithms in the frequentist setting (see section Questions for precise references). - The computational side of the presented algorithm was not discusses. - The upper bound in linear setup seems to be a contradiction with established lower bound in the setup of linear contextual bandits (see reference below for example). This effect requires additional explanations why is it possible in the presented setting. - Lattimore, Tor, and Csaba Szepesvári. *Bandit algorithms*. Cambridge University Press, 2020.

Questions

- Is there any results in literature where this type of dimension were called “Kolmogorov”? Seems that this definition is a just usual covering dimension (at least in the presented setup of $\ell_1$ distance). - Is there examples where $\lambda$ is much smaller than $H$? - What is the limitation to show this analysis for a more general class of MDPs such as MDPs with a finite Eluder dimension? - Where is topological structure of $S$ and $A$ were used during the proofs? What is the topological structure of them? - The missed references of frequentist regret bounds for TS-based exploration in tabular and linear MDPs: - Zanette, Andrea, et al. "Frequentist regret bounds for randomized least-squares value iteration." *International Conference on Artificial Intelligence and Statistics*. PMLR, 2020. - Agrawal, Shipra, and Randy Jia. "Optimistic posterior sampling for reinforcement learning: worst-case regret bounds." *Advances in Neural Information Processing Systems* 30 (2017). - Tiapkin, Daniil, et al. "Optimistic posterior sampling for reinforcement learning with few samples and tight guarantees." *Advances in Neural Information Processing Systems* 35 (2022): 10737-10751. - Agrawal, Priyank, Jinglin Chen, and Nan Jiang. "Improved worst-case regret bounds for randomized least-squares value iteration." *Proceedings of the AAAI Conference on Artificial Intelligence*. Vol. 35. No. 8. 2021. - Line 83: In [32] they consider not episodic setup. The state-of-the-art result in the episodic setup were presented in [4].

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

The paper presented the theoretical research on Bayesian regret for posterior-sampling algorithms for reinforcement learning, thus it does not require discussion of ethical limitations.

Summary

This paper considers the problem setting of Bayesian reinforcement learning, in which both the transition function and the reward function are sampled from a known prior distribution. The authors study Thompson sampling in this setting and prove a Bayesian regret bound of order O(\lambda \sqrt{ d T}) where \lambda is the average value diameter induced by the prior, d is the Kolmogorov dimension (with respect to l1 distance) of the environment, and T is the number of episodes the learner interacts with the environment. The authors instantiate their general result to two previously studied settings. - In the tabular setting, the authors show that their main result implies a regret bound that matches the previous state of the art by Osband and Van Roy (2017), but generalized to hold over any prior distribution rather than specific to the product of Dirichlet distribution prior considered by Osband and Van Roy. - In the linear MDP setting, the authors give a regret bound of $O(\lambda \sqrt{d^f T})$, where $d^f$ is the Kolmogorov l1 dimension of the feature space. The authors also present a counterexample showing that the previously claimed state of the art due to Hao and Lattimore (2022) was in fact incorrect. The paper also provides corollaries for specialized finite mixtures settings.

Strengths

The paper's main contribution is a general treatment of Thompson sampling in MDPs. Specifically, the paper claims to provide the most general results to date on the Bayesian regret of Thompson sampling in RL. These results appear to generalize the results of Osband and Van Roy (2017) in the tabular case, and, when their counterexample to Hao and Lattimore (2022) is taken into account, provides the tightest upper bounds in the linear MDP case. The paper clearly signposts these contributions and provides proofs for their claims.

Weaknesses

Some of the theorem statements/assumptions could be more explicit. For example, the strong consistency assumption (Assumption 1) is not rigorously defined until Appendix J. Also, in my reading of the proof of Theorem 4, it appears that there is another assumption needed in the statement (Assumption 2 from Appendix D). I think it is also worth pointing out that T_0 in Theorem 4 is doing a lot of heavy lifting, as it seems like it could actually be a very large constant, depending on the prior and the structure of the RL problem.

Questions

On line 138, it is claimed that the law of Thompson sampling aligns with the true posterior distribution. Is this true with no other assumptions? For example, if two environments induce the same optimal policy, then it seems like this would not be true.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The paper does point out that they do not have lower bounds to substantiate the tightness of their upper bounds. Another limitation of the paper, not mentioned by the authors, is that the analysis is limited to the setting where the prior is specified with perfect accuracy.