Gradual Transition from Bellman Optimality Operator to Bellman Operator in Online Reinforcement Learning

Thank you very much for the highly constructive feedback. We provide several responses below.

Evaluation using optimality gap

Thank you for the suggestion. As we understand it, the optimality gap refers to how much the agent's performance falls short of a target score, such as a human-level or oracle performance. In our tasks, however, such target scores are not always clearly defined. If the maximum achievable score in the task (e.g., 1000 in DM Control) is considered as the target, then we assume the optimality gap corresponds to the difference between 1000 and the agent’s average score. If this interpretation is incorrect, we would greatly appreciate clarification.

Evaluating overestimation via Q-value gap

In Figure 12, we report the gap between the estimated Q-values and the actual Q-values computed via Monte Carlo return, across our proposed method and several ablations. In AQ-SAC, our proposed method, we observe that the bias is initially larger—potentially encouraging exploration—but gradually decays to a level comparable with the SAC (SARSA-based method) toward the end. This behavior aligns with our intended design.

Theoretical basis and impact of the annealing scheme

If we focus solely on optimality, when $\tau$ = 0.5, the max operator in Equation (3) of our paper is replaced by an expectation, turning the inequality into an equality. As a result, no bias is introduced, allowing for a more optimal value estimation. On the other hand, $\tau \simeq 1$ corresponds to the max operator, which introduces bias. Therefore, we anneal $\tau$ toward 0.5 during training to reduce bias and eventually enable the estimation of an optimal policy. It is an open question, as the reviewer correctly pointed out, how the max operator and bias affect the speed of improvement, and it is theoretically challenging to characterize this relationship. The table included in our response to Q2 of reviewer dvAE provides additional empirical evidence suggesting that bias can promote exploration, thereby highlighting the effectiveness of our method.

Thank you again for the valuable feedback. If you have any further concerns, we would be happy to address them.

Thank you for the valuable feedback. Please find our responses below.

What is the justification for the linear decay in w?

As shown in Table 4 and Figure 18, we experimented with several annealing patterns and found that linear decay achieved sufficiently good performance. While other patterns or adaptive strategies could also be viable design choices, we prioritized simplicity in this work.

Why in the cheetah-run and humanoid-stand environments, are the proposed methods less efficient than some oracle methods? Especially, it seems that SAC is still the best in the latter one?

In the cheetah-run environment, even the base algorithms such as SAC and TD3 converge relatively quickly to high performance. This suggests that sufficient exploration and improvement in policy optimality are already achieved without the need for further bias-induced acceleration. In such cases, the additional bias introduced by AQL may outweigh its benefits, leading to lower overall efficiency. This interpretation is supported by Figure 13, where reducing the initial value of $\tau$ helps mitigate the bias and results in convergence speeds comparable to SAC.

A similar explanation applies to the humanoid-stand environment. Here, a high initial $\tau$ value of 0.9 likely introduces excessive bias, again offsetting the intended benefits of AQL. When $\tau$ is reduced to 0.7 or 0.8, the convergence becomes comparable to SAC, which further supports this hypothesis.

These observations indicate that the inefficiency of our method in these environments can be mitigated through appropriate tuning of $\tau$. Importantly, regardless of the $\tau$ setting, the final returns achieved by our method remain competitive highlighting the robustness of the proposed approach.

For the results of biases in Figure 12, how about annealed $\tau$?

The AQ-SAC results in Figure 12 correspond to the case where $\tau$ is annealed from 0.9 . In AQ-SAC, the initial bias increases, which can contribute to exploration, and then gradually decreases to a level comparable to the SARSA-based approach (SAC) toward the end. This behavior aligns with our intention. Similar trends were observed when annealing from different initial values of $\tau$, and we will include these additional results in the camera-ready version.

Line 212–213: what is the expectation over (where is the randomness)?

The expectation is over the randomness in the Q-function, specifically the variable $\epsilon$ mentioned in the following sentence. We will add a clearer explanation to improve readability.

We sincerely appreciate your helpful feedback once again. We hope that our responses have sufficiently addressed your concerns. If there are any remaining issues, we would greatly appreciate your guidance on what further explanations or revisions would be necessary to improve your score.

Thank you very much for pointing out that interesting and important prior work.

BEE and AQL share a similarity in that both utilize the Bellman optimality operator based on in-sample maximization as well as the Bellman (expectation) operator. As the reviewer correctly noted, the key difference lies in the motivation. While BEE focuses on addressing underestimation, our approach emphasizes the potential benefits of overestimation in promoting learning, as supported by our preliminary experiments. Moreover, our method introduces a scheduling strategy that gradually decays optimality over time—a scheduling not explored in BEE.

Additionally, unlike BEE, which combines the outputs of two separate Q-functions using different operators, our approach transitions gradually from one operator to the other. This allows us to maintain a single Q-function throughout training, simplifying the overall design.

Therefore, our method can be seen as a simplification of BEE that introduces a novel motivation and scheduling mechanism to decay optimality, while relying on a single Q-function.

We agree that the relationship with BEE is highly relevant, and we will revise our camera-ready version to explicitly discuss this connection and clarify our contributions accordingly.

The hyperparameters used in our experiments are listed in Appendix B. To further improve clarity, we will also include an overview table summarizing them in the camera-ready version.

Once again, we sincerely appreciate the valuable feedback. We hope that the inclusion of this discussion in the paper addresses your concerns. If not, we would greatly appreciate it if you could let us know what further explanations or revisions would be needed to improve the score.

Thank you very much for the highly valuable feedback. The concerns are comprehensively covered in the "Claims and Evidence" section. Below, we provide responses to each of the specific points mentioned there.

1. Why use annealing between max-Q and SARSA? If max-Q causes overestimation, why not reduce it directly? And if SARSA is suboptimal or slow, why use it at all?

Max-Q introduces an overestimation bias, but as discussed later, this can encourage exploration. Therefore, reducing this bias directly may not always be desirable.

The reviewer asks, “If SARSA leads to suboptimal or slow learning, why use it at the end of training?” However, we emphasize that SARSA’s value estimates are not suboptimal. As an on-policy method, SARSA avoids the distribution mismatch between the actions used for target estimation and those actually taken. Furthermore, since SARSA does not involve Max, it introduces less bias. Although it may learn more slowly, it provides more accurate value estimates, as shown in Section 3.2.

2. How early max Q update leads to better exploration. There is no experiment that validates this claim.

We agree and appreciate this point. To address it, we measured policy entropy during early training. The table below shows average entropy over DMC tasks for SAC (Fixed (0.5), (0.7), and (0.9)), corresponding to SAC with expectile loss with $\tau = 0.5, 0.7, 0.9$. As shown in Figure 12, these methods exhibit overestimation bias in the order: Fixed (0.9) > Fixed (0.7) > SAC. The entropy follows the same trend, suggesting higher bias leads to broader exploration.

This supports the intuitive hypothesis that overestimation can lead to suboptimal actions due to inflated Q-values, promoting exploration. Prior work (e.g., Section 3 of [1]) also demonstrates that overestimation can be beneficial in tasks where exploration is important, while it degrades performance in tasks where exploration is undesirable. These results support the claim that overestimation bias promotes exploration.

We will include these points in the camera-ready version to clarify the link between exploration and overestimation.

[1] Q. Lan, Y. Pan, A. Fyshe, and M. White. Maxmin q-learning: Controlling the estimation bias of q-learning. In ICLR, 2020.

Table: The average policy entropy in DM Control tasks. 15k steps corresponds to shortly after training begins at 10k steps.These results suggest that a large $\tau$ in the early stages of training increases policy entropy and promotes exploration.

3. Why not just use max-Q throughout, since overestimation can be mitigated by exploration? Why is it necessary to balance max-Q and SARSA-style updates?

While exploration can reduce overestimation, it doesn't eliminate it entirely. As shown in Figures 2 (right) and 12, higher $\tau$ values lead to greater final bias, exceeding that of SAC, a SARSA-style method. AQ-SAC starts with $\tau = 0.9$ to encourage exploration but gradually reduces bias to SAC's level, highlighting the benefit of balancing max-Q and SARSA updates. Fixed $\tau$ settings (e.g., 0.9, 0.95) perform poorly (Table 2), indicating that persistent overestimation harms optimality. While overestimation tends to diminish with more data, prior studies [1,2,3] have shown that actively suppressing it can significantly enhance sample efficiency. Balancing both perspectives, our method offers a natural compromise.

[2] Deep reinforcement learning with double Q-Learning. Hado van Hasselt, Arthur Guez, David Silver. AAAI 2016.

[3] Addressing Function Approximation Error in Actor-Critic Methods. Scott Fujimoto, Herke van Hoof, David Meger. ICML 2018.

4. If a well-chosen fixed τ performs similarly to annealing, is the added complexity of annealing really necessary?

We acknowledge that a carefully selected fixed $\tau$ can yield good performance. However, as shown in Table 2, performance becomes highly sensitive to $\tau$ when it increases beyond a certain threshold, and performance can deteriorate significantly due to the increased bias.

In RL tasks where sample efficiency is critical and many hyperparameters are inherently delicate, it is often impractical to finely tune all hyperparameters. In this context, our annealing strategy, which provides robustness against hyperparameter sensitivity, is a meaningful advantage.

Once again, we sincerely appreciate the thoughtful and constructive feedback. It has helped us clarify and strengthen the motivation and evidence behind our proposed method. Please feel free to let us know if you have any further questions or concerns.

Thank you very much for your insightful and helpful comments. Below, we address each of the points raised:

Additional experiments (Longer runs on Humanoid-Walk/Run, DMC Dog tasks, action penalty env, D4PG baseline):

We appreciate the suggestion to conduct additional experiments. Due to limited computational resources, it is difficult to perform all the experiments; however, we have started running several of them and will share the results once they are complete.

Related work [1, 2]:

Thank you for pointing out the name collision with Amortized Q-learning. We will rename our method to AQ-L in the camera-ready version to avoid confusion. We also appreciate the pointer to [2], and we will add a discussion on this work as part of the related research on action discretization.

Potential extensions towards distributional RL:

As in QR-DQN [3], estimating Q-values for each discretized expectile and progressively reducing the target expectile may improve the consistency of the loss function during training. We believe this is a promising direction for extending our approach.

Line 409 – Counter-argument to "accurate action selection becomes difficult":

While discretization can be sufficient in certain tasks, it may lead to reduced sample efficiency in high-dimensional settings. For example, in the humanoid-run task, our method achieves a return of 250 within 3M steps, whereas [2] requires over 5M steps to reach the same performance. We will incorporate this discussion, including the effectiveness of discretization in lower-dimensional tasks, into the camera-ready version.

Figure 5 caption — "locomotion tasks" → "manipulation tasks":

Thank you for catching this error. We will correct it in the final version.

Once again, we sincerely thank you for the constructive and valuable feedback. Please feel free to reach out if there are any further questions or points that require clarification.

[1] T. Van de Wielde, et al. "Q-learning in enormous action spaces via amortized approximate maximization." arXiv, 2020.

[2] D. Ireland, and Giovanni Montana. "Revalued: Regularised ensemble value-decomposition for factorisable markov decision processes." ICLR, 2024.

[3] Will Dabney, Mark Rowland, Marc G Bellemare, and Rémi Munos. Distributional reinforcement learning with quantile regression. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.