Learning in complex action spaces without policy gradients

Thank you for recognizing the intriguing observations and clear presentation of our work. We appreciate your constructive feedback and the opportunity to address your concerns and questions.

---

Question 1: “The proposed method uses log-likelihood gradient to train the argmax predictors. Why not use the policy gradient directly to update the ensemble of argmax predictors?”

Thank you for this pertinent question. The primary reason we opted for the log-likelihood gradient over the policy gradient for training the ensemble of argmax predictors lies in maintaining the off-policy nature of Q-learning. Using the policy gradient directly to update the ensemble would inherently tie the training of the argmax predictors to the behavior policy, thereby compromising the off-policy learning capability of Q-learning.

In traditional algorithms like DDPG, the policy is constrained to a delta function to facilitate off-policy updates while still leveraging policy gradients (Section 2.3). However, this restriction limits the method to continuous action domains and confines the policy to deterministic predictors. By employing the log-likelihood gradient instead of the policy gradient, we decouple the training of the argmax predictors from the policy gradient framework. This allows us to:

• Maintain Off-Policy Learning: Q-learning remains fully off-policy, enabling the use of diverse and potentially historical data without being constrained by the current policy's distribution.

• Enhance Flexibility in Action Spaces: We can train argmax predictors that are not limited to delta functions, supporting discrete, continuous, and hybrid action spaces (e.g. see Figure 12). This flexibility also permits the use of an ensemble of arbitrary distribution types, rather than being restricted to deterministic policies.

In essence, the log-likelihood gradient facilitates the training of a versatile ensemble of argmax predictors while preserving the foundational benefits of off-policy Q-learning. This strategic choice underpins the scalability and adaptability of our QMLE framework across various action space complexities.

---

Weakness 1: Lack of “theoretical guarantees for computing the maximization in $A_m$ instead of $\mathcal{A}$”

We appreciate this concern. Our approach is theoretically grounded by recent work such as DAVI (Tian et al., 2022), which formally studies the use of Monte Carlo (MC) approximations for Q-maximization within Asynchronous Value Iteration (AVI). DAVI was shown to converge to the optimal value function under standard conditions, providing a theoretical grounding for the combination of tabular AVI with MC approximation for Q-maximization and learned tabular argmax predictors. Given that Q-learning is an instance of AVI, such foundations also extend to tabular Q-learning (with standard modifications to the conditions).

---

Weakness 2: “The iterative dependency restricted the actions to a subset where most actions are similar, potentially leading to a suboptimal solution.”

To mitigate the risk of restricting actions to a narrow subset, our framework incorporates uniform sampling alongside learned argmax predictors (as detailed in Equation 21). By allocating 90% of the sampling budget to uniform sampling (see Table 1) and the remaining 10% to the ensemble, we maintain diversity in action samples, thereby avoiding statistical bias and ensuring comprehensive coverage. This balanced sampling strategy helps prevent the iterative dependency from causing the action set to become overly similar, reducing the likelihood of converging to suboptimal policies.

---

Weakness 3: "As illustrated in Figure.2, QMLE can transcend DPG through a uniform sampling over the action space. But in high-dimensional action spaces, uniform sampling is usually inefficient."

You are correct that uniform sampling becomes inefficient in high-dimensional action spaces. To address this, our approach combines uniform sampling with an ensemble of learned argmax predictors. While uniform sampling ensures unbiased coverage, the ensemble focuses computational resources on promising regions of the action space, enhancing sample efficiency.

We believe this hybrid strategy provides a robust foundation and can be further optimized with more sophisticated sampling techniques in future work.

---

We hope this explanation provides clarity, and we’re always open to further discussion if there are any aspects that need additional attention or if you feel your concerns haven’t been fully resolved.

We appreciate your feedback and the opportunity to clarify and elaborate on several aspect of our work. Below, we address your questions in detail.

---

Question 1: "What are the limitations of policy gradients that lead to their replacement?"

Our primary aim is not to replace policy gradient (PG) methods but to demonstrate that action-value methods can effectively incorporate the core principles that make PG methods successful in complex action spaces. Nonetheless, while PG methods excel in continuous and high-dimensional action domains, they inherently possess certain limitations:

1. On-Policy Learning Constraints: PG methods are fundamentally on-policy, relying solely on data generated by the current policy. This restricts their sample efficiency and flexibility.
2. Complexity of Off-Policy Extensions: Extending PG methods to off-policy settings often involves restrictive policy choices (e.g. deterministic policies in DDPG and TD3) and intricate mechanisms around importance sampling which generally introduce bias for practical success (incl. V-Trace).
3. Local Optimality Issues: As illustrated in Section 5.1 (Figure 2), PG methods can converge to local optima even in simple problems, due to the local tendencies of policy gradients.

How QMLE Addresses These Limitations:

• Off-Policy data utilization: Being based on Q-learning, QMLE naturally supports off-policy learning, allowing it to leverage diverse data sources more efficiently without restrictive policy parameterizations or importance sampling corrections.

• Amortized maximization: By integrating Monte Carlo sampling and amortized maximization through Maximum Likelihood Estimation (MLE), QMLE can approximate the argmax operation with statistical global coverage, reducing the risk of converging to local optima.

---

Question 2.1: "Why does the number of seeds vary across different tasks?"

Simulation of complex physical domains such as Dog and Humanoid are more computationally intensive than simpler ones such as Hopper and Walker. This makes sampling from these domains more time-consuming per each environment step. On the other hand, these tasks are also more challenging and require longer training (5-10 million environment steps). To balance thoroughness and practicality, we conducted the more simulation-expensive tasks over 5 random seeds (Dog and Humanoid), and over 10 random seeds for all other tasks.

---

Question 2.2: "What do the shaded regions in the figures represent?"

The shaded regions represent the standard error of the mean across the seeds (as discussed in Section B.4).

---

We hope this response satisfactorily addresses your questions. We look forward to engaging further during the discussion period.

Thank you for your response and taking the time to read other reviewers' comments.

We have performed the ablation studies you suggested and will shortly include them in the manuscript for your consideration. Additionally, we will address each of the identified weaknesses in detail in our forthcoming response. Apologies for not addressing these issues in the first instance; our priority was to respond to your questions first and then incorporate revisions based on the weaknesses raised.

In the meantime, does our initial response address your questions satisfactorily?

Weakness 1.1: "First, what is the issue with policy gradients that the authors are aiming to replace them? This should have been clarified to justify the need for an alternative approach."

We believe our initial response (posted on Nov 18) to the Question 1 raised by the reviewer should have addressed this question. Please do let us know if more clarification is needed.

---

Weakness 1.3: "Furthermore, the method eventually requires a parametric component for predicting the argmax (Principle 2 in Section 4). In my view, this component functions as a type of policy, albeit in a somewhat convoluted and unintuitive way. Its inclusion seems to contradict the paper’s aim of eliminating the need for a policy and policy gradients. In fact, I would argue that the proposed method cannot be considered purely as an action-value method, as claimed by the authors."

In comparison to PG methods, QMLE does not introduce any additional burden on choosing a parametric distribution. The choice of policy in policy gradient methods is one that can be varied. For instance, in Schulman et al. (2015) "Trust Region Policy Optimization", the authors used a diagonal-covariance Gaussian policy in continuous-action problems and a factored-categorical policy in the discrete-action domains of Atari. However, Beta policies (see, e.g., Chou et al. (2017) "Improving Stochastic Policy Gradients in Continuous Control with Deep Reinforcement Learning using the Beta Distribution") and (non-factored) Categorical policies are also used with such PG methods, among other possible choices. However, deterministic policies (e.g. Delta policies) are incompatible with the on-policy PG methods, such as TRPO and PPO.

Then, to enable off-policy learning for policy gradient methods, DDPG uses Delta policies (which requires changes to the entire algorithm). While off-policy learning is gained, the limitation to Delta policies restricts the possibility to switch the policy type to a more expressive one if needed (e.g. in multimodal reward landscapes), a stochastic one, or a discrete-action one.

In conclusion, QMLE unifies the possibility to choose any distribution types (whether discrete, continuous, or a mixture of both and whether stochastic, deterministic, or a mixture of both). This is in our view a simplification by unification. Lastly, what are considered fixed choices in policy gradient methods are only the best practices over the originally variable components, which over time have been refined and made it into the mainstream implementations of the policy gradient methods such as PPO.

---

Weakness 1.2: "If the goal is to develop a method that is simpler (i.e. fewer components, reduced computation, fewer hyperparameters) than policy gradients, similar to the approach in [1], I would argue that the proposed method is in fact more complex than policy gradients. It introduces additional hyperparameters and design decisions."

To respond to the concern, let us examine a continuous-only variant of QMLE with a Delta-based argmax predictor for continuous control problems. In comparison to DDPG, we only have the following added hyperparameters (see also the top segment of Table 1 for QMLE-specific hyperparameters in a general case):

• sampling budgets $m_\textrm{target}$ and $m_\textrm{greedy}$
• sampling ratios $\rho_\textrm{uniform}$ and $\rho_\textrm{delta}$

Note that the same network architecture can be used by DDPG and QMLE, as done in Section 5.1.

Now we answer two key questions:

• Why deal with the extra hyperparameters? The added hyperparameters come with more global properties for QMLE in comparison to DDPG, as illustrated in Section 5.1 and Figure 2.

• How sensitive are the choices over these hyperparameters? As we show in Appendix D.1 (blue curves), using even the most basic and minimal choice of sampling budgets $m_\textrm{target} = m_\textrm{greedy} = 2$ and sampling ratios $\rho_\textrm{uniform} = \rho_\textrm{delta} = 0.5$ yields strong performance levels for the delta-based QMLE agent. Also, as we show in Appendix D.2, significant changes to the sampling budgets from 2 to 1000 does not cause significant changes in the performance, which shows that QMLE is relatively robust to these new parameters.

---

We believe that our responses and the revisions made to the paper address your remaining concerns. We hope that this clarifies our contributions and merits a reconsideration of your evaluation. If you have any further questions or require additional clarification, please do not hesitate to reach out.

Q5: Comparisons with Other Methods

In Appendix C, Figure 7 provides a comparison against QT-Opt and AQL, two notable action-value methods designed to extend Q-learning to complex action spaces. QMLE demonstrates superior performance in most tested domains. We have also included comparisons against SAC, TD3, MPO, PPO, TRPO, A2C in the Figures 5 and 6.

Additionally, methods like DecQN (Seyde et al., 2023) are designed for combinatorial discrete action spaces. They scale to high-dimensional discrete-action problems using rank-1 action-hypergraph representations (Tavakoli et al., 2021). While effective in such settings, these methods are not directly applicable to continuous-action domains (without discretization). We are happy to include performance curves for DecQN if the reviewer believes this would add value.

---

Q6: Extensions and Modifications

In Appendix E (pages 26–28), we outline three promising avenues for future exploration, including:

• Combining QMLE with advances in MLE (e.g. for heteroscedastic variance estimation) and deep RL (e.g. cross-entropy loss for approximate Q-learning and parallel Q-learning).

• Extending QMLE to multi-agent reinforcement learning under centralized training with decentralized execution (CTDE).

• Exploring adaptive curriculum strategies through dynamically growing action spaces.

We aim to release the QMLE code to encourage the community to iterate on these ideas.

---

Q7: Robustness to Noise and Variability

We have not explicitly tested QMLE under noisy or highly variable conditions. However, we are eager to explore this direction, particularly if the reviewer has specific scenarios in mind. Testing robustness under such conditions could provide valuable insights into the framework’s practical utility and resilience.

---

We hope this response clarifies the concerns raised and provides additional context for evaluating our work. Please let us know if there are any aspects that require further elaboration. We are grateful for your constructive feedback and look forward to engaging further.

Thank you for your insightful review and for highlighting both the strengths and areas for improvement in our paper. We appreciate your thoughtful questions and address them below.

---

Q1: Theoretical Assumptions

The QMLE framework builds upon established theoretical foundations related to sampling-based approximations for Q-maximization. Specifically, Tian et al. (2022) explored this within the context of tabular Asynchronous Value Iteration (AVI), utilizing uniform sampling alongside a tabular mechanism for caching and retrieving the best historical argmax actions in each state. Our approach extends this by training an ensemble of parametric argmax predictors, thereby generalizing the caching mechanism to function approximators.

These theoretical insights are applicable to the broader family of Value Iteration (VI) algorithms, with tabular Q-learning being an instance. Importantly, Tian et al.'s (2022) convergence proofs accommodate the replacement of a tabular argmax predictor with an ensemble of approximate predictors, provided uniform sampling is maintained.

Our third principle in QMLE—using action-in architectures for representation learning and generalization—is specifically pertinent to action-value learning with function approximation (e.g. neural networks). The theoretical underpinnings of approximate Q-learning remain an open problem, even for the simpler case of action-out architectures. Nevertheless, we believe that conducting a comparative study of action-in versus action-out architectures across diverse domains would be a useful direction for future research.

---

Q2: Performance Beyond the DeepMind Control Suite

Our focus in this work was to demonstrate that action-value methods can compete with policy gradient (PG) approaches in continuous, high-dimensional action spaces—a domain where PG methods are conventionally considered dominant. The DeepMind Control Suite (DMC) serves as a standard benchmark for such tasks, encompassing complexities like:

• Combinatorial action spaces: Tasks range from single-dimensional actions to high-dimensional ones (e.g. 38 action dimensions in the Dog task).

• Continuous action spaces: These domains are where PG methods are typically favored, making DMC a representative testbed.

Additionally, our experiments within these domains demonstrate QMLE's flexibility in handling a fusion of discrete and continuous action spaces through two approaches:

• Dual Predictors: Utilizing both discrete and continuous argmax predictors simultaneously, allowing the framework to leverage the strengths of each type in different contexts.

• Action Space Growth: Initiating with a discrete action space and progressively expanding it into the original continuous space, effectively implementing a curriculum that enhances learning efficiency and policy refinement (see Figure 12).

While we have not yet tested QMLE in environments beyond DMC, we believe its principles are broadly applicable. We hope this work inspires the community to explore QMLE in more diverse domains and welcome suggestions for environments that could further test its robustness and limitations.

---

Q3: Hyperparameter Selection Guidelines

The hyperparameters of QMLE can be categorized into three groups, as outlined in Table 1 of the paper:

1. DQN. These follow standard practices from DQN and are adapted directly from Seyde et al. (2023) to avoid overfitting QMLE on the benchmark.

2. Prioritized Replay. Similarly, these mirror the same values as used by Seyde et al. (2023).

3. QMLE-specific. These include:

   • Sampling budgets ($m_\text{target}$, $m_\text{greedy}$): Appendix A (lines 935--975) provides guidelines for selecting these values. In general, higher values for $m_\text{greedy}$ improve training interaction quality, while moderate values for $m_\text{target}$ balance computational cost and overestimation risks.

   • Sampling ratios ($\rho_k$): We allocate 90% of the sampling budget to uniform sampling to ensure statistically unbiased approximations and dedicate the remainder to local sampling strategies (e.g. from deterministic delta distributions or other argmax predictors). For non-deterministic predictors, evenly distributing the remaining budget (beyond the uniform-sampling ratio) across ensemble members should be a reasonable choice.

---

Q4: Implementation Challenges

We did not encounter any implementation challenges or unexpected behaviors. Our QMLE implementation is straightforward, built on a simple DQN implementation from CleanRL (Huang et al., 2022). The results presented in the paper are from the initial implementation after correctness validation, underscoring its simplicity and reproducibility.

Once again, we would like to thank the reviewer for their thoughtful feedback. Below we would like to outline the additions which we have incorporated into a revised version.

We have added ablation studies for QMLE in Appendix D.

• Appendix D.1 examines QMLE with and without amortized maximization. Both variants use only 2 action samples for approximate maximization (i.e. sampling budgets of $m_\textrm{target} = m_\textrm{greedy} = 2$). The ablated variant relies solely on uniform sampling (i.e. sampling ratio $\rho_\textrm{uniform} = 1$). The standard variant uses only a delta-based argmax predictor, allocating 1 sample to the argmax predictor and 1 to uniform sampling. The results demonstrate that amortized maximization significantly improves performance, particularly as the complexity of the action space increases.

• Appendix D.2 examines performance under sampling budgets 2 (minimal number of samples needed to allow 1 sample from the learned argmax predictor and 1 from the uniform distribution) and 1000. The results show that, as expected the performance mildly improves due to more accurate approximation of the argmax for the case with sampling budgets of 1000. However, the difference is minimal owing to amortization, which effectively dampens the negative impact of undersampling by enabling reuse of past computations over time. This shows robustness of QMLE wrt. large variations in the sampling budgets.

• Appendix D.3 compares the performance of a discrete-only variant of QMLE (using a learned argmax predictor based on a factored categorical distribution) against DQN (which is a variant of QMLE with the action-in architecture ablated, and in turn obviating the need for amortization and approximate maximization). The results here illustrate the benefits of action-in architectures in regards sample-efficiency and generalization over actions (as demonstrated in the lower-dimensional action domains) and computational scalability (as seen in the higher-dimensional action problems, where DQN entirely fails with memory errors).

---

We hope that these newly added results help shed light regarding your question around sensitivity of the QMLE approach to hyperparameters. Overall, we hope that our responses to your questions / concerns and the added experiments help further clarify our contributions and merit a reconsideration of your evaluation.

Dear Reviewer uFAB,

We want to express our sincere gratitude for your thorough and insightful feedback on our work, "Learning in complex action spaces without policy gradients." We understand that reviewing service is a significant commitment and a time-consuming task. We truly appreciate the attention to detail and the thoughtful consideration you have given to our work. We have carefully considered your concerns and provided detailed responses to the points you raised. We hope that our explanations address your questions and improve the understanding of our work.

The open discussion phase is a distinctive and highly valued aspect of the ICLR experience. We are eager to continue benefiting from this collaborative process. If you have the opportunity, we would greatly appreciate any final feedback or thoughts you might have on our revisions and in light of our responses.

Thank you again for your time and consideration of our work.

Best regards,

The Authors