Counterintuitive RL: The Hidden Value of Acting Bad

Authors: Ezgi Korkmaz
Primary area: reinforcement learning
Keywords: Counterintuitive, reinforcement learning

Abstract:
Learning to make sequential decisions solely from interacting with an environment without any supervision has been achieved by the initial installation of deep neural networks as function approximators to represent and learn a value function in high-dimensional MDPs. Reinforcement learning policies face exponentially growing state spaces in experience collection in high dimensional MDPs resulting in a dichotomy between computational complexity and policy success. In our paper we focus on the agent’s interaction with the environment in a high-dimensional MDP during the learning phase and we introduce a theoretically-founded novel method based on experiences obtained through extremum actions. Our analysis and method provides a theoretical basis for effective, accelerated and efficient experience collection, and further comes with zero additional computational cost while leading to significant acceleration of training in deep reinforcement learning. We conduct extensive experiments in the Arcade Learning Environment with high-dimensional state representation MDPs. We demonstrate that our technique improves the human normalized median scores of Arcade Learning Environment by 248% in the low-data regime.

Decision: reject
Reviewer scores: 6, 5, 3, 3

Reviews and discussion:
<thread>
creation date:
1730299589105

thread_type:
official_review

<thread_object>
creator: reviewer_qwcj

<content>
summary:
The authors propose MaxMin TD Learning, an algorithm that alternates between optimistic and pessimistic strategies for action sampling and Q-estimation updates. This approach addresses sample inefficiency in deep reinforcement learning (RL), though the method offers only incremental novelty. The authors provide both theoretical and empirical analysis, evaluating their method on the popular Atari benchmark.

strengths:
The authors tested their approach using both DDQN and a more recent approach that represents the possible returns as distribution (QRDQN), which shows the flexibility of applying MaxMin TD Learning over a variety of different algorithms. Moreover, the tested environment is the well-known Atari benchmark, offering tasks with various characteristics. The paper is relatively easy to follow.

weaknesses:
* *Marginal novelty*: The proposed method introduces limited novelty since exploring different selection criteria based on Q-estimations has been previously explored with ensembles [1, 2]. Additionally, similar work addressing the optimistic/pessimistic policy update trade-off exists using a more task-dependent strategy [3]. A Related Works section would help clarify where the proposed method advances existing literature. Furthermore, count-based exploration strategies should be referenced in the Background section for completeness.

* *Evaluation in high-dimensional MDPs*: The evaluation lacks depth, particularly concerning high-dimensional MDPs. MaxMin TD Learning is designed to enhance sample efficiency via exploration, yet it is compared against a standard $\epsilon$-greedy strategy, which performs well given a larger interaction budget and appropriately tuned decay factors. Limiting the interaction budget significantly impacts $\epsilon$ decay and policy performance, and it appears that the decay factor used here converges too rapidly to its minimum (see Q1). I would recommend including experiments with varying $\epsilon$ values, especially in the 200-million-frame setting. Additionally, while the 100k benchmark used the NoisyNetworks exploration strategy, it was absent in the 200-million-frame experiments.

* *Fair comparison*:  A more balanced comparison would be to benchmark MaxMin TD Learning against alternative approaches designed to enhance sample efficiency as seen in [4, 5]. The authors could emphasize the benefit of MaxMin TD Learning, such as enabling effective learning without requiring prior logged data or a guide policy, which could potentially lead to distribution shifts.

**General remarks**

- In the phrase “Thus, in high-dimensional complex MDPs…”, the citation of Kakade (2003) seems out of place, as deep reinforcement learning was developed later.

- The second question raised saying that the goal is to achieve a *zero cost* experience collection seems infeasible in the context of exploration since interactions with the environment have an inherently associated cost. I think the authors suggest *zero additional cost*

- I suggest having a single Reference section.

**References**

[1] Lan, Qingfeng, et al. "Maxmin q-learning: Controlling the estimation bias of q-learning." arXiv preprint arXiv:2002.06487 (2020).

[2] Agarwal, Rishabh, Dale Schuurmans, and Mohammad Norouzi. "An optimistic perspective on offline reinforcement learning." International conference on machine learning. PMLR, 2020.

[3] Moskovitz, Ted, et al. "Tactical optimism and pessimism for deep reinforcement learning." Advances in Neural Information Processing Systems 34 (2021): 12849-12863.

[4] Yao, Yao, et al. "Sample efficient reinforcement learning via model-ensemble exploration and exploitation." 2021 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2021.

[5] Uchendu, Ikechukwu, et al. "Jump-start reinforcement learning." International Conference on Machine Learning. PMLR, 2023.

questions:
Q1: Could the authors clarify the decay rate for the hyperparameter $\textit{Exploration epsilon decay frame fraction}$? It seems that $\epsilon$ decreases every 0.8% of the total interaction budget. How was this value selected?

Q2: Could you provide more details on how NoisyNetworks was implemented in the experiments? Clarifying architecture choices and how this was selected would be useful, as it apparently allows for a range of configurations.

Q3: In Figure 1, constant 2 appears to balance exploration and exploitation in the UCB algorithm. Has this constant been optimized for the problem, and if so, could the results for varying values be shown? I'd like to see results for values such as [0.5, 1, 2, 3] as done for the epsilon value.

Q4: Could the authors clarify the intended interpretation of Figure 4 for the reader? What is exactly the meaning of TD error being stable or suffering from a drop during environment interactions? What are "high" negative or positive values in this case?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730494206166

thread_type:
official_review

<thread_object>
creator: reviewer_o2wg

<content>
summary:
This paper argues for an alternative exploration strategy to $\epsilon$-greedy for deep/approximate value-based RL methods (mostly those founded on Q-learning) in which instead of sampling uniformly at random with probability $\epsilon$, their approach samples actions based on $min_a Q(s, a)$. Algorithmically, the TD update rule of the basis algorithm remains intact. The authors argue that experiences generated by this method of acting have meaningful implications during experience replay/consolidation by TD methods (in particular, deep Q-learning family of algorithms). As such, the authors frame their proposal as a TD approach, in what they call MaxMin TD learning.

They examine the learning performance on a few tasks of the Atari suite (200M frames), full set of the Atari 100K benchmark, and an illustrative Chain MDP task. The key Atari results are based on the combination of their MaxMin TD learning with QRDQN (a distributional RL algorithm) in comparison with QRDQN with $\epsilon$-greedy, where MaxMin TD variant achieves higher AUC on both the Median and 80th Percentile aggregate measures.

strengths:
**Interesting problem scenario:**
Considering exploration strategies that are directly useful for structural/temporal credit assignment is an interesting area to focus on in approximate/deep RL.

**Analysis tools around acting uniformly vs. Q-minimizing actions after parameter initialization:**
I found the approach of the propositions to analyze the impact of acting uniformly vs. taking the Q-minimizing action on the TD error to be interesting.

**Experimental testbeds:** 
The choice of testbeds, ranging from a toy MDP problem to 100K and 200M Atari benchmarks is reasonable. 

**Evaluation metrics:**
Reporting Median and 80% aggregate measures, using 5 seeds per each method in Atari for DQN-based methods, and reporting standard error of the mean return are all reasonable choices. However, statistical measures introduced by Agrawal et al. (2021) [arXiv:2108.13264] would have been a step up.

weaknesses:
- **Framing the approach as a TD method, as opposed to an exploration strategy:**
Framing of the approach as a TD algorithm is not justifiable. A strategic exploration approach could facilitate credit assignment, but categorizing them as a TD approach is rarely ever useful in my view. The proposed method only touches experience generation and not experience consolidation and in this way, I see it as best described as a behavior/exploration strategy. Also, the baselines in question are Noisy Nets and $\epsilon$-greedy, which are both known as exploration/behavior strategies.

- **Propositions and proofs do not deliver** a full picture of what's going on, unlike the claims for theoretical foundations on par with those existing in tabular settings. 

- The approach of only choosing actions from $max Q$ and $min Q$ can easily be shown to introduce bias in a simple counterexample. Say in a multiarmed bandit, action *a* is initialized to the minimal value at random (wrt. to the other initialized actions' values) but as it happens it's *true* Q value is lower than the initialized value. Let's assume also that action *b* is initialized to the maximal value at random (wrt. to the other initialized actions' values) and its corresponding *true* action value is higher than all other initialized actions' values. Note that, even if we use functional approximation (e.g. a neural network) to solve this problem, with parameters shared between the Q estimators for the various actions, it can easily end up being the case that no other actions are experienced during the course of training interactions. This would hold even despite the fact that neither of actions *a* and *b* would be the Q-minimizing or the Q-maximizing actions, respectively, wrt. the *true* Q function.

- Consider the example above again: The TD error reaches zero/near-zero for the Q-minimizing and Q-maximizing actions after a few updates (where Q is the current estimator and not the true Q-function). However, all other actions will have a much higher TD error since no updates is performed on them. This effectively shows that while the results of the Propositions in the paper could hold probabilistically assuming uniform initialization of the outputs of the Q-estimator network, they do not hold on a case by case setting nor do would they hold after several updates (after the uniformity of the outputs is no longer the case).
 
- Results on Atari 100K are significant, but not on Atari 200M experiments (especially given the fact that the plots for the latter are truncated earlier than 200M frames; e.g. StarGunner is truncated at 70M frames). This likely has ties to my argument above. MaxMin TD could help at the beginning of training (assuming settings like my counterexample occur less commonly in practice / in these tasks), but would not be able to reach higher final performances after enough training of a good baseline on the task. 

- I think any benefit emerging from MaxMin TD could have ties to epistemic uncertainty minimization. I think discussions, detailed analysis, and comparisons with approaches directly purposed to do so (incl. bootstrapped DQN of Osband et al., 2016) would have been beneficial.

questions:
1. Section 5 suggests that experiments were also done with Double DQN (with PER), however all I could find were learning curves for QRDQN, and Table 1 with results for DDQN. Generally, figuring out what results are based on which basis algorithm was challenging as I had to go back to the text several times without success. Could you please clarify what basis agent/algorithm each plot/table is based on. E.g. Figure 3's caption says "MaxMin TD Learning and canonical temporal difference learning in [ALE]...". The canonical TD learning method actually implies more of the TD($\lambda$) class of methods for prediction than a deep RL method such as DDQN or QRDQN. So please specify.

2. Why are the curves for Atari 200M truncated in some cases? (Could be beneficial to add the performance curves for the full length of the experiments.)

3. What was the reasoning behind choosing the specific subset of games for the Atari 200M experiments. 

4. Can you comment on the counterexample that I've mentioned in the "Weaknesses" section? What is your view on it? (Perhaps experimenting with such a setting would be useful.)

Minor suggestions:
- Line 87: "MDP [...] contains continuous set of states"; I believe this intro is incorrect and also not applicable to the setting of this paper. In Atari and Chain MDP, states are in fact discrete. In Atari, pixel values are discrete, yielding a discrete combinatorial set of states.

- Line 89: The definition corresponds to the *expected* reward function. 

- Line 90: The PMF-based definition of the policy does not hold fully for the continuous-state definition of the MDP. But this will be fine if Line 87 is changed to discrete set of states. 

- Line 102: I believe the second expectation is mis-specified and in fact is not needed. 

- Line 108: "In deep reinforcement learning, the state space or the action space is large enough that it is not possible to learn and
store the state-action values in a tabular form."; state-action spaces being large is not a property of DRL. I think better phrasing would be in this line: domains often tackled with DRL tend to have large state and/or action spaces.

-  Definition 3.3 seems to be formalized such that $\theta$ is a random variable of the expectation, but the wording seems to imply that $Q_\theta$ is a given.

- Would be good to have a visualization of the Chain MDP for ease of readability. Also, what was the number of states $N$?

- Number of environment interactions are not equal to the number of frames in Atari 2600 tasks, because of frame skipping of > 1 used. As such, the X axis labels should change to number of frames.

- The proposed approach is only compatible with discrete-action Q-based methods. That is to say, methods like DDPG cannot utilize it. I think it would be good to mention this somewhere.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730692299117

thread_type:
official_review

<thread_object>
creator: reviewer_bh4h

<content>
summary:
The authors present a new algorithm which explores by choosing the worst action as estimated by the neural q function. They demonstrate the efficacy of this in low data regimes for double DWN and compare it to vanilla epsilon greedy based double DQN.

strengths:
The paper provides a good set of experimental results in the low data regime. The method requires fairly simple changes to existing algorithms and it tends to improve performance while being so. The paper is largely well written and I was able to follow along easily.

weaknesses:
I see a few important issues that need addressing before I can raise my score.

In **Proposition 3.4 and 3.6** you start with statements for state $s_t$, which is random variable corresponding to state at time $t$ but in the inequality on the RHS you somehow have $\mathcal D(s)$ for a fixed state $s$. I am unclear as to where this $s$ is coming from. Moreover, I believe this would significantly complicate the proofs because you will have to account for the time step or "loosen" the lower bound because you will have to take some kind of infimum.

While I am able to follow intuitively why you would benefit from taking the value minimizing action, I believe you should also include a **comment on the estimated regret** for this choice. It might be beneficial for a randomly initialized $Q$-function in a game setting but we must consider cases where large negative rewards are "harmful" to the agent. This is one of the reasons why minimizing regret is important to both theoreticians and practitioners.

In the experimental section I would be interested to see **comparison with two other papers**: "Exploration with random network distillation" and "Flipping Coins to Estimate Pseudocounts for Exploration in Reinforcement Learning". Former is based on quantifying how novel a data point is and the latter is directly related to optimistically choosing an action based on pseudo counts. You refer to the inability of doing count based exploration (as done in tabular setting) in your paper but these works are doing some form of counts based exploration. For reference, in lines 126-128 you write
>> incorporating these count-based methods in high-dimensional state representation MDPs requires substantial complexity including training additional deep neural networks to estimate counts or other uncertainty metrics

I would expect some comparison to how much better these more complex methods are.

questions:
I see the following minor issues and make some auggestions:

Line 50: I wouldn't call $\epsilon$-greedy "naive and standard technique"

Line 96: comma at the end, not a full stop

Line 113: I believe you could use different subscript for $\theta$ to differentiate the gradient step from the environment time step.

Line 123: full stop at the end of eqn

Line 124: "a family of algorithms have been proposed based on counting state visitations" what are these algorithms? I would strongly recommend citing "R-max – A General Polynomial Time Algorithm for Near-Optimal Reinforcement Learning" and "Reinforcement Learning in Finite MDPs: PAC Analysis" here.

Line 155: Why is there an $s' \sim \mathcal T(s, \hat{a})$ in the first expectation? I don't see any dependence on $s'$ in the term inside the bracket. Same question for later versions of smoothness too.

Proof of Proposition 3.4: could you expand on the second inequality please?

Line 264: I am unclear on what is the "information gained" here? Is it in an information theoretic sense or in terms of optimizaing the loss?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730712391792

thread_type:
official_review

<thread_object>
creator: reviewer_eipg

<content>
summary:
This work considers the problem of experience collection through behavior policy in RL. They argue the benefit of leveraging extremum actions to learn optimal policy and outlined an algorithm that collects and uses such samples. They theoretically show that how actions with minimum value could be helpful. Experimental validation of the approach has been conducted using the Atari game environment.

strengths:
1. In my view, the main strength of this work lies in the presented theoretical assessment. It shows that the minimum-action value leads to higher temporal difference (TD) than random actions and the difference in the TD is equal to the disadvantage gap. Such finding reveals the underlying importance of the bad actions that may help in accelerate the learning which if often ignored. 

2. This work nicely formalizes and defines the relevant concepts, and then gradually presents the core propositions. I have found the paper easy to follow. Also, the detailing of the propositions for both single and double Q-learning is helpful for the reader.

weaknesses:
1. While the paper presents several experimental results on ALE, it lacks experiments across different benchmarks. It needs rigorous validation to uphold the claim. I would suggest adding more experiments on other benchmarks that are specially designed to assess exploration such as MiniGrid [1], Crafter [2].

2. Comparison with more recent and effective exploration techniques is missing. It would be interesting to see comparisons with Random Network Distillation [3] or curiosity-driven approaches [4] (which may require some adaptation).

3. Some part of the writing needs improvement. For example, 
    - add more technical clarity such as in lines 291-292, please elaborate on what you intend to mean by "solely due to the experience collection". 
    - minor grammatical issues such as "a fundamental theoretically well-motivated" -> "a fundamental and theoretically well-motivated" OR "a fundamental, theoretically well-motivated". 
    - it is very hard to identify how Figures 2 and 5 differ. It would be helpful to the reader if you would add key information (the underlying architecture in this case) in the caption.

[1] Chevalier-Boisvert, Maxime, et al. "Minigrid & miniworld: Modular & customizable reinforcement learning environments for goal-oriented tasks." Advances in Neural Information Processing Systems 36 (2024).

[2] Hafner, Danijar. "Benchmarking the Spectrum of Agent Capabilities." International Conference on Learning Representations (2022).

[3] Yuri Burda, Harrison Edwards, Amos Storkey, Oleg Klimov. "Exploration by random network distillation", International Conference on Learning Representations (2019).

[4] Pathak, Deepak, et al. "Curiosity-driven exploration by self-supervised prediction." International Conference on Machine Learning (2017).

questions:
1. It has been mentioned that "minimizing the state-action value function in early training ...". Does the algorithm considers actions with minimum value "only" in early training and does the value of $\epsilon$ in Algorithm 1 gradually reaches to zero? What is $e$ in algorithm 1?

2. Is there any motivating factor to cluster the games in figure 4 or is it just because of the value range?
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces a counterintuitive notion that instead of exploring uniformly randomly, exploring with minimum-value action helps enlarge the temporal difference error and hence benefits learning. Justification in terms of theory is given. The approach can be well formulated in terms of max-min optimization. One issue I find is that following the minimum-value action might be quite harmful in some cases.

The learning part of the pseudocode in Algorithm 1 is confusing. I believe the updates are made simply based on the drawn samples. The statement “TD receives update with probability ϵ:” serves as an explanation of what’s happening instead of an if-else mechanism that needs to be implemented, an impression of which is created by this block of statement and it may confuse readers. This explanation should be moved out of the pseudocode.

The implication of their results in the asymptotic sense and comparison to a range of baseline exploration strategies and benchmark tasks would make the algorithm much stronger and acceptable in the next submission.