CONQUR: MITIGATING DELUSIONAL BIAS IN DEEP Q-LEARNING
Year: 2019

Abstract:
Delusional bias is a fundamental source of error in approximate Q-learning. To date, the only techniques that explicitly address delusion require comprehensive search using tabular value estimates. In this paper, we develop efficient methods to mitigate delusional bias by training Q-approximators with labels that are “consistent” with the underlying greedy policy class. We introduce a simple penalization scheme that encourages Q-labels used across training batches to remain (jointly) consistent with the expressible policy class. We also propose a search framework that allows multiple Q-approximators to be generated and tracked, thus mitigating the effect of premature (implicit) policy commitments. Experimental results demonstrate that these methods can improve the performance of Q-learning in a variety of Atari games, sometimes dramatically.

heading: 1 INTRODUCTION
text: Q-learning (Watkins & Dayan, 1992; Sutton & Barto, 2018) lies at the heart of many of the recent successes of deep reinforcement learning (RL) (Mnih et al., 2015; Silver et al., 2016), with recent advancements (e.g., van Hasselt (2010); Bellemare et al. (2017); Wang et al. (2016); Hessel et al. (2017)) helping to make it among the most widely used methods in applied RL. Despite these successes, many properties of Q-learning are poorly understood, and it is challenging to successfully apply deep Q-learning in practice. When combined with function approximation, Q-learning can become unstable (Baird, 1995; Boyan & Moore, 1995; Tsitsiklis & Roy, 1996; Sutton & Barto, 2018). Various modifications have been proposed to improve convergence or approximation error (Gordon, 1995; 1999; Szepesvári & Smart, 2004; Melo & Ribeiro, 2007; Maei et al., 2010; Munos et al., 2016); but it remains difficult to reliably attain both robustness and scalability.
Recently, Lu et al. (2018) identified a source of error in Q-learning with function approximation known as delusional bias. It arises because Q-learning updates the value of state-action pairs using estimates of (sampled) successor-state values that can be mutually inconsistent given the policy class induced by the approximator. This can result in unbounded approximation error, divergence, policy cycling, and other undesirable behavior. To handle delusion, the authors propose a policy-consistent backup operator that maintains multiple Q-value estimates organized into information sets. Each information set has its own backed-up Q-values and corresponding “policy commitments” responsible for inducing these values. Systematic management of these sets ensures that only consistent choices of maximizing actions are used to update Q-values. All potential solutions are tracked to prevent premature convergence on any specific policy commitments. Unfortunately, the proposed algorithms use tabular representations of Q-functions, so while this establishes foundations for delusional bias, the function approximator is used neither for generalization nor to manage the size of the state/action space. Consequently, this approach is not scalable to RL problems of practical size.
In this work, we propose CONQUR (CONsistent Q-Update Regression), a general framework for integrating policy-consistent backups with regression-based function approximation for Q-learning and for managing the search through the space of possible regressors (i.e., information sets). With suitable search heuristics, our framework provides a computationally effective means for minimizing the effects of delusional bias in Q-learning, while admitting scaling to practical problems.
Our main contributions are as follows. First we define novel augmentations of standard Q-regression to increase the degree of policy consistency across training batches. While testing exact consistency
is expensive, we introduce an efficient soft-consistency penalty that promotes consistency of new labels with earlier policy commitments. Second, drawing on the information-set structure of Lu et al. (2018), we define a search space over Q-regressors to allow consideration of multiple sets of policy commitments. Third, we introduce heuristics for guiding the search over regressors, which is critical given the combinatorial nature of information sets. Finally, we provide experimental results on the Atari suite (Bellemare et al., 2013) demonstrating that CONQUR can offer (sometimes dramatic) improvements over Q-learning. We also show that (easy-to-implement) consistency penalization on its own (i.e., without search) can improve over both standard and double Q-learning.

heading: 2 BACKGROUND
text: We assume a discounted, infinite horizon Markov decision process (MDP), M = (S, A, P, p0, R, γ). The state space S can reflect both discrete and continuous features, but we take the action space A to be finite (and practically enumerable). We consider Q-learning with a function approximator Qθ to learn an (approximately) optimal Q-function (Watkins, 1989; Sutton & Barto, 2018), drawn from some approximation class parameterized by Θ (e.g., the weights of a neural network). When the approximator is a deep network, we generically refer to the algorithm as DQN, the method at the heart of many recent RL successes (Mnih et al., 2015; Silver et al., 2016).
For online Q-learning, at a transition s, a, r, s′, the Q-update is given by: θ ← θ + α ( r + γmax
a′∈A Qθ(s
′, a′)−Qθ(s, a) ) ∇θQθ(s, a). (1)
Batch versions of Q-learning, including DQN, are similar, but fit a regressor repeatedly to batches of training examples (Ernst et al., 2005; Riedmiller, 2005). Batch methods are usually more data efficient and stable than online Q-learning. Abstractly, batch Q-learning works through a sequence of (possibly randomized) data batches D1, · · ·DT to produce a sequence of regressors Qθ1 , . . . , QθT = Qθ, estimating the Q-function.1 For each (s, a, r, s′) ∈ Dk, we use a prior estimator Qθk−1 to bootstrap the Q-label q = r + γmaxa′ Qθk−1(s
′, a′). We then fit Qθk to this training data using a suitable regression procedure with an appropriate loss function. Once trained, the (implicit) induced policy πθ is the greedy policy w.r.t. Qθ, i.e., πθ(s) = arg maxa∈AQθ(s, a). Let F(Θ), resp. G(Θ), be the corresponding class of expressible Q-functions, resp. greedy policies.
Intuitively, delusional bias occurs whenever a backed-up value estimate is derived from action choices that are not (jointly) realizable in G(Θ) (Lu et al., 2018). Standard Q-updates back up values for each (s, a) pair by independently choosing maximizing actions at the corresponding next states s′. However, such updates may be “inconsistent” under approximation: if no policy in G(Θ) can jointly express all past action choices, backed up values may not be realizable by any expressible policy. Lu et al. (2018) show that delusion can manifest itself with several undesirable consequences. Most critically, it can prevent Q-learning from learning the optimal representable policy in G(Θ); it can also cause divergence. To address this, they propose a non-delusional policy consistent Q-learning (PCQL) algorithm that provably eliminates delusion. We refer to the original paper for details, but review the main concepts we need to consider below.
The first key concept is that of policy consistency. For any S ⊆ S , an action assignment σS : S → A associates an action σ(s) with each s ∈ S. We say σ is policy consistent if there is a greedy policy π ∈ G(Θ) s.t. π(s) = σ(s) for all s ∈ S. We sometimes equate a set SA of state-action pairs with an implied assignment π(s) = a for all (s, a) ∈ SA. If SA contains multiple pairs with the same state s, but different actions a, it is a multi-assignment (though we loosely use the term “assignment” in both cases when there is no risk of confusion).
In (batch) Q-learning, each successive regressor uses training labels generated by assuming maximizing actions (under the prior regressor) are taken at its successor states. Let σk reflect the collection of states and corresponding maximizing actions taken to generate labels for regressor Qθk (assume it is policy consistent). Suppose we train Qθk by bootstrapping on Qθk−1 and consider a training sample (s, a, r, s′). Q-learning generates label r + γmaxa′ Qθk−1(s ′, a′) for input (s, a). Notice,
1We describe our approach using a straightforward form of batch Q-learning, but it can accommodate many variants, e.g., where the regressor used for bootstrapping is some earlier Q-estimator, or the estimators generating the max-actions and the value estimates are different as in double Q-learning (van Hasselt, 2010; Hasselt et al., 2016); indeed, we experiment with such variants.
however, that taking action a∗ = argmaxa′ Qθk(s ′, a′) at s′ may not be policy consistent with σk. Thus Q-learning will estimate a value for (s, a) assuming the execution of a policy that cannot be realized given the limitations of the approximator. The PCQL algorithm (Lu et al., 2018) prevents this by insisting that any action assignment σ used to generate bootstrapped labels is consistent with earlier assignments. Notice that this means Q-labels will often not be generated using maximizing actions relative to the prior regressor.
The second key concept is that of information sets. One will generally not be able to use maximizing actions to generate labels, so tradeoffs can be made when deciding which actions to assign to different states. Indeed, even if it is feasible to assign a maximizing action a to state s early in training, say at batch k, since it may prevent assigning a maximizing a′ to s′ later, say batch k + `, we may want to consider a different assignment to s to give more flexibility to maximize at other states later. PCQL doesn’t try to anticipate the tradeoffs—rather it maintains multiple information sets, each corresponding to a different assignment to the states seen in the training data so far. Each gives rise to a different Q-function estimate, resulting in multiple hypotheses. At the end of training, the best hypothesis is the one maximizing expected value w.r.t. an initial state distribution.
PCQL provides strong convergence guarantees, but it is a tabular algorithm: the function approximator retricts the policy class, but is not used to generalize Q-values. Furthermore, its theoretical guarantees come at a cost: it uses exact policy consistency tests—tractable for linear approximators, but not practical for large problems; and it maintains all consistent assignments. As a result, PCQL cannot be used for large RL problems of the type tackled by DQN.

heading: 3 THE CONQUR FRAMEWORK
text: We develop the CONQUR framework to provide a practical approach to reducing delusion in Qlearning, specifically addressing the limitations of PCQL identified above. CONQUR consists of three main components: a practical soft-constraint penalty that promotes policy consistency; a search space to structure the search over multiple regressors (information sets, action assignments); and heuristic search schemes (expansion, scoring) to find good Q-regressors.

heading: 3.1 PRELIMINARIES
text: We assume a set of training data consisting of quadruples (s, a, r, s′), divided into (possibly nondisjoint) batches D1, . . . DT for training. This perspective is quite general: online RL corresponds to |Di| = 1; off-line batch training (with sufficiently exploratory data) corresponds to a single batch (i.e., T = 1); and online or batch methods with replay are realized when the Di are generated by sampling some data source with replacement.
For any data batch D, let χ(D) = {s′ : (s, a, r, s′) ∈ D} denote the collection of successor states of D. An action assignment σD for D is an assignment (or multi-assignment) from χ(D) to A: this dictates which action σD(s′) is considered “maximum” for the purpose of generating a Q-label for pair (s, a); i.e., (s, a) will be assigned training label r + γQ(s′, σ(s′)) rather than r + γmaxa′∈AQ(s
′, a′). The set of all such assignments is Σ(D) = Aχ(D); note that it grows exponentially with |D|. Given Q-function parameterization Θ, we say σD is Θ-consistent (w.r.t. D) if there is some θ ∈ Θ s.t. πθ(s′) = σ(s′) for all s′ ∈ χ(D).2 This is simple policy consistency, but with notation that emphasizes the policy class. Let ΣΘ(D) denote the set of all Θ-consistent assignments over D. The union σ1 ∪ σ2 of two assignments (over D1, D2, resp.) is defined in the usual way.

heading: 3.2 CONSISTENCY PENALIZATION
text: Enforcing strict Θ-consistency as regressors θ1, θ2, . . . , θT are generated is computationally challenging. Suppose assignments σ1, . . . , σk−1, used to generate labels for D1, . . . Dk−1, are jointly Θ-consistent (let σ≤k−1 denote their multi-set union). Maintaining Θ-consistency when generating θk imposes two requirements. First, one must generate an assignment σk over Dk s.t. σ≤k−1 ∪ σk is consistent. Even testing assignment consistency can be problematic: for linear approximators this is a
2We suppress mention of D when clear from context or implied by the assignment under consideration.
linear feasibility program (Lu et al., 2018) whose constraint set grows linearly with |D1 ∪ . . . ∪Dk|. For DNNs, this is a complex, and much more expensive, polynomial program. Second, the regressor θk should itself be consistent with σ≤k−1 ∪ σk. Again, this imposes a significant constraint on the regression optimization: in the linear case, this becomes a constrained least-squares problem (solvable, e.g., as a quadratic program); while with DNNs, it could be solved, say, using a much more complicated projected SGD. However, the sheer number of constraints makes this impractical.
Rather than enforcing consistency, we propose a simple, computationally tractable scheme that “encourages” it: a penalty term that can be incorporated into the regression itself. Specifically, we add a penalty function to the usual squared loss to encourage updates of the Q-regressors to be consistent with the underlying information set, i.e., the prior action assignments used to generate its labels.
When constructing θk, let D≤k = ∪{Dj : j ≤ k}, and σ ∈ ΣΘ(D≤k) be the collective (possibly multi-) assignment used to generate labels for all prior regressors (including θk itself). The multiset of pairs B = {(s′, σ(s′))|s′ ∈ χ(D≤k)}, is called a consistency buffer. The collective assignment need not be consistent (as we elaborate below), nor does the regressor θk need to be consistent with σ. Instead, we incorporate the following soft consistency penalty when constructing θk:
Cθ(s ′, a) = ∑ a′∈A [Qθ(s ′, a′)−Qθ(s′, a)]+ Cθ(B) = ∑ (s′,σ(s′))∈B Cθ(s ′, σ(s′)),
where [x]+ = max(0, x). This penalizes Q-values of actions at state s that are larger than that of action σ(s). We note that σ is Θ-consistent if and only if minθ∈Θ Cθ(B) = 0. We incorporate this penalty into our regression loss for batch Dk:
Lθ(Dk, B) = ∑
(s,a,r,s′)∈Dk
[r + γQθk−1(s ′, σ(s′))−Qθ(s, a)]2 + λCθ(B). (2)
Here Qθk is prior estimator on which labels are bootstrapped (other prior regressors may be used). The penalty effectively acts as a “regularizer” on the squared Bellman error, where λ controls the degree of penalization, allowing a tradeoff between Bellman error and consistency with the action assignment used to generate labels. It thus promotes consistency without incurring the expense of testing strict consistency. It is a simple matter to replace the classical Q-learning update (1) with one using a consistency penalty:
θk ← θk−1 +  ∑ (s,a,r,s′)∈Dk α[r + γQθk−1(s ′, σ(s′))−Qθ(s, a)]∇θQθ(s, a)  + αλ∇θCθ(B) ∣∣∣ θ=θk−1 . (3)
This scheme is quite general. First, it is agnostic as to how the prior action assignments are made, which can be the standard maximizing action at each stage w.r.t. the prior regressor like in DQN, Double DQN (DDQN) (Hasselt et al., 2016), or other variants. It can also be used in conjunction with a search through alternate assignments (see below).
Second, the consistency buffer B may be populated in a variety of ways. Including all max-action choices from all past training batches promotes full consistency in an attempt to minimize delusion. However, this may be too constraining since action choices early in training are generally informed by very inaccurate value estimates. Hence, B may be implemented in other ways to focus only on more recent data (e.g., with a sliding recency window, weight decay, or subsampling); and the degree of recency bias may adapt during training (e.g., becoming more inclusive as training proceeds and the Q-function approaches convergence). Reducing the size of B also has various computational benefits. We discuss other practical means of promoting consistency in Sec. 5.
The proposed consistency penalty resembles the temporal-consistency loss of Pohlen et al. (2018), but our aims are very different. Their temporal consistency notion penalizes changes in a next state’s Q-estimate over all actions, whereas we discourage inconsistencies in the greedy policy induced by the Q-estimator, regardless of the actual estimated values.

heading: 3.3 THE SEARCH SPACE
text: Ensuring optimality requires that PCQL track all Θ-consistent assignments. While the set of such assignments is shown to be of polynomial size (Lu et al., 2018), it is still impractical to track this set in realistic problems. As such, in CONQUR we recast information set tracking as a search problem and propose several strategies for managing the search process. We begin by defining the search space and discussing its properties. We discuss search procedures in Sec. 3.4.
As above, assume training data is divided into batches D1, . . . DT and we have some initial Qfunction estimate θ0 (for bootstrapping D1’s labels). The regressor θk for Dk can, in principle, be trained with labels generated by any assignment σ ∈ ΣΘ(Dk) of actions to its successor states χ(Dk), not necessarily maximizing actions w.r.t. θk−1. Each σ gives rise to a different updated Q-estimator θk. There are several restrictions we could place on “reasonable” σ-candidates: (i) σ is Θ-consistent; (ii) σ is jointly Θ-consistent with all σj , for j < k, used to construct the prior regressors on which we bootstrap θk−1; (iii) σ is not dominated by any σ′ ∈ ΣΘ(Dk), where we say σ′ dominates σ if Qθk−1(s
′, σ′(s′)) ≥ Qθk−1(s′, σ(s′)) for all s′ ∈ χ(D), and this inequality is strict for at least one s′. Conditions (i) and (ii) are the strict consistency requirements of PCQL. We will, however, relax these below for reasons discussed in Sec. 3.2. Condition (iii) is inappropriate in general, since we may add additional assignments (e.g., to new data) that render all non-dominated assignments inconsistent, requiring that we revert to some dominated assignment.
This gives us a generic search space for finding policy-consistent, delusion-free Q-function, as illustrated in Fig. 1. Each node nik at depth k in the search tree is associated with a regressor θ i k defining Qθik and action assignment σ i k that justifies the labels used to train θ i k (σ i k can also be viewed as an information set). We assume the root n0 is based on an initial regression θ0, and has an empty action assignment σ0. Nodes at level k of the tree are defined as follows. For each node nik−1 at level k − 1—with regressor θik−1 and Θ-consistent assignment σik−1—we generate a child n j k for each σjk ∈ ΣΘ(Dk) such that σik−1 ∪ σ j k is Θ-consistent. Node n j k’s assignment is σ i k−1 ∪ σ j k, and its regressor θik is trained using the following data set:
{(s, a) 7→ r + γQθik−1(s ′, σjk(s ′)) : (s, a, r, s′) ∈ Dk}.
The entire search space constructed in this fashion to a maximum depth of T . See Appendix B, Algorithm 1 for pseudocode of a simple depth-first recursive specification.
The exponential branching factor in this search tree would appear to make complete search intractable; however, since we only allow Θ-consistent “collective” assignments we can bound the size of the tree—it is polynomial in the VC-dimension of the approximator.
Theorem 1. The number of nodes in the search tree is no more than O(nm · [ ( m 2 ) n]VCDim(G)) where VCDim(·) is the VC-dimension (Vapnik, 1998) of a set of boolean-valued functions, and G is the set of boolean functions defining all feasible greedy policies under Θ:
G = {gθ(s, a, a′) := 1[fθ(s, a)− fθ(s, a′) > 0],∀s, a 6= a′ | θ ∈ Θ}. (4)
A linear approximator with a fixed set of d features induces a policy-indicator function class G with VC-dimension d, making the search tree polynomial in the size of the MDP. Similarly, a fixed ReLU
DNN architecture with W weights and L layers has VC-dimension of size O(WL logW ) again rendering the tree polynomially sized.
Even with this bound, navigating the search space exhaustively is generally impractical. Instead, various search methods can be used to explore the space, with the aim of reaching a “high quality” regressor at some leaf of the tree (i.e., trained using all T data sets/batches). We discuss several key considerations in the next subsection.

heading: 3.4 SEARCH HEURISTICS
text: Even with the bound in Theorem 1, traversing the search space exhaustively is generally impractical. Moreover, as discussed above, enforcing consistency when generating the children of a node, and their regressors, may be intractable. Instead, various search methods can be used to explore the space, with the aim of reaching a “high quality” regressor at some (depth T ) leaf of the tree. We outline three primary considerations in the search process: child generation, node evaluation or scoring, and the search procedure.
Generating children. Given node nik−1, there are, in principle, exponentially many action assignments, or children, ΣΘ(Dk) (though Theorem 1 significantly limits the number of children if we enforce consistency). For this reason, we consider heuristics for generating a small set of children. Three primary factors drive these heuristics.
The first factor is a preference for generating high-value assignments. To accurately reflect the intent of (sampled) Bellman backups, we prefer to assign actions to state s′ ∈ χ(Dk) with larger predicted Q-values over actions with lower values, i.e., a preference for a over a′ if Qθjk−1(s ′, a) > Qθjk−1 (s′, a′). However, since the maximizing assignment may be Θ-inconsistent (in isolation, or jointly with the parent’s information set, or with future assignments), candidate children should merely have higher probability of a high-value assignment. The second factor is the need to ensure diversity in the assignments among the set of children. Policy commitments at stage k constrain the possible assignments at subsequent stages. In many search procedures (e.g., beam search), we avoid backtracking, so we want the policy commitments we make at stage k to offer as much flexibility as possible in later stages. The third is the degree to which we enforce consistency.
There are several ways to generate such high-value assignments. We focus on just one natural technique: sampling action assignments using a Boltzmann distribution. Specifically, let σ denote the assignment (information set) of some node (parent) at level k − 1 in the tree. We can generate an assignment σk for Dk as follows. Assume some permutation s′1, . . . , s ′ |Dk| of χ(Dk). For each s ′ i in turn, we sample ai with probability proportional to e τQθk−1 (s ′ i,ai). This can be done without regard to consistency, in which case we would generally use the consistency penalty when constructing the regressor θk for this child to “encourage” consistency rather than enforce it. If we want strict consistency, we can use rejection sampling without replacement to ensure ai is consistent with σjk−1 ∪ σ≤i−1 (we can also use a subset of σ j k−1 as a less restrictive consistency buffer).
3 The temperature parameter τ controls the degree to which we focus on purely maximizing assignments versus more diverse, random assignments. While stochastic sampling ensures some diversity, this procedure will bias selection of high-value actions to states s′ ∈ χ(Dk) that occur early in the permutation. To ensure sufficient diversity, we use a new random permutation for each child.
Scoring children. Once the children of some expanded node are generated (and, optionally, their regressors constructed), we need some way of evaluating the quality of each child as a means of deciding which new nodes are most promising for expansion. Several techniques can be used. We could use the average Q-label (overall, or weighted using some initial state distribution), Bellman error, or loss incurred by the regressor (including the consistency penalty or other regularizer). However, care must be taken when comparing nodes at different depths of the search tree, since deeper nodes have a greater chance to accrue rewards or costs—simple calibration methods can be used. Alternatively, when a simulator is available, rollouts of the induced greedy policy can be used evaluate the quality of a node/regressor. Notice that using rollouts in this fashion incurs considerable computational expense during training relative to more direct scoring based on properties on the node, regressor, or information set.
3Notice that at least one action for state s′i must be consistent with any previous (consistent) information set.
Search Procedure. Given any particular way of generating/sampling and scoring children, a variety of different search procedures can be applied: best-first search, beam search, local search, etc. all fit very naturally within the CONQUR framework. Moreover, hybrid strategies are possible—one we develop below is a variant of beam search in which we generate multiple children only at certain levels of the tree, then do “deep dives” using consistency-penalized Q-regression at the intervening levels. This reduces the size of the search tree considerably and, when managed properly, adds only a constant-factor (proportional to beam size) slowdown to standard Q-learning methods like DQN.

heading: 3.5 A CONCRETE INSTANTIATION OF THE CONQUR FRAMEWORK
text: We now outline a specific instantiation of the CONQUR framework that can effectively navigate the large search space that arises in practical RL settings. We describe a heuristic, modified beamsearch strategy with backtracking and priority scoring. Pseudocode is provided in Algorithm 2 (see Appendix B); here we simply outline some of the key refinements.
Our search process grows the tree in a breadth-first manner, and alternates between two phases. In an expansion phase, parent nodes are expanded, generating one or more child nodes with action assignments sampled from the Boltzmann distribution. For each child, we create target Q-labels, then optimize the child’s regressor using consistency-penalized Bellman error (Eq. 2) as our loss. We thus forego strict policy consistency, and instead “encourage” consistency in regression. In a dive phase, each parent generates one child, whose action assignment is given by the usual max-actions selected by the parent node’s regressor as in standard Q-learning. No additional diversity is considered in the dive phase, but consistency is promoted using consistency-penalized regression.
From the root, the search begins with an expansion phase to create c children—c is the splitting factor. Each child inherits its parent’s consistency buffer from which we add the new action assignments that were used to generate that child’s Q-labels. To limit the size of the tree, we only track a subset of the children, the frontier nodes, selected using one of several possible scoring functions. We select the top `-nodes for expansion, proceed to a dive phase and iterate.
It is possible to move beyond this “beam-like” approach and consider backtracking strategies that will return to unexpanded nodes at shallower depths of the tree. We consider this below as well.

heading: 3.6 RELATED WORK
text: Other work has considered multiple hypothesis tracking in RL. One particularly direct approach has been to use ensembling, where multiple Q-approximators are updated in parallel (Faußer & Schwenker, 2015; Osband et al., 2016; Anschel et al., 2017) then combined straightforwardly to reduce instability and variance. An alternative approach has been to consider population-based methods inspired by evolutionary search. For example, Conti et al. (2018) combine a novelty-search and quality diversity technique to improve hypothesis diversity and quality in RL. Khadka & Tumer (2018) consider augmenting an off-policy RL method with diversified population information from an evolutionary algorithm. Although these techniques do offer some benefit, they do not systematically target an identified weakness of Q-learning, such as delusion.

heading: 4 EMPIRICAL RESULTS
text: We experiment using the Atari test suite (Bellemare et al., 2013) to assess the performance of CONQUR. We first assess the impact of using the consistency penalty in isolation (without search) as a “regularizer” that promotes consistency with both DQN and DDQN. We then test the modified beam search described in Appendix B to assess the full power of CONQUR.

heading: 4.1 IMPACT OF CONSISTENCY PENALIZATION
text: We first study the effects of introducing the soft-policy consistency in isolation, augmenting both DQN and DDQN with the consistency penalty term. We train our models using an open-source implementation (Guadarrama et al., 2018) of both DQN and DDQN (with the same hyperparameters). We call these modified algorithms DQN(λ) and DDQN(λ), respectively, where λ is the penalty coefficient defined in Eq. 2. Note that λ = 0 recovers the original methods. This is a lightweight
0
1
2
3
4
5
6 1e2 Gravitar
DQN(λ=0) DQN(λ=0.25) DQN(λ=0.50) DQN(λ=1.00) DQN(λ=1.50) DDQN(λ=0) DDQN(λ=0.25) DDQN(λ=0.50) DDQN(λ=1.00) DDQN(λ=1.50)
0.00 0.25 0.50 0.75 1.00 1.25 1e7
0.0
0.5
1.0
1.5
2.0
2.5
3.0 1e3 SpaceInvaders
QN(λ=0)
DQN(λ=0.50) DQN(λ=2.00) DDQN(λ=0) DDQN(λ=0.50) DDQN(λ=2.00)
Fig. 2: Varying penalization λ (no search procedure).
1
2
3
4
1e3 Alien 8 nodes
initial baseline ConQUR( =10) 1 2
3
4
1e3 Alien 16 nodes
initial baseline ConQUR( =10)
0 20 40 60 80 100 iterations
0
1
2
3
4 1e3 Solaris 8 nodes
initial baseline ConQUR( =10)
0 20 40 60 80 100 iterations
0
1
2
3
4 1e3 Solaris 16 nodes
initial baseline ConQUR( =10)
Fig. 3: Effects of increasing the number of nodes.
0
1
2 1e3 Solaris node_id=1
ConQUR baseline
0
1
2 1e3 Solaris node_id=2
ConQUR baseline
0
1
2 1e3 Solaris node_id=3
ConQUR baseline
0
1
2 1e3 Solaris node_id=4
ConQUR baseline
0 20 40 60 80 100 iterations
0
1
2 1e3 Solaris node_id=5
ConQUR baseline
0 20 40 60 80 100 iterations
0
1
2 1e3 Solaris node_id=6
ConQUR baseline
0 20 40 60 80 100 iterations
0
1
2 1e3 Solaris node_id=7
ConQUR baseline
0 20 40 60 80 100 iterations
0
1
2 1e3 Solaris node_id=8
ConQUR baseline
Fig. 5: Training curves of 8 (of 16) sorted nodes.
modification that can be applied readily to any regression-based Q-learning method, and serves to demonstrate the effectiveness of soft-policy consistency penalty. Since we don’t consider search (i.e., don’t track multiple hypotheses), we maintain a small consistency buffer using only the current data batch by sampling from the replay buffer—this prevents getting “trapped” by premature policy constraints. As the action assignment is the maximizing action of some network, σ(s′) can be computed easily for each batch. This results in a simple algorithmic extension that adds only an additional penalty term to the original TD-loss.
We train and evaluate DQN(λ) and DDQN(λ) for λ = {0.25, 0.5, 1, 1.5, 2} on 19 Atari games. In training, λ is initialized to 0 and slowly annealed to the desired value to avoid premature commitment to poor action assignments. Without annealing, the model tends fit to poorly informed action assignments during early phases of training, and thus fails to learn a good model.
The best λ is generally different across games, depending on the nature of the game and the extent of delusional bias. Though a single λ = 0.5 works well across all games tested, Fig. 2 illustrates the effect of increasing λ on two games. In Gravitar, increasing λ generally results in better performance for both DQN and DDQN, whereas in SpaceInvaders, λ = 0.5 gives improvement over both baselines, but performance starts to degrade for λ = 2.
We compare the performance of the algorithms using each λ value separately, as well as using the best λ for each game. Under the best λ, DQN(λ) and DDQN(λ) outperform their “potentially delusional” counterparts on all except 3 and 2 games, respectively. In 9 of these games, each of DQN(λ) and DDQN(λ) beats both baselines. With a constant λ = 0.5, each algorithm still beats their respective baseline in 11 games. These results suggest that consistency penalization (independent of the general CONQUR model) can improve the performance of DQN and DDQN by addressing the delusional bias that is critical to learning a good policy. Moreover, we see that consistency penalization seems to have a different effect on learned Q-values than double Q-learning, which addresses maximization bias. Indeed, consistency penalization, when applied to DQN, can achieve gains that are greater than DDQN (in 15 games). Third, in 9 games DDQN(λ) provides additional performance gains over DQN(λ).
A detailed description of the experiments and further results can be found in Appendix C.

heading: 4.2 CONQUR RESULTS
text: We test the full CONQUR framework using the modified beam search discussed above. Rather than training a full Q-network, for effective testing of its core principles, we leverage pre-trained networks from the Dopamine package Castro et al. (2018).4. These networks have the same architecture as in Mnih et al. (2015) and are trained on 200M frames with sticky actions using DQN. We use CONQUR to retrain only the last (fully connected) layer (implicitly freezing the other layers), which can be viewed as a linear Q-approximator over the features learned by the CNN. We run CONQUR using only 4M addtional frames to train our Q-regressors.5
We consider splitting factors c of 2 and 4; impose a limit on the frontier size of 8 or 16; and an expansion factor of 2 or 4. The dive phase is always of length 9 (i.e., 9 batches of data), giving an expansion phase every 10 iterations. Regressors are trained using the loss in Eq. 2 and the consistency buffer comprises all prior action assignments. (See Appendix D for details, hyperparameter choices and more results.)
We run CONQUR with λ = {1, 10, 100, 1000} and select the best performing policy. We initially test two scoring approaches, policy evaluation using rollouts and scoring using the loss function (Bellman error with consistency penalty). Results comparing the two on a small selection of games are shown in Table 1. While rollouts, not surprisingly, tend to give rise to better-performing policies, consistent-Bellman scoring is competitive. Since the latter much less computationally intense, and does not require sampling the environment, we use it throughout our remaining experiments.
We compare CONQUR with the value of the pre-trained DQN. We also evaluate a “multi-DQN” baseline that applies multiple versions of DQN independently, warm-starting from the same pretrained DQN. It uses the same number of frontier nodes as CONQUR, and is otherwise trained identically as CONQUR but with direct Bellman error (no consistency penalty). This gives DQN the same advantage of multiple-hypothesis tracking as CONQUR but without policy consistency.
We test on 59 games, comparing CONQUR with frontier size 16 and expansion factor 4 and splitting factor 4 (16-4-4) with backtracking (as described in the Appendix D) resulted in significant improvements to the pre-trained DQN, with an average score improvement of 125% (excluding games with non-positive pre-trained score). The only games without improvement are Montezuma’s Revenge, Tennis, PrivateEye and BankHeist. This demonstrates that, even when simply retraining the last layer of a highly tuned DQN network, removing delusional bias has the potential to offer strong improvements in policy performance. It is able exploit the reduced parameterization to obtain these gains with only 4M frames of training data. Roughly, a half-dozen games have outsized score improvements, including Solaris (11 times greater value), Tutankham (6.5 times) and WizardOfWor (5 times).6
Compared to the stronger multi-DQN baseline (with 16 nodes), CONQUR wins by at least a 10% margin in 20 games, while 22 games see improvements of 1–10% and 8 games show little effect
4See https://github.com/google/dopamine 5This approach is simply to reduce the computational and memory footprint of our experiments. The
framework is not limited to this approach. 6This may be in part, but not fully, due to the sticky-action training of the pre-trained model.
(plus/minus 1%) and 7 games show a decline of greater than 1% (most are 1–6% with the exception of Centipede at -12% and IceHockey at -86%). Results are similar when comparing CONQUR and multi-DQN each with 8 nodes (8-2-2): 9 games exhibit 10%+ improvement, 21 games show 1–8% improvement, 12 games perform comparably and 7 games do worse under CONQUR. A table of complete results appears in Appendix D.3, Table 4, and training curves (all games, all λ) in Fig. 11.
Increasing the number of nodes from 8 to 16 generally leads to better performance for CONQUR, with 38 games achieving strictly higher scores with 16 nodes (16-4-4): 16 games with 10%+ improvement, 5 games tied and the remaining 16 games performing worse (only a few with a 5%+ decline). Fig. 3 shows the (smoothed) effect of increasing the number of nodes for a fixed λ = 10. The y-axis represents the rollout value of the best frontier node (i.e., the greedy policy of its Q-regressor) as a function of the training iteration. For both Alien and Solaris, the multi-DQN (baseline) training curve is similar with both 8 and 16 nodes, but CONQUR improves Alien from 3k to 4.3k while Solaris improves from 2.2k to 3.5k.
Fig. 4 and Fig. 5 (smoothed, best frontier node) shows node policy values and training curves, respectively, for Solaris. When considering nodes ranked by their policy value, comparing nodes of equal rank generated by CONQUR and by multi-DQN (baseline), we see that CONQUR nodes dominate their multi-DQN counterparts: the three highest-ranked nodes achieve a score improvement of 18%, 13% and 15%, respectively, while the remaining nodes achieve improvements of roughly 11–12%. Fig. 6 (smoothed, best frontier node) shows the effects of varying λ. In Alien, increasing λ from 1 to 10 improves performance, but it starts to decline for higher values of 100 and 1000. This is similar to patterns observed in 4.1 and represents a trade-off between emphasizing consistency and not over-committing to action assignments. In Atlantis, stronger penalization tends to degrade performance. In fact, the stronger the penalization, the worse the performance.

heading: 5 CONCLUDING REMARKS
text: We have introduced CONQUR, a framework for mitigating delusional bias in value-based RL that relaxes some of the strict assumptions of exact delusion-free algorithms to ensure scalability. Its two main components are (a) a tree-search procedure used to create and maintain diverse, promising Q-regressors (and corresponding information sets); and (b) a consistency penalty that encourages “maximizing” actions to be consistent with the FA class. CONQUR embodies elements of both value-based and policy-based RL: it can be viewed as using partial policy constraints to bias the value estimator or as a means of using candidate value functions to bias the search through policy space. Empirically, we find that CONQUR can improve the quality of existing approximators by removing delusional bias. Moreover, the consistency penalty applied on its own, directly in DQN or DDQN, itself can improve the quality of the induced policies.
Given the generality of the CONQUR framework, there remain numerous interesting directions for future research. Other methods for nudging regressors to be policy-consistent include exact consistency (constrained regression), other regularization schemes that bias the regressor to fall within the information set, etc. Given its flexibility, more extensive exploration of search strategies (e.g., best first), child-generation strategies, and node scoring schemes should be examined within CONQUR. Our (full) experiments should also be extended beyond those that warm-start from a DQN model, as should testing CONQUR in other domains.
Other connections and generalizations are of interest as well. We believe our methods can be extended to both continuous actions and soft max-action policies. We suspect that there is a connection between maintaining multiple “hypotheses” (i.e., Q-regressors) and notions in distributional RL, which maintains distributions over action values Bellemare et al. (2017).

heading: A AN EXAMPLE OF DELUSIONAL BIAS
text: We describe an example, taken directly from (Lu et al., 2018), to show concretely how delusional bias causes problems for Q-learning with function approximation. The MDP in Fig. 7 illustrates the phenomenon: Lu et al. (2018) use a linear approximator over a specific set of features in this MDP to show that:
(a) No π ∈ G(Θ) can express the optimal (unconstrained) policy (which requires taking a2 at each state);
(b) The optimal feasible policy in G(Θ) takes a1 at s1 and a2 at s4 (achieving a value of 0.5). (c) Online Q-learning (Eq. 1) with data generated using an ε-greedy behavior policy must converge
to a fixed point (under a range of rewards and discounts) corresponding to a “compromise” admissible policy which takes a1 at both s1 and s4 (value of 0.3).
Algorithm 1 CONQUR SEARCH (Generic, depth-first)
Input: Data sets Dk, Dk+1, . . . DT ; regressor Q̂k−1; and assignment σ over D≤k−1 = ∪1≤j≤k−1Dj reflecting prior data; policy class Θ.
1: Let ΣΘ,σ = {σk ∈ ΣΘ(Dj) : σk ∪ σ is consistent} 2: for all σjk ∈ ΣΘ,σ do 3: Training set S ← {} 4: for all (s, a, r, s′) ∈ Dk do 5: q ← r + γQ̂k−1(s′, σjk(s′)) 6: S ← S ∪ {((s, a), q)} 7: end for 8: Train Q̂jk using training set S 9: if k = T then
10: Return Q̂jk // terminate 11: else 12: Return SEARCH(Dk+1, . . . DT ; Q̂ j k; σ j k ∪ σ; Θ) // recurse 13: end if 14: end for
Q-learning fails to find a reasonable fixed-point because of delusion. Consider the backups at (s2, a2) and (s3, a2). Suppose θ̂ assigns a “high” value to (s3, a2), so that Qθ̂(s3, a2) > Qθ̂(s3, a1) as required by πθ∗ . They show that any such θ̂ also accords a “high” value to (s2, a2). But Qθ̂(s2, a2) > Qθ̂(s2, a1) is inconsistent the first requirement. As such, any update that makes the Q-value of (s2, a2) higher undercuts the justification for it to be higher (i.e., makes the “max” value of its successor state (s3, a2) lower). This occurs not due to approximation error, but the inability of Q-learning to find the value of the optimal representable policy.

heading: B ALGORITHMS
text: The pseudocode of (depth-first) version of the CONQUR search framework is listed in Algorithm 1. As discussed in Sec. 3.5, a more specific instantiation of the CONQUR algorithm is listed in Algorithm. 2.

heading: C ADDITIONAL DETAIL: EFFECTS OF CONSISTENCY PENALIZATION

heading: C.1 DELUSIONAL BIAS IN DQN AND DDQN
text: Both DQN and DDQN uses a delayed version of the Q-network Qθ−(s′, a′) for label generation, but in a different way. In DQN, Qθ−(s′, a′) is used for both value estimate and action assignment σDQN(s ′) = argmaxa′ Qθk(s ′, a′), whereas in DDQN, Qθ−(s′, a′) is used only for value estimate and the action assignment is computed from the current network σDDQN(s′) = argmaxa′ Qθk(s ′, a′).
With respect to delusional bias, action assignment of DQN is consistent for all batches after the latest network weight transfer, as σDQN(s′) is computed from the same Qθ−(s′, a′) network. DDQN, on the other hand, could have very inconsistent assignments, since the action is computed from the current network that is being updated at every step.
Algorithm 2 Modified Beam Search Instantiation of CONQUR Algorithm Input: Search control parameters: m, `, c, d, T
1: Maintain list of data batches D1, ..., Dk, initialized empty 2: Maintain candidate pool P of at most m nodes, initialized P = {n0} 3: Maintain frontier list F of `c nodes 4: Maintain for each node nik a regressor θ i k and an ancestor assignment σ i k
5: for each search level k ≤ T do 6: Find top scoring node n1 ∈ P 7: Use ε-greedy policy extracted from Qθ1 to collect next data batch Dk 8: if k is an expansion level then 9: Select top ` scoring nodes n1, ..., n` ∈ P
10: for each selected node ni do 11: Generate c children ni,1, ..., ni,c using Boltzmann sampling on Dk with Qθi 12: for each child ni,j do 13: Let assignment history σi,j be σi ∪ {new assignment} 14: Determine regressor θi,j by applying update (3) from θi 15: end for 16: Score and add child nodes to the candidate pool P 17: Assign frontier nodes to set of child nodes, F = {ni,j} 18: if |P | > m then 19: evict bottom scoring nodes, keeping top m in P 20: end if 21: end for 22: end if 23: if k is a refinement ("dive") level then 24: for each frontier node ni,j ∈ F do 25: Update regressor θi,j by applying update (3) to θi,j 26: end for 27: end if 28: Run d "dive" levels after each expansion level
29: end for

heading: C.2 TRAINING METHODOLOGY AND HYPERPARAMETERS
text: We implement consistency penalty on top of the DQN and DDQN algorithm by modifying the opensource TF-Agents library (Guadarrama et al., 2018). In particular, we modify existing DqnAgent and DdqnAgent by adding a consistency penalty term to the original TD loss.
We use TF-Agents implementation of DQN training on Atari with the default hyperparameters, which are mostly the same as that used in the original DQN paper (Mnih et al., 2015). For conveniece to the reader, some important hyperparameters are listed in Table 2. The reward is clipped between [−1, 1] following the original DQN.

heading: C.3 EVALUATION METHODOLOGY
text: We empirically evaluate our modified DQN and DDQN agents trained with consistency penalty on 15 Atari games. Evaluation is run using the training and evaluation framework for Atari provided in TF-Agents without any modifications.

heading: C.4 DETAILED RESULTS
text: Fig. 8 shows the effects of varying λ on both DQN and DDQN. Table 3 summarizes the best penalties for each game and their corresponding scores. Fig. 9 shows the training curves of the best penalization constants. Finally, Fig. 10 shows the training curves for a fixed penalization of λ = 1/2. The datapoints in each plot of the aforementioned figures are obtained by taking windows of size 30
steps, and within each window, we take the largest policy value (and over ≈2–5 multiple runs). This is done to reduce visual clutter.

heading: D ADDITIONAL DETAIL: CONQUR RESULTS
text: Our results use a frontier queue of size (F ) 8 or 16 (these are the top scoring leaf nodes which receive gradient updates and rollout evaluations during training). To generate training batches, we select the best node’s regressor according to our scoring function, from which we generate training samples (transitions) using ε-greedy. Results are reported in Table 4 and 5, and related figures where max number of nodes are 8 or 16. We used Bellman error plus consistency penalty as our scoring function. During the training process, we also calibrated the scoring to account for the depth difference between
the leaf nodes at the frontier versus the leaf nodes in the candidate pool. We calibrated by taking the mean of the difference between scores of the current nodes in the frontier with their parents. We scaled this difference by multiplying with a constant of 2.5.
In our implementation, we initialized our Q-network with a pre-trained DQN. We start with the expansion phase. During this phase, each parent node splits into l children nodes and the Q-labels are generated using action assignments from the Boltzmann sampling procedure, in order to create high quality and diversified children. We start the dive phase until the number of children generated is at least F . In particular, with F = 16 configuration, we performed the expansion phase at the zero-th and first iterations, and then at every tenth iteration starting at iteration 10, then at 20, and so on until ending at iteration 90. In the F = 8 configuration, the expansion phase occurred at the zero-th and first iterations, then at every tenth iterations starting at iterations 10 and 11, then at iterations 20 and 21, and so on until ending at iterations 90 and 91. All other iterations execute the “dive” phase. For every fifth iteration, Q-labels are generated from action assignments sampled according to the Boltzmann distribution. For all other iterations, Q-labels are generated in the same fashion as the standard Q-learning (taking the max Q-value). The generated Q-labels along with the consistency penalty are then converted into gradient updates that applies to one or more generated children nodes.

heading: D.1 TRAINING METHODOLOGY AND HYPERPARAMETERS
text: Each iteration consists of 10k transitions sampled from the environment. Our entire training process has 100 iterations which consumes 1M transitions or 4M frames. We used RMSProp as the optimizer with a learning rate of 2.5 × 10−6. One training iteration has 2.5k gradient updates and we used a batch size of 32. We replace the target network with the online network every fifth iteration and reward is clipped between [−1, 1]. We use a discount value of γ = 0.99 and ε-greedy with ε = 0.01 for exploration. Details of hyper-parameter settings can be found in Table 6 (for 16 nodes) and Table 7 (for 8 nodes).

heading: D.2 EVALUATION METHODOLOGY
text: We empirically evaluate our algorithms on 59 Atari games (Bellemare et al., 2013), and followed the evaluation procedure as in Hasselt et al. (2016). We evaluate our agents every 10th iterations (and also the initial and first iteration) by suspending our training process. We evaluate on 500k frames, and we cap the length of the episodes for 108k frames. We used ε-greedy as the evaluation policy with ε = 0.001.

heading: D.3 DETAILED RESULTS
text: Fig. 11 shows training curves of CONQUR with 16 nodes under different penalization strengths λ. Each plotted step of each training curve (including the baseline) shows the best performing node’s policy value as evaluated with full rollouts. Table 4 shows the summary of the highest policy values achieved for all 59 games for CONQUR and the baseline under 8 and 16 nodes. Table 5 shows a similar summary, but without no-op starts (i.e. policy actions are applied immediately). Both the baseline and CONQUR improve overall, but CONQUR’s advantage over the baseline is amplified. This may suggest that for more deterministic MDP environments, CONQUR may have even better improvements. The results on 16 and 8 nodes use a splitting factor of 4 and 2, respectively.

heading: Hyperparameters Description Value

Review summaries:
A recent paper by Lu et al introduced delusional bias in Q-learning, an error due to the max in the Bellman backup not being consistent with the policy representation implied by the greedy operator applied to the approximated value function. That work proposed a consistent algorithm for small and finite state spaces, which essentially enumerates over realizable policies. This paper proposes an algorithm for overcoming delusional bias in large state spaces. The idea is to add to the Q-learning objective a smooth penalty term that induces approximate consistency, and search over possible Q-function approximators. Several heuristic methods are proposed for this search, and results are demonstrated in Atari domains.

This paper presents a solution to tackling the problem of delusional bias in Deep Q-learning, building upon Lu et.al. (NeuRIPS 2018).  Delusional bias arises because independently choosing maximizing actions at a state may be inconsistent as the backed-up values may not be realizable by any policy. They encourage non-delusional Q-functions by adding a penalty term that enforces that the max_a in Q-learning chooses actions that do not give rise to actions outside the realizable policy class. Further, in order to keep track of all consistent assignments, they pose a search problem and propose heuristics to approximately perform this search. The heuristics are based on sampling using exponentiated Q-values and scoring possible children using scores like Bellman error, and returns of the greedy policy. Their final algorithm is evaluated on a DQN and DDQN, where they observe some improvement from both components (consistency penalty and approximate search).

This paper focuses on addressing the delusional bias problem in deep Q-learning, and propose a general framework (ConQUR) for integrating policy-consistent backups with regression-based function approximation for Q-learning and for managing the search through the space of possible regressors. Specifically, it proposes a soft consistency penalty to alleviate the delusional bias problem while avoiding the expensive exact consistency testing. This penalty encourages the parameters of the model to satisfy the consistency condition when solving the MSBE problem.