Mitigating Suboptimality of Deterministic Policy Gradients in Complex Q-functions

## Abstract

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 optimal actions more frequently and outperforms alternate actor architectures.

### 1 Introduction

Figure: Figure 1: An actor $\mu$ trained with gradient ascent on a challenging Q-landscape gets stuck in local optima. Our approach learns a sequence of surrogates $\Psi_{i}$ of the Q-function that successively prune out the Q-landscape below the current best Q-values, resulting in fewer local optima. Thus, the actors $\nu_{i}$ trained to ascend on these surrogates produce actions with a more optimal Q-value.
Refer to caption: x1.png

In sequential decision-making, the goal is to build an optimal agent that maximizes the expected cumulative returns (Sondik, ; Littman, ). Value-based reinforcement learning (RL) approaches learn each action’s expected returns with a Q-function and maximize it (Sutton & Barto, ).
However, in continuous action spaces, evaluating the Q-value of every possible action is impractical.
This necessitates an actor to globally maximize the Q-function and efficiently navigate the vast action space (Grondman et al., ).
Yet, this is particularly challenging in tasks such as restricted locomotion, with a *non-convex* Q-function landscape with many local optima (Figure 2).

Figure: Figure 2: Complex Q-landscapes. We plot Q-value versus action $a$ for some state. In control of Inverted-Double-Pendulum-Restricted (left) and Hopper-Restricted (middle), certain action ranges are unsafe, resulting in various locally optimal action peaks. In a large discrete-action recommendation system (right), there are local peaks at actions representing real items (black dots).
Refer to caption: x2.png

Can we build an actor architecture to find closer to optimal actions in such complex Q-landscapes? Prior methods perform a search over the action space with evolutionary algorithms like CEM (De Boer et al., ; Kalashnikov et al., ; Shao et al., ), but this requires numerous costly re-evaluations of the Q-function.
To avoid this, deterministic policy gradient (DPG) algorithms (Silver et al., ), such as DDPG (Lillicrap et al., ) and TD3 (Fujimoto et al., )
train a parameterized actor to output actions with the objective of maximizing the Q-function *locally*.

A significant challenge arises in environments where the Q-function has many local optima, as shown in Figure 2. An actor trained via gradient ascent may converge to a local optimum with a much lower Q-value than the global maximum. This leads to *suboptimal* decisions during deployment and *sample-inefficient* training, as the agent fails to explore high-reward trajectories (Kakade, ).

To improve actors’ ability to identify optimal actions in complex, non-convex Q-function landscapes, we propose the Successive Actors for Value Optimization (SAVO) algorithm. SAVO leverages two key insights: (1) combining multiple policies using an $\arg\max$ on their Q-values to construct a superior policy (§4.1), and (2) simplifying the Q-landscape by excluding lower Q-value regions based on high-performing actions, inspired by tabu search (Glover, ), thereby reducing local optima and facilitating gradient-ascent (§4.2). By iteratively applying these strategies through a sequence of simplified Q-landscapes and corresponding actors, SAVO progressively finds more optimal actions.

We evaluate SAVO in complex Q-landscapes such as (i) *continuous* control in dexterous manipulation (Rajeswaran et al., ) and restricted locomotion (Todorov et al., ), and (ii) *discrete* decision-making in the large action spaces of simulated (Ie et al., ) and real-data recommender systems (Harper & Konstan, ), and gridworld mining expedition (Chevalier-Boisvert et al., ).
We use the reframing of large discrete action RL to continuous action RL following Van Hasselt & Wiering () and Dulac-Arnold et al. (), where a policy acts in continuous actions, such as the feature space of recommender items (Figure 2), and the nearest discrete action is executed.

Our key contribution is SAVO, an actor architecture to find better optimal actions in complex non-convex Q-landscapes (§4).
In experiments, we visualize how SAVO’s successively learned Q-landscapes have fewer local optima (§6.2), making it more likely to find better action optima with gradient ascent. This enables SAVO to outperform alternative actor architectures, such as sampling more action candidates (Dulac-Arnold et al., )
and learning an ensemble of actors (Osband et al., ) (§6.1) across continuous and discrete action RL.

### 2 Related Work

Q-learning (Watkins & Dayan, ; Tesauro et al., ) is a fundamental value-based RL algorithm that iteratively updates Q-values to make optimal decisions. Deep Q-learning (Mnih et al., ) has been applied to tasks with manageable discrete action spaces, such as Atari (Mnih et al., ; Espeholt et al., ; Hessel et al., ), traffic control (Abdoos et al., ), and small-scale recommender systems (Chen et al., ). However, scaling Q-learning to continuous or large discrete action spaces requires specialized techniques to efficiently maximize the Q-function.

Analytical Q-optimization.
Analytical optimization of certain Q-functions, such as wire fitting algorithm (Baird & Klopf, ) and normalized advantage functions (Gu et al., ; Wang et al., ), allows closed-form action maximization without an actor. Likewise,  Amos et al. () assume that the Q-function is convex in actions and use a convex solver for action selection. In contrast, the Q-functions considered in this paper are inherently non-convex in action space, making such an assumption invalid. Generally, analytical Q-functions lack the expressiveness of deep Q-networks (Hornik et al., ), making them unsuitable to model complex tasks like in Figure 2.

Evolutionary Algorithms for Q-optimization.
Evolutionary algorithms like simulated annealing (Kirkpatrick et al., ), genetic algorithms (Srinivas & Patnaik, ), tabu search (Glover, ), and the cross-entropy method (CEM) (De Boer et al., ) are employed in RL for global optimization (Hu et al., ). Approaches such as QT-Opt (Kalashnikov et al., ; Lee et al., ; Kalashnikov et al., ) utilize CEM for action search, while hybrid actor-critic methods like CEM-RL (Pourchot & Sigaud, ), GRAC (Shao et al., ), and Cross-Entropy Guided Policies (Simmons-Edler et al., ) combine evolutionary techniques with gradient descent. Despite their effectiveness, CEM-based methods require numerous Q-function evaluations and struggle with high-dimensional actions (Yan et al., ). In contrast, SAVO achieves superior performance with only a few (e.g., three) Q-evaluations, as demonstrated in experiments (§6).

Actor-Critic Methods with Gradient Ascent.
Actor-critic methods can be on-policy (Williams, ; Schulman et al., ; ) primarily guided by the policy gradient of expected returns, or off-policy (Silver et al., ; Lillicrap et al., ; Fujimoto et al., ; Chen et al., ) primarily guided by the Bellman error on the critic. Deterministic Policy Gradient (DPG) (Silver et al., ) and its extensions like DDPG Lillicrap et al. (), TD3 (Fujimoto et al., ) and REDQ (Chen et al., ) optimize actors by following the critic’s gradient. Soft Actor-Critic (SAC) (Haarnoja et al., ) extends DPG to stochastic actors. However, these methods can get trapped in local optima within the Q-function landscape. SAVO addresses this limitation by enhancing gradient-based actor training. This issue also affects stochastic actors, where a local optimum means an *action distribution* (instead of a single action) that fails to minimize the KL divergence from the Q-function density fully, and is a potential area for future research.

Sampling-Augmented Actor-Critic.
Sampling multiple actions and evaluating their Q-values is a common strategy to find optimal actions. Greedy actor-critic (Neumann et al., ) samples high-entropy actions and trains the actor towards the best Q-valued action, yet remains susceptible to local optima. In large discrete action spaces, methods like Wolpertinger (Dulac-Arnold et al., ) use k-nearest neighbors to propose actions, requiring extensive Q-evaluations on up to 10% of total actions. In contrast, SAVO efficiently generates high-quality action proposals through successive actor improvements without being confined to local neighborhoods.

Ensemble-Augmented Actor-Critic.
Ensembles of policies enhance exploration by providing diverse action proposals through varied initializations (Osband et al., ; Chen & Peng, ; Song et al., ; Zheng12 et al., ; Huang et al., ). The best action is selected based on Q-value evaluations. Unlike ensemble methods, SAVO systematically eliminates local optima, offering a more reliable optimization process for complex tasks (§6).

### 3 Problem Formulation

Our work tackles the effective optimization of the Q-value landscape in off-policy actor-critic methods for continuous and large-discrete action RL.
We model a task as a Markov Decision Process (MDP), defined by a tuple $\{\mathcal{S},\mathcal{A},\mathcal{T},R,\gamma\}$ of states, actions, transition probabilities, reward function, and a discount factor.
The action space $\mathcal{A}\!\subseteq\!\mathbb{R}^{D}$ is a $D$-dimensional *continuous* vector space.
At every step $t$ in the episode, the agent receives a state observation $s_{t}\in\mathcal{S}$ from the environment and acts with $a_{t}\in\mathcal{A}$. Then, it receives the new state after transition $s_{t+1}$ and a reward $r_{t}$.
The objective of the agent is to learn a policy $\pi(a\mid s)$ that maximizes the expected discounted reward, $\max_{\pi}\mathbb{E}_{\pi}\left[\sum_{t}\gamma^{t}r_{t}\right].$

#### 3.1 Deterministic Policy Gradients (DPG)

DPG (Silver et al., ) is an off-policy actor-critic algorithm that trains a deterministic actor $\mu_{\phi}$ to maximize the Q-function.
This happens via two steps of generalized policy iteration, GPI (Sutton & Barto, ): policy evaluation estimates the Q-function (Bellman, ) and policy improvement greedily maximizes the Q-function. To approximate the $\arg\max$ over continuous actions in Eq. (2), DPG proposes the policy gradient to update the actor locally in the direction of increasing Q-value,

$$ $\displaystyle Q^{\mu}(s,a)$ $\displaystyle=r(s,a)+\gamma\mathbb{E}_{s^{\prime}}\left[Q^{\mu}(s^{\prime},\mu (s^{\prime}))\right],$ (1) $\displaystyle\mu(s)$ $\displaystyle=\arg\max_{a}Q^{\mu}(s,a),$ (2) $\displaystyle\nabla_{\phi}J(\phi)$ $\displaystyle=\mathbb{E}_{s\sim\rho^{\mu}}\left[\nabla_{a}Q^{\mu}(s,a)\big{|}_ {a=\mu(s)}\nabla_{\phi}\mu_{\phi}(s)\right].\vspace{-15pt}$ (3) $$

DDPG (Lillicrap et al., ) and TD3 (Fujimoto et al., ) made DPG compatible with deep networks via techniques like experience replay and target networks to address non-stationarity of online RL, twin critics to mitigate overestimation bias, target policy smoothing to prevent exploitation of errors in the Q-function, and delayed policy updates so critic is reliable to provide actor gradients.

#### 3.2 The Challenge of an Actor Maximizing a Complex Q-landscape

DPG-based algorithms train the actor following the chain rule in Eq. (3). Specifically, its first term, $\nabla_{a}Q^{\mu}(s,a)$ involves gradient ascent in Q-versus-$a$ landscape.
This Q-landscape is often highly non-convex (Figures 2, 3) and non-stationary because of its own training. This makes the actor’s output $\mu(s)$ get stuck at suboptimal Q-values, thus leading to insufficient policy improvement in Eq. (2). We can define the suboptimality of the $\mu$ w.r.t. $Q^{\mu}$ at state $s$ as

$$ $\Delta(Q^{\mu},\mu,s)=\arg\max_{a}Q^{\mu}(s,a)-Q^{\mu}(s,\mu(s))\geq 0.$ (4) $$

Suboptimality in actors is a crucial problem because it leads to (i) poor sample efficiency by slowing down GPI, and (ii) poor inference performance even with an optimal Q-function, $Q^{*}$ as seen in Figure 3 where a TD3 actor gets stuck at a locally optimum action $a_{0}$ in the final Q-function.

Figure: Figure 3: Non-convex Q-landscape in Inverted-Pendulum-Restricted leads to a suboptimally converged actor.
Refer to caption: x5.png

This challenge fundamentally differs from the well-studied field of non-convex optimization, where non-convexity arises in the *loss function w.r.t. the model parameters* (Goodfellow, ). In those cases, stochastic gradient-based optimization methods like SGD and Adam (Kingma & Ba, ) are effective at finding acceptable local minima due to the smoothness and high dimensionality of the parameter space, which often allows for escape from poor local optima (Choromanska et al., ). Moreover, overparameterization in deep networks can lead to loss landscapes with numerous good minima (Neyshabur et al., ).

In contrast, our challenge involves non-convexity in the *Q-function w.r.t. the action space*. The actor’s task is to find, for every state $s$, the action $a$ that maximizes $Q^{\mu}(s,a)$. Since the Q-function can be highly non-convex and multimodal in $a$, the gradient ascent step $\nabla_{a}Q^{\mu}(s,a)$ used in Eq. (3) may lead the actor to converge to suboptimal local maxima in action space. Unlike parameter space optimization, the actor cannot rely on high dimensionality or overparameterization to smooth out the optimization landscape in action space because the Q-landscape is determined by the task’s reward. Furthermore, the non-stationarity of the Q-function during training compounds this challenge. These properties make our non-convex challenge unique, requiring a specialized actor to navigate the complex Q-landscape.

Tasks with several local optima in the Q-function include restricted inverted pendulum shown in Figure 3, where certain regions of the action space are invalid or unsafe, leading to a rugged Q-landscape (Florence et al., ). Dexterous manipulation tasks exhibit discontinuous behaviors like inserting a precise peg in place with a small region of high-valued actions (Rajeswaran et al., ) and surgical robotics have a high variance in Q-values of nearby motions (Barnoy et al., ).

##### 3.2.1 Large Discrete Action RL Reframed as Continuous Action RL

We discuss another practical domain where non-convex Q-functions are present. In large discrete action tasks like recommender systems (Zhao et al., ; Zou et al., ; Wu et al., ), a common approach (Van Hasselt & Wiering, ; Dulac-Arnold et al., ) is to use continuous representations of actions as a medium of decision-making. Given a set of actions, $\mathcal{I}=\{\mathscr{I}_{1},\dots,\mathscr{I}_{N}\}$, a predefined module $\mathcal{R}:\mathcal{I}\rightarrow\mathcal{A}$ assigns each $\mathscr{I}\in\mathcal{I}$ to its representation $\mathcal{R}(\mathscr{I})$, e.g., text embedding of a given movie (Zhou et al., ).
A continuous action policy $\pi(a\mid s)$ is learned in the action representation space, with each $a\in\mathcal{A}$ converted to a discrete action $\mathscr{I}\in\mathcal{I}$ via nearest neighbor,

$$ $f_{\text{NN}}(a)=\arg\min_{\mathscr{I}_{i}\in\mathcal{I}}\|\mathcal{R}( \mathscr{I}_{i})-a\|_{2}.$ $$

Importantly, the nearest neighbor operation creates a challenging piece-wise continuous Q-function with suboptima at various discrete points as shown in Figure 2 (Jain et al., ; ).

### 4 Approach: Successive Actors for Value Optimization (SAVO)

Figure: Figure 4: SAVO Architecture. (left) Q-network is unchanged. (center) Instead of a single actor, we learn a sequence of actors and surrogate networks connected via action predictions. (right) Conditioning on previous actions is done with the help of a deep-set summarizer and FiLM modulation.
Refer to caption: x6.png

Our objective is to design an actor architecture that efficiently discovers better actions in complex, non-convex Q-function landscapes. We focus on gradient-based actors and introduce two key ideas:

- 1.
Maximizing Over Multiple Policies: By combining policies using an $\arg\max$ over their Q-values, we can construct a policy that performs at least as well as any individual policy (§4.1).
- 2.
Simplifying the Q-Landscape: Drawing inspiration from tabu search (Glover, ), we propose using actions with good Q-values to eliminate or “tabu” the Q-function regions with lower Q-values, thereby reducing local optima and facilitating gradient-based optimization (§4.2).

#### 4.1 Maximizer Actor over Action Proposals

We first show how additional actors can improve DPG’s policy improvement step.
Given a policy $\mu$ being trained with DPG over $Q$, consider $k$ additional arbitrary policies $\nu_{1},\dots,\nu_{k}$, where $\nu_{i}:\mathcal{S}\to\mathcal{A}$ and let $\nu_{0}=\mu$. We define a maximizer actor $\mu_{M}$ for $a_{i}=\nu_{i}(s)$ for $i=0,1,\dots,k$,

$$ $\displaystyle\mu_{M}(s):=\operatorname*{arg\,max}_{a\in\{a_{0},a_{1},\dots,a_{ k}\}}Q(s,a),$ (5) $$

Here, $\mu_{M}$ is shown to be a better maximizer of $Q(s,a)$ in Eq. (2) than $\mu\;\forall s$ :

$$ $\displaystyle Q(s,\mu_{M}(s))=\max_{a_{i}}Q(s,a_{i})\geq Q(s,a_{0})=Q(s,\mu(s)).$ $$

Therefore, by policy improvement theorem (Sutton & Barto, ), $V^{\mu_{M}}(s)\geq V^{\mu}(s)$, proving that $\mu_{M}$ is better than a single $\mu$ for a given $Q$. Appendix A proves the following theorem by showing that policy evaluation and improvement with $\mu_{M}$ converge.

###### Theorem 4.1 (Convergence of Policy Iteration with Maximizer Actor) .

A modified policy iteration algorithm where $\nu_{0}=\mu$ is the current policy learned with DPG and *maximizer actor* $\mu_{M}$ defined in Eq. (5), converges in the tabular setting to the optimal policy.

This algorithm is valid for arbitrary $\nu_{1},\dots\nu_{k}$. We experiment with $\nu$’s obtained by sampling from a Gaussian centered at $\mu$ or ensembling on $\mu$ to get diverse actions. However, in high-dimensionality, *randomness* around $\mu$ is not sufficient to get action proposals to significantly improve $\mu$.

###### Theorem 4.1 (Convergence of Policy Iteration with Maximizer Actor) .

#### 4.2 Successive Surrogates to Reduce Local Optima

To train additional policies $\nu_{i}$ that can improve upon $\mu_{M}$, we introduce surrogate Q-functions with fewer local optima, inspired by the principles of tabu search (Glover, ), which is an optimization technique that uses memory structures to avoid revisiting previously explored inferior solutions, thereby enhancing the search for optimal solutions. Similarly, our surrogate functions act as memory mechanisms that “tabu” certain regions of the Q-function landscape deemed suboptimal based on previously identified good actions. Given a known action $a^{\dagger}$, we define a surrogate function that elevates the Q-values of all inferior actions to $Q(s,a^{\dagger})$, which serves as a constant threshold:

$$ $\Psi(s,a;a^{\dagger})=\max\{Q(s,a),Q(s,a^{\dagger})\}.$ (6) $$

Extending this idea, we define a sequence of surrogate functions using the actions from previous policies. Let $a_{<i}=\{a_{0},a_{1},\dots,a_{i-1}\}$. The $i$-th surrogate function is:

$$ $\Psi_{i}(s,a;a_{<i})=\max\left\{Q(s,a),\max_{j<i}Q(s,a_{j})\right\}.$ (7) $$

###### Theorem 4.2 .

For a state $s\in\mathcal{S}$ and surrogates $\Psi_{i}$ defined as above, the number of local optima decreases with each successive surrogate:

$$ $N_{\text{opt}}(Q(s,\cdot))\geq N_{\text{opt}}(\Psi_{1}(s,\cdot;a_{0}))\geq \dots\geq N_{\text{opt}}(\Psi_{k}(s,\cdot;a_{<k})),$ $$

where $N_{\text{opt}}(f)$ denotes the number of local optima of function $f$ over $\mathcal{A}$.

Proof Sketch.
As $\Psi_{i}\!\to\Psi_{i+1}$, the anchor Q-value in Eq. (7) weakly increases, $\max_{j<i}Q(s,a_{j})\leq\max_{j<(i+1)}Q(s,a_{j})$, thus, eliminating more local minima below it (proof in Appendix B.1).
∎

###### Theorem 4.2 .

#### 4.3 Successive Actors for Surrogate Optimization

To effectively reduce local optima using the surrogates $\Psi_{1},\dots,\Psi_{k}$, we design the policies $\nu_{i}$ to optimize their respective surrogates $\Psi_{i}(s,a;a_{<i})$. Each $\nu_{i}$ focuses on regions where $Q(s,a)\geq\max_{j<i}Q(s,a_{j})$, allowing it to find better optima than previous policies. The actor $\nu_{i}$ is conditioned on previous actions $\{a_{0},\dots,a_{i-1}\}$, summarized using deep sets (Zaheer et al., ) (Figure 4). The maximizer actor $\mu_{M}$ (Eq. (5)) selects the best action among all proposals.

We train each actor $\nu_{i}$ using gradient ascent on its surrogate $\Psi_{i}$, similar to DPG:

$$ $\displaystyle\nabla_{\phi_{i}}J(\phi_{i})=\mathbb{E}_{s\sim\rho^{\mu_{M}}} \left[\nabla_{a}\Psi_{i}(s,a;a_{<i})\big{|}_{a}\,\nabla_{\phi_{i}}\nu_{i}(s;a_ {<i})\right].$ (8) $$

#### 4.4 Approximate Surrogate Functions

The surrogates $\Psi_{i}$ have zero gradients when $Q(s,a)<\tau$, where $\tau=\max_{j<i}Q(s,a_{j})$,

$$ $\displaystyle\nabla_{a}\Psi_{i}(s,a;a_{<i})=\begin{cases}\nabla_{a}Q^{\mu_{M}} (s,a)&\text{if }Q(s,a)\geq\tau,\\ 0&\text{if }Q(s,a)<\tau.\end{cases}$ $$

This means the policy gradient only updates $\nu_{i}$ when $Q(s,a)\geq\tau$, which may slow down learning. To address this issue,
we ease the gradient flow by learning a smooth lossy approximation $\hat{\Psi}_{i}$ of $\Psi_{i}$.

Figure: Figure 5: In restricted inverted pendulum, given an anchor $Q(a_{0})$ value, $\Psi$ (left) has some zero-gradient surfaces which $\hat{\Psi}$ (right) *approximately* follows while allowing non-zero gradients towards high Q-values to flow into its actor $\nu$.
Refer to caption: x7.png

We approximate each surrogate $\Psi_{i}$ with a neural network $\hat{\Psi}_{i}$. This approach leverages the universal approximation theorem (Hornik et al., ; Cybenko, ) and benefits from empirical evidence that deep networks can effectively learn non-smooth functions (Imaizumi & Fukumizu, ). The smooth surrogate $\hat{\Psi}_{i}$ enables continuous gradient propagation, which is essential for optimizing the actors $\nu_{i}$. We train $\hat{\Psi}_{i}$ to approach $\Psi_{i}$ by minimizing the mean squared error at two critical points:

- 1.
$\tilde{\mu}_{M}(s)$ is the action selected by the current maximizer actor $\mu_{M}$, having a high Q-value,
- 2.
$\nu_{i}(s;a_{<i})$ is the action proposed by the $i$-th actor conditioned on previous actions $a_{<i}$,

$$ $\displaystyle\mathcal{L}_{\text{approx}}=\mathbb{E}_{s\sim\rho^{\mu_{M}}}\left [\sum_{a\in\{\tilde{\mu}_{M}(s),\nu_{i}(s;a_{<i})\}}\left\|\hat{\Psi}_{i}(s,a; a_{<i})-\Psi_{i}(s,a;a_{<i})\right\|_{2}^{2}\right].$ (9) $$

This design ensures $\hat{\Psi}_{i}$ is updated on high Q-value actions and thus the landscape is biased towards those values. This makes the gradient flow trend in the direction of high Q-values. So, even when $a_{i}$ from $\nu_{i}$ falls in a region of zero gradients for $\Psi_{i}$, in $\hat{\Psi}_{i}$ would provide policy gradient in a higher Q-value direction, if it exists. Figure 5 shows $\Psi_{1}$ and $\hat{\Psi}_{1}$ in restricted inverted pendulum task.

#### 4.5 SAVO-TD3 Algorithm and Design Choices

While the SAVO architecture (Figure 4) can be integrated with any off-policy actor-critic algorithm, we choose to implement it with TD3 (Fujimoto et al., ) due to its compatibility with continuous and large-discrete action RL (Dulac-Arnold et al., ). Using the SAVO actor in TD3 enhances its ability to find better actions in complex Q-function landscapes. Algorithm 1 depicts SAVO (highlighted) applied to TD3. We discuss design choices in SAVO and validate them in §6.

1. Removing policy smoothing: We eliminate TD3’s policy smoothing, which adds noise to the target action $\tilde{a}$ during critic updates. In non-convex landscapes, nearby actions may have significantly different Q-values and noise addition might obscure important variations.

Figure: Algorithm 1 SAVO-TD3

2. Exploration in Additional Actors:
Added actors $\nu_{i}$ explore the surrogate landscapes for high-reward regions by adding OU (Lillicrap et al., ) or Gaussian (Fujimoto et al., ) noise to their actions.

3. Twin Critics for Surrogates:
To prevent overestimation bias in surrogates $\hat{\Psi}_{i}$, we use twin critics to compute the target of each surrogate, mirroring TD3.

4. Conditioning on Previous Actions:
Actors $\nu_{i}$ and surrogates $\hat{\Psi}_{i}$ are conditioned on preceding actions via FiLM layers (Perez et al., ) as in Figure 4.

5. Discrete Action Space Tasks:
We apply 1-nearest-neighbor $f_{\text{NN}}$ before Q-value evaluation to ensure the Q-function is only queried at in-distribution actions.

SAVO-TD3 employs SAVO actor to systematically reduce the local optima in its base algorithm TD3. We empirically validate the proposed design improvements.

### 5 Environments

We evaluate SAVO on discrete and continuous action space environments with challenging Q-value landscapes.
More environment details are presented in Appendix C and Figure 13.

Locomotion in Mujoco. We evaluate on MuJoCo (Todorov et al., ) environments of Hopper-v4, Walker2D-v4, Inverted Pendulum-v4, and Inverted Double Pendulum-v4.

Figure: Figure 6: Hopper’s 3D visualization of Action Space.
Refer to caption: x9.png

Locomotion in Restricted Mujoco.
We create a restricted locomotion suite of the same environments as in MuJoCo. A *hard* Q-landscape is realized via high-dimensional discontinuities that restrict the action space. Concretely, a set of predefined hyper-spheres (as shown in Figure 6) in the action space are sampled and set to be valid actions, while the other invalid actions have a null effect if selected. The complete details can be found in Appendix C.3.1.

Adroit Dexterous Manipulation. Rajeswaran et al. () propose manipulation tasks with a dexterous multi-fingered hand.
Door: In this task, a robotic hand is required to open a door with a latch. The challenge lies in the precise manipulation needed to unlatch and swing open the door using the fingers.
Hammer: the robotic hand must use a hammer to drive a nail into a board. This task tests the hand’s ability to grasp the hammer correctly and apply force accurately to achieve the goal.
Pen: This task involves the robotic hand manipulating a pen to reach a specific goal position and rotation. The objective is to control the pen’s orientation and position using fingers, which demands fine motor skills and coordination.

Mining Expedition in Grid World.
We develop a 2D Mining grid world environment (Chevalier-Boisvert et al., ) where the agent (Figure 13) navigates a 2D maze to reach the goal, removing mines with correct pick-axe tools to reach the goal in the shortest path.
The action space includes navigation and tool-choice actions, with a procedurally-defined action representation space. The Q-landscape is non-convex because of the diverse effects of nearby action representations.

Simulated and Real-Data Recommender Systems.
RecSim (Ie et al., ) simulates sequential user interactions in a recommender system with a large discrete action space.
The agent must recommend the most relevant item from a set of 10,000 items based on user preference information.
The action representations are simulated item characteristic vectors in simulated and movie review embeddings in the real-data task based on MovieLens (Harper & Konstan, ) for items.

### 6 Experiments

#### 6.1 Effectiveness of SAVO in challenging Q-landscapes

Figure: (a) SAVO versus baseline actor architectures.
Refer to caption: x10.png

Figure: Figure 8: SAVO against baselines on discrete and continuous tasks. Results averaged over 10 seeds.
Refer to caption: x12.png

We compare SAVO against the following baseline actor architectures, where $k=3$:

- •
1-Actor (TD3): Conventional single actor architecture which is susceptible to local optima.
- •
1-Actor, $k$ samples (Wolpertinger): Gaussian sampling centered on actor’s output. For discrete actions, we select $k$-NN discrete actions around the continuous action (Dulac-Arnold et al., ).
- •
$k$-Actors (Ensemble): Best Q-value among diverse actions from ensemble (Osband et al., ).
- •
Evolutionary actor (CEM): Iterative CEM search over the action space (Kalashnikov et al., ).
- •
Greedy-AC: Greedy Actor Critic (Neumann et al., ) trains a high-entropy proposal policy and primary actor trained from best proposals with gradient updates.
- •
Greedy TD3: Our version of Greedy-AC with TD3 exploration and update improvements.
- •
SAVO: Our method with $k$ successive actors and surrogate Q-landscapes.

We ablate the crucial components and design decisions in SAVO:

- •
SAVO - Approximation: removes the approximate surrogates (§4.4), using $\Psi_{i}$ instead of $\hat{\Psi}_{i}$.
- •
SAVO - Previous Actions: removes conditioning on $a_{<i}$ in SAVO’s actors and surrogates.
- •
SAVO + Action Smoothing: TD3’s policy smoothing (Fujimoto et al., ) compute Q-targets.
- •
SAVO + Joint Action: trains an actor with a joint action space of $3\times D$. The $k$ action samples are obtained by splitting the joint action into $D$ dimensions. Validates successive nature of SAVO.

Aggregate performance.
We utilize performance profiles (Agarwal et al., ) to aggregate results across different environments in Figure 7(a) (evaluation mechanism detailed in Appendix G.1). SAVO consistently outperforms baseline actor architectures like single-actor (TD3) and sampling-augmented actor (Wolpertinger), showing wide robustness across challenging Q-landscapes. In Figure 7(b), SAVO outperforms its ablations, validating each proposed component and design decision.

Per-environment results.
In discrete action tasks, the Q-value landscape is only well-defined at exact action representations and nearby discrete actions might have very different values (§3.2.1). This makes the Q-value landscape uneven, with multiple peaks and valleys (Figure 2).
For example, actions in Mining Expedition involve both navigation and tool-selection which are quite different, while RecSim and RecSim-Data have many diverse items to choose from.
Methods like Wolpertinger that sample many actions a local neighborhood perform better than TD3 which considers a single action (Figure 8).
However, SAVO achieves the best performance by directly simplifying the non-convex Q-landscape.
In restricted locomotion, there are several good actions that are far apart. SAVO actors can search and explore widely to optimize the Q-landscape better than only nearby sampled actions. Figure 16 ablates SAVO in all 7 environments and shows that the most critical features are its successive nature, removing policy smoothing, and approximate surrogates.

#### 6.2 Q-Landscape Analysis: Do successive surrogates reduce local optima?

Figure 9 visualizes surrogate landscapes in Inverted-Pendulum-Restricted for a given state $s$. Successive pruning and approximation smooth the Q-landscapes, reducing local optima. A single actor gets stuck at a local optimum $a_{0}$ (left), but surrogate $\hat{\Psi}_{1}$ uses $a_{0}$ as an anchor to find a better optimum $a_{1}$. The maximizer policy finally selects the highest Q-valued action among $a_{0},a_{1},a_{2}$. Figure 24 extends this visualization to Inverted-Double-Pendulum-Restricted.
Figure 23 shows how one actor is sufficient in the *convex* Q-landscape of unrestricted Inverted-Pendulum-v4. Figures 25, 26 show how Hopper-v4 Q-landscape provides a path to global optimum, while Hopper-Restricted is non-convex.

Figure: (a) $Q(s,a_{0})$
Refer to caption: x20.png

#### 6.3 Challenging Dexterous Manipulation (Adroit)

In Adroit dexterous manipulation tasks (Door, Pen, Hammer) (Rajeswaran et al., ), SAVO improves the sample efficiency of TD3 (Figure 10). The non-convexity in Q-landscape likely arises from nearby actions having high variance outcomes like grasping, missing, dropping, or no impact.

Figure: Figure 10: SAVO improves the sample-efficiency of TD3 on Adroit dexterous manipulation tasks.
Refer to caption: x21.png

#### 6.4 Quantitative Analysis: The Effect of Successive Actors and Surrogates

We investigate the effect of increasing the number of successive actor-surrogates in SAVO
in Pendulum (Figure 11(a)) and
MineWorld (Figure 11(b)). Additional actor-surrogates significantly help to reduce severe local optima initially. However, the improvement saturates as the suboptimality gap reduces.

Figure: (a) Length Analysis Pendulum
Refer to caption: x24.png

Next, we show that successive actors are needed because a single actor can get stuck in local optima even with an optimal Q-function.
In Figure 11(c), we consider a SAVO agent trained to optimality with 3 actors.
When we remove the additional actors, the remaining single-actor agent resembles TD3 trained to maximize an “optimal” Q-function.
However, the significant performance gap indicates that the single actor could not find optimal actions for the given Q-function.

#### 6.5 Does RL with Resets address the issue of Q-function Optimization?

Figure: Figure 12: Reset (primacy bias) does not improve Q-optimization.
Refer to caption: x27.png

Primacy bias (Nikishin et al., ; Kim et al., ) occurs when an agent is trapped in suboptimal behaviors from early training. To mitigate this, methods like resetting parameters and re-learning from the replay buffer aim to reduce reliance on initial samples.
We run TD3 in MineEnv with either a full-reset or last-layer reset every 200k, 500k, or 1 million iterations. None of these versions outperformed the original TD3 algorithm without resets. This is because resetting does not help an actor to navigate the Q-landscape better and can even cause an otherwise optimal actor to get stuck in a suboptimal solution during retraining. In contrast, the SAVO actor architecture specifically addresses the non-convex Q-landscapes, being a more robust method to finding closer to optimal actions.

#### 6.6 Further experiments to validate SAVO

- •
Unrestricted locomotion.
Figure 15 shows that both SAVO and baselines achieve optimal performance in simple Q-landscapes, confirming effective hyperparameter tuning (§G.4, §G.3) and indicating that the baselines underperform due to the complexity introduced in Q-landscapes.
- •
SAVO orthogonal to SAC.
Figure 17 shows that SAVO+TD3 > SAC > TD3, indicating that SAC’s stochastic policy does not address non-convexity, but can itself suffer from local optima (Figure 18)
- •
Design Choices. Figure 20 shows that LSTM, DeepSet, and Transformers are all valid choices as summarizers of preceding actions $a_{<i}$ in SAVO.
Figure 21 shows that FiLM conditioning on $a_{<i}$ especially helps for discrete action space tasks but has a smaller effect in continuous action space.
In Figure 22(a), we find Ornstein-Uhlenbeck (OU) noise and Gaussian noise to be largely equivalent.
- •
Massive Discrete Actions. SAVO outperforms in RecSim with 100k and 500k actions (Figure 19).

**Table 1: Compute v/s Performance Gain (Mujoco)**
| Method | GPU Mem. | Return | Time |
| --- | --- | --- | --- |
| TD3 | 619MB | 1107.795 | 0.062s |
| SAVO k=3 | 640MB | 2927.149 | 0.088s |
| SAVO k=5 | 681MB | 3517.319 | 0.122s |

### 7 Limitations and Conclusion

Introducing more actors in SAVO has negligible influence on GPU memory, but leads to longer inference time (Table 1). However, even for 3 actor-surrogates, SAVO achieves significant improvements in all our experiments. Further, for tasks with a simple convex Q-landscape, a single actor does not get stuck in local optima, making the gain from SAVO negligible. In conclusion, we improve Q-landscape optimization in deterministic policy gradient RL with Successive Actors for Value Optimization (SAVO) in both continuous and large discrete action spaces. We demonstrate with quantitative and qualitative analyses how the improved optimization of Q-landscape with SAVO leads to better sample efficiency and performance.

### Acknowledgements

This work was supported by Institute of Information & communications Technology Planning & Evaluation (IITP) grant (No.RS-2019-II190075, Artificial Intelligence Graduate School Program, KAIST) and National Research Foundation of Korea (NRF) grant (NRF-2021H1D3A2A03103683, Brain Pool Research Program), funded by the Korea government (MSIT). Ayush Jain was supported partly as intern at Naver AI Lab during the initiation of the project. We appreciate the fruitful discussions with members of CLVR Lab at KAIST and LiraLab at USC.

### Appendix

## 

### Appendix A Proof of Convergence of Maximizer Actor in Tabular Settings

###### Theorem A.1 (Convergence of Policy Iteration with Maximizer Actor) .

In a finite Markov Decision Process (MDP) with finite state space $\mathcal{S}$,
consider a modified policy iteration algorithm where, at each iteration $n$, we have a set of $k+1$ policies $\{\nu_{0},\nu_{1},\dots,\nu_{k}\}$, with $\nu_{0}=\mu_{n}$ being the policy at the current iteration learned with DPG. We define the *maximizer actor* $\mu_{M}$ as:

$$ $\displaystyle\mu_{M}(s)=\arg\max_{a\in\{\nu_{0}(s),\nu_{1}(s),\dots,\nu_{k}(s) \}}Q^{\mu_{n}}(s,a),$ (10) $$

where $Q^{\mu_{n}}(s,a)$ is the action-value function for policy $\mu_{n}$.
Then, the modified policy iteration algorithm using the maximizer actor is guaranteed to converge to a final policy $\mu_{N}$.

###### Proof.

To prove convergence, we will show that the sequence of policies ${\mu_{n}}$ yields monotonically non-decreasing value functions that converge to a stable value function $V^{N}$.

###### Theorem A.1 (Convergence of Policy Iteration with Maximizer Actor) .

###### Proof.

#### Policy Evaluation Converges

Thus, iteratively applying $\mathcal{T}^{\pi}$ starting from any initial $Q_{0}$ converges to the unique fixed point $Q^{\pi}$.

Given the current policy $\mu_{n}$, the policy evaluation computes the action-value function $Q^{\mu_{n}}$, satisfying:

$$ $Q^{\mu_{n}}(s,a)=R(s,a)+\gamma\sum_{s^{\prime}}P(s,a,s^{\prime})V^{\mu_{n}}(s^ {\prime}),$ $$

where $V^{\mu_{n}}(s^{\prime})=Q^{\mu_{n}}(s^{\prime},\mu_{n}(s^{\prime}))$.

In the tabular setting, the Bellman operator $\mathcal{T}^{\mu_{n}}$ defined by

$$ $[\mathcal{T}^{\mu_{n}}Q](s,a)=R(s,a)+\gamma\sum_{s^{\prime}}P(s,a,s^{\prime})Q (s^{\prime},\mu_{n}(s^{\prime}))$ $$

is a contraction mapping with respect to the max norm $\|\cdot\|_{\infty}$ with contraction factor $\gamma$,

$$ $\|\mathcal{T}^{\mu_{n}}Q-\mathcal{T}^{\mu_{n}}Q^{\prime}\|_{\infty}\leq\gamma \|Q-Q^{\prime}\|_{\infty}.$ $$

Therefore, iteratively applying $\mathcal{T}^{\mu_{n}}$ converges to the unique fixed point $Q^{\mu_{n}}$.

#### Policy Improvement with DPG and Maximizer Actor

Step 1: DPG Update

We define $\tilde{\mu}_{n}$ as the DPG policy that locally updates $\mu_{n}$ towards maximizing the expected return based on $Q^{\mu_{n}}$. For each state $s$, we perform a gradient ascent step using the Deep Policy Gradient (DPG) method to obtain an improved policy $\tilde{\mu}_{n}$:

$$ $\tilde{\mu}_{n}(s)\leftarrow\mu_{n}(s)+\alpha\nabla_{a}Q^{\mu_{n}}(s,a)\big{|} _{a=\mu_{n}(s)},$ $$

where $\alpha>0$ is a suitable step size.

This DPG gradient step leads to local policy improvement following over $\mu_{n}$ (Silver et al., ):

$$ $V^{\tilde{\mu}_{n}}(s)\geq V^{\mu_{n}}(s),\quad\forall s\in\mathcal{S}.$ $$

(b) *Maximizer Actor*

Given additional policies $\nu_{1},\dots,\nu_{k}$, define the maximizer actor $\mu_{n+1}$ as:

$$ $\mu_{n+1}(s)=\arg\max_{a\in\{\tilde{\mu}_{n}(s),\nu_{1}(s),\dots,\nu_{k}(s)\}} Q^{\mu_{n}}(s,a).$ $$

Since $\mu_{n+1}(s)$ selects the action maximizing $Q^{\mu_{n}}(s,a)$ among candidates, we have:

$$ $Q^{\mu_{n}}(s,\mu_{n+1}(s))=\max_{a\in\{\tilde{\mu}_{n}(s),\nu_{1}(s),\dots, \nu_{k}(s)\}}Q^{\mu_{n}}(s,a)\geq Q^{\mu_{n}}(s,\tilde{\mu}_{n}(s))\geq V^{\mu _{n}}(s).$ $$

By the Policy Improvement Theorem, since $Q^{\mu_{n}}(s,\mu_{n+1}(s))\geq V^{\mu_{n}}(s)$ for all $s$, it follows that:

$$ $V^{\mu_{n+1}}(s)\geq V^{\mu_{n}}(s),\quad\forall s\in\mathcal{S}.$ $$

Thus, the sequence $\{V^{\mu_{n}}\}$ is monotonically non-decreasing.

#### Convergence of Policy Iteration

Since the sequence $\{V^{\mu_{n}}\}$ is monotonically non-decreasing and bounded above by $V^{*}$, it converges to some $V^{\infty}\leq V^{*}$.
Given the finite number of possible policies, the sequence $\{\mu_{n}\}$ must eventually repeat a policy. Suppose that at some iteration $N$, the policy repeats, i.e., $\mu_{N+1}=\mu_{N}$.

At this point, since the policy hasn’t changed, we have:

$$ $\mu_{N}(s)=\arg\max_{a\in\{\tilde{\mu}_{N}(s),\nu_{1}(s),\dots,\nu_{k}(s)\}}Q^ {\mu_{N}}(s,a),\quad\forall s\in\mathcal{S}.$ $$

Since $\tilde{\mu}_{N}(s)$ is obtained by performing a DPG update on $\mu_{N}(s)$, and we have that $\mu_{N}(s)$ maximizes $Q^{\mu_{N}}(s,a)$ among $\{\tilde{\mu}_{N}(s),\nu_{1}(s),\dots,\nu_{k}(s)\}$, it must be that:

$$ $Q^{\mu_{N}}(s,\mu_{N}(s))\geq Q^{\mu_{N}}(s,a),\quad\forall a\in\{\tilde{\mu}_ {N}(s),\nu_{1}(s),\dots,\nu_{k}(s)\}.$ $$

Moreover, since $\tilde{\mu}_{N}(s)$ is obtained via gradient ascent from $\mu_{N}(s)$, and yet does not yield a higher $Q$-value, it implies that:

$$ $\nabla_{a}Q^{\mu_{N}}(s,a)\big{|}_{a=\mu_{N}(s)}=0.$ $$

This suggests that $\mu_{N}(s)$ is a local maximum of $Q^{\mu_{N}}(s,a)$. This shows that this modification to the policy iteration algorithm of DPG is guaranteed to converge.

Since the set $\{\tilde{\mu}_{N}(s),\nu_{1}(s),\dots,\nu_{k}(s)\}$ includes more actions from $\mathcal{A}$, $\mu_{N}(s)$ is the action that better maximizes $Q^{\mu_{N}}(s,a)$ than $\tilde{\mu}_{N}$. Therefore, $\mu_{N}$ is a greedier policy with respect to $Q^{\mu_{N}}$ than $\tilde{\mu}_{N}$.

∎

### Appendix B Proof of Reducing Number of Local Optima in Successive Surrogates

###### Theorem B.1 .

Consider a state $s\in\mathcal{S}$, the function $Q$ as defined in Eq. 1, and the surrogate functions $\Psi_{i}$ as defined in Eq. 7. Let $N_{\text{opt}}(f)$ denote the number of local optima (assumed countable) of a function $f:\mathcal{A}\to\mathbb{R}$, where $\mathcal{A}$ is the action space. Then,

$$ $N_{\text{opt}}(Q(s,a))\geq N_{\text{opt}}(\Psi_{0}(s,a;\{a_{0}\}))\geq N_{ \text{opt}}(\Psi_{1}(s,a;\{a_{0},a_{1}\}))\geq\dots\geq N_{\text{opt}}(\Psi_{k }(s,a;\{a_{0},\dots,a_{k}\})).$ $$

###### Proof.

For each $i\geq 0$, define the surrogate function $\Psi_{i}$ recursively:

$$ $\Psi_{i}(s,a;\{a_{0},\dots,a_{i}\})=\max\left\{Q(s,a),\tau_{i}\right\},$ (11) $$

where

$$ $\tau_{i}=\max_{0\leq j\leq i}Q(s,a_{j}).$ $$

Note that $\tau_{i}$ is non-decreasing with respect to $i$, i.e., $\tau_{i+1}\geq\tau_{i}$.

Our goal is to show that for each $i\geq 0$,

$$ $N_{\text{opt}}(\Psi_{i}(s,a;\{a_{0},\dots,a_{i}\}))\geq N_{\text{opt}}(\Psi_{i +1}(s,a;\{a_{0},\dots,a_{i+1}\})).$ $$

We proceed by considering how the set of local optima changes from $\Psi_{i}$ to $\Psi_{i+1}$.

Consider any local optimum $a^{\prime}$ of $\Psi_{i}$. There are two cases:

Case 1: $Q(s,a^{\prime})>\tau_{i}$

In this case, $\Psi_{i}(s,a^{\prime})=Q(s,a^{\prime})$ and $\Psi_{i}$ coincides with $Q$ in a neighborhood of $a^{\prime}$. Since $a^{\prime}$ is a local optimum of $\Psi_{i}$, it is also a local optimum of $Q$. Because $\tau_{i+1}\geq\tau_{i}$, there are two subcases:

Subcase 1a: $Q(s,a^{\prime})>\tau_{i+1}$

Here, $\Psi_{i+1}(s,a^{\prime})=Q(s,a^{\prime})$ and, in a neighborhood of $a^{\prime}$, $\Psi_{i+1}$ coincides with $Q$. Thus, $a^{\prime}$ remains a local optimum of $\Psi_{i+1}$.

Subcase 1b: $Q(s,a^{\prime})\leq\tau_{i+1}$

Since $Q(s,a^{\prime})>\tau_{i}$ and $\tau_{i+1}\geq\tau_{i}$, this implies $\tau_{i+1}>\tau_{i}$ and $Q(s,a^{\prime})=\tau_{i+1}$. Then,

$$ $\Psi_{i+1}(s,a^{\prime})=\tau_{i+1},$ $$

and in a neighborhood around $a^{\prime}$, $\Psi_{i+1}(s,a)\geq\tau_{i+1}$. Thus, $a^{\prime}$ is not a local optimum of $\Psi_{i+1}$ because there is no neighborhood where $\Psi_{i+1}(s,a)<\Psi_{i+1}(s,a^{\prime})$.

Case 2: $Q(s,a^{\prime})\leq\tau_{i}$

In this case, $\Psi_{i}(s,a^{\prime})=\tau_{i}$, and $\Psi_{i}$ is constant at $\tau_{i}$ in a neighborhood of $a^{\prime}$. Thus, $a^{\prime}$ may be considered a local optimum in $\Psi_{i}$ if the function does not exceed $\tau_{i}$ nearby. When moving to $\Psi_{i+1}$, since $\tau_{i+1}\geq\tau_{i}$, we have:

$$ $\Psi_{i+1}(s,a^{\prime})=\tau_{i+1}\geq\tau_{i}.$ $$

In the neighborhood of $a^{\prime}$, $\Psi_{i+1}$ remains at least $\tau_{i+1}$, so $a^{\prime}$ is not a local optimum in $\Psi_{i+1}$ unless $Q(s,a)<\tau_{i+1}$ in a neighborhood around $a^{\prime}$.

However, since $\Psi_{i+1}(s,a)\geq\tau_{i+1}$ for all $a$, the function does not decrease below $\Psi_{i+1}(s,a^{\prime})$ in any neighborhood of $a^{\prime}$. Therefore, $a^{\prime}$ is not a local optimum of $\Psi_{i+1}$.

Conclusion: From the above cases, we observe that:

- •
Any local optimum $a^{\prime}$ of $\Psi_{i}$ where $Q(s,a^{\prime})>\tau_{i+1}$ remains a local optimum in $\Psi_{i+1}$.
- •
Any local optimum $a^{\prime}$ of $\Psi_{i}$ where $Q(s,a^{\prime})\leq\tau_{i+1}$ does not remain a local optimum in $\Psi_{i+1}$.

Since $\Psi_{i+1}$ does not introduce new local optima (because $\Psi_{i+1}(s,a)\geq\Psi_{i}(s,a)$ for all $a$ and coincides with $Q$ only where $Q(s,a)>\tau_{i+1}$), the number of local optima does not increase from $\Psi_{i}$ to $\Psi_{i+1}$.

Base Case: For $i=0$, we have:

$$ $\Psi_{0}(s,a;\{a_{0}\})=\max\left\{Q(s,a),Q(s,a_{0})\right\}.$ $$

If we consider $Q(s,a_{0})$ to be less than the minimum value of $Q(s,a)$ (which can be arranged by choosing $a_{0}$ appropriately or by defining $\tau_{0}$ to be less than $\inf_{a}Q(s,a)$), then $\Psi_{0}(s,a)=Q(s,a)$, and the base case holds trivially.

Inductive Step: Assuming that

$$ $N_{\text{opt}}(\Psi_{i}(s,a;\{a_{0},\dots,a_{i}\}))\leq N_{\text{opt}}(\Psi_{i }(s,a;\{a_{0},\dots,a_{i}\})),$ $$

we have shown that

$$ $N_{\text{opt}}(\Psi_{i+1}(s,a;\{a_{0},\dots,a_{i+1}\}))\leq N_{\text{opt}}( \Psi_{i}(s,a;\{a_{0},\dots,a_{i}\})).$ $$

By induction, it follows that:

$$ $N_{\text{opt}}(Q(s,a))\geq N_{\text{opt}}(\Psi_{0}(s,a;\{a_{0}\}))\geq N_{ \text{opt}}(\Psi_{1}(s,a;\{a_{0},a_{1}\}))\geq\dots\geq N_{\text{opt}}(\Psi_{k }(s,a;\{a_{0},\dots,a_{k}\})).$ $$

∎

###### Theorem B.1 .

###### Proof.

### Appendix C Environment Details

Figure: Figure 13: Benchmark Environments involve discrete action space tasks like Mine World and recommender systems (simulated and MovieLens-Data) and restricted locomotion tasks.
Refer to caption: x28.png

Figure: Figure 14: Mining Expedition. The red agent must reach the green goal by navigating the grid and using one or more pick-axes to clear each mine blocking the path.
Refer to caption: x29.png

#### C.1 MiningEnv

The grid world environment, introduced in  §5, requires an agent to reach a goal by navigating a 2D maze as soon as possible while breaking the mines blocking the way.

State: The state space is an 8+K dimensional vector, where K equals to mine-category-size. This vector consists of 4 independent pieces of information: Agent Position, Agent Direction, Surrounding Path, and Front Cell Type.

- 1.
Agent Position: A 2D vector representing the agent’s x and y coordinates.
- 2.
Agent Direction: One dimension representing directions (0: right, 1: down, 2: left, 3: up).
- 3.
Surrounding Path: A 4-dimensional vector indicating if the adjacent cells are empty or a goal (1: empty/goal, 0: otherwise).
- 4.
Front Cell Type: A $(K+1)$-dimensional one-hot vector with first $K$ dimensions representing the type of mine and the last dimension representing if the cell is empty (zero) or goal (one).

Finally, we will normalize each dimension to [0, 1] with each dimension’s minimum/maximum value.

Termination:
An episode terminates when the agent reaches the goal or after 100 timesteps. Upon reset, the grid layout changes while keeping the agent’s start and goal positions fixed.

Actions:
Actions include navigation (up, down, left, right) and pick-axe categories. Navigation changes the agent’s direction and attempts to move forward. The agent cannot step into a mine but will change direction when trying to step onto a mine or the border of the grid.
The pick-axe tool actions (50 types) have a predefined one-to-one mapping of how they interact with the mines, which means they can be successfully applied to only one kind of mine, and either transform that kind of mine into another type of mine or directly break it.

Reward:
The agent’s reward comprises a goal-reaching reward, a distance-based step reward, and rewards for successful tool use or mine-breaking. The goal reward is discounted by steps taken over the episode, encouraging shorter paths to reach the goal.

$$ $\begin{split}R(s,a)\>=\>&\mathbbm{1}_{Goal}\cdot R_{\text{Goal}}\left(1- \lambda_{\text{Goal}}\frac{N_{\text{current steps}}}{N_{\text{max steps}}} \right)\>+\\ &R_{\text{Step}}\left(D_{\text{distance \> before}}-D_{\text{distance \>after} }\right)\>+\\ &\mathbbm{1}_{correct\>tool\>applied}\cdot R_{\text{Tool}}\>+\\ &\mathbbm{1}_{successfully\>break\>mine}\cdot R_{\text{Bonus}}\end{split}$ (12) $$

where    $R_{\text{Goal}}=10,\>\>R_{\text{Step}}=0.1,\>\>R_{\text{Tool}}=0.1,\>\>R_{
\text{Bonus}}=0.1,\>\>\lambda_{\text{Goal}}=0.9,\>\>N_{\text{max steps}}=100$

Action Representations
Actions are represented as a 4D vector with normalized values [0, 1] as described in Figure 14. Dimensions represent skill category (navigation or pick-axe), movement direction (right, down, left, up), mine type where this action can be applied, and the outcome of applying the tool to the mine, respectively.

#### C.2 RecSim

In the simulated recommendation system (RecSys) environment, the agent selects an item from a large set that aligns with the user’s interests. Users are modeled with dynamically changing preferences that evolve based on their interactions (clicks). The agent’s objective is to infer these evolving preferences from user clicks and recommend the most relevant items to maximize the total number of clicks.

State: The user’s interest is represented by an embedding vector $e_{u}\in\mathbb{R}^{n}$, where $n$ is the number of item categories. This embedding evolves over time as the user interacts with different items. When a user clicks on an item with embedding $e_{i}\in\mathbb{R}^{n}$, the user interest embedding $e_{u}$ is updated as follows:

$$ $\displaystyle e_{u}$ $\displaystyle\leftarrow e_{u}+\Delta e_{u},\quad\text{with probability }\frac{ e_{u}^{\top}e_{i}+1}{2}$ $\displaystyle e_{u}$ $\displaystyle\leftarrow e_{u}-\Delta e_{u},\quad\text{with probability }\frac{ 1-e_{u}^{\top}e_{i}}{2},$ $$

where $\Delta e_{u}$ represents an adjustment that depends on the alignment between $e_{u}$ and $e_{i}$. This update mechanism adjusts the user’s preference towards the clicked item, reinforcing the connection between the current action on future recommendations.

Action: The action set consists of all items that can be recommended, and the agent must select the item most relevant to the user’s long-term preferences over the episode.

Reward:
The reward is based on user feedback: either a click (reward = 1) or skip (reward = 0). The user model computes a score for each item using the dot product of the user and item embeddings:

$$ $\displaystyle\text{score}_{item}$ $\displaystyle=\langle e_{u},e_{i}\rangle$ $$

The click probability is computed with a softmax over the item score and a predefined skip score:

$$ $\displaystyle p_{item}$ $\displaystyle=\frac{e^{\text{score}_{item}}}{e^{\text{score}_{item}}+e^{\text{ score}_{skip}}},\quad p_{skip}=1-p_{item}$ $$

The user then stochastically chooses to click or skip based on this distribution.

Action Representations:
Following Jain et al. (), items are represented as continuous vectors sampled from a Gaussian Mixture Model (GMM), with centers representing item categories.

#### C.3 Continuous Control

MuJoCo (Todorov et al., ) is a physics engine that provides a suite of standard reinforcement learning tasks with continuous action spaces, commonly used for benchmarking continuous control algorithms. We briefly describe some of these tasks below:

Hopper: The agent controls a one-legged robot that must learn to hop forward while maintaining balance. The objective is to maximize forward velocity without falling.

Walker2d: The agent controls a two-legged bipedal robot that must learn to walk forward efficiently while maintaining balance. The goal is to achieve stable locomotion at high speeds.

HalfCheetah: The agent controls a planar, cheetah-like robot with multiple joints in a 2D environment. The task requires learning a coordinated gait to propel the robot forward as quickly as possible.

Ant: The agent controls a four-legged, ant-like robot with multiple degrees of freedom. The challenge is to learn to walk and navigate efficiently while maximizing forward progress.

##### C.3.1 Restricted Locomotion in Mujoco

The restricted locomotion Mujoco tasks are introduced to demonstrate how common DPG-based approaches get stuck in local optima when the Q-landscape is complex and non-convex. This setting limits the range of actions the agent can perform in each dimension, simulating realistic scenarios such as wear and tear of hardware. For example, action space may be affected as visualized in Figure 6. A mixture-of-hypersphere action space is used to simulate such asymmetric restrictions, which affect the range of torques for the Hopper and Walker joints, as well as the forces applied to the inverted pendulum and double pendulum. The hyperspheres are sampled randomly, and their size and radius are carefully tuned to ensure that the action space has enough valid actions to solve the task.

Definition of restriction.

- •
Restricted Hopper & Walker
Invalid action vectors are replaced with 0 by changing the environment’s step function code:
[⬇](data:text/plain;base64,ZGVmIHN0ZXAoYWN0aW9uKToKICAgIC4uLgogICAgaWYgY2hlY2tfdmFsaWQoYWN0aW9uKToKICAgICAgICBzZWxmLmRvX3NpbXVsYXRpb24oYWN0aW9uKQogICAgZWxzZToKICAgICAgICBzZWxmLmRvX3NpbXVsYXRpb24obnAuemVyb3NfbGlrZShhY3Rpb24pKQogICAgLi4u)
1def step(action):
2 ...
3 if check_valid(action):
4 self.do_simulation(action)
5 else:
6 self.do_simulation(np.zeros_like(action))
7 ...
The Hopper action space is $3$-dimensional, with torque applied to $[\text{thigh},\text{leg},\text{foot}]$, while the Walker action space is $6$-dimensional, with torque applied to $[\text{right thigh},\text{right leg},\text{right foot},\text{left thigh},\text
{left leg},\text{left foot}]$. The physical implication of restricted locomotion is that zero torques are exerted for the $\Delta t$ duration between two actions, i.e., no torques are applied for $0.008$ seconds. This effectively slows down the agent’s current velocities and angular velocities due to friction whenever the agent selects an invalid action.
- •
Inverted Pendulum & Inverted Double Pendulum
Invalid action vectors are replaced with -1 by changing the environment’s step function code:
[⬇](data:text/plain;base64,ZGVmIHN0ZXAoYWN0aW9uKToKLi4uCiAgICBpZiBub3QgY2hlY2tfdmFsaWQoYWN0aW9uKToKICAgICAgICBhY3Rpb25bOl0gPSAtMS4KICAgIHNlbGYuZG9fc2ltdWxhdGlvbihhY3Rpb24pCi4uLg==)
1def step(action):
2...
3 if not check_valid(action):
4 action[:] = -1.
5 self.do_simulation(action)
6...
The action space is $1$-dimensional, with force applied on the cart. The implication is that the cart is pushed in the left direction for $0.02$ (default) seconds. Note that the action vectors are not zeroed because a 0 0-action is often the optimal action, particularly when the agent starts upright. This would make the optimal policy trivially be *learning to select invalid actions*.

### Appendix D Additional Results

#### D.1 Experiments on Continuous Control (Unrestricted Mujoco)

In standard MuJoCo tasks, the Q-landscape is likely easier to optimize compared to MuJoCo-Restricted tasks. In Figure 15, we find that baseline models consistently perform well in all standard tasks, unlike in MuJoCo-Restricted tasks. Thus, we can infer the following:

- 1.
Baselines have sufficient capacity, are well-tuned, and can navigate simple Q-landscapes optimally.
- 2.
SAVO performs on par with other methods in MuJoCo tasks where the Q-landscape is easier to optimize, showing that SAVO is a robust, widely applicable actor architecture.
- 3.
Baselines performing well in unrestricted locomotion but suboptimally in restricted locomotion delineates the cause of suboptimality to be the complexity of the underlying Q-landscapes, such as those shown in Figure 2. SAVO is closer to optimal in both settings because it can navigate both simple and complex Q-functions better than alternate actor architectures.

Figure: Figure 15: Unrestricted Locomotion (§D.1). SAVO and most baselines perform optimally in standard MuJoCo continuous control tasks, where the Q-landscape is easy to navigate.
Refer to caption: x30.png

Figure: Figure 16: Ablations of SAVO variations (§D.2) shows the importance of (i) the approximation of surrogates, (ii) removing TD3’s action smoothing, (iii) conditioning on preceding actions in the successive actor and surrogate networks, and (iv) individual actors that separate the action candidate prediction instead of a joint high-dimensional learning task.
Refer to caption: x35.png

#### D.2 Per-Environment Ablation Results

Figure 16 shows the per-environment performance of SAVO ablations, compiled into aggregate performance profiles in Figure 7(b). The SAVO - Approximation variant underperforms significantly in discrete action space tasks, where traversing between local optima is complex due to nearby actions having diverse Q-values (see the right panel of Figure 2). Similarly, adding TD3’s target action smoothing to SAVO results in inaccurate learned Q-values when several differently valued actions exist near the target action, as in the complex landscapes of all tasks considered.

Removing information about preceding actions does not significantly degrade SAVO’s performance since preceding actions’ Q-values are indirectly incorporated into the surrogates’ training objective (see Eq. (9)), except for MineWorld where this information helps improve efficiency.

The SAVO + Joint ablation learns a single actor that outputs a joint action composed of $k$ constituents, aiming to cover the action space so that multiple coordinated actions can better maximize the Q-function compared to a single action. However, this increases the complexity of the architecture and only works in low-dimensional tasks like Inverted-Pendulum and Inverted-Double-Pendulum. SAVO simplifies action candidate generation by using several successive actors with specialized objectives, enabling easier training without exploding the action space.

Figure: Figure 17: SAC is orthogonal to the effect of SAVO (§D.3). SAC is a different algorithm than TD3, whereas SAVO is a plug-in actor architecture for TD3. Thus, tasks where SAC outperforms TD3 differ from tasks where SAVO outperforms TD3. Also, TD3 outperforms SAC in Restricted Hopper and Inverted-Double-Pendulum. However, SAVO+TD3 guarantees improvement over TD3.
Refer to caption: x43.png

#### D.3 SAC is Orthogonal to SAVO

We compare Soft Actor-Critic (SAC), TD3, and TD3 + SAVO across various Mujoco-Restricted tasks. Figure 17 shows that SAC sometimes outperforms and sometimes underperforms TD3. Therefore, SAC’s stochastic policy does not address the challenge of non-convexity in the Q-function. In contrast, SAVO+TD3 consistently outperforms TD3 and SAC, demonstrating the effectiveness of SAVO in complex Q-landscapes. While SAC can be better than TD3 in certain environments, its algorithmic modifications are orthogonal to the architectural improvements due to the SAVO actor.

Figure: Figure 18: SAC is suboptimal in complex Q-landscape (§D.3) of Restricted Inverted Double Pendulum, but SAVO helps.
Refer to caption: x47.png

In the Restricted Inverted Double Pendulum task (Figure 18), SAC underperforms even TD3. Analogous to TD3, the suboptimality is due to the non-convexity in the soft Q-function landscape, where small changes in nearby actions can lead to significantly different environment returns. We combine SAC with SAVO’s successive actors and surrogates to better maximize the soft Q-function, naively considering action candidates for $\mu_{M}$ as the mean action of the stochastic actors. We observe that this preliminary version of SAC + SAVO shows significant improvements over SAC in complex Q-landscapes. In future work, we aim to formalize a SAVO-like objective that effectively enables SAC’s stochastic actors to navigate the non-convexity of its soft Q-function.

#### D.4 Increasing Size of Discrete Action Space in RecSim

We test the robustness of our method to more challenging Q-value landscapes in Figure 19, especially in discrete action space tasks with massive action spaces. In RecSim, we increase the number of actual discrete actions from $10,000$ to $100,000$ and $500,000$. The experiments show that SAVO outperforms the best-performing baseline of TD3 + Sampling (Wolpertinger) and the best-performing ablation of SAVO + Joint Action. This shows that SAVO maintains robust performance even as the action space size increases and the Q-function landscape becomes more intricate. In contrast, the baselines experienced performance deterioration as action sizes grew larger.

Figure: Figure 19: Increasing RecSim action set size (§D.4). (Left) $100,000$ items, (Right) $500,000$ items (6 seeds) maintains the performance trends of SAVO and the best-performing baseline (TD3 + Sampling) and the best-performing ablation (SAVO with Joint-Action).
Refer to caption: x48.png

### Appendix E Validating SAVO Design Choices

#### E.1 Design Choices: Action summarizers

Three key architectures were considered for the design of the action summarizer: DeepSets, LSTM, and Transformer models, represented by SAVO, SAVO-LSTM, and SAVO-Transformer in Figure 20, respectively.
In general, the effect of the action summarizer is not significant, and we choose DeepSet for its simplicity for most experiments.

Figure: Figure 20: Action summarizer comparison (§E.1). The effect is not significant The results are averaged over 5 random seeds, and the seed variance is shown with shading.
Refer to caption: x50.png

#### E.2 Conditioning on Previous Actions: FiLM vs. MLP

We examined two approaches for conditioning on the previous action list summary: Feature-wise Linear Modulation (FiLM) and concatenation with input, represented by the FiLM and non-film variants in Figure 21. Across tasks, FiLM outperformed the non-FiLM version, showing the effectiveness of layerwise conditioning in leveraging prior action information for action selection and surrogate value prediction. This shows that the successive actors are appropriately utilizing the actions from the preceding actors to tailor their search for optimal actions, and the successive surrogates can better evaluate Q-values, knowing where they could be thresholded by the loss function.

Figure: Figure 21: FiLM to condition on preceding actions (§E.2). FiLM ensures layerwise dependence on the preceding actions for acting in actors $\nu_{i}$ and for predicting value in surrogates $\hat{\Psi}_{i}$, which generally results in better performance across tasks.
Refer to caption: x53.png

#### E.3 Exploration Noise comparison: OUNoise vs Gaussian

Figure: (a) Noise types
Refer to caption: x60.png

We compare Ornstein-Uhlenbeck (OU) noise with Gaussian noise across our environments and find that OU noise was generally better, with the difference being minimal. We chose to use OU for our experiments and a comparison on Hopper-Restricted is shown in Figure 22(a). We note that TD3 (Fujimoto et al., ) also suggests no significant difference between OU and Gaussian noise and favored Gaussian for simplicity. All our baselines use the same exploration backbone, and we confirm that using OU noise is consistent with the available state-of-the-art results with TD3 + Gaussian noise on common environments like Ant, HalfCheetah, Hopper, and Walker2D.

### Appendix F Network Architectures

#### F.1 Successive Actors

The entire actor is built as a successive architecture (see Figure 4), where each successive actor receives two pieces of information: the current state and the action list generated by preceding actors.
Each action is concatenated with the state to contextualize it and then summarized using a list-summarizer, described in §F.3.
This list summary is concatenated with the state again and passed into an MLP with ReLU (3 layers for MuJoCo tasks and 4 layers for MineWorld and RecSim) as described in Table 2. This MLP generates one action for each successive actor, which is subsequently used as an input action to the succeeding action lists. For discrete action space tasks, this generated action is processed with a 1-NN to find the nearest exact discrete action. Finally, the actions generated by each individual successive actor are accumulated, and the maximizer actor $\mu_{M}$ step from Eq. (5) selects the highest-valued action according to the Critic Q-network, described in §F.2.

#### F.2 Successive Surrogates

As Figure 4 illustrates, there is a surrogate network for each actor in the successive actor-architecture. Each successive critic receives three pieces of information: the current state, the action list generated by preceding actors, and the action generated by the actor corresponding to the current surrogate.
Each action is concatenated with the state to contextualize it and then summarized using a list-summarizer, described in §F.3.
This list summary is concatenated with the state and the current action, and passed into a 2-layer MLP with ReLU (See Table 2). This MLP generates the surrogate value $\hat{\Psi}_{i}(s,a;a_{<i})$ and is used as an objective to ascend over by its corresponding actor $\nu_{i}$.

#### F.3 List Summarizers

To extract meaningful information from the list of candidate actions, we employed several list summarization methods following Jain et al. (). These methods are described below:

Bi-LSTM:
The action representations of the preceding actors’ actions are first passed through a two-layer multilayer perceptron (MLP) with ReLU activation functions. The output of this MLP is then processed by a two-layer bidirectional LSTM network (Huang et al., ). The resulting output is fed into another two-layer MLP to create an action set summary, which serves as an input for the actor-network (§F.1) and the surrogate network (§F.2).

DeepSet:
The action representations of the preceding actors’ actions are initially processed by a two-layer MLP with ReLU activations. The outputs are then aggregated using mean pooling over all candidate actions to compress the information into a fixed-size summary. This summary is passed through another two-layer MLP with ReLU activation to produce the action set summary, which serves as an input for the actor-network (§F.1) and the surrogate network (§F.2).

Transformer: Similar to Bi-LSTM, the action representations of the preceding actors’ actions are first processed by a two-layer MLP with ReLU activations. The outputs are then input into a Transformer network with self-attention and feed-forward layers to summarize the information. The resulting summary is used as part of the input to the actor-network (§F.1) and the surrogate network (§F.2).

#### F.4 Feature-wise Linear Modulation (FiLM)

Feature-wise Linear Modulation (Perez et al., ) is a technique used in neural networks to condition intermediate feature representations based on external information, enhancing the network’s adaptability and performance across various tasks. FiLM modulates the features of a layer by applying learned, feature-wise affine transformations. Specifically, given a set of features $\mathbf{F}$, FiLM applies a scaling and shifting operation,

$$ $\text{FiLM}(\mathbf{F})=\gamma\odot\mathbf{F}+\beta,$ $$

where $\gamma$ and $\beta$ are modulation parameters learned from another source (e.g., a separate network or input), and $\odot$ denotes element-wise multiplication. This approach allows the network to selectively emphasize or de-emphasize aspects of the input data, effectively capturing complex and context-specific relationships. FiLM has been successfully applied in tasks such as visual question answering and image captioning, where conditioning visual features on textual input is essential. We apply FiLM while conditioning the actor and surrogate networks on the summary of preceding actions.

### Appendix G Experiment and Evaluation Setup

#### G.1 Aggregated Results: Performance Profiles

To rigorously validate the aggregate efficacy of our approach, we adopt the robust evaluation methodology proposed by Agarwal et al. (). By incorporating their suggested performance profiles, we conduct a comprehensive comparison between our method and baseline approaches, providing a thorough understanding of the statistical uncertainties inherent in our results.
Figure 7(a) shows the performance profiles across all tasks. The x-axis represents normalized scores, calculated using min-max scaling based on the initial performance of untrained agents aggregated across random seeds (i.e., Min) and the final performance from Figure 8 (i.e., Max). The results show that our method consistently outperforms the baselines across various random seeds and environments. Our performance curve remains at the top as the x-axis progresses, while the baseline curves decline earlier. This highlights the reliability of SAVO over different environments and 10 seeds.

#### G.2 Implementation Details

We used PyTorch (Paszke et al., ) for our implementation, and the experiments were primarily conducted on workstations with either NVIDIA GeForce RTX 2080 Ti, P40, or V32 GPUs on. Each experiment seed takes about 4-6 hours for Mine World, 12-72 hours for Mujoco, and 6-72 hours for RecSim, to converge. We use the Weights & Biases tool (Biewald, ) for plotting and logging experiments. All the environments were interfaced using OpenAI Gym wrappers (Brockman et al., ). We use the Adam optimizer (Kingma & Ba, ) throughout for training.

#### G.3 Common Hyperparameter Tuning

To ensure fairness across all baselines and our methods, we performed hyperparameter tuning over parameters that are common across methods:

- •
Learning Rates of Actor and Critic: (Actor) We searched over learning rates $\{0.01,0.001,0.0001,0.0003\}$ and found that $0.0003$ was the most stable for the actor’s learning across all tasks. (Critic) Similar to the actor, we searched over the same set of learning rates and found the same value of $0.0003$ was the most stable for the critic’s learning across all tasks.
- •
Network Sizes of Actor and Critic:
For each task, we searched over simple 3 or 4 MLP layers to determine the network size that performed best but did not observe major differences.
(Critic) To ensure a fair comparison, we used the same network size for the critic (Q-network) and surrogates across all methods within each task. (Actor) Similar to the critic, we used the same network size for the various actors in all the baselines and successive actors in SAVO within a particular task.

#### G.4 Hyperparameters

The environment and RL algorithm hyperparameters are described in Table 2.

**Table 2: Environment/Policy-specific Hyperparameters**
| Hyperparameter | Mine World | MuJoCo & Adroit | RecSim |
| --- | --- | --- | --- |
| Environment |  |  |  |
|  |  |  |  |
| Total Timesteps | $10^{7}$ | $3\times 10^{6}$ | $10^{7}$ |
| Number of epochs | 5,000 | 8,000 | 10,000 |
| # Envs in Parallel | 20 | 10 | 16 |
| Episode Horizon | 100 | 1000 | 20 |
| Number of Actions | 104 | N/A | 10000 |
| True Action Dim | 4 | 5 | 30 |
| Extra Action Dim | 5 | N/A | 15 |
| RL Training |  |  |  |
|  |  |  |  |
| Batch size | 256 | 256 | 256 |
| Buffer size | $5\times 10^{5}$ | $5\times 10^{5}$ | $10^{6}$ |
| Actor: LR | $3\times 10^{-4}$ | $3\times 10^{-4}$ | $3\times 10^{-4}$ |
| Actor: $\epsilon_{\text{start}}$ | 1 | 1 | 1 |
| Actor: $\epsilon_{\text{end}}$ | 0.01 | 0.01 | 0.01 |
| Actor: $\epsilon$ decay steps | $5\times 10^{6}$ | $5\times 10^{5}$ | $10^{7}$ |
| Actor: $\epsilon$ in Eval | 0 | 0 | 0 |
| Actor: MLP Layers | 128_64_64_32 | 256_256 | 64_32_32_16 |
| Critic: LR | $3\times 10^{-4}$ | $3\times 10^{-4}$ | $3\times 10^{-4}$ |
| Critic: $\gamma$ | 0.99 | 0.99 | 0.99 |
| Critic: MLP Layers | 128_128 | 256_256 | 64_32 |
| # updates per epoch | 20 | 50 | 20 |
| List Length | 3 | 3 | 3 |
| Type of List Encoder | DeepSet | DeepSet | DeepSet |
| List Encoder LR | $3\times 10^{-4}$ | $3\times 10^{-4}$ | $3\times 10^{-4}$ |

### Appendix H Q-Value Landscape Visualizations

#### H.1 1-Dimensional Action Space Environments

We analyzed the Q-value landscapes in Mujoco environments to show how successive critics help actors find better actions by reducing local optima. Figure 23 illustrates a typically smooth and easy-to-optimize Q-value landscape in unrestricted Inverted-Pendulum. Figure 24 illustrates that in restricted locomotion, the Q-value landscape (leftmost and rightmost figures) is uneven with many local optima. However, the Q-value landscapes learned by successive surrogates $\hat{\Psi}_{i}$ become successively smoother by removing local peaks below the Q-values of previously selected actions. This helps actors find closer to optimal actions than with a single critic.

Finally, when we plot the actions $a_{0},a_{1},a_{2}$ selected by the learned successive actors on the original Q-landscape (rightmost figure), we see they often achieve higher Q-values than $a_{0}$, the action a single actor has learned. Thus, the maximizer actor $\mu_{M}$ often finds closer to optimal actions than a single actor, resulting in better performance as shown in the return comparison between $\mu_{M}$ and single actor (Figure 11(c)) and the performance against baselines (Figure 8).

Figure: (a) $Q_{0}(s,a_{0})$
Refer to caption: extracted/5927604/images/q-function-plots/all_envs/inverted_pendulum_easy/ar_critic_plot_0_2d.png

Figure: Figure 24: Successive surrogate landscapes and Q landscape for Restricted Inverted-Pendulum and Restricted Inverted-Double-Pendulum environments.
Refer to caption: x61.png

#### H.2 High-Dimensional Action Space Environments

Figure 25 visualize Q-value landscapes for a TD3 agent in Hopper-v4. We project actions from the 3D action space of Hopper-v4 onto a 2D plane using Uniform Manifold Approximation and Projection (UMAP) and sample 10,000 actions evenly to ensure thorough coverage. The Q-values are plotted using trisurf, which may introduce some artificial roughness but offers more reliable visuals than grid-surface plotting. Despite limitations of dimensionality reduction — such as distortion of distances — the Q-landscape for Hopper-v4 reveals a large globally optimal region (shown in yellow), offering a clear gradient path that prevents the gradient-based actor from getting stuck in local optima.

In contrast, Hopper-Restricted (Figure 26) has more complex Q-landscapes due to valid actions being restricted in one of the hyperspheres shown in Figure 6. Consequently, these Q-landscapes appear to have more locally optimal regions than Hopper-v4. This creates many peaks where gradient-based actors might get trapped, degrading the resultant agent performance.

The curse of dimensionality limits conclusive analyses on higher dimensional environments like Walker2D-v4 (6D) and Ant-v4 (8D) because projecting to 2D causes significant information loss, making it difficult to assess convexity in their Q-landscapes.

Figure: Figure 25: Hopper-v4: Q landscape visualization at different states show a path to optimum.
Refer to caption: x69.png

Figure: Figure 26: Hopper-restricted: Q landscape visualization at different states show several local optima.
Refer to caption: x70.png

## Peer Reviews

confidence: 2
contribution: 2
initial_rating: 5
presentation: 2
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.
soundness: 3
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.
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.
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.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
questions: Section 4.3 defines \nabla \Psi as a function of \nabla Q. Is \Psi simply Q + constant with the truncation term?
soundness: 2
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.
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.
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.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
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?
soundness: 2
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.
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.
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.

Meta-review: 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).

Decision: Reject