Mitigating Suboptimality of Deterministic Policy Gradients in Complex Q-functions

We appreciate the reviewer for their thoughtful evaluation and valuable ideas to improve our method. We are pleased that you appreciated the motivation and evidence of the suboptimality problem, paper writing, extensive experiments, and trade-off of compute and performance. We incorporate all your suggestions below:

1. Added Q-smoothing as a baseline

The surrogate value function also requires a smooth version to improve performance. Is it also possible to add smoothness to the original Q-value? It would be helpful to add it as a baseline.

Thank you for your insightful suggestion! Notably, we had already done this study and our baselines already incorporate smoothness over the Q-value in discrete action space tasks, where it was deemed necessary. Based on your question, we have added an exhaustive analysis in Appendix G.6, Figure 24, and Table 2.

We empirically analyze the effect of Q-smoothing, where an auxiliary Q-function smooths the primary Q-function to ease gradient flow, just like an approximate surrogate does for the hard-threshold surrogate (Section 4.4).

This table compares the performance of baselines with and without Q-smoothing across tasks. 1-Actor k-Samples or Wolpertinger [Naive] significantly underperforms in discrete action space tasks, and thus, we already reported results on Wolpertinger [Q-Smoothing]. In continuous action space tasks, there was no benefit to Q-smoothing, and thus we chose to report results on Wolpertinger [Naive] as it is closer to the underlying TD3 algorithm. Note that the same Q-smoothing principle is already applied for TD3, SAVO, and all baselines, i.e., their Q-function is smoothed in discrete action spaces, but unsmoothed in continuous action space tasks.

1. Discrete Action Space results have Q-smoothing: Q-smoothing is essential for discrete tasks, facilitating gradient flow on points in the space that lie between the action representations of true actions. This helps because an actor can query for gradients anywhere, but it is not necessary that the Q-landscape is meaningful there. Smoothing ensures gradients towards valid actions’ Q-values.
2. Continuous Action Space results do not have Q-smoothing: Q-smoothing provides no benefit in continuous tasks, as gradients are naturally preserved.

2A. Added comparison to specialized initialization for diverse actor-surrogates

The diversity of policy function and surrogate value function will have a large influence on the algorithm's final performance. For the policy, do special initialization techniques increase the diversity of the policy and improve its performance?

This is an insightful suggestion! We did not explicitly enforce diversity in the actors and surrogates, and initialized the networks with standard Xavier initialization. However, based on your suggestion, we tried 2 specialized initialization strategies:

• Random: weights are initialized from standard Normal distribution, instead of Xavier. ⇒ w = noise $\sim \mathcal{N}(0, 1)$
• Add: weights are initialized with Xavier, but then standard normal noise is added. ⇒ w = Xavier-init + noise $\sim 0.5 * \mathcal{N}(0, 1)$

The reward curves are reported in Figure 25 and their performance summarized below:

1. MineWorld: Add $\approx$ Random $\approx$ Xavier
2. RecSim: Add $\approx$ Random $\approx$ Xavier
3. Hopper (Restricted): Add $\approx$ Random $\approx$ Xavier
4. Adroit Door : Add $\approx$ Random < Xavier

Thus, specialized initialization to enforce larger diversity did not boost performance. However, we believe incorporating diversity as an explicit objective could be a helpful heuristic and will investigate it in the future, thank you again for a great suggestion!

2. Added experiment: SAC+SAVO > SAC

The experiment environments are quite simplistic with only one set of 3D environments. There needs to be more analysis on how this method works with high dimensional continuous state and action spaces, especially because here Q would be a function of these high dimensional parameters. In SAC’s original paper, they baseline with Ant and humanoid, and SAVO should be compared to those environments as well.

We highlight the existing and new results to address this concern:

• The 3 Adroit environments have a high-dimensional 28-D action space and RecSim and RecSim-data have 45-D action representation space.
• Appendix reports results on unrestricted locomotion in Ant-v4 and HalfCheetah-v4 in Figure 15 (we did not create restricted versions of these environments). SAVO matches the performance of TD3 here, but does not improve, likely because there is no suboptimality to mitigate — for unrestricted Inverted Pendulum and Hopper, the Q-landscapes are fairly convex (see Figures 29, 31).
• In the new results, SAC underperforms in Ant and HalfCheetah, and SAC+SAVO mitigates SAC's suboptimality successfully in Figure 28 (details below).

Since SAC is another method that proposes to exit local optima with the stochastic actor and entropy objective, a full comparison between SAVO + DDPG/TD3 and SAC (+ SAVO) should be done.

We appreciate your insightful comment. In response, we have extended our analysis to include both theoretical explanations and experimental results demonstrating that A. SAC also suffers from gradient-descent-based local optima in the soft Q-landscape, and B. SAC+SAVO enhances SAC's performance in high-dimensional continuous state and action spaces.

[A. SAC is susceptible to local optima in soft Q-landscape]

DPG-based methods like TD3 optimize the following maximization problem with gradient ascent:

In contrast, SAC learns stochastic policies and augments the objective to encourage exploration through entropy maximization, optimizing:

where $\mathcal{H}(\pi(\cdot | s)) = -\mathbb{E}_{a \sim \pi} [\log \pi(a | s)]$ is the entropy of the policy, and $\alpha > 0$ controls the weight of the entropy term.

$\implies$ Even with entropy regularization, SAC's policy gradients still rely on the soft Q-function $Q^\pi(s, a)$, which can possess local optima due to inherent non-convexity of the MDP’s reward structure. This non-convexity arises from complex relationships between the agent’s actions and the environment rewards. Consequently, SAC’s stochastic actor can get stuck in the local optima (in the KL-divergence sense) within the soft Q-landscape, limiting its performance.

[B. SAVO+SAC outperforms SAC]

We perform a preliminary analysis of combining SAVO with SAC, where we learn a maximizer stochastic actor $\pi_M$ that selects from successive stochastic actors $\nu_i(s; a_{<i})$ with the entropy regularized objective.

We evaluated this SAC+SAVO approach alongside SAC in three continuous control environments: Restricted Inverted Double Pendulum, unrestricted Ant-v4, and unrestricted HalfCheetah-v4. Figure 28 shows SAC is suboptimal (note that we directly use stable-baselines3 SAC implementation), even worse than TD3, but SAVO+SAC is significantly better. We draw these key insights:

• Improved Performance: SAC+SAVO consistently outperforms SAC in all evaluated environments, indicating that SAVO effectively mitigates the susceptibility of SAC to local optima.
• High-Dimensional Action Spaces: SAC successfully improves suboptimality, when present, in high-dimensional action spaces like Ant-v4 and HalfCheetah-v4.
• SAC improvements are orthogonal to SAVO: Figure 18 already showed that in different restricted locomotion tasks, SAC may or may not be better than TD3, but SAVO+TD3 is always better than TD3, mitigating its suboptimality in non-convex Q-landscapes.

We sincerely thank the reviewer for their thoughtful evaluation and valuable feedback. We are pleased that you appreciated the paper writing, motivation of the suboptimality problem, the tabu-inspired approach, and overall novelty. We address your concerns below.

1. Added analysis on the optimal number of surrogates

1. The complexity of the true underlying Q function should affect how many surrogates are needed. There should be an analysis or heuristic on how to determine the optimal or necessary number of surrogates needed for a particular task. This will also determine the computational viability of SAVO, in situations where we might require several surrogates to converge to global optima.

Thank you for this great suggestion! We have run an exhaustive study to analyze how many surrogates are needed to reach near-optimal performance in the various tasks we have. Appendix Figure 26 plots the performance by ablating the length of the actor sequence on various environments. In the below table, we list the optimal number of actors beyond which the performance gain saturates. Note that the number of surrogates = length of actor sequence - 1.

Note: all other results in the paper were reported on a length of 3, across all environments, to keep a uniform hyperparameter across all tasks that addresses most of the suboptimality with a small amount of extra compute (Table 1).

[Key insights]

• The number of actors needed is a function of how severely non-convex the underlying Q-landscape is.
• For discrete actions, a larger action space and a larger dimensionality of action representations would likely imply a more challenging Q-landscape. Thus, RecSim with 10,000 actions and 45-D action representations needs 15 actors while MineWorld with 50 actions and 9-D action representations needs only 4 actors.
• For continuous actions, it is less a matter of how high-dimensional the action space is, but how non-convex is the Q-landscape on different states of the environment. Therefore, Restricted Hopper has a 3-D action space but has non-convexity on every state (because of restrictions) requires the equal number of actors as Adroit Door which has a 28-D action space but has non-convexity only in states that require precise manipulation.

[Heuristic Recommendation] We agree with the reviewer that it would be valuable to pre-determine the number of actors needed, but pre-determining this hyperparameter would be an open challenge. This number scales with the non-convexity of the underlying Q-function across all states of the environment, which is a property of the underlying MDP. Unfortunately, it is hard to make an accurate estimation of this non-convexity, because environments can require different kinds of decision-making at different states and the Q-landscape could look very different even within a single environment. This applies to any method trying to optimize these Q-landscapes. For instance, CEM would require more iterations of refinement of the action distribution and SAVO would require more actors.

We attempt to understand the non-convexity of Q-landscapes via visualizations shown in Figures 29-32 in 1-D action space and 3-D action space (by projecting it to 2D). But, such visualization is not possible in higher dimensional environments, because the 2D projection cannot preserve the information about non-convexity.

[Recipe for finding the optimal number of actors]

1. For any given task, we recommend mapping it to the closest environment that we have analyzed, such as Adroit Door for a manipulation task. Then, we start with that number of actors, such as 5 or 10.
2. Next, we can employ exponential search or doubling search, where the number of actors is doubled until diminishing returns: 5 → 10 → 20 → ...

We sincerely thank the reviewer for their thoughtful evaluation and valuable feedback. We are pleased that you appreciated the identified problem, the novelty of our approach, and the convergence proof. We address your concerns below.

1. [Q] Quality of Action Proposals. [A] SAVO proposes better actions than baselines by using tabu-based surrogates

Quality of Action Proposals: I'm wondering whether the quality of action proposals from additional policies could affect the effectiveness of the maximizer actor? If these proposals are not close to the optimal actions, the maximizer actor’s effectiveness is limited, as it can only select from the actions provided.

Precisely! Your comment aptly describes the capability and limits of the maximizer actor. Since one of the action proposals comes from the original actor, the maximizer actor is guaranteed to improve over it. However, the maximizer actor would only improve if the action proposals are of better quality. This is exactly why simple ways to propose actions such as Ensemble and 1-Actor k-Samples baselines are not sufficiently effective in experiments (Figures 7a, 8).

To address this limitation, SAVO introduces the idea of successive surrogates that reduce local optima (Section 4.2) and successive actors that propose effective actions by gradient-ascending these surrogates (Section 4.3). As a result, our proposed algorithm SAVO outperforms the baselines because SAVO improves the effectiveness of the maximizer actor with higher quality action proposals.

While it is true that achieving global optimum cannot be guaranteed, SAVO significantly mitigates the suboptimality of the underlying DPG-actor with additional actor-surrogate pairs. Furthermore, SAVO’s quality of action proposals scales well with more actors and surrogates (Figure 11a,b). In conclusion, SAVO offers a gradient-based method that is fast at inference (unlike CEM), while finding near-optimal actions to improve over a single gradient-based actor. To our knowledge, our work is the first to identify the challenge of local optima in gradient-based actors and propose an efficient solution to it.

2. Added Surrogate Sensitivity Analysis: show surrogates stay up-to-date with the Q-function

The effect of smoothing in highly dynamical environments : In rapidly changing Q-landscapes, the surrogate-based tabu regions may become outdated, potentially causing the actor to miss newly optimal regions

[Surrogates are updated throughout training]

We clarify a potential misunderstanding about surrogates being outdated here. The surrogates are actually updated alongside the Q-function at every training step with Eq. 9.

So, whenever the Q-function is updated with a training sample $s_t, a_t, s_t’, r_t$, the surrogates are also updated at

• (i) $a = a_t$, because that’s where the Q-function has latest updates $\implies$ capture newly discovered optimal regions, and
• (ii) $a = \nu_i(s_k; a_{<i})$ because that’s where training the i-th actor $\nu_i$ requires a gradient $\implies$ make surrogate up-to-date just before a gradient query is made.

A sensitivity analysis on surrogate accuracy could clarify whether this might be happening (specially with the more complex and dynamical tasks where the performances are mediocre)

[Added sensitivity analysis of the surrogate accuracy: Figure 23] Thank you for this great suggestion (also: Reviewer S3Pa)! We have added this in Appendix G.5 and plotted $\frac{\text{Surrogate Approximation Error}}{\text{Bellman Error}} \\%$ for all environments in Figure 23, where the numerator is $\mathcal{L}_\text{approx}$ from Eq. 9. We observe the following:

• Low Error: Surrogates converge to 1—10% of the Bellman error, successfully tracking Q-function changes.
• Non-zero error ensures smoothness: Non-zero error ensures gradients propagate in flat regions, preventing stagnation, as proposed in Section 4.4.

This analysis confirms surrogates remain accurate, simplify Q-landscapes, and enable robust gradient flow. Empirically, we showed that this approximation is necessary, because SAVO beats its ablation without approximation underperforms in Figures 7b, 22.

Q. How is the quality of the surrogate Q-landscape monitored to avoid filtering out high-reward regions? Is there a mechanism to re-evaluate excluded areas if necessary?

We hope the above discussion clarifies that Equation (9) “re-evaluates” the surrogate at every step. No high-reward region from the Q-function is excluded because the information is propagated into the surrogate both (i) immediately and (ii) before a gradient query. This ensures that the surrogate remains accurate and up-to-date.

We appreciate your time and effort to review our work. Since it is the last day of discussion, we would be grateful for any comments or suggestions in response to our rebuttal, and we would be happy to incorporate any specific suggestions. If our response adequately addresses your concerns, we kindly request to consider revising your score. Thank you.

To summarize the key improvements made in response to your feedback:

1. We added more empirical evidence:

• (i) SAVO improves further with more actors (Fig. 27).
• (ii) SAC + SAVO > SAC in Ant, HalfCheetah (Fig. 28).

2. We added surrogate approximation loss analysis plot that shows SAVO stays up-to-date to true Q-value throughout training (Fig. 23).
3. We emphasize SAVO’s core contribution is explicitly improving the quality of action proposals using tabu-based surrogates, thus beating naive maximizer-actor baselines (Fig 7a, 8).
4. We highlight that SAVO “mitigates” the suboptimality in non-convex Q-landscapes, thus its gains are targeted to tasks where TD3 / SAC suffers. It outperforms TD3 significantly in non-convex Q-landscapes (Fig 7,8,10,19) and matches performance in simpler Q-landscapes (Fig. 15) because TD3 is already near-optimal there.