---
author:
- 'Adam White and Richard S. Sutton'
date: 'Revised July 29, 2014'
title: |
    GQ(${\lambda}$)\
    Quick Reference and Implementation Guide
---

This document should serve as a quick reference for and guide to the implementation of linear GQ(${\lambda}$), a gradient-based off-policy temporal-difference learning algorithm. Explanation of the intuition and theory behind the algorithm are provided elsewhere (e.g., Maei & Sutton 2010, Maei 2011). If you questions or concerns about the content in this document or the attached java code please email Adam White (adam.white@ualberta.ca).

Requirements and Setting
========================

For each use of GQ(${\lambda}$) you will need to provide three [*question functions*]{} specifying the quantity to be predicted, and four *answer functions* characterizing the approximation that will be found. Let ${\mathcal{S}}$ and ${\mathcal{A}}$ denote the sets of states and actions. Then the question functions are:

-   $\pi: {\mathcal{S}}\times {\mathcal{A}}{\rightarrow}[0,1]$; target policy to be learned. Incidently, if $\pi$ is chosen as the greedy policy with respect to the learned value function, then the algorithm will implement a generalization of the Greedy-GQ algorithm (Maei, Szepesvari, Bhatnagar & Sutton 2010).\

-   ${\gamma}: {\mathcal{S}}{\rightarrow}[0, 1]$; termination or discounting function (${\gamma}(s) = 1 - \beta(s)$ in GQ paper)\

-   $r: {\mathcal{S}}\times {\mathcal{A}}\times {\mathcal{S}}{\rightarrow}{\mathbb{R}}$; reward function

In many publications there is also specified a fourth question function, the terminal reward function $z : {\mathcal{S}}{\rightarrow}{\mathbb{R}}$ used to specify a final reward at termination. More recently its has been recognized that this functionality can be included in the reward function, making use of the discounting function (Modayil, White & Sutton 2014). For example, if one wanted only a terminal reward function $z(s)$ upon termination in state $s$, one would use a reward function of $r(s, a, s') = (1-\gamma(s'))z(s')$. This completes the specification of the predictive question that you are seeking to answer using the GQ(${\lambda}$) algorithm.

The answer functions are:

-   $b: {\mathcal{S}}\times {\mathcal{A}}{\rightarrow}[0,1]$; behavior policy\

-   $I : {\mathcal{S}}\times {\mathcal{A}}{\rightarrow}[0, 1]$; interest function (can set to 1 for all state-action pairs or indicate selected state-action pairs to be best approximated)\

-   $\ph : {\mathcal{S}}\times {\mathcal{A}}{\rightarrow}{\mathbb{R}}^n$; feature-vector function\

-   ${\lambda}: {\mathcal{S}}{\rightarrow}[0, 1]$; bootstrapping or eligibility-trace decay-rate function

The following data structures are internal to GQ:

-   $\th \in {\mathbb{R}}^n$; the learned weights of the linear approximation: $Q^\pi(s,a) = \th^\top\ph(s, a) = \sum_{i=1}^n \th_i\ph_i(s,a)$\

-   ${{\bm w}}\in {\mathbb{R}}^n$; secondary set of learned weights\

-   ${{\bm e}}\in {\mathbb{R}}^n$; eligibility trace vector

Parameters internal to GQ:

-   $\alpha$; step-size parameter for learning $\th$

-   $\eta \in [0, 1]$; relative step-size parameter for learning ${{\bm w}}$ $(\alpha\eta)$

Algorithm Specification
=======================

We can now specify GQ(${\lambda}$). Let ${{\bm w}}$ and ${{\bm e}}$ be initialized to zero and $\th$ be initialized arbitrarily. Let the subscript $t$ denote the current time step. Let $\rho_t$ denote the “importance sampling" ratio: $$\rho_t = \frac{\pi(S_t,A_t)}{b(S_t, A_t)},$$ where $S_t$ and $A_t$ are the state and action occuring on time step $t$. Let $\bar\ph_t$ denote the expected next feature vector, defined by: $$\bar\ph_t = \sum_{a \in {\mathcal{A}}} \pi(S_t,a)\ph(S_t,a)$$ Then the following equations fully specify GQ(${\lambda}$): $$\delta_t = r(S_t,A_t,S_{t+1}) + {\gamma}(S_{t+1})\th^\top_t \bar\ph_{t+1} - \th^\top_t \ph(S_t,A_t)$$ $$\th_{t+1} = \th_{t} + \alpha\left[\delta_t{{\bm e}}_t - {\gamma}(S_{t+1})(1 - {\lambda}(S_{t+1}))({{\bm w}}^\top_t {{\bm e}}_t)\bar\ph_{t+1}\right]$$ $${{\bm w}}_{t+1} = {{\bm w}}_t + \alpha\eta[\delta_t{{\bm e}}_t  - ({{\bm w}}^\top_t \ph(S_t,A_t))\ph(S_t,A_t)]$$ $${{\bm e}}_t = I(S_t)\ph(S_t,A_t) + {\gamma}(S_t) {\lambda}(S_t)\rho_t{{\bm e}}_{t-1}$$

Pseudocode
==========

The following pseudocode characterizes the algorithm and its use.

Code
====

The files [GQlambda.java]{} and [GQlambda.cpp]{} (in the arXiv source archive) contain implementations of the GQlearn function described in the pseudocode. We have excluded optimizations (e.g., binary features or efficient trace implementation) to ensure the code is simple and easy to understand. We leave it to the reader to provide environment code for interfacing to GQ(${\lambda}$) (e.g., using RL-Glue).

References
==========

Maei, H. R., Szepesvári, Cs., Bhatnagar, S., Sutton, R. S. (2010). Toward off-policy learning control with function approximation. In [*Proceedings of the 27th International Conference on Machine Learning*]{}, Haifa, Israel.

Maei, H. R. and Sutton, R. S. (2010). GQ(${\lambda}$): A general gradient algorithm for temporal-difference prediction learning with eligibility traces. In [*Proceedings of the Third Conference on Artificial General Intelligence*]{}, pp. 91–96.

Modayil, J., White, A., Sutton, R. S. (2014). Multi-timescale nexting in a reinforcement learning robot. *Adaptive Behavior 22*(2):146–160.

Sutton, R. S., Barto, A. G. (1998). Reinforcement Learning: An Introduction. MIT Press.
