The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learning

Summary

This paper explores the benefits of distributional RL and provides a theoretical understanding of its advantages through the lens of small-loss bounds. The authors propose distributional algorithms for contextual bandits, online RL, and offline RL, and prove that these algorithms achieve small-loss regret bounds.

Strengths

I appreciate the attempts to understand the practically powerful algorithm and also the provided empirical simulations, which should be the promising direction in the RL theory study. The obtained bound scales with the minimum loss so can outperform standard results when it is small. This result seems to be the first line of work in the literature on RL. The paper is also very well-written and easy to follow.

Weaknesses

1 The algorithm of RL setting still follows 1) reduce the out-of-sample target (immediate regret) to the in-sample loss by complexity measure (SEC); 2) maintain a version space by effective estimation of in-sample loss and choose the optimistic estimator to handle the difference between V^* and V_f (min_a f_1 in this case). The technical novelty is rather limited since similar treatments have been developed in the literature. Also, as far as I know, there are some proofs based on Banach fixed point theorem for the distributional RL, which typically assumes that we can always solve the sub-optimization problems. These results should have supported the effectiveness of the distributional RL to some degree. 2 The proposed algorithm relies on the (distributional) Bellman completeness assumption, which is hard to satisfy because it is non-monotone (adding a new function can violate this assumption). While I understand it is common in the literature to handle the double-sampling issue, it limits the contribution of this work if the goal is to provide a theoretical understanding of the DRL algorithms. I am a little bit confused indeed because, in my mind, the MLE analysis does not require a completeness assumption. Does the distributional setting lead to unique technical challenges here so you have to make such an assumption? In particular, I am wondering whether it is possible to replace it with the trajectory average technique (at a cost of worse regret bound) as in [2,3]. 3 The definition of linear SEC. I am wondering whether there are more non-trivial examples captured by it. For linear structure, my understanding is that the square comes from Cauchy-Schwarz to relate $|\phi(z_t)^T \theta_f|$ to $||\phi(z_t)||_{\Sigma_t^{-1}}$ and $ ||\theta_f||_{\Sigma_t} $. The square also exists in the definition of the standard eluder dimension. One exception is the $\ell_1$ eluder dimension developed in [1] (see the end of section 5) where both the out-of-sample prediction error and the in-sample training error are linear. I am wondering whether there is any direct application or corollary between them. Another minor comment is that you may also mention the decoupling/eluder coefficient in [4, 5] where such a reduction treatment is first proposed and generalized by them and you can easily bound the complexity measures via SEC. **The generality of the framework is indeed my main concern**. Actually, I personally have obtained a very similar first-order result with OMLE. I think we have a similar technical issue that we need to have a result as in line 778. My choice is to define the eluder dimension as in [7] (so, we can call it linear eluder dimension just like linear SEC) but I could not find more interesting instances covered by it. 4 An interesting point is that you choose to decouple the original target with two types of complexity measures. In contextual bandit, the immediate regret is decoupled to another out-of-sample target plus some decoupling cost (that is why we need an online oracle). It turns out that this type of complexity measure can be sub-optimal (especially in model-free cases, see [6] for examples). I am wondering whether this choice is only for a convention or for technical requirements because otherwise, we can definitely apply the eluder techniques to reduce the immediate regret to the in-sample error as in the RL case (that is why we only need an offline oracle that looks back at the k-1 samples collected so far). [1] When Is Partially Observable Reinforcement Learning Not Scary? [2] Contextual decision processes with low bellman rank are pac-learnable [3] Bilinear classes: A structural framework for provable generalization in rl [4] A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning [5] GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond [6] A note on model-free reinforcement learning with the decision-estimation coefficient [7] Eluder-based Regret for Stochastic Contextual MDP

Questions

see weakness.

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

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

yes

Summary

This paper establishes the regret bounds of the proposed distributional methods from the perspective of the small-loss bound, where the regret upper bound depends not only on the number of iterations but also the optimal value. Based on this, they can show that regret could be lower under those environments whose optimal policy corresponds to a higher value function. This paper provides three new distribution RL approaches for three different RL settings. The first one combines ReIGW and MLE to solve contextual bandits. The second one and the third one use the similar concept, which apply confidence intervals on the estimation of likelihood, to solve online RL and offline RL, respectively. They show that the proposed method can achieve competitive regret bound theoretically. The numerical results also demonstrate the empirical performance of the distributional approach for contextual bandits.

Strengths

- The concept of small-loss bound is very interesting and appears novel in the context of distributional RL. This new perspective indeed offers a promising way to theoretically understand why distribution methods could empirically achieve better performance in the existing distributional RL literature. - This paper is thorough in that it considers three important RL settings: (i) contextual bandits, (ii) online RL, and (iii) offline RL. This paper rigorously shows that the distributional MLE methods have provable benefits in terms of regret for a wide variety of RL problems. - The idea of combining MLE and confidence set is interesting and different from the traditional idea of considering the confidence interval of mean return.

Weaknesses

- Page 7 seems to be missing. This makes the upper half of Page 8 somewhat difficult to read. - The regret bounds depend on some factors about the size of the distribution class. For example, in contextual bandits, the regret bound depends on Regret_{log}(K). Similarly, in online and offline RL, the regret bounds depend on $|\mathcal{F}|$. The finiteness of distribution classes appears to be a fairly strong assumption in RL. - Accordingly, another concern is on the assumption that there exists good distribution classes that satisfy Bellman completeness. While it is mentioned in Section 5 that this assumption could hold under some special tabular MDPs, it is unclear how far this argument could go in the more general RL settings. - The numerical simulations only discuss the result of contextual bandits. While typically I would not complain about the simulations in a theory paper, I do think that experiments on both online RL and offline RL could be very helpful in understanding the connection between small loss bounds and the empirical regrets.

Questions

I agree with the authors that there is very limited theoretical understanding of distributional RL, and therefore overall I can appreciate the contribution of this paper which offers a new viewpoint for understanding distributional methods in RL. That said, the algorithms proposed and analyzed in this paper are all of MLE style, and somehow they are quite distant from the mainstream distributional RL methods (e.g., C51, QR-DQN, IQN, etc). While the results in this paper are nice to have, I am not sure by how much these analytical insights could benefit the understanding of these popular distributional RL methods. In other words, one of my concerns is that the usefulness of small-loss bounds is tied to the specific algorithms presented in this paper. It would be very helpful if the authors could comment on the connection between the small-loss bounds and other common distributional methods. Some detailed questions: - Line 55: The paper claims that triangular discrimination is a novel approach for decomposing the regret, but this idea has been adapted from [Foster and Krishnamurthy, 2021. - Line 131: The cost distribution should be some distribution in [0, H-h]? Similar issue occurs for the distribution of the loss-to-go in Line 146. - Lines 127&148: The notation \bar{C} and \bar{Z} is not defined. - Line 152: How to define the sum of two distributions (or two random variables)? Do we assume independence here? - In Algorithm, line 4 and Algorithm 3, line 3: What is $\bar{f}_1$ in line 3? - I am not sure how to compute the inner max of the confidence set. It seems that if the policy is not given, the \mathcal{F}, which is a function of {\pi}, is hard to compute. - There are many hyperlinks pointing to the wrong positions. - Line 626, the notation in this inequality is misleading, does f_1 only depend on x or (x,y)? I am starting with 5 and would be willing to raise the score if the authors could address these questions and the issues mentioned above.

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

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

3 good

Presentation

3 good

Contribution

3 good

Limitations

The authors do not describe any specific limitation of this paper.

Summary

This paper explores the benefits of distributional reinforcement learning (RL) and provides a mathematical basis for its advantages. Traditional RL approaches focus on learning the mean loss-to-go, but recent developments have shown that learning the entire loss distribution can lead to improved performance in various tasks. However, the theoretical understanding of why and when distributional RL works well has been limited. The paper introduces the concept of small-loss bounds, which are instance-dependent bounds based on the minimum achievable cost in the problem. By optimizing over distributional confidence sets constructed through distributional Bellman equations, the proposed algorithms achieve small-loss regret bounds in tabular Markov decision processes (MDPs) and small-loss PAC bounds in latent variable models. The paper also presents a distributional contextual bandit algorithm and an offline RL algorithm with a novel robustness property. Empirical results demonstrate the effectiveness of the distributional RL algorithms in challenging benchmark tasks.

Strengths

This paper investigates an important problem in theoretical RL and deepens our understanding of its benefits based on rigorous mathematical analysis. It proposes new distributional algorithms for contextual bandits, online and offline RL settings and provides corresponding small-loss bounds. The work presented in this paper is novel and original, to the best of my knowledge. The paper is well-structured, building from the simple setting of contextual bandits and then extending the analysis to more complex RL setups. The paper clearly states the assumptions, theorems and the proof sketches in each section and provides formal algorithms wherever required.

Weaknesses

The readability of the paper is poor owing to the large amount of text/math. It seems the authors have modified the spacing between lines and headings in some parts of the paper in order to adhere to the page limit.

Questions

None.

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

4 excellent

Presentation

2 fair

Contribution

3 good

Limitations

The paper includes a brief discussion of the limitations.

Summary

The paper's main concern is to theoretically understand why distributional RL achieves good performance. They consider three different settings: contextual bandit, online RL with an optimistic algorithm, and offline RL with a pessimistic algorithm. In each case, they use MLE to learn a distribution over the unknown cost (bandit case) and loss-to-go (RL case). The key technique that enables the proof is the relating a new notion of distributional regret to the regular regret; this is done by manipulation of distributional divergences. It appears that the key across settings is that distributional divergence gives more fine-grained control over value/cost differences compared to only looking at means. This enables them to provide small-loss bounds in each case. They validate their findings empirically for the contextual-bandit case.

Strengths

Significance and Originality: 1. The problem considered is important and relevant to practitioners. The authors do a good job in the introduction of motivating the theoretical conundrum. 2. The tools developed by the authors around distributional divergence are novel to the best of my knowledge. Quality 1. The results appear correct. And the settings considered are comprehensive across contextual bandit, online and online RL. 2. The empirical results display improved performance over well-chosen benchmarks.

Weaknesses

Clarity: 1. The regret decomposition using triangular discrimination, while novel, is intricate and difficult to interpret intuitively. If further intuition were provided, this would help inspire future theoretical work. 2. The writing is notation-heavy and takes a while to parse through and keep track of notation. 3. Relating to point 1, it would be nice if there were further connections to the practical applications around risk-sensitive RL, which are the primary motivating examples for distributional RL. This would help bridge the gap to practitioners.

Questions

1. The triangular discrimination technique seems central to converting distributional divergence into bounds on value difference. Intuitively, what are the main factors that enable the small-loss term to show up when distributional approaches are used? Are there ways to make this term appear without distributional RL? If not, is there reasoning for why it is not possible? 2. How restrictive are the realizability and Bellman completeness assumptions made in the analyses? Do you have a sense of how the techniques could extend to violated assumptions? 3. Would it be easy to generalize the results to linear MDPs? What obstacles may arise?

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

Yes

thanks for the response

Congratulations on your nice work. My major concerns have been addressed. I raise my score to 7 to support this paper for acceptance. Another minor comment is that you may check the techniques in [1] to see whether we can find more interesting examples as they also consider the linear eluder dimension of Hellinger/TV. [1] On the Statistical Efficiency of Mean Field Reinforcement Learning with General Function Approximation

Thanks for the response

Thank the authors for the detailed response. My main concerns about the BC condition, the distribution class, and the connection between the mainstream distributional RL and this paper have been addressed. With that said, I raise the score to 7 and vote for acceptance.