Proximal Gradient Temporal Difference Learning Algorithms

1 Introduction

Designing a true stochastic gradient unconditionally stable temporal difference (TD) method with finite-sample convergence analysis has been a longstanding goal of reinforcement learning (RL) [Bertsekas and Tsitsiklis, 1996; Sutton and Barto, 1998]. It was discovered more than two decades ago that the original TD method was unstable in many offpolicy scenarios where the target behavior being learned and the exploratory behavior producing samples differ by Baird and others [Baird, 1995]. Sutton et al.; Sutton et al. [2008; 2009] proposed the family of gradient-based temporal difference (GTD) algorithms to address the limitations of the standard TD algorthm. A key property of this class of GTD algorithms is that they are asymptotically off-policy convergent, which was shown using the framework of stochastic approximation [Borkar, 2008]. Many RL algorithms, especially those that are based on stochastic approximation, such as TD(λ), do not have convergence guarantees in the off-policy setting. Unfortunately, this class of GTD algorithms are not true stochastic gradient methods with respect to their original objective functions, as pointed out in Szepesv´ari [2010]. The reason is not surprising: the gradient of the objective functions used involve products of terms, which cannot be sampled directly, and was decomposed by an ad-hoc splitting of terms. In this paper, we show a principled way of designing true stochastic gradient TD algorithms by using a primal-dual saddle point objective function, derived from the original objective functions, coupled with the principled use of operator splitting [Bauschke and Combettes, 2011].

2 Preliminaries

Reinforcement Learning (RL) [Bertsekas and Tsitsiklis, 1996; Sutton and Barto, 1998] is a class of learning problems in which an agent interacts with an unfamiliar, dynamic and stochastic environment, where the agent's goal is to optimize some measure of its long-term performance. This interaction is conventionally modeled as a Markov decision process (MDP). A MDP is defined as the tuple (S↪ A↪ P a ss0 ↪ R↪ γ), where S and A are the sets of states and actions, the transition kernel P a ss0 specifying the probability of transition from state s 2 S to state s0 2 S by taking action a 2 A, R(s↪ a) : S ⇥ A ! R is the reward function bounded by Rmax., and 0  γ < 1 is a discount factor. A stationary policy ⇡ : S ⇥ A ! [0↪ 1] is a probabilistic mapping from states to actions. The main objective of a RL algorithm is to find an optimal policy. In order to achieve this goal, a key step in many algorithms is to calculate the value function of a given policy ⇡, i.e., V ⇡ : S ! R, a process known as policy evaluation. It is known that V ⇡ is the unique fixed-point of the Bellman operator T ⇡ , i.e.,

where R⇡ and P ⇡ are the reward function and transition kernel of the Markov chain induced by policy ⇡. In Eq. 1, we may imagine V ⇡ as a ♣S♣-dimensional vector and write everything in vector/matrix form. In the following, to simplify the notation, we often drop the dependence of T ⇡ , V ⇡ , R⇡ , and P ⇡ to ⇡.

We denote by ⇡b, the behavior policy that generates the data, and by ⇡, the target policy that we would like to evaluate. They are the same in the on-policy setting and different in the off-policy scenario. For each state-action pair (si↪ ai), such that ⇡b(ai♣si) > 0, we define the importance-weighting factor ⇢i = ⇡(ai♣si)◁⇡b(ai♣si) with ⇢max ≥ 0 being its maximum value over the state-action pairs.

When S is large or infinite, we often use a linear approximation architecture for V ⇡ with parameters ✓ 2 Rd and L-bounded basis functions ¶'i♦di=1 , i.e., 'i : S ! R and maxi ♣♣'i♣♣1  L. We denote by φ(·) = ('1(·)↪ ▷ ▷ ▷ ↪ 'd(·))> the feature vector and by F the linear function space spanned by the basis functions ¶'i♦di=1 , i.e., F = {f✓ ♣ ✓ 2 Rd and f✓(·) = φ(·)>✓ . We may write the approximation of V in F in the vector form as ˆ v = Φ✓, where Φ is the ♣S♣ ⇥ d feature matrix. When only n training samples of the form D = {(si↪ ai↪ ri = r(si↪ ai)↪ s0i ) ni=1 ↪ si ⇠ ⇠↪ ai ⇠ ⇡b(·♣si)↪ s0i ⇠ P(·♣si↪ ai), are available (⇠ is a distribution over the state space S), we may write the empirical Bellman operator ˆ T for a function in F as

where ˆΦ (resp. ˆΦ0 ) is the empirical feature matrix of size n⇥ d, whose i-th row is the feature vector φ(si)> (resp. φ(s0i )>), and ˆR 2 Rn is the reward vector, whose i-th element is ri. We denote by δi(✓) = ri +γφ0> i ✓-φ>i ✓, the TD error for the i-th sample (si↪ ri↪ s0i ) and define ∆φi = φi - γφ0i . Finally, we define the matrices A and C, and the vector b as

A := E⇥⇢iφi(∆φi)>⇤↪ b := E [⇢iφiri] ↪ C := E[φiφ>i ]↪ (3) where the expectations are w.r.t. ⇠ and P ⇡b . We also denote by ⌅, the diagonal matrix whose elements are ⇠(s), and ⇠max := maxs⇠(s). For each sample i in the training set D, we can calculate an unbiased estimate of A, b, and C as follows:ˆ

2.1 Gradient-Based TDAlgorithms

The class of gradient-based TD (GTD) algorithms were proposed by Sutton et al.; Sutton et al. [2008; 2009]. These algorithms target two objective functions: the norm of the expected TD update (NEU) and the mean-square projected Bellman error (MSPBE), defined as (see e.g., Maei 2011) 1

where C = E[φiφ>i ] = Φ>⌅Φ is the covariance matrix defined in Eq. 3 and is assumed to be non-singular, and ⇧ = Φ(Φ>⌅Φ)-1Φ>⌅ is the orthogonal projection operator into the function space F, i.e., for any bounded function g↪ ⇧g = argminf2F ♣♣g -f♣♣⇠. From (5) and (6), it is clear that NEU and MSPBE are square unweighted and weighted by C -1 , `2norms of the quantity Φ>⌅(Tˆ v - ˆ v), respectively, and thus, the two objective functions can be unified as

with M equals to the identity matrix I for NEU and to the covariance matrix C for MSPBE. The second equality in (7) holds because of the following lemma from Section 4.2 in Maei [2011].

1 It is important to note that T in (5) and (6) is T ⇡ , the Bellman operator of the target policy ⇡.

Lemma 1. Let D = {(si↪ ai↪ ri↪ s0i ) ni=1 ↪ si ⇠ ⇠↪ ai ⇠ ⇡b(·♣si)↪ s0i ⇠ P(·♣si↪ ai) be a training set generated by the behavior policy ⇡b and T be the Bellman operator of the target policy ⇡. Then, we have

Motivated by minimizing the NEU and MSPBE objective functions using the stochastic gradient methods, the GTD and GTD2 algorithms were proposed with the following update rules:

However, it has been shown that the above update rules do not update the value function parameter ✓ in the gradient direction of NEU and MSPBE, and thus, NEU and MSPBE are not the true objective functions of the GTD and GTD2 algorithms [Szepesv´ari, 2010]. Consider the NEU objective function in (5). Taking its gradient w.r.t. ✓, we obtain

If the gradient can be written as a single expectation, then it is straightforward to use a stochastic gradient method. However, we have a product of two expectations in (10), and unfortunately, due to the correlation between them, the sample product (with a single sample) won't be an unbiased estimate of the gradient. To tackle this, the GTD algorithm uses an auxiliary variable yt to estimate E⇥⇢iδi(✓)φi ⇤, and thus, the overall algorithm is no longer a true stochastic gradient method w.r.t. NEU. It can be easily shown that the same problem exists for GTD2 w.r.t. the MSPBE objective function. This prevents us from using the standard convergence analysis techniques of stochastic gradient descent methods to obtain a finite-sample performance bound for the GTD and GTD2 algorithms.

It should be also noted that in the original publications of GTD/GTD2 algorithms [Sutton et al., 2008; 2009], the authors discussed handling the off-policy scenario using both importance and rejected sampling. In rejected sampling that was mainly used in Sutton et al.; Sutton et al. [2008; 2009], a sample (si↪ ai↪ ri↪ s0i ) is rejected and the parameter ✓ does not update for this sample, if ⇡(ai♣si) = 0. This sampling strategy is not efficient since a lot of samples will be discarded if ⇡b and ⇡ are very different.

2.2 RelatedWork

The line of research reported here began with the development of a broad framework called proximal reinforcement learning [Mahadevan et al., 2014], which explores firstorder reinforcement learning algorithms using mirror maps

[Bubeck, 2014; Juditsky et al., 2008] to construct primaldual spaces. This framework led to a dual space formulation of first-order sparse TD learning [Mahadevan and Liu, 2012]. A saddle point formulation for off-policy TD learning was initially explored in Liu et al. [2012] and later in Valcarcel Macua et al. [2015], where the objective function is the norm of the approximation residual of a linear inverse problem [ ´Avila Pires and Szepesv´ari, 2012]. A sparse off-policy GTD2 algorithm with regularized dual averaging is introduced by Qin and Li [2014]. These studies provide different approaches to formulating the problem, first as a variational inequality problem [Juditsky et al., 2008; Mahadevan et al., 2014] or as a linear inverse problem [Liu et al., 2012], or as a quadratic objective function (MSPBE) using two-time-scale solvers [Qin and Li, 2014]. In this paper, we are going to explore the true nature of the GTD algorithms as stochastic gradient algorithm w.r.t the convexconcave saddle-point formulations of NEU and MSPBE.

3 AlgorithmAnalysis

3.1 Saddle-Point Formulation of GTDAlgorithms

In this section, we show how the GTD and GTD2 algorithms can be formulated as true stochastic gradient (SG) algorithms by writing their respective objective functions, NEU and MSPBE, in the form of a convex-concave saddle-point. As discussed earlier, this new formulation of GTD and GTD2 as true SG methods allows us to use the convergence analysis techniques for SG methods to derive finite-sample performance bounds for these RL algorithms. Moreover, it allows us to use more efficient algorithms that have been recently developed to solve SG problems, such as stochastic MirrorProx (SMP) [Juditsky et al., 2008], to derive more efficient versions of GTD and GTD2.

In this paper, we consider the saddle-point problem formulation as follows,

where A and b were defined by Eq. 3, and M is a positive definite matrix.

We first show in Proposition 1 that if (✓⇤ ↪ y⇤ ) is the saddlepoint of problem (11), then ✓⇤ will be the optimum of NEU and MSPBE defined in Eq. 7. We then prove in Proposition 2 that GTD and GTD2 in fact find this saddle-point.

Proof. Since L(✓↪ y) is an unconstrained quadratic program w.r.t. y, the optimal y⇤ (✓) = argmaxy L(✓↪ y) can be analytically computed asy⇤ (✓) = M -1 (b - A✓)▷ (12)

The result follows by substituting y⇤ into (11) and using the definition of J(✓) in Eq. 7 and Lemma 1.

Proposition 2. GTD and GTD2 are true stochastic gradient algorithms w.r.t. the objective function L(✓↪ y) of the saddlepoint problem (11) with M = I and M = C = Φ>⌅Φ (the covariance matrix), respectively.

Proof. It is easy to see that the gradient updates of the saddlepoint problem (11) (ascending in y and descending in ✓) may be written as

We denote ˆM := 1 (resp. ˆM := ˆ C) for GTD (resp. GTD2). We may obtain the update rules of GTD and GTD2 by replacing A, b, and C in (13) with their unbiased estimates ˆ A, ˆb, and ˆ C from Eq. 4, which completes the proof.

3.2 Accelerated Algorithm

As discussed at the beginning of Section 3.1, this saddle-point formulation not only gives us the opportunity to use the techniques for the analysis of SG methods to derive finite-sample performance bounds for the GTD algorithms, but also it allows us to use the powerful algorithms that have been recently developed to solve the SG problems and derive more efficient versions of GTD and GTD2. Stochastic MirrorProx (SMP) [Juditsky et al., 2008] is an "almost dimensionfree" non-Euclidean extra-gradient method that deals with both smooth and non-smooth stochastic optimization problems (see Juditsky and Nemirovski 2011 and Bubeck 2014 for more details). Using SMP, we propose a new version of GTD/GTD2, called GTD-MP/GTD2-MP, with the following update formula: 2

and ¯ yT := PTt=1 ↵tyt PTt=1 ↵t . The details of the algorithm is shown in Algorithm 1, and the experimental comparison study between GTD2 and GTD2-MP is reported in Section 4.

After T iterations, these algorithms return ¯ ✓T := PTt=1 ↵t✓t PTt=1 ↵t

Algorithm 1 GTD2-MP

• 1: for t = 1↪ ▷ ▷ ▷ ↪ n do
• 2: Update parameters

• 3: end for
• 4: OUTPUT¯

2 For simplicity, we only describe mirror-prox GTD methods where the mirror map is identity, which can also be viewed as extragradient (EG) GTDmethods. [Mahadevan et al., 2014] gives a more detailed discussion of a broad range of mirror maps in RL.

3.3 Finite-Sample Analysis

In this section, we are going to discuss the convergence rate of the accelerated algorithms using off-the-shelf accelerated solvers for saddle-point problems. Due to space limitations, many details are relegated to a longer paper [Liu et al., 2015], where both error bounds and performance bounds are provided, which shows that the value function approximation bound of the GTD algorithms family is O ( d n1◁4 ). For simplicity, we will discuss the error bound of 12 ♣♣A✓-b♣♣2M-1 , and the corresponding error bound of 12 ♣♣A✓-b♣♣2⇠ and kV -¯ vn♣♣⇠ can be likewise derived, We show the convergence rate of the GTD algorithms family is

We also discuss the interesting question: what is the "optimal" GTD algorithm? To answer this question, we review the convex-concave formulation of GTD2. According to convex programming complexity theory [Juditsky et al., 2008], the un-improvable convergence rate of stochastic saddle-point problem (11) is

There are many readily available stochastic saddle-point solvers, such as stochastic Mirror-Prox (SMP) [Juditsky et al., 2008] algorithm, which leads to our proposed GTD2-MP algorithm. SMP is able to improve the convergence rate of our gradient TD method to:

Another example of an optimal solver is the stochastic accelerated primal-dual (SAPD) method [Chen et al., 2013] which can reach the optimal convergence rate in (16). Due to space limitations, we are unable to present a more complete description, and refer interested readers to Juditsky et al. [2008]; Chen et al. [2013]for more details.

4 Empirical Evaluation

In this section, we compare the previous GTD2 method with our proposed GTD2-MP method using various domains. It should be mentioned that since the major focus of this paper is on policy evaluation, the comparative study focuses on value function approximation and thus comparisons on control learning performance is not reported in this paper.

The Baird example [Baird, 1995] is a well-known example to test the performance of off-policy convergent algorithms. Constant stepsize ↵ = 0▷005 for GTD2 and ↵ = 0▷004 for GTD2-MP, which are chosen via comparison studies as in [Dann et al., 2014]. Figure 1 shows the MSPBE curve of GTD2, GTD2-MP of 8000 steps averaged over 200 runs. We can see that GTD2-MP has a significant improvement over the GTD2 algorithm wherein both the MSPBE and the variance are substantially reduced.

4.1 EnergyManagement Domain

In this experiment we compare the performance of the proposed algorithms using an energy management domain. The decision maker must decide how much energy to purchase or sell subject to stochastic prices. This problem is relevant in the context of utilities as well as in settings such as hybrid vehicles. The prices are generated from a Markov chain process. The amount of available storage is limited and it also degrades with use. The degradation process is based on the physical properties of lithium-ion batteries and discourages fully charging or discharging the battery. The energy arbitrage problem is closely related to the broad class of inventory management problems, with the storage level corresponding to the inventory. However, there are no known results describing the structure of optimal threshold policies in energy storage.

Note that since for this off-policy evaluation problem, the formulated A✓ = b does not have a solution, and thus the optimal MSPBE(✓⇤ ) (resp. MSBE(✓⇤ ) ) do not reduce to 0. The result is averaged over 200 runs, and ↵ = 0▷001 for both GTD2 and GTD2-MP is chosen via comparison studies for each algorithm. As can be seen from FIgure 2, in the initial transit state, GTD2-MP performs much better than GTD2 at the transient state. Based on the above empirical results and many other experiments we have conducted, we conclude that GTD2-MP usually performs much better than the "vanilla" GTD2 algorithm.

5 Summary

The proximal gradient TD framework yields a principled approach to designing off-policy convergent gradient TD algorithms. We proposed and analyzed a new family of gradient TD algorithms with a nearly optimal convergence rate.