Adaptive Tree Backup Algorithms for
Temporal-Difference Reinforcement Learning

Unifying temporal-difference (TD), dynamic programming (DP), and Monte Carlo (MC) methods has helped illuminate trade-offs in reinforcement learning and has lead to the development of better algorithms. Much work has focused on the length of backups as a unifying axis between TD and MC methods, in which these two classes can be understood as opposite extremes of the TD($\lambda$) algorithm (Sutton, 1988; Sutton and Barto, 1998). In this view, the decay parameter $\lambda\in[0,1]$ serves not only as a conceptual link between these distinct methods, but also as a mechanism for managing the bias-variance trade-off (Kearns and Singh, 2000), where intermediate values of $\lambda$ often deliver the best empirical performance (Sutton and Barto, 1998).

Recent research has begun to explore an orthogonal unification between TD and DP methods by varying the width of backups. This concept was formally introduced by Sutton and Barto (2018) in the Q($\sigma$) algorithm; the method interpolates linearly, via a parameter $\sigma\in[0,1]$, between Expected Sarsa ($\sigma=0$) (Sutton and Barto, 1998) and Sarsa ($\sigma=1$) (Rummery and Niranjan, 1994). As such, Q($\sigma$) can be seen as a spectrum of algorithms whose backup widths lie somewhere between those of a sample backup and a full (expected) backup. De Asis et al. (2018) conducted further theoretical and empirical analysis of Q($\sigma$), arriving at two major hypotheses: $\sigma$ is a bias-variance trade-off parameter, and dynamically adapting $\sigma$ can lead to faster convergence. These hypotheses appeared to be corroborated by their experiments, where intermediate $\sigma$-values performed well, and exponentially decaying $\sigma$ during training performed even better.

In our work, we re-examine these two hypotheses regarding Q($\sigma$), and ultimately show that they are incorrect. In particular, we prove that the choice of $\sigma=0$ minimizes the variance of Q($\sigma$) without increasing the bias. It follows that the choice of $\sigma$ does not constitute a bias-variance trade-off, since both bias and variance can be simultaneously optimized without competition. Furthermore, we prove that the contraction rate and fixed point of the Q($\sigma$) operator are independent of $\sigma$, suggesting again that the choice of $\sigma=0$ is preferable for its variance-reduction effect. These findings are intriguing given the empirical results obtained by De Asis et al. (2018), which did not demonstrate a clear superiority of $\sigma=0$. This apparent discrepancy between theory and practice suggests that other factors are responsible for the observed benefits of Q($\sigma$), and that our understanding of the algorithm must be revised accordingly.

We therefore advance a new hypothesis to explain the effectiveness of intermediate $\sigma$-values: conducting partial backups ($\sigma\neq 0$) helps escape poor initializations of the value function $Q$ by reducing the chance that previously unvisited state-action pairs are considered during the backup. The value estimates of these pairs could be arbitrarily incorrect, slowing initial learning; however, as training progresses and the majority of state-action pairs have been visited, $\sigma=0$ starts to become more favorable for its variance reduction. This explanation matches the intuition of the time-decayed schedule utilized by De Asis et al. (2018), in which $\sigma=1$ is desirable early in training and $\sigma=0$ is desirable later.

This new hypothesis suggests that backup width should be adjusted based on the number of visitations to each state-action pair, with more emphasis placed on frequently sampled pairs. We therefore develop a new family of TD algorithms that we call Adaptive Tree Backup (ATB) methods, which generalizes Tree Backup (Precup et al., 2000) to arbitrary weightings of the value estimates. We highlight two instances of ATB methods (Count-Based and Policy-Based) that we believe to be promising. The proposed methods have the advantage of eliminating the hyperparameter $\sigma$, as they adapt automatically to the data experienced by the agent. Finally, our experiments demonstrate that Policy-Based ATB outperforms the exponential-decay schedule for $\sigma$ introduced by De Asis et al. (2018).

We model the environment as a Markov Decision Process (MDP) described by the tuple $(\mathcal{S},\mathcal{A},P,R)$: $\mathcal{S}$ is a finite set of environment states, $\mathcal{A}$ is a finite set of actions, $P$ is the transition function, and $R$ is the reward function. An agent interacts with the environment by selecting an action $a_{t}\in\mathcal{A}$ in state $s_{t}$ with probability $\pi(a_{t}|s_{t})$, receiving a reward $r_{t}\coloneqq R(s_{t},a_{t})$ and changing the state to $s_{t+1}$ with probability $P(s_{t+1}|s_{t},a_{t})$. Given the agent’s policy $\pi$, the objective is to estimate the expected discounted return $Q^{\pi}(s_{t},a_{t})\coloneqq\mathbb{E}_{\pi}[r_{t}+\gamma r_{t+1}+\gamma^{2}r_{t+2}+\dots]$, where $\gamma\in[0,1]$, since acting greedily with respect to $Q^{\pi}$ is known to produce a better policy (Sutton and Barto, 1998).

Q($\sigma$) (Sutton and Barto, 2018) is a method that iteratively improves its estimated value function $Q$ according to

where $\sigma\in[0,1]$ is a user-specified hyperparameter. This hyperparameter interpolates between the exact on-policy expectation (Expected Sarsa, $\sigma=0$) and noisy sample estimates of it (Sarsa, $\sigma=1$), and has been hypothesized to serve as a bias-variance trade-off parameter that improves the contraction rate of the algorithm (De Asis et al., 2018). In the subsequent section, we analyze the theoretical properties of the Q($\sigma$) update to investigate the validity of this hypothesis.

We investigate the effects that $\sigma$ has on the Q($\sigma$) algorithm in terms of convergence, contraction rate, bias, and variance. Our analysis dispels two misconceptions about Q($\sigma$): that dynamically adjusting $\sigma$ can achieve a faster contraction rate, and that $\sigma$ functions as a bias-variance trade-off parameter.

Q($\sigma$) does not address the standard bias-variance trade-off for temporal-difference learning, since the choice of $\sigma=0$ minimizes variance without impacting bias. Why, then, did De Asis et al. (2018) observe empirical improvement when employing an intermediate $\sigma$-value? We conjecture that Expected Sarsa ($\sigma=0$) struggles to overcome initialization error early in training (during which the majority of the state-action space is unexplored). Until every action has been sampled at least once in a given state, Expected Sarsa mixes one or more nonsensical value estimates into its full backup, potentially resulting in severe inaccuracies. In contrast, a sample method like Sarsa ($\sigma=1$) is likely to visit previously taken actions (simply by definition of a probabilistic policy), thereby bootstrapping sooner from more accurate estimates, but also with additional noise due to sampling. This phenomenon helps explain why the time-decayed schedule for $\sigma$ proposed by De Asis et al. (2018) is effective; excluding incorrect value estimates ($\sigma=1$) is important when most state-action pairs have not been visited, but minimizing variance ($\sigma=0$) becomes more important once all estimates are relatively accurate.

If our hypothesis is correct, then methods that dynamically increase the effective backup width based on state-action pair visitations should generally perform better than Q($\sigma$) with a fixed $\sigma$-value or time-annealed schedule. We call these Adaptive Tree Backup (ATB) methods, as they generalize Tree Backup (Precup et al., 2000) to arbitrary backup weightings. For a given transition $(s_{t},a_{t},r_{t},s_{t+1},a_{t+1})$, ATB algorithms can be written in the generic form

where each $c_{t}(s,a)$ is a nonnegative (possibly random) coefficient. Note that if $c_{t}(s,a)=(1-\sigma)\pi(a|s)+\sigma\mathbb{I}_{a=a_{t+1}}$, then we recover Q($\sigma$) exactly. However, the generality of the coefficients $c_{t}(s,a)$ permits myriad possibilities beyond the limited, one-dimensional spectrum spanned by Q($\sigma$).

The backup associated with update (6) admits the correct fixed point $Q^{\pi}$ only if $\mathbb{E}[c_{t}(s,a)]=\pi(a|s)$. Even so, if we ensure that $\mathbb{E}[c_{t}(s,a)]\to\pi(a|s)$ as $t\to\infty$, then the ATB method will eventually converge to $Q^{\pi}$ according to Theorem 1. We subsequently discuss two promising variants that do this.

To test whether adaptive strategies can outperform fixed $\sigma$-values and the handcrafted schedule proposed by De Asis et al. (2018), we compare our two ATB variants against Q($\sigma$) in a 19-state deterministic random walk environment (Sutton and Barto, 2018) and an 11-state stochastic gridworld environment (Russell and Norvig, 2010). For all methods, we fix $\alpha_{t}=0.4$ and $\gamma=1$. We train the agents for 200 episodes and plot the root-mean-square (RMS) error of the estimated value function $Q$ relative to $Q^{\pi}$ (Figure 1). We plot the error after each episode, averaging over 50 independent trials, where the shaded regions represent 99% confidence intervals. Policy-Based ATB performs strongly, learning significantly faster than all of the methods except Q($0$), and even surpassing the handcrafted, dynamic $\sigma$ schedule of De Asis et al. (2018)—an impressive feat for an automatic method. Count-Based ATB outperforms Q($1$), but its asymptotic performance in the deterministic random walk deteriorates due to the fixed-point bias we discussed earlier; however, this seems to have a less detrimental effect in the stochastic gridworld. Surprisingly, in contrast to the results of De Asis et al. (2018), we find that $\sigma=0$ is the best choice of fixed $\sigma$-value in both environments.

The empirical success of our adaptive methods—particularly Policy-Based ATB—has important implications. First, it shows that data-driven adaptive strategies for adjusting the backup width can be more effective than Q($\sigma$) with a fixed $\sigma$-value or a pre-specified schedule for annealing $\sigma$. In addition, since both of our methods gradually expand the effective backup width as new state-action pairs are visited, they further strengthen our hypothesis that initialization error in the value estimates is an important consideration when determining backup width. This also helps formalize the intuition of De Asis et al. (2018) that backup width should increase over time. Finally, these results show that $\sigma=0$ is a good choice in practice, corroborating our theoretical predictions that it minimizes variance without negatively impacting the bias or contraction rate of Q($\sigma$). Although $\sigma$ does not represent a bias-variance trade-off in temporal-difference learning, it is clear that $\sigma$ does play an important role in learning, and that analyzing methods in terms of how well their backups can balance initialization error with variance is a promising pathway to further algorithmic improvements.