Bellman Unbiasedness: Toward Provably Efficient Distributional Reinforcement Learning with General Value Function Approximation

We sincerely thank the reviewers for their time and thorough evaluation of our paper. We have organized our responses to your comments below. Due to character limits, we have focused on addressing what we considered to be the most important comments. We ask for your understanding that we could not provide responses to all questions.

1. Theorem 5.5 says nothing about how well $n$-th moment are learnt.

First, we note that our paper investigates the necessary conditions for achieving provable efficiency and learning all moments simultaneously in distRL by using finite-dimensional sketch-based updates.

The reviewer’s concern seems to stem from the observation that standard regret is not well-suited for evaluating the effectiveness of distRL, as it fails to capture discrepancies in higher-order moments (order 2 and above). This may have led to a misunderstanding that SF-LSVI does not achieve moment matching. However, Lemmas 5.3 and 5.4 theoretically guarantee that all sketches are learned exactly in finite-dimensional spaces. The reason we use the standard regret in our quantitative evaluation is to follow the conventional regret analysis framework in RL literature.

2. Minor issues on theoretical claims

Thank you for the careful review of these points. It can be assured that the issues you raised do not change the theoretical results.

• (A2-1) In Lemma 3.2, since we derive a contradiction when $p_{y_0}>\alpha$ and $p_{z_0}<\alpha$ , we cannot include cases where $\alpha=0 \text{ or } 1$. Therefore, it is correct to modify it to $\alpha \in (0,1)$, which allows us to draw conclusions consistent with existing max and min functionals.
• (A2-2) If we understood your second point correctly, we believe the above response addresses it. If not, please let us know and we’d be happy to clarify further.
• (A2-3) Are you referring to $(\mathcal{B}\_r)$? For the max functional, since $\max_{z \in Z}(Z+r)=\max_{z \in Z}(Z)+r$ (and similarly for the min functional), $T_{\psi_\text{max}}$ and $T_{\psi_\text{min}}$ are valid operators. For clarity, we’ll revise Line 703 as:
  • $T_{\psi_\text{max}}\Big(\psi_{\text{max}}(\bar{\eta}(s))\Big)= \max_{s' \sim \mathbb{P}(\cdot|s,a)}\Big(r + \psi_{\text{max}}(\bar{\eta}(s'))\Big)$

3. Theorem 3.6 essentially reduces to the exact same result of [Rowland et al 2019]

Theorem 3.6 extends the results of [Rowland et al. 2019] by encompassing a broader class of statistical functionals. Since [Rowland et al. 2019] only focuses on linear functionals (i.e., $s(\mu)=\mathbb{E}_{Z \sim \mu}[h(Z)]$), they cannot demonstrate whether variance is a Bellman closed sketch.

However, since $\text{Var}(\mu) = \mathbb{E}\_{Z\_1 \sim \mu}[(Z\_1-\mathbb{E}\_{Z\_2 \sim \mu}[Z\_2])^2] = \mathbb{E}\_{Z\_1 ,Z\_2 \sim \mu}[Z\_1 ^2 -2Z\_1 Z\_2+Z\_2^2]=\mathbb{E}\_{Z\_1 ,Z\_2 \sim \mu }[h(Z\_1, Z\_2)],$ it is a functional that is homogeneous of degree 2. By Lemma 3.5, such functional is Bellman unbiased, and our result, Theorem 3.6 leads to the property that variance is also Bellman closed. That is to say, Theorem 3.6 can be summarized as a generalized conclusion that determines whether unbiasedly estimatable statistical functionals, which represent a broader domain, are Bellman closed.

4. Response to [Other Comments and Suggestions]

(A4-1) While $\eta^{\star}_h$ is generally not uniquely defined, this occurs in cases where $\pi^{\star}$ is not uniquely defined due to the lack of total ordering on distributions in a control case. We will mention this in [Bellemare et al 2017] along with a statement excluding such situations.

(A4-3, 5) We will add text defining linear functionals. As demonstrated earlier with the variance example, homogeneity is a separate concept that does not overlap with linear functionals. Therefore, the statement following Theorem 3.6 is valid.

5. Response to [Questions For Authors]

While the questions are beyond our current scope, they are insightful, and we would be happy to explore them further. Briefly speaking, we believe that the algorithm cannot achieve the tight regret bound if the bias does not converge to 0 during the learning process. However, due to the character limit and the possibility that these points are not central to the reviewer’s evaluation, we have chosen not to focus on them here. If the reviewer’s main concerns have been addressed, we will aim to revisit these topics in the next response round, as space permits.

We sincerely thank the reviewers for their time and thorough evaluation of our paper. We have organized our responses to your comments below. If any of our responses fail to address the intent of your questions or if you have remaining concerns, please let us know.

1. The advantage of SF-LSVI over standard expectation-based learning algorithm

SF-LSVI is an algorithm that has the advantage of accurately learning distribution information beyond expectation while maintaining a tight upper bound in terms of standard regret. Therefore, it has the advantage of being able to accurately obtain not only the mean but also various moment information.

However, the standard regret measure currently used to evaluate online RL algorithms cannot measure discrepancy in moments other than the first-order moment (expectation). Due to this inherent limitation of the measure, we do not believe it is suitable for distinguishing between the performance of expectation RL and distRL. As we wrote in the Conclusion section, we believe a generalized definition of regret that also evaluates discrepancies occurring in second and higher-order moments is needed, and we are pursuing this in our follow-up research.

2. How would parameter N affect learning and sample complexity?

Through Lemma 5.3, since the size of the confidence region increases as $\tilde{O}(\sqrt{N})$, the regret also reflects a factor of $\tilde{O}(\sqrt{N})$. Learning $N$ moments can be viewed as increasing the feature dimension by $N$ times, so space complexity adds a factor of $O(N)$, and according to [Jin et al 2020]'s results, (per-step) computational complexity adds a factor of $O(N^2)$. We will add this explanation to Theorem 5.5 for a deeper understanding of the results.

3. Relationship between Bellman unbiasedness and closeness

Bellman closedness refers to a property of sketches that allows accurate updating of distribution information when the transition kernel is given. However, in sample-based updates, since the transition kernel is not given, additional sketch properties beyond Bellman closedness are needed. Bellman unbiasedness refers to a complementary property that ensures unbiased learning of sketch updates through finite samples, and through this property, we can guarantee tight upper bounds in regret.

The position of categorical sketch in Figure 1 is based on the results from [Rowland et al 2019]. They showed that categorical sketch is a linear functional (Lemma 3.2 of [Rowland et al 2019]), and by our Lemma 3.5, since all linear functionals are homogeneous over degree 1, categorical sketch is Bellman unbiased.

The fact that categorical sketch is not Bellman closed was proven in Lemma 4.4 of [Rowland et al 2019], so combining these two results leads to the representation in Figure 1. We will clarify this process more explicitly in Figure 1 and Appendix C.

4. Alternative approach to estimate directly on the mixture distributions

A key distinction between "Bellman unbiasedness" and "Bellman closedness" is that we can learn exact information about the return distribution without the knowledge of the pre-defined transition kernel. This means SF-LSVI needs only a finite number of sampled sketches to learn the return distribution unbiasedly, rather than requiring knowledge of the transition kernel. As noted in Line 324, this unbiasedness property allows us to transform the learning process into a martingale, construct confidence regions through concentration inequality, and ultimately develop an algorithm that achieves tight upper bounds.

While we could introduce new definitions for sketches (such as max, min) that can be estimated consistently but with bias, constructing confidence regions for non-martingale processes remains largely unexplored without distribution priors. The theoretical analysis of such an approach would likely be extremely challenging.

References

• [Jin et al 2021] : Jin, Chi, Qinghua Liu, and Sobhan Miryoosefi. "Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms." Advances in neural information processing systems 34 (2021): 13406-13418.

• [Rowland et al 2019] : Rowland, Mark, et al. "Statistics and samples in distributional reinforcement learning." International Conference on Machine Learning. PMLR, 2019.

We sincerely thank you for your time and effort in reviewing our paper. We have organized our responses to your comments below. If any of our reconstructed responses miss the intent of your questions or if there are remaining concerns, please let us know so we can address them.

1. Concrete examples of statistical functionals

In our paper, we indicated in Figure 1 that max and min are Bellman closed but not unbiased statistical functionals, and the proof for this is provided in Appendix C.2. To make it easier to follow, we will add a note in the main text stating that 'the proof is included in the appendix.' For the categorical sketch, since Lemma 4.4 of [Rowland et al 2019] proves that it is not Bellman closed, we did not include a separate proof. We will update Figure 1 in the main text to include a reference to their proven result.

2. Bellman unbiasedness vs Closedness

First, Theorem 4.3 from [Rowland et al 2019] states:

The only finite sets of statistics of the form $s(\mu)=\mathbb{E}_{Z\sim\mu}[h(Z)]$ that are Bellman closed are ...

In other words, they provide theoretical results for sets of "linear" statistical functionals that satisfy Bellman closedness. Since max and min are non-linear statistical functionals that fall outside the scope of their theory, we cannot determine whether they are Bellman closed.

Similarly, since variance is nonlinear, we cannot determine its Bellman closedness using their results. However, since we already know that first and second moments are Bellman closed, we can naturally derive that variance is Bellman closed. Therefore, this indicates that their theory does not sufficiently cover various commonly used statistical functionals. Keeping this in mind and comparing with Rowland's theory, our theory can be interpreted as a generalized result that is helpful to test Bellman closedness for a broader category of unbiasedly estimatable statistical functionals.

Although the second question falls outside the scope of our paper, it raises important points to address by breaking it into two parts.

"For a given transition kernel, does a nonlinear Bellman closed sketch always have a fixed point?"

Since Lemma 3 in [Bellemare et al 2017] proves that the distributional update is a contraction, we can see that statistical functionals with bounded values also converge to a fixed point.

"In sample-based updates without a given transition kernel, does a nonlinear Bellman closed sketch always have a fixed point?"

Our paper proves convergence for Bellman unbiased sketches in a scenario with "only finite sampling allowed without a given transition kernel," but does not examine convergence for other Bellman closed sketches. Since max and min are Bellman closed but nonlinear, we cannot use existing linearity-based contraction proofs. A separate proof approach would be needed, making this an interesting direction for future work.

3. Translating results to discount case

While regret analysis for the infinite horizon discounted case falls outside the scope of our current paper, we believe it presents an interesting problem. In our results, when performing $N$ sketch-based updates, there is no additional cost beyond the confidence region increasing by a factor of $\sqrt{N}$, so we expect that in the discount case, there would also be an additional factor of $\sqrt{N}$ involved.

4. Lack of empirical validation

While we acknowledge the importance of experimental results, our paper aims to theoretically connect two fields - distRL and General Value Function Approximation (GVFA) - so our main contribution lies in establishing theoretical foundations and broadening understanding. We kindly request that you consider this in your evaluation, as many GVFA papers with similar objectives [Jin et al 2021, Li et al 2024] also do not necessarily include experimental validation.

References

• [Rowland et al 2019] : Rowland, Mark, et al. "Statistics and samples in distributional reinforcement learning." International Conference on Machine Learning. PMLR, 2019.
• [Bellemare et al 2017] : Bellemare, Marc G., Will Dabney, and Rémi Munos. "A distributional perspective on reinforcement learning." International conference on machine learning. PMLR, 2017.
• [Jin et al 2021] : Jin, Chi, Qinghua Liu, and Sobhan Miryoosefi. "Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms." Advances in neural information processing systems 34 (2021): 13406-13418.
• [Li et al 2024 ] : Li, Yunfan, and Lin Yang. "On the model-misspecification in reinforcement learning." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.

We sincerely thank the reviewers for their time and thorough evaluation of our paper. We have organized our responses to your comments below. If any of our responses fail to address the intent of your questions or if you have remaining concerns, please let us know.

1. Lack of empirical validation

While we acknowledge the value of experimental results, our primary aim is to establish theoretical connections between distributional RL and General Value Function Approximation (GVFA). Our main contribution lies in developing theoretical foundations and deepening understanding of these fields. We note that many GVFA papers with similar theoretical objectives [Jin et al 2021, Li et al 2024] likewise focus on theoretical advances without experimental validation.

2. Potential applicability in deep reinforcement learning scenarios

Thank you for your interest in deep RL applications. Our SF-LSVI algorithm, which learns distributions via moment matching, can be related to MMDQN [Nguyen et al., 2021] when adapted to deep RL. Notably, MMDQN has already demonstrated superior performance compared to C51, QRDQN, and IQN.

While MMDQN uses particle-based moment matching, SF-LSVI explicitly constructs and updates predefined moment functionals. Since it is well known that, in truncated moment problems, 10-20 moments typically suffice for reconstructing distributions, we could learn the sketches of distribution (moments) more efficiently than existing distRL methods that require 50-200 statistical functionals.

References

• [Jin et al 2021] : Jin, Chi, Qinghua Liu, and Sobhan Miryoosefi. "Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms." Advances in neural information processing systems 34 (2021): 13406-13418.
• [Li et al 2024] : Li, Yunfan, and Lin Yang. "On the model-misspecification in reinforcement learning." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.
• [Nguyen et al 2021] : Nguyen-Tang, Thanh, Sunil Gupta, and Svetha Venkatesh. "Distributional reinforcement learning via moment matching." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 10. 2021.