Mitigating Suboptimality of Deterministic Policy Gradients in Complex Q-functions

Authors: Ayush Jain, Norio Kosaka, Xinhu Li, Kyung-Min Kim, Erdem Biyik, Joseph J Lim
Primary area: reinforcement learning
Keywords: Deterministic Policy Gradients, Complex Q-functions, Actor-critic RL, TD3.

Abstract:
In reinforcement learning, off-policy actor-critic approaches like DDPG and TD3 are based on the deterministic policy gradient. Herein, the Q-function is trained from off-policy environment data and the actor (policy) is trained to maximize the Q-function via gradient ascent. We observe that in complex tasks like dexterous manipulation and restricted locomotion, the Q-value is a complex function of action, having several local optima or discontinuities. This poses a challenge for gradient ascent to traverse and makes the actor prone to get stuck at local optima. To address this, we introduce a new actor architecture that combines two simple insights: (i) use multiple actors and evaluate the Q-value maximizing action, and (ii) learn surrogates to the Q-function that are simpler to optimize with gradient-based methods.
We evaluate tasks such as restricted locomotion, dexterous manipulation, and large discrete-action space recommender systems and show that our actor finds more optimal actions and outperforms alternate actor architectures.

Decision: reject
Reviewer scores: 5, 5, 8

Reviews and discussion:
<thread>
creation date:
1730394559170

thread_type:
official_review

<thread_object>
creator: reviewer_6956

<content>
summary:
The paper presents a new actor architecture that combines multiple actors and simplified Q-function surrogates. The new method eases the challenge of maximizing Q-function in complex tasks like dexterous manipulation and restricted locomotion.

strengths:
1. The paper has a clear motivation for the challenge of maximization Q-function in commonly used deterministic policy gradient algorithms. Figures 1-3 are all strong evidence of this problem. 
2. The paper is well-written. Especially for the transition from Section 3 to Section 4, the connection is quite natural. The introduction of the main method of SAVO is also clear. 
3. The extensive experiments (5 environments) also strongly prove the effectiveness of the SAVE architecture. 
4. It is very appreciated that the authors also mention about the potential limitations in the inference time of the proposed method. I think it's a nice trade-off between better optima and computational efficiency.

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

questions:
1. The diversity of policy function $\nu$ and surrogate value function $\Psi$ 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? For the value function introduced in 4.4, is $Q(s, a)$ different from $Q^{\mu_M}(s,a)$ with separate neural networks? Besides, both policy and value function requires conditional input on the previous action. How to deal with the variational number of inputs? 
2. If the action dimension is large, maximizing Q-function could be even harder. Do you recommend using the SAVO method could potentially require more agents?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730416711993

thread_type:
official_review

<thread_object>
creator: reviewer_s3pa

<content>
summary:
Summary Of The Paper:

The paper develops a method to mitigate actors from getting stuck in a locally optimal Q value. Their proposed method considers producing surrogate estimates of the Q landscape based on the last seen maximum Q value, and restricts the actor from making actions in local optima through a successive actor architecture.

strengths:
The paper is easy to read, and generally well written and is well motivated by the issue of converging to a local optima.

The idea of restricting local optimal using tabu search in this successive manner is very interesting.

The idea appears fairly novel. The closest work to this is probably SAC, although this paper is quite a bit different in motivation. This helps with novelty.

weaknesses:
### Weaknesses

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.

2. 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. Since SAC is another method that proposes to exit local optima with the stochastic actor and entropy objective, a full comparison between SAV + DDPG/TD3 and SAC (+ SAVO) should be done.

3. Surrogates are trained via L2 loss. How do we know if the surrogates have approximated modified Q function sufficiently? What if there are margins of errors that potentially result in the surrogates converging to local optima. Then how do we diagnose or detect these problems? It seems like SAVO involves increasing the number of hyperparameters that require tuning. How sensitive is the training regime of the surrogates, and at what point do they yield no benefit compared to the baseline architectures? How do the design choices of the surrogates impact the stability of training? This method adds a lot of overhead on top of something like DDPG. That's my biggest worry about the paper. 

4. It would be nice to better understand the generalizability of SAVO to other environmental regimes. How does SAVO perform in sparse reward environments? It seems that SAVO is highly dependent on how well we estimate the truncated Q through surrogates. It would be helpful to see how SAVO can help with improving HER or other actor critic architectures.

questions:
Section 4.3 defines \nabla \Psi as a function of \nabla Q. Is \Psi simply Q + constant with the truncation term?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730781380006

thread_type:
official_review

<thread_object>
creator: reviewer_pevp

<content>
summary:
This paper introduces the *Successive Actors for Value Optimization (SAVO)* algorithm, addressing the non-convex Q-function landscapes. The claim is that in high-dimensional and multimodal action spaces, Q-functions often exhibit numerous local optima, making it difficult for gradient ascent-based actors to discover globally optimal actions. This issue can lead to poor sample efficiency and suboptimal policy performance, even when the Q-function is accurate.

SAVO tackles both continuous and discrete action settings (recommender systems). However discrete actions are mapped to a continuous representation space.

SAVO employs two main techniques: 
- **Maximizer Actor**: It instroduces a maximizer actor $\mu_M(s)$ that selects actions from a set of action proposals based on the higher Q-value. Proof has been provied that this method converges in the tabular setting and show that $\mu_M(s)$ is at least as good as the base policy $\mu$ based on the policy improvement theorem. This leads to a multi-actor architecture.
- **Successive Surrogates to Simplify the Q-Landscape**: Inspired by tabu search, SAVO progressively filters out suboptimal regions in the Q-landscape. By “tabu-ing” low Q-value areas, it reduces the number of local optima, thereby making gradient ascent more effective.

strengths:
- Ensemble of Actors: The ensemble-style actor, which combines policies and selects actions based on the highest Q-values, is novel afaik.
-  The surrogate Q-functions inspired by tabu search could potentially improve gradient-based optimization by reducing the number of local optima in the action space.
- The convergence proof for the maximizer actor in the tabular setting has been provided, although I did not have time to check in-depth.

weaknesses:
- Quality of Action Proposals: I'm wondering whether the quality of action proposals from additional policies $v_i$ 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. In other words, the performance of the maximizer actor is capped by the quality of these action proposals.

- 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. 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)

- Empirical Results: While results in Figure 8 show slight improvements on simpler tasks (e.g., Hopper, Inverted Pendulum), Figure 15 shows that SAVO’s performance on more complex tasks (e.g., Ant, HalfCheetah) is only on par with other methods, without demonstrating a clear advantage.
Same trend is observed for results on recommender system in Figure 20 and Figure 22.

Overall the empirical results in this paper are not compelling enough to show a clear advantage of SAVO over existing methods. Across tasks, the results show that SAVO often performs on par with or worse than baseline methods, failing to convincingly outperform them. Therefore it’s unclear to me whether the proposed strategy is genuinely addressing suboptimal behavior or simply matching baseline performance without significant improvement. This leaves some doubt about the effectiveness of the approach in achieving better optimization in complex Q-landscapes.

questions:
- 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?
- Figure 9 Plot: The third plot in Figure 9 appears misaligned, with lines and text outside the figure’s bounds.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732377276640

thread_type:
official_comment

<thread_object>
creator: area_chair_qrpo

<content>
title:
From AC

comment:
Dear authors,
If possible, I wanted to ask you to start a discussion with the reviewers by providing a rebuttal.

Thanks,
AC
</content>
</thread_object>

</thread>
<thread>
creation date:
1732619819120

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of revisions

comment:
We sincerely thank the reviewers for feedback and suggestions for improvements. We apologize for the delayed rebuttal, as we conducted all the suggested analysis and extension experiments to ensure a comprehensive response. We hope the following revisions fully address your concerns and look forward to further discussion.

&nbsp;

**[Summarizing reviews]**
- The reviewers appreciated the importance of the central problem, novelty and scalability of the tabu-inspired SAVO approach, theoretical guarantees, paper writing, and extensive experiments on various benchmarks, baselines, and analyses.
- The primary feedback was to conduct **analyses** of (i) the approximation error of surrogates, (ii) the optimal number of actors needed, and (iii) SAVO’s performance on high-dimensional locomotion like Ant. Further suggestions included **extending** SAVO to SAC and enforcing diversity in SAVO.

&nbsp;

**[Summary of Revisions]**  
We have exhaustively run the requested experiments, with updates to the paper highlighted under blue headings:
1. **Analyze surrogate approximation error** as a percentage of the Q-function bellman error across all tasks: `Appendix G.5`  
$\implies$ the error stays small, meaning surrogates easily stay up-to-date to the Q-function, while being smooth.
2. **SAC+SAVO experiment**, which outperforms SAC in tasks like Ant and HalfCheetah: `Appendix J.`  
$\implies$ TD3+SAVO $\approx$ TD3 > **SAC + SAVO > SAC**
3. **Find optimal number of actors** for SAVO to attain maximum performance in diverse environments: `Appendix I`  
$\implies$ 10 actors are usually enough and SAVO more significantly outperforms baselines.
4. **Analyze Q-function smoothing**, motivated by smoothing of surrogates: `Appendix G.6`  
$\implies$ Q-smoothing is essential for discrete-action tasks, and all our baselines already included it.
5. **Try diversity-enhancing initialization** of different actors and surrogates in SAVO: `Appendix G.7`  
$\implies$ A promising idea, but default Xavier initialization works the best.

&nbsp;

**[Recap our contributions]**  
We believe that our experiments sufficiently justify the primary contributions of our paper:
1. identify the problem of Deterministic Policy Gradient methods like TD3 are susceptible to the *actor getting stuck in local optima*,
2. study environments like restricted locomotion where TD3 actor gets stuck in suboptimal actions due to severe non-convexity in Q-function (unlike unrestricted Mujoco where TD3 is optimal),
3. visualize the non-convexity in Q-function landscapes,
4. propose a novel solution (SAVO) composed of a maximizer actor and tabu-inspired improvement that scales well with additional compute.
5. demonstrate local optima is mitigated via quantitative and visualized evidence on a variety of discrete and continuous action space tasks.
6. extensively validate ablations of SAVO and show it is robust to design choices.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733290932155

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Rebuttal and Discussion

comment:
We are grateful for the reviewers’ and AC’s time, and summarize our key discussions below.

&nbsp;

## Paper summary
Our paper identifies a key limitation in tasks with severely non-convex Q-functions, where an actor trained with deterministic policy gradients (e.g., TD3) is prone to becoming stuck in locally optimal actions, leading to suboptimal policy performance. We introduce SAVO as a novel actor architecture that mitigates this suboptimality through a sequence of additional actors and Q-like surrogates, enhancing performance without the need for extra hyperparameters.

&nbsp;

## Rebuttal summary
We received valuable suggestions on further analysis and extension experiments, which we incorporated as below:
1. `Surrogate Accuracy Analysis` [Appendix G.5]: The loss stays low showing surrogates follow the latest Q-function. (Reviewer PEvp, S3Pa)
2. `SAC Extension` [Appendix J]: SAC suffers suboptimality too; SAVO+SAC outperforms SAC in Ant, HalfCheetah. (Reviewer PEvp, S3Pa)
3. `Scalability Analysis` [Appendix I]: SAVO performance increases near-monotonically with more actor-surrogates until saturation,  thus a practical guideline is to use as many actors as feasible. However, even 2 additional actors help significantly. (Reviewer S3Pa, 6956)
4. `Smoothing and Diversity Extension` [Appendix G.6, G.7]: Smoothing Q-function helps in discrete-action tasks, wherein our baselines already perform Q-smoothing. We also tried the suggested diversity-enhanced initialization of the actors in SAVO, but did not see improvement. (Reviewer 6956)

&nbsp;

## Discussion summary
1. **`Reviewer 6956`** appreciated the experiments we added to their suggestion, especially on Q-smoothing and performance scaling with more actors, and subsequently raised their score.
2. **`Reviewer S3Pa`** acknowledged our comprehensive response with their suggested experiments on SAC+SAVO > SAC, surrogate accuracy, SAVO ablations, and design choices. Their one remaining concern was about the new analysis in Appendix I: *does SAVO introduce complexity for tuning the number of actors?*. We clarified that since SAVO performance gain is **near-monotonic with the number of actors**, there is no overhead needed to tune it — even our paper does not tune it and reports all results with **just two additional actors** — more would help further. Crucially, SAVO is guaranteed to improve the reliability of baselines like TD3 by trading off compute (quantified in Table 1) to provide substantial gains in performance and sample efficiency.

&nbsp;
We did not receive further engagement from the reviewer, but to address this potential confusion, we will revise the analysis title to be **“minimal” number of actors** for saturating SAVO performance, as the phrase “optimal number” might give the wrong indication that it is a sensitive hyperparameter that needs tuning.

3. **`Reviewer PEvp`** did not engage during rebuttal, but we incorporated their valuable suggestions on more empirical evidence to support SAVO. Their primary concern was about *why SAVO only matches the performance of TD3 in simpler unrestricted locomotion tasks in Figure 15?*. But, we clarified that this is exactly what is expected. SAVO is a **“suboptimality-mitigating” method** that matches TD3’s performance when the Q-landscape is not severely non-convex (visualizations in Figures 29, 31) because TD3 is already optimal, leaving no suboptimality to mitigate. However, when TD3/SAC is suboptimal due to severely non-convex Q-landscape (visualizations in Figures 30, 32), SAVO significantly outperforms the baselines as shown in Figures 7,8,10,19,28.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper attempts to improve policy gradient methods that rely on learning a critic. The authors (rightly) observe that gradient descent on the critic will not find the global optimum if the critic is non-convex. Instead, they propose optimising a series of surrogates. 

The main strength of the paper is that it attempts to solve a hugely relevant problem (performance of methods that extend the deterministic policy gradient). 

However, the paper has fatal weaknesses which make me doubt the quality of the proposed solution.
- Unsound theory. For example, near line 300 the universal approximation theorem is applied to a function that isn't continuous. Also, the equation near line 282 talks about gradients for $Q=\tau$, i.e. where the function isn't differentiable in general. 
- Near line 305, evaluating at only two actions might not be enough data to fit a good surrogate.

For these reasons, I strongly recommend rejection. 

If the authors want to resubmit, I would advise them to do the following.
- Remove all unsound theoretical claims
- Optimising a general non-convex function is (under mild assumptions) a very hard problem. The sampling inherent in running an RL algorithm only makes it harder. This means you should probably first address the case where the function you optimise is fully known. This would disentangle exploration and non-convex optimisation. Only when you can show an improvement in this regime would I advise applying it in the RL setting (and then I would recommend starting with bandits).