Soft Q(λ): A multi-step off-policy method for entropy regularised reinforcement learning using eligibility traces
arXiv:2604.13780v1 [cs.LG] 15 Apr 2026
A P REPRINT Pranav Mahajan University of Oxford [email protected]
Ben Seymour University of Oxford [email protected]
April 16, 2026
A BSTRACT Soft Q-learning has emerged as a versatile model-free method for entropy-regularised reinforcement learning, optimising for returns augmented with a penalty on the divergence from a reference policy. Despite its success, the multi-step extensions of soft Q-learning remain relatively unexplored and limited to on-policy action sampling under the Boltzmann policy. In this brief research note, we first present a formal n-step formulation for soft Q-learning and then extend this framework to the fully off-policy case by introducing a novel Soft Tree Backup operator. Finally, we unify these developments into Soft Q(λ), an elegant online, off-policy, eligibility trace framework that allows for efficient credit assignment under arbitrary behaviour policies. Our derivations propose a model-free method for learning entropy-regularised value functions that can be utilised in future empirical experiments.
1
Introduction
Entropy-regularised reinforcement learning (RL) improves exploration, robustness and stability during learning by augmenting the reward objective with a penalty on the divergence from a reference policy (or a default policy) (Haarnoja et al., 2017; Van Niekerk et al., 2019). Entropy-regularised RL has its roots in Linear MDPs proposed by (Kappen, 2005; Todorov, 2006, 2009), sharing the same objective function. When the reference policy is set to a uniform random policy, it reduces to the special case of max entropy RL (Ziebart, 2010). One of the core features of such methods is that instead of learning a single deterministic behaviour that has the highest cumulative reward, the resulting policies try to learn all of the ways of performing the task, explicitly maximising the entropy of the corresponding policy. Such a stochastic policy is optimal when we consider the connection between optimal control and probabilistic inference (Todorov, 2008). A number of methods have been proposed, including Z-learning (Todorov, 2006, 2009), maximum entropy inverse RL (Ziebart et al., 2008), approximate inference using message passing (Toussaint, 2009), Ψ-learning (Rawlik et al., 2012), and G-learning (Fox et al., 2015), as well as more recent proposals in deep RL such as PGQ (O’Donoghue et al., 2016). Previous work has also established equivalence between policy gradient methods and soft Q-learning, where the optimal policy is shown to be a Boltzmann distribution of the action-values (Schulman et al., 2017). However, extending this framework to multi-step estimation introduces significant limitations. Specifically, the n-step soft Q-learning estimator proposed by Schulman et al. (2017) is unbiased only when trajectories are sampled using the target (soft-optimal) Boltzmann policy. This on-policy constraint restricts the algorithm’s utility in fully off-policy regimes or settings with arbitrary exploration schedules. In this research note, we bridge this gap by extending soft Q-learning to a fully off-policy, multi-step regime. We first formalise a stepwise n-step soft Q-learning formulation and then introduce a novel Soft Tree Backup operator that leverages the recursive relationship between the state-value function VQ and the action-value function Q. This operator handles entropy terms over multiple time steps without requiring knowledge of the behaviour policy, effectively eliminating the on-policy bias inherent in standard n-step soft backups. Finally, we unify these developments into
Soft Q(λ)
A P REPRINT
Soft Q(λ), an elegant eligibility trace framework that can enable efficient, online, off-policy credit assignment. Our derivations demonstrate that entropy-regularised value functions can be learned stably under arbitrary behaviour policies without the reliance on target networks or fixed exploration schedules, providing a theoretically grounded toolkit for robust reinforcement learning.
2
Background
2.1
Reinforcement learning in MDPs
Let the environment be a Markov Decision Process, where at time t = 0, 1, 2, ..., the agent is in state st ∈ S and takes action at ∈ A and receives the next state st+1 ∈ S and the reward rt+1 = r(st , at ) ∈ R giving rise to trajectories . s0 , a0 , r1 , s1 , a1 , r2 , .... The dynamics of MDP are given by the conditional probability p(s′ , r|s, a) = Pr(st = s′ , rt = r|st−1 = s, at−1 = a). P∞ The discounted return at time t is given by Gt = rt+1 + γrt+2 + γ 2 rt+3 + ... = k=0 γ k rt+k+1 , where γ ∈ [0, 1]. Policy π(a|s) is a mapping from states to the probabilities of choosing each possible action. The value function of a state s under the policy π is is the expected return when starting in s and following π thereafter, which is formalized . as Vπ = Eπ [Gt |st = s], ∀s ∈ S. Similarly, the value of taking action a in state s and following policy π thereafter is . given by the Q-value or the action-value function, Qπ (s, a) = Eπ [Gt |st = s, at = a]. The Bellman equation of a value function vπ is a fundamental property in reinforcement learning expressing the recursive relationship between the value of a state and the value of its possible successor states. . Vπ (s) = Ea∼π(·|s) E(s′ ,r)∼p(s′ ,r|s,a) [r + γVπ (s′ )], ∀s ∈ S
(1)
Since value functions define a partial ordering over policies, there exists at least one optimal policy π ∗ that is better than all policies, where a policy π ≥ π ′ if and only if Vπ (s) ≥ Vπ′ (s), ∀s ∈ S. The optimal state-value function . . is V ∗ (s) = maxπ Vπ (s), ∀s ∈ S. Similarly, the optimal action-value function is Q∗ (s, a) = maxπ Qπ (s, a) = ∗ E[rt+1 + V (st+1 )|st = s, at = a]. Once we have the optimal action-values, one can simply perform actions greedily to get the optimal policy π ∗ = [GQ∗ ](s) = arg maxa Q∗ (s, a). The recursive Bellman equations can also be written for the value function under the optimal policy, referred to as the Bellman optimality equations: V ∗ (s) = max E(s′ ,r)∼p(s′ ,r|s,a) [r + γV ∗ (s′ )] a
2.2
(2)
Entropy-regularised reinforcement learning in Linear MDPs
Entropy-regularised RL (Todorov, 2006, 2009; Van Niekerk et al., 2019) augments the reward function with a term that penalises deviating from some default policy π d , essentially making “soft” assumptions about the future policy (in the form of a stochastic action distribution). When π d is a uniform policy, this reduces to max entropy reinforcement learning (Ziebart, 2010; Haarnoja et al., 2017). The expected reward on taking action at in state st is given by Eat ∼π [r(st , at ) − τ DKL (π(·|st )∥π d (·|st ))], which can be further compactly written as Eat ∼π [rt+1 − τ KL(st )]. Here, τ is the scalar temperature parameter, and KL(st ) is the Kullback-Leibler divergence between the current policy π and P∞ a default policy π d in state st . Thus, the entropy-augmented return is Gt = k=0 γ k (rt+k+1 − τ KL(st+k )). The value function definitions under a policy π at any timestep t based on the entropy-augmented returns are as follows, "∞ # X . k Vπ (s) = Eπ [Gt |st = s] = Eπ γ (rt+k+1 − τ KL(st+k )) st = s
(3)
k=0
" # ∞ X . k Qπ (s, a) = Eπ [Gt |st = s, at = a] = Eπ rt+1 + γ (rt+k+1 − τ KL(st+k )) st = s, at = a
(4)
k=1
Note that this Q-function does not include the first KL penalty term (KL(st )), as it does not depend on action action at which has already been chosen (Ziebart, 2010; Haarnoja et al., 2017; Schulman et al., 2017). This gives the following relationship which holds for all policies π. 2
Soft Q(λ)
A P REPRINT
Vπ (s) = Ea∼π [Qπ (s, a)] − τ KL(s)
(5)
The Bellman equation and the Bellman optimality equation are as follows: . Vπ (s) = Ea∼π(·|s) E(s′ ,r)∼p(s′ ,r|s,a) [r − τ KL(s) + γVπ (s′ )]
(6)
V ∗ (s) = max E(s′ ,r)∼p(s′ ,r|s,a) [r − τ KL(s) + γV ∗ (s′ )]
(7)
a
Note, unlike the greedy (deterministic) policy [GQ](s) = arg maxa Q(s, a) in standard RL, the greedy (stochastic) B policy in entropy-regularised RL is the Boltzmann policy (πQ ). B πQ (·|s) = [GQ](s) = P
π d (a|s) exp(Q(s, a)/τ ) ′ d ′ A exp(Qπ (s, a )/τ )π (a |s)
(8)
Prior work (Todorov, 2006, 2009; Haarnoja et al., 2017; Van Niekerk et al., 2019) shows that this Boltzmann policy B holds the two properties: (1) it is the optimal policy (π ∗ = πQ ∗ ) i.e. it uniquely solves the Bellman optimality equations and (2) under the Boltzmann policy, the Bellman equation is equivalent to the "soft" Bellman equation, thus the value B (s) = VQ (s), essentially performing a soft maximum operation over Q-values. function VπQ VQ (s) = τ log Ea∼πd exp(Qπ (s, a)/τ ) X = τ log exp(Qπ (s, a)/τ )π d (a|s)
(9)
A
Note, this log-sum-exp performs a soft maximum because, max{x1 , ..., xn } max{x1 , ..., xn } + log(n). 2.3
≤
softmax(x1 , ..., xn )
≤
Off-policy model-free learning algorithms in Linear MDPs
Model-free algorithms do not assume a probabilistic model about state transitions and rewards but instead learn value functions through reward prediction errors. Here, we focus on online algorithms, such as soft Q-learning (Haarnoja et al., 2017), which update values continuously during episodes rather than waiting until the end, unlike offline algorithms like Z-learning (Todorov, 2006), a Monte Carlo control algorithm. We further particularly focus on off-policy algorithms like Soft Q-learning and our subsequent extensions. Soft Q-learning (One-Step) We adopt soft Q-learning and extend it from the maximum entropy formulation to a relative entropy formulation. The Q-value update equation is given by: Q(st , at ) ← Q(st , at ) + αδt ,
(10)
where α is the learning rate, and δt is the reward prediction error at timestep t, defined as: δt = rt+1 + γVQ (st+1 ) − Q(st , at ),
(11)
where VQ is given by equation 9. Deep RL implementations inspired by Mnih et al. (2015) may use a separate target network (e.g., Q, resulting in VQ ) to construct the loss function, which we exclude here for simplicity.
3
Results: Multi-step Soft Q-learning
This section presents novel update rules for multi-step extensions of soft Q-learning, where the agent learns from multiple steps rather than the most immediate step. Under the assumption that the state action values are approximately unchanging (Sutton and Barto, 2018), we can write the update rule for the N-step soft Q learning and its extension with eligibility traces, soft Q(λ) using TD-errors. 3
Soft Q(λ)
A P REPRINT
When following the Boltzmann policy, the N-step soft Q-learning is simply,
min(T −1,t+n−1)
Qt+n (st , at ) ← Qt+n−1 (st , at ) + α
X
γ k δk .
(12)
k=t
Where T is the time step at which the episode terminated, Qt+n denotes Q-value accessed or updated at timestep t + n, and the TD-errors are defined as follows. For k = t, the TD-error is given by equation 11. For k > t, it includes the KL divergence term and is given by, δk = rk+1 − τ KLk + γVQ (sk+1 ) − VQ (sk )
(13)
However, if one is following a behavioural policy that is not the Boltzmann policy (equation 8), then we need a truly off-policy update rule. If the agent has access to the behavioural policy, then it can use importance sampling (detailed derivation provided in Appendix 1). However, this can lead to higher variance in the updates and requires access to the behavioural policy. Therefore, we derive an alternative method using Tree Backup, which does not require explicit knowledge about the behavioural policy. The update rule is as follows,
min(T −1,t+n−1)
Qt+n (st , at ) ← Qt+n−1 (st , at ) + α
X k=t
δk
k Y
B γπQ (ai |si ) .
(14)
i=t+1
We next extend these methods to incorporate eligibility traces. Under the Boltzmann policy, the Q-value update rule is, Qt+1 (s, a) ← Qt (s, a) + αδt et (s, a) ∀s, a
(15)
and eligibility traces are updated as follows (in the tabular setting), et (s, a) =
γλet−1 (s, a) + 1, γλet−1 (s, a),
if (s, a) = (st , at ), otherwise,
(16)
The TD-error (δt ) is the same as equation 13 (except substitute k with t). Note, this algorithm is entirely online. For a full off-policy Soft Q(λ), we build upon the Tree Backup approach. The Q-value update rule and the TD-errors B remain the same, but the eligibility trace updates are adjusted to include the target policy πQ , et (s, a) =
B γλπQ (at |st )et−1 (s, a) + 1, B γλπQ (at |st )et−1 (s, a),
if (s, a) = (st , at ), otherwise,
(17)
All detailed derivations for N-step soft Q-learning and Soft Q(λ) are provided in Appendices 1 and 2, respectively.
4
Conclusions and a Neuroscientific Epilogue
This note extends soft Q-learning to a multi-step, off-policy regime. By introducing a novel Soft Tree Backup operator and then extending to the Soft Q(λ) framework, the method overcomes prior on-policy limitations and enables multi-step credit assignment under arbitrary, unknown behaviour policies. This work, laying the theoretical foundations, is particularly useful to the neuroscience of learning and decision making. Recent work (Mahajan and Seymour, 2025) utilises the benefits of entropy-regularised RL, such as optimal composition of multiple values and stable learning due to KL-regularisation, to provide a new theoretical update to the seminal theory of phasic dopamine responses (Schultz et al., 1997). The proposed theory also attempts to unify several disparate heterogeneities between and within different dopamine targets, including recently observed action prediction errors (Greenstreet et al., 2025), into the temporal difference RL framework. Meanwhile, model-based solutions to Linear MDPs have also been recently used to explain phenomena in human planning, grid fields, cognitive control and medial entorhinal cortex representations (Piray and Daw, 2021, 2024). Ultimately, these theoretical derivations provide a robust, model-free toolkit for entropy-regularised reinforcement learning, establishing a mathematical foundation for future empirical evaluations in complex environments. 4
Soft Q(λ)
A P REPRINT
Author Contributions PM: Conceptualisation, Formal Analysis, Writing – Original Draft Preparation, Writing – Review & Editing. BS: Funding Acquisition, Supervision.
Acknowledgments Authors thank the funders: Wellcome Trust (214251/Z/18/Z, 203139/Z/16/Z and 203139/A/16/Z), IITP (MSIT 20190-01371) and JSPS (22H04998). This research was also partly supported by the NIHR Oxford Health Biomedical Research Centre (NIHR203316). The views expressed are those of the author(s) and not necessarily those of the NIHR or the Department of Health and Social Care. For the purpose of open access, the authors have applied a CC BY public copyright licence to any Author Accepted Manuscript version arising from this submission.
References Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In International conference on machine learning, pages 1352–1361. PMLR, 2017. Benjamin Van Niekerk, Steven James, Adam Earle, and Benjamin Rosman. Composing value functions in reinforcement learning. In International conference on machine learning, pages 6401–6409. PMLR, 2019. Hilbert J Kappen. Linear theory for control of nonlinear stochastic systems. Physical review letters, 95(20):200201, 2005. Emanuel Todorov. Linearly-solvable markov decision problems. Advances in neural information processing systems, 19, 2006. Emanuel Todorov. Efficient computation of optimal actions. Proceedings of the national academy of sciences, 106(28): 11478–11483, 2009. Brian D Ziebart. Modeling purposeful adaptive behavior with the principle of maximum causal entropy. Carnegie Mellon University, 2010. Emanuel Todorov. General duality between optimal control and estimation. In 2008 47th IEEE conference on decision and control, pages 4286–4292. IEEE, 2008. Brian D Ziebart, Andrew L Maas, J Andrew Bagnell, Anind K Dey, et al. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pages 1433–1438. Chicago, IL, USA, 2008. Marc Toussaint. Robot trajectory optimization using approximate inference. In Proceedings of the 26th annual international conference on machine learning, pages 1049–1056, 2009. Konrad Rawlik, Marc Toussaint, and Sethu Vijayakumar. On stochastic optimal control and reinforcement learning by approximate inference. Proceedings of Robotics: Science and Systems VIII, 2012. Roy Fox, Ari Pakman, and Naftali Tishby. Taming the noise in reinforcement learning via soft updates. arXiv preprint arXiv:1512.08562, 2015. Brendan O’Donoghue, Remi Munos, Koray Kavukcuoglu, and Volodymyr Mnih. Combining policy gradient and q-learning. arXiv preprint arXiv:1611.01626, 2016. John Schulman, Xi Chen, and Pieter Abbeel. Equivalence between policy gradients and soft q-learning. arXiv preprint arXiv:1704.06440, 2017. Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529–533, 2015. Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018. Pranav Mahajan and Ben Seymour. Composing the value signal for dopamine-mediated learning. bioRxiv, 2025. doi:10.1101/2025.10.10.681616. Wolfram Schultz, Peter Dayan, and P Read Montague. A neural substrate of prediction and reward. Science, 275(5306): 1593–1599, 1997. Francesca Greenstreet, Hernando Martinez Vergara, Yvonne Johansson, Sthitapranjya Pati, Laura Schwarz, Stephen C Lenzi, Jesse P Geerts, Matthew Wisdom, Alina Gubanova, Lars B Rollik, et al. Dopaminergic action prediction errors serve as a value-free teaching signal. Nature, pages 1–10, 2025. 5
Soft Q(λ)
A P REPRINT
Payam Piray and Nathaniel D Daw. Linear reinforcement learning in planning, grid fields, and cognitive control. Nature communications, 12(1):4942, 2021. Payam Piray and Nathaniel D Daw. Reconciling flexibility and efficiency: Medial entorhinal cortex represents a compositional cognitive map. bioRxiv, pages 2024–05, 2024. Doina Precup. Eligibility traces for off-policy policy evaluation. Computer Science Department Faculty Publication Series, page 80, 2000. Kristopher De Asis, J Hernandez-Garcia, G Holland, and Richard Sutton. Multi-step reinforcement learning: A unifying algorithm. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
6
Soft Q(λ)
A P REPRINT
Appendix Appendix 1: Novel derivations extending Soft Q-learning to N-step soft Q-learning In this section, we provide a detailed derivation of how soft Q-learning can be extended to N-step soft Q-learning. We will first begin with the on-policy setting, under the special case of Boltzmann policy (the stochastic optimal policy) and then extend it to a fully off-policy algorithm. N-step Soft Q-learning (on-policy with Boltzmann policy) N-step soft Q-learning incorporates multiple future rewards and KL penalties for deviating from the default policy, starting from the second time step onward. The N-step return at time t, after taking an action at in state st is defined as: . Gt:t+n = rt+1 + γ(rt+2 − τ KLt+1 ) + γ 2 (rt+3 − τ KLt+2 ) + . . . + γ n−1 (rt+n − τ KLt+n−1 ) + γ n VQ (st+n ), (18) Note that the KL penalty terms appear only from the second timestep onward, as the cost of deviating from the default policy affects subsequent actions. If the episode terminates at timestep T , which can be less than t + n, then we will see next that the summation of TD-errors is appropriately truncated to min(T − 1, t + n − 1). We can rewrite Gt:t+n in terms of the temporal difference (TD) error δ, by adding and subtracting γVQ (st+1 ), γ 2 VQ (st+2 ), γ 3 VQ (st+3 ) and so on: Gt:t+n = (rt+1 + γVQ (st+1 )) + γ(rt+2 − τ KLt+1 + γVQ (st+2 ) − VQ (st+1 )) + . . . + γ n−1 (rt+n − τ KLt+n−1 + γVQ (st+n ) − VQ (st+n−1 )).
(19)
Simplifying, we obtain: min(T −1,t+n−1)
Gt:t+n = (rt+1 + γVQ (st+1 )) +
X
γ k δk
k=t+1 min(T −1,t+n−1)
= Qt−1 (st , at ) + (rt+1 + γVQ (st+1 ) − (Qt−1 (st , at )) +
X
γ k δk
(20)
k=t+1 min(T −1,t+n−1)
= Qt−1 (st , at ) +
X
γ k δk
k=t
where the TD error δk at each timestep is given as follows. If k = t, the same as soft Q-learning: δt = rt+1 + γVQ (st+1 ) − Q(st , at )
(21)
δk = rk+1 − τ KLk + γVQ (sk+1 ) − VQ (sk )
(22)
For k ≥ t, The first TD error term, δt = rt+1 + γVQ (st+1 ) − Q(st , at ), does not include the KL penalty since it doesn’t depend on the action at which has already been chosen (Ziebart, 2010; Haarnoja et al., 2017; Schulman et al., 2017). Thus, the N-step soft Q-learning update rule is defined as: Qt+n (st , at ) ← Qt+n−1 (st , at ) + α (Gt:t+n − Qt+n−1 (st , at )) ,
(23)
where α is the learning rate. The subscripts denote the timestep in the episode when the Q-value was used or updated. Note that n-step returns for n > 1 involve future rewards and states that are not available at the time of transition from t to t + 1. Thus, the first Q-update of state st is performed at timestep t + n and not t. 7
Soft Q(λ)
A P REPRINT
If the approximate action-values are unchanging, i.e. Qt−1 (st , at ) ≃ Qt+n−1 (st , at ) (similar to Exercise 7.11 in Sutton and Barto (2018)), then we can substitute the expression for Gt:t+n to get:
min(T −1,t+n−1)
Qt+n (st , at ) ← Qt+n−1 (st , at ) + α
X
γ k δk .
(24)
k=t
If the approximate action values are changing, then we will have an additional term of Qt−1 (st , at ) − Qt+n−1 (st , at ) in the update. N-step Soft Q-learning (off-policy with importance sampling) B We can now extend this to an off-policy algorithm that learns the Boltzmann policy (πQ ) as the target policy while collecting data under any behavioural policy b. Considering that soft Q-learning is akin to expected SARSA for relative-entropy regularised objective, this derivation is similar to the N-step expected SARSA derivation (Sutton and Barto, 2018).
We define the importance sampling ratio as follows (T is the last time step of the episode), min(h,T −1)
Y
ρt:h =
k=t
B πQ (ak |sk ) b(ak |sk )
(25)
Now the update from the previous subsection can be replaced with its off-policy form, Qt+n (st , at ) ← Qt+n−1 (st , at ) + αρt+1:t+n−1 (Gt:t+n − Qt+n−1 (st , at )) ,
Qt+n (st , at ) ← Qt+n−1 (st , at ) + αρt+1:t+n−1
t+n−1 X
(26)
! γ k δk
.
(27)
k=t
where, δt+k is defined as per equations 21 and 22. Note, we use ρt+1:t+n−1 and not ρt+1:t+n as in any N-step expected SARSA such as this one, all possible actions are taken into account in the last state; the one actually taken has no effect and does not have to be corrected for (Sutton and Barto, 2018, Page 150). One can further write this recursively using per-decision importance sampling (Sutton and Barto, 2018; Precup, 2000), but it is not essential to our derivations. N-step Soft Q-learning (off-policy with Tree Backup) We next present N-step Soft Q-learning using the Tree Backup algorithm. N-step soft Q-learning with importance sampling only uses the expectation over actions in the last time step. Tree Backup instead uses it at every step. This provides the following advantages: (1) reduces the variance due to the importance sampling ratio, (2) an importance sampling ratio does not need to be computed, thus the behavioural policy b does not need to be stationary, Markov, or even known (De Asis et al., 2018; Precup, 2000). We begin by writing the N-step return under the Boltzmann policy after taking action at in state st in the Tree Backup format. Note, this is the soft-Bellman optimal return regardless of the behavioural policy which chooses actions at , at+1 , at+2 , ... leading to states st+1 , st+2 , st+3 , ... respectively. . B (st+1 ) Gt:t+n = rt+1 + γVπQ
(28)
Using equation 5, we get, . Gt:t+n = rt+1 + γ
! X
B πQ (a|st+1 )Qt (st+1 , a) − τ KLt+1
a
We can now write it in Tree-Backup format, 8
(29)
Soft Q(λ)
A P REPRINT
X . B πQ (a|st+1 )Qt (st+1 , a) − γτ KLt+1 Gt:t+n = rt+1 + γ a̸=at+1
X
B + γπQ (at+1 |st+1 ) rt+2 − τ KLt+1 + γ
B πQ (a|st+2 )Qt+1 (st+2 , a) − γτ KLt+2
a̸=at+2
X
B B + γ 2 πQ (at+2 |st+2 )πQ (at+1 |st+1 ) rt+3 − τ KLt+2 + γ
B πQ (a|st+3 )Qt+2 (st+3 , a) − γτ KLt+3
a̸=at+3
+ ... min(t+n−1,T −1)
+γ
Y
n−1
! B πQ (ai |si )
rt+n − KLt+n−1 + γ
X
B πQ (a|st+n )Qt+n−1 (st+n , a) − γτ KLt+n
a
i=t+1
(30) This is visualised as follows: The update is from the estimated action values of the leaf nodes of the tree. The action nodes in the interior, corresponding to the actual actions taken, do not participate. Each leaf node contributes to the target with a weight proportional to its probability of occurring under the target policy. This can now be written recursively as, X . B B Gt:t+n = rt+1 + γ πQ (a|st+1 )Qt (st+1 , a) + γπQ (at+1 |st+1 )(Gt+1:t+n − τ KLt+1 )
(31)
a̸=at+1
Alternatively, it can also be compactly written in terms of temporal difference errors, by using the following relation from equation 9: X
B πQ (a|sk )Qk−1 (sk , a) =
X
B B πQ (a|sk )Qk−1 (sk , a) − πQ (ak |sk )Qk−1 (sk , ak ))
(32)
a
a̸=ak
B = VQ (sk ) + τ KLk − πQ (ak |sk )Qk−1 (sk , ak ))
By substituting this relation in equations 30, the τ KLk terms cancel out and we can write the Tree-Backup return in terms of TD-errors as follows: . B Gt:t+n = rt+1 + γ VQ (st+1 ) − πQ (at+1 |st+1 )Qt (st+1 , at+1 ) B B + γπQ (at+1 |st+1 ) rt+2 − τ KLt+1 + γVQ (st+2 ) − γπQ (at+2 |st+2 )Qt+1 (st+2 , at+2 ) B B B + γ 2 πQ (at+2 |st+2 )πQ (at+1 |st+1 ) rt+3 − τ KLt+2 + γVQ (st+3 ) − γπQ (at+3 |st+3 )Qt+2 (st+3 , at+3 )
+ ...
min(t+n−1,T −1)
+ γ n−1
Y
B B πQ (ai |si ) rt+n − KLt+n−1 + γVQ (st+n ) − γπQ (at+n |st+n )Qt+n−1 (st+n , at+n )
i=t+1
(33) If we combine rk+1 − τ KLk + VQ (sk+1 ) with the last term of the (previous) k-th term, and add and subtract Q(st , at ) for the first term, then we have the following. min(T −1,t+n−1)
Gt:t+n = Qt−1 (st , at )+
X k=t
" δk
k Y
min(T −1,t+n−1)
# B γπQ (ai |si )
i=t+1
−γ n Qt+n−1 (st+n , at+n )
Y
B πQ (ai |si )
i=t+1
(34) 9
Soft Q(λ)
A P REPRINT
If the t + n − 1 > T − 1, that is, the last state is terminal, then we can set the last Q-term to zero, and this expression simplifies to,
Gt:t+n = Qt−1 (st , at ) +
T −1 X k=t
" δk
#
k Y
B γπQ (ai |si )
(35)
i=t+1
Again, if we assume the approximate Q-values are unchanging (similar to Exercise 7.11 in Sutton and Barto (2018)), then this gives us our Q-update equation as follows,
min(T −1,t+n−1)
Qt+n (st , at ) ← Qt+n−1 (st , at ) + α
X
δk
k Y
B γπQ (ai |si ) .
(36)
i=t+1
k=t
where δk are defined as per equations 21 and 22. These updates lead to the estimation of off-policy multi-step returns under any behavioural policy, without knowing the behavioural policy. B (st+1 ), then this leads to an alternate Note, that if one starts the Tree Backup derivation with VQ (st + 1) instead of VπQ equivalent derivation in terms of the default policy instead of the Boltzmann policy (which requires calculating TD-errors under the default policy as well). We think this alternate derivation is less relevant as the agent is the target policy for the agent is the soft-Bellman optimal Boltzmann policy; therefore, we focus on the derivation in terms of the Boltzmann policy.
This concludes our novel derivations of off-policy N-step extensions of Soft Q-learning, using either importance sampling or Tree-Backup. One may further aspire to unify these two multi-step off-policy methods, as done in the standard RL setting by De Asis et al. (2018), but it is not essential to the current work and is left as future work. Appendix 2: Novel derivations extending N-step soft Q-learning to an elegant algorithm with eligibility traces Soft Q(λ) (on-policy with Boltzmann policy) Here, we build upon the N-step Soft Q-learning results to develop Soft Q(λ), a solution using eligibility traces. We define a λ-return, which is the weighted summation of n-step returns (Sutton and Barto, 2018). Gλt = (1 − λ)
∞ X
λn−1 Gt:t+n
(37)
n=1
To simplify the derivation, we define the Boltzmann backup operator following Schulman et al. (2017), ′ ′ B Q](s, a) = E(s′ ,r)∼p(s′ ,r|s,a) [r + γτ log Ea′ ∼π d [exp(Q(s , a )/τ )]] [TπQ
= E(s′ ,r)∼p(s′ ,r|s,a) [r + γVQ (s′ )]]
(38)
B ,λ Q](s, a), as We can now define the SARSA(λ) version of this backup operator under the Boltzmann policy, [TπQ follows.
2 B ,λ Q] = (1 − λ)(1 + λTπ B + (λTπ B ) + ...)Tπ B Q Gλt = [TπQ Q Q Q
(39)
Based on n-step methods, we can derive it to be, B ,λ Q](s, a) = Q(s, a) + E Gλt = [TπQ
"∞ X
# k
(40)
δk = rk+1 − τ KLk + γVQ (sk+1 ) − VQ (sk )
(41)
(γλ) δk
k=t
where,
10
Soft Q(λ)
A P REPRINT
The update rule using Gλt , with a forward-view but offline algorithm is, Qt+1 (s, a) ← Qt (s, a) + α(Gλt − Qt (s, a))
(42)
This can be approximated using a backwards view (SARSA(λ)-like) online algorithm under the Boltzmann policy, with eligibility traces (et ) and the TD-errors as mentioned above in equation 41 (δt ). Qt+1 (s, a) ← Qt (s, a) + αδt et (s, a) ∀s, a
(43)
and eligibility traces are updated as follows (in the tabular setting), et (s, a) =
γλet−1 (s, a) + 1, γλet−1 (s, a),
if (s, a) = (st , at ), otherwise,
(44)
Soft Q(λ) (off-policy with Tree Backup) We next extend the algorithm to a full off-policy algorithm, developing upon the n-step method using the Tree Backup algorithm. Gλt ≈ Q(s, a) +
"∞ X
δk
k X
# B γi λi πQ (ai |si )
(45)
i=t+1
k=t
Which gives us an online off-policy soft Q(λ) algorithm, similar to the previous one, but the eligibility trace update is B adjusted with the target policy πQ , Qt+1 (s, a) ← Qt (s, a) + αδt et (s, a) ∀s, a
(46)
δt = rt+1 − τ KLt + γVQ (st+1 ) − VQ (st )
(47)
where,
and, et (s, a) =
B γλπQ (at |st )et−1 (s, a) + 1, B γλπQ (at |st )et−1 (s, a),
if (s, a) = (st , at ), otherwise,
(48)
This concludes our derivation of a basic online off-policy Soft Q(λ) algorithm. Such algorithms can be extended to (1) function approximation, (2) a more "true" online algorithm and (3) more stable algorithms following Chapter 12 in Sutton and Barto (2018).
11