Finite-Sample Analysis of Proximal Gradient TD Algorithms

INTRODUCTION

Obtaining a true stochastic gradient temporal difference method has been a longstanding goal of reinforcement learning (RL) (Bertsekas and Tsitsiklis, 1996; Sutton and Barto, 1998), ever since it was discovered that the original TD method was unstable in many off-policy scenarios where the target behavior being learned and the exploratory behavior producing samples differ. Sutton et al. (2008, 2009) proposed the family of gradient-based temporal difference (GTD) algorithms which offer several interesting properties. A key property of this class of GTD algorithms is that they are asymptotically off-policy convergent, which was shown using stochastic approximation (Borkar, 2008). This is quite important when we notice that many RL algorithms, especially those that are based on stochastic approximation, such as TD($\lambda$), 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ári (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 a rather ad-hoc splitting of terms. In this paper, we take a major step forward in resolving this problem by showing 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).

Since in real-world applications of RL, we have access to only a finite amount of data, finite-sample analysis of gradient TD algorithms is essential as it clearly shows the effect of the number of samples (and the parameters that play a role in the sampling budget of the algorithm) in their final performance. However, most of the work on finite-sample analysis in RL has been focused on batch RL (or approximate dynamic programming) algorithms (e.g., Kakade and Langford 2002; Munos and Szepesvári 2008; Antos et al. 2008; Lazaric et al. 2010a), especially those that are least squares TD (LSTD)-based (e.g., Lazaric et al. 2010b; Ghavamzadeh et al. 2010, 2011; Lazaric et al. 2012), and more importantly restricted to the on-policy setting. In this paper, we provide the finite-sample analysis of the GTD family of algorithms, a relatively novel class of gradient-based TD methods that are guaranteed to converge even in the off-policy setting, and for which, to the best of our knowledge, no finite-sample analysis has been reported. This analysis is challenging because 1) the stochastic approximation methods that have been used to prove the asymptotic convergence of these algorithms do not address convergence rate analysis; 2) as we explain in detail in Section 2.1, the techniques used for the analysis of the stochastic gradient methods cannot be applied here; 3) finally, the difficulty of finite-sample analysis in the off-policy setting.

The major contributions of this paper include the first finite-sample analysis of the class of gradient TD algorithms, as well as the design and analysis of several improved GTD methods that result from our novel approach of formulating gradient TD methods as true stochastic gradient algorithms w.r.t. a saddle-point objective function. We then use the techniques applied in the analysis of the stochastic gradient methods to propose a unified finite-sample analysis for the previously proposed as well as our novel gradient TD algorithms. Finally, given the results of our analysis, we study the GTD class of algorithms from several different perspectives, including acceleration in convergence, learning with biased importance sampling factors, etc.

PRELIMINARIES

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

We denote by $\pi_{b}$, the behavior policy that generates the data, and by $\pi$, 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 $(s_{i},a_{i})$, such that $\pi_{b}(a_{i}|s_{i})>0$, we define the importance-weighting factor $\rho_{i}=\pi(a_{i}|s_{i})/\pi_{b}(a_{i}|s_{i})$ with $\rho_{\max}\geq 0$ being its maximum value over the state-action pairs.

where the expectations are w.r.t. $\xi$ and $P^{\pi_{b}}$. We also denote by $\Xi$, the diagonal matrix whose elements are $\xi(s)$, and ${\xi_{\max}}:={\max_{s}}\xi(s)$. For each sample $i$ in the training set $\mathcal{D}$, we can calculate an unbiased estimate of $A$, $b$, and $C$ as follows:

The class of gradient-based TD (GTD) algorithms were proposed by 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)It is important to note that $T$ in (5) and (6) is $T^{\pi}$, the Bellman operator of the target policy $\pi$.

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).

Let \mathcal{D}=\big{\{}\big{(}s_{i},a_{i},r_{i},s^{\prime}_{i}\big{)}\big{\}}_{i=1}^{n},\;s_{i}\sim\xi,\;a_{i}\sim\pi_{b}(\cdot|s_{i}),\;s^{\prime}_{i}\sim P(\cdot|s_{i},a_{i}) be a training set generated by the behavior policy $\pi_{b}$ and $T$ be the Bellman operator of the target policy $\pi$. 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 $\theta$ 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ári, 2010). Consider the NEU objective function in (5). Taking its gradient w.r.t. $\theta$, we obtain

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. (2008, 2009), a sample $({s_{i}},{a_{i}},{r_{i}},s^{\prime}_{i})$ is rejected and the parameter $\theta$ does not update for this sample, if $\pi(a_{i}|s_{i})=0$. This sampling strategy is not efficient since a lot of samples will be discarded if $\pi_{b}$ and $\pi$ are very different.

2 RELATED WORK

Before we present a finite-sample performance bound for GTD and GTD2, it would be helpful to give a brief overview of the existing literature on finite-sample analysis of the TD algorithms. The convergence rate of the TD algorithms mainly depends on $(d,n,\nu)$, where $d$ is the size of the approximation space (the dimension of the feature vector), $n$ is the number of samples, and $\nu$ is the smallest eigenvalue of the sample-based covariance matrix $\hat{C}=\hat{\Phi}^{\top}\hat{\Phi}$, i.e., $\nu=\lambda_{\min}(\hat{C})$.

The line of research reported here has much in common with work on proximal reinforcement learning (Mahadevan et al., 2014), which explores first-order reinforcement learning algorithms using mirror maps (Bubeck, 2014; Juditsky et al., 2008) to construct primal-dual spaces. This work began originally with 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), where the objective function is the norm of the approximation residual of a linear inverse problem (Ávila Pires and Szepesvári, 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 convex-concave saddle-point formulations of NEU and MSPBE.

SADDLE-POINT FORMULATION OF GTD ALGORITHMS

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 SGs in order 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 Mirror-Prox (SMP) (Juditsky et al., 2008), to derive more efficient versions of GTD and GTD2.

A particular type of convex-concave saddle-point formulation is formally defined as

where $F(\theta)$ is a convex function and $K(y)$ is a smooth convex function such that

Next we follow Juditsky et al. (2008); Nemirovski et al. (2009); Chen et al. (2013) and define the following error function for the saddle-point problem (11).

The error function of the saddle-point problem (11) at each point $(\theta^{\prime},y^{\prime})$ is defined as

In this paper, we consider the saddle-point problem (11) with $F(\theta)=0$ and $K(y)=\frac{1}{2}||y||_{M}^{2}$, i.e.,

where $A$ and $b$ were defined by Eq. 3, and $M$ is a positive definite matrix. It is easy to show that $K(y)=\frac{1}{2}||y||^{2}_{M}$ satisfies the condition in Eq. 12.

We first show in Proposition 1 that if $(\theta^{*},y^{*})$ is the saddle-point of problem (14), then $\theta^{*}$ 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.

For any fixed $\theta$, we have $\frac{1}{2}J(\theta)=\mathop{\max}_{y}L(\theta,y)$, where $J(\theta)$ is defined by Eq. 7.

Since $L(\theta,y)$ is an unconstrained quadratic program w.r.t. $y$, the optimal $y^{*}(\theta)=\arg\max_{y}L(\theta,y)$ can be analytically computed as

The result follows by plugging $y^{*}$ into (14) and using the definition of $J(\theta)$ in Eq. 7 and Lemma 1. ∎

GTD and GTD2 are true stochastic gradient algorithms w.r.t. the objective function $L(\theta,y)$ of the saddle-point problem (14) with $M=I$ and $M=C={\Phi^{\top}}\Xi\Phi$ (the covariance matrix), respectively.

It is easy to see that the gradient updates of the saddle-point problem (14) (ascending in $y$ and descending in $\theta$) may be written as

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

FINITE-SAMPLE ANALYSIS

In this section, we provide a finite-sample analysis for a revised version of the GTD/GTD2 algorithms. We first describe the revised GTD algorithms in Section 4.1 and then dedicate the rest of Section 4 to their sample analysis. Note that from now on we use the $M$ matrix (and its unbiased estimate $\hat{M}_{t}$) to have a unified analysis for GTD and GTD2 algorithms. As described earlier, $M$ is replaced by the identity matrix $I$ in GTD and by the covariance matrix $C$ (and its unbiased estimate $\hat{C}_{t}$) in GTD2.

The revised GTD algorithms that we analyze in this paper (see Algorithm 1) have three differences with the standard GTD algorithms of Eqs. 8 and 9 (and Eq. 16). 1) We guarantee that the parameters $\theta$ and $y$ remain bounded by projecting them onto bounded convex feasible sets $\Theta$ and $Y$ defined in Assumption 2. In Algorithm 1, we denote by $\Pi_{\Theta}$ and $\Pi_{Y}$, the projection into sets $\Theta$ and $Y$, respectively. This is standard in stochastic approximation algorithms and has been used in off-policy TD($\lambda$) (Yu, 2012) and actor-critic algorithms (e.g., Bhatnagar et al. 2009). 2) after $n$ iterations ($n$ is the number of training samples in $\mathcal{D}$), the algorithms return the weighted (by the step size) average of the parameters at all the $n$ iterations (see Eq. 18). 3) The step-size $\alpha_{t}$ is selected as described in the proof of Proposition 3 in the supplementary material. Note that this fixed step size of $O(1/\sqrt{n})$ is required for the high-probability bound in Proposition 3 (see Nemirovski et al. 2009 for more details).

2 ASSUMPTIONS

In this section, we make several assumptions on the MDP and basis functions that are used in our finite-sample analysis of the revised GTD algorithms. These assumptions are quite standard and are similar to those made in the prior work on GTD algorithms (Sutton et al., 2008, 2009; Maei, 2011) and those made in the analysis of SG algorithms (Nemirovski et al., 2009).

(Boundedness) Assume the features $(\phi_{i},\phi^{{}^{\prime}}_{i})$ have uniformly bounded second moments. This together with the boundedness of features (by $L$) and importance weights (by $\rho_{\max}$) guarantees that the matrices $A$ and $C$, and vector $b$ are uniformly bounded.

This assumption guarantees that for any $(\theta,y)\in\Theta\times Y$, the unbiased estimators of $b-A\theta-My$ and $A^{\top}y$, i.e.,

where $\sigma_{1}$ and $\sigma_{2}$ are non-negative constants. We further define

Assumption 4 also gives us the following “light-tail” assumption. There exist constants ${M_{*,\theta}}$ and ${M_{*,y}}$ such that

This “light-tail” assumption is equivalent to the assumption in Eq. 3.16 in Nemirovski et al. (2009) and is necessary for the high-probability bound of Proposition 3. We will show how to compute ${M_{*,\theta}},{M_{*,y}}$ in the Appendix.

3 FINITE-SAMPLE PERFORMANCE BOUNDS

The finite-sample performance bounds that we derive for the GTD algorithms in this section are for the case that the training set $\mathcal{D}$ has been generated as discussed in Section 2. We further discriminate between the on-policy ($\pi=\pi_{b}$) and off-policy ($\pi\neq\pi_{b}$) scenarios. The sampling scheme used to generate $\mathcal{D}$, in which the first state of each tuple, $s_{i}$, is an i.i.d. sample from a distribution $\xi$, also considered in the original GTD and GTD2 papers, for the analysis of these algorithms, and not in the experiments (Sutton et al., 2008, 2009). Another scenario that can motivate this sampling scheme is when we are given a set of high-dimensional data generated either in an on-policy or off-policy manner, and $d$ is so large that the value function of the target policy cannot be computed using a least-squares method (that involves matrix inversion), and iterative techniques similar to GTD/GTD2 are required.

We first derive a high-probability bound on the error function of the saddle-point problem (14) at the GTD solution $(\bar{\theta}_{n},\bar{y}_{n})$. Before stating this result in Proposition 3, we report the following lemma that is used in its proof.

Let $(\bar{\theta}_{n},\bar{y}_{n})$ be the output of the GTD algorithm after $n$ iterations (see Eq. 18). Then, with probability at least $1-\delta$, we have

where ${\rm{Err}}({\bar{\theta}_{n}},{\bar{y}_{n}})$ is the error function of the saddle-point problem (14) defined by Eq. 13, $R$ defined in Assumption 2, $\sigma$ is from Eq. 21, and $\tau=\sigma_{\max}(M)$ is the largest singular value of $M$, which means $\tau=1$ for GTD and $\tau=\sigma_{\max}(C)$ for GTD2.

Let $\bar{\theta}_{n}$ be the output of the GTD algorithm after $n$ iterations (see Eq. 18). Then, with probability at least $1-\delta$, we have

From Proposition 1, for any $\theta$, we have

Given Assumption 3, the system of linear equations $A\theta=b$ has a solution $\theta^{*}$, i.e., the (off-policy) fixed-point $\theta^{*}$ exists, and thus, we may write

In this case, we also haveWe may write the second inequality as an equality for our saddle-point problem defined by Eq. 14.

From Eq. 26, for any $(\theta,y)\in\Theta\times Y$ including $(\bar{\theta}_{n},\bar{y}_{n})$, we may write

Since $||A\bar{\theta}_{n}-b||_{\xi}^{2}\leq\tau\xi_{\max}\;||A\bar{\theta}_{n}-b||_{M^{-1}}^{2}$, where $\tau$ is the largest singular value of $M$, we have

The proof follows by combining Eqs. 28 and Proposition 3. It completes the proof. ∎

With the results of Proposition 3 and Theorem 1, we are now ready to derive finite-sample bounds on the performance of GTD/GTD2 in both on-policy and off-policy settings.

In this section, we consider the on-policy setting in which the behavior and target policies are equal, i.e., $\pi_{b}=\pi$, and the sampling distribution $\xi$ is the stationary distribution of the target policy $\pi$ (and the behavior policy $\pi_{b}$). We use Lemma 3 to derive our on-policy bound. The proof of this lemma can be found in Geist et al. (2012).

For any parameter vector $\theta$ and corresponding $\hat{v}=\Phi\theta$, the following equality holds

Using Lemma 3, we derive the following performance bound for GTD/GTD2 in the on-policy setting.

Let $V$ be the value of the target policy and ${{\bar{v}}_{n}}=\Phi{{\bar{\theta}}_{n}}$, where $\bar{\theta}_{n}$ defined by (18), be the value function returned by on-policy GTD/GTD2. Then, with probability at least $1-\delta$, we have

where $\rm{Err}(\bar{\theta}_{n},\bar{y}_{n})$ is upper-bounded by Eq. 24 in Proposition 3, with $\rho_{\max}=1$ (on-policy setting).

Remark: It is important to note that Proposition 4 shows that the error in the performance of the GTD/GTD2 algorithm in the on-policy setting is of $O\left({\frac{{{L^{2}}d\sqrt{\tau{\xi_{\max}}\log\frac{1}{\delta}}}}{{{n^{1/4}\nu}}}}\right)$. Also note that the term $\frac{\tau}{\nu}$ in the GTD2 bound is the conditioning number of the covariance matrix $C$.

3.2 Off-Policy Performance Bound

In this section, we consider the off-policy setting in which the behavior and target policies are different, i.e., $\pi_{b}\neq\pi$, and the sampling distribution $\xi$ is the stationary distribution of the behavior policy $\pi_{b}$. We assume that off-policy fixed-point solution exists, i.e., there exists a $\theta^{*}$ satisfying $A\theta^{*}=b$. Note that this is a direct consequence of Assumption 3 in which we assumed that the matrix $A$ in the off-policy setting is non-singular. We use Lemma 4 to derive our off-policy bound. The proof of this lemma can be found in Kolter (2011). Note that $\kappa(\bar{D})$ in his proof is equal to $\sqrt{\rho_{\max}}$ in our paper.

If $\Xi$ satisfies the following linear matrix inequality

and let $\theta^{*}$ be the solution to $A\theta^{*}=b$, then we have

Note that the condition on $\Xi$ in Eq. 33 guarantees that the behavior and target policies are not too far away from each other. Using Lemma 4, we derive the following performance bound for GTD/GTD2 in the off-policy setting.

Let $V$ be the value of the target policy and ${{\bar{v}}_{n}}=\Phi{{\bar{\theta}}_{n}}$, where $\bar{\theta}_{n}$ is defined by (18), be the value function returned by off-policy GTD/GTD2. Also let the sampling distribution $\Xi$ satisfies the condition in Eq. 33. Then, with probability at least $1-\delta$, we have

ACCELERATED ALGORITHM

As discussed at the beginning of Section 3, 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, as we will show in Section 4, 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 Mirror-Prox (SMP) (Juditsky et al., 2008) is an “almost dimension-free” 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:For simplicity, we only describe mirror-prox GTD methods where the mirror map is identity, which can also be viewed as extragradient (EG) GTD methods. Mahadevan et al. (2014) gives a more detailed discussion of a broad range of mirror maps in RL.

After $T$ iterations, these algorithms return ${\bar{\theta}_{T}}:=\frac{{\sum\nolimits_{t=1}^{T}{{\alpha_{t}}{\theta_{t}}}}}{{\sum\nolimits_{t=1}^{T}{{\alpha_{t}}}}}$ and ${\bar{y}_{T}}:=\frac{{\sum\nolimits_{t=1}^{T}{{\alpha_{t}}{y_{t}}}}}{{\sum\nolimits_{t=1}^{T}{{\alpha_{t}}}}}$. The details of the algorithm is shown in Algorithm 2, and the experimental comparison study between GTD2 and GTD2-MP is reported in Section 7.

FURTHER 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. For simplicity, we will discuss the error bound of $\frac{1}{2}||A\theta-b||_{{M^{-1}}}^{2}$, and the corresponding error bound of $\frac{1}{2}||A\theta-b||_{\xi}^{2}$ and $\|V-{\bar{v}}_{n}|{|_{\xi}}$ can be likewise derived as in above analysis. As can be seen from the above analysis, the convergence rate of the GTD algorithms family is

In this section, we raise an 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 (14) is

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

and stochastic accelerated primal-dual (SAPD) method (Chen et al., 2013) which can reach the optimal convergence rate in (38). 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.

The importance weight factor $\rho_{t}$ is lower bounded by , but yet may have an arbitrarily large upper bound. In real applications, the importance weight factor $\rho_{t}$ may not be estimated exactly, i.e., the estimation $\hat{\rho}_{t}$ is a biased estimation of the true $\rho_{t}$. To this end, the stochastic gradient we obtained is not the unbiased gradient of $L(\theta,y)$ anymore. This falls into a broad category of learning with inexact stochastic gradient, or termed as stochastic gradient methods with an inexact oracle (Devolder, 2011). Given the inexact stochastic gradient, the convergence rate and performance bound become much worse than the results with exact stochastic gradient. Based on the analysis by Juditsky et al. (2008), we have the error bound for inexact estimation of $\rho_{t}$.

This implies that the inexact estimation of $\rho_{t}$ may cause disastrous estimation error, which implies that an exact estimation of $\rho_{t}$ is very important.

3 FINITE-SAMPLE ANALYSIS OF ONLINE LEARNING

Another more challenging scenario is online learning scenario, where the samples are interactively generated by the environment, or by an interactive agent. The difficulty lies in that the sample distribution does not follow i.i.d sampling condition anymore, but follows an underlying Markov chain $\mathcal{M}$. If the Markov chain $\mathcal{M}$’s mixing time is small enough, i.e., the sample distribution reduces to the stationary distribution of $\pi_{b}$ very fast, our analysis still applies. However, it is usually the case that the underlying Markov chain’s mixing time $\tau_{\rm{mix}}$ is not small enough. The analysis result can be obtained by extending the result of recent work (Duchi et al., 2012) from strongly convex loss functions to saddle-point problems, which is non-trivial and is thus left for future work.

4 DISCUSSION OF TDC ALGORITHM

EMPIRICAL EVALUATION

In this section, we compare the previous GTD2 method with our proposed GTD2-MP method using various domains with regard to their value function approximation performance capability. 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 $\alpha=0.005$ for GTD2 and $\alpha=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.

2 505050-STATE CHAIN DOMAIN

The 50 state chain (Lagoudakis and Parr, 2003) is a standard MDP domain. There are 50 discrete states $\{{s_{i}}\}_{i=1}^{50}$ and two actions moving the agent left ${s_{i}}\to{s_{\max({{i-1}},1)}}$ and right ${s_{i}}\to{s_{\min({{i+1}},50)}}$. The actions succeed with probability $0.9$; failed actions move the agent in the opposite direction. The discount factor is $\gamma=0.9$. The agent receives a reward of $+1$ when in states $s_{10}$ and $s_{41}$. All other states have a reward of . In this experiment, we compare the performance of the value approximation w.r.t different set of stepsizes $\alpha=0.0001,0.001,0.01,0.1,0.2,\cdots,0.9$ using the BEBF basis (Parr et al., 2007), and Figure 2 shows the value function approximation result, where the cyan curve is the true value function, the red dashed curve is the GTD result,and the black curve is the GTD2-MP result. From the figure, one can see that GTD2-MP is much more robust with stepsize choice than the GTD2 algorithm.

3 ENERGY MANAGEMENT DOMAIN

In this experiment we compare the performance of the algorithms on 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\theta=b$ does not have a solution, and thus the optimal MSPBE($\theta^{*}$) (resp. MSBE($\theta^{*}$) ) do not reduce to . The result is averaged over $200$ runs, and $\alpha=0.001$ for both GTD2 and GTD2-MP is chosen via comparison studies for each algorithm. As can be seen from FIgure 3, in the initial transit state, GTD2-MP performs much better than GTD2 at the transient state. Then after reaching the steady state, as can be seen from Table 1, we can see that GTD2-MP reaches better steady state solution than the GTD algorithm. Based on the above empirical results and many other experiments we have conducted in other domains, we can conclude that GTD2-MP usually performs much better than the “vanilla” GTD2 algorithm.

SUMMARY

In this paper, we showed how gradient TD methods can be shown to be true stochastic gradient methods with respect to a saddle-point primal-dual objective function, which paved the way for the finite-sample analysis of off-policy convergent gradient-based temporal difference learning algorithms such as GTD and GTD2. Both error bound and performance bound are provided, which shows that the value function approximation bound of the GTD algorithms family is $O\left({\frac{d}{{{n^{1/4}}}}}\right)$. Further, two revised algorithms, namely the projected GTD2 algorithm and the accelerated GTD2-MP algorithm, are proposed. There are many interesting directions for future research. Our framework can be easily used to design regularized sparse gradient off-policy TD methods. One interesting direction is to investigate the convergence rate and performance bound for the TDC algorithm, which lacks a saddle-point formulation. The other is to explore tighter value function approximation bounds for off-policy learning.

Acknowledgements

This material is based upon work supported by the National Science Foundation under Grant Nos. IIS-1216467. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF.

References

Appendix A PROOF OF LEMMA 2

From the boundedness of the features (by $L$) and the rewards (by ${{\rm{R}}_{\max}}$), we have

The second inequality is obtained by the consistent inequality of matrix norm, the third inequality comes from the triangular norm inequality, and the fourth inequality comes from the vector norm inequality $||\phi(s)|{|_{2}}\leq||\phi(s)|{|_{\infty}}\sqrt{d}\leq L\sqrt{d}$. The bound on $||b||_{2}$ can be derived in a similar way as follows.

Appendix B PROOF OF PROPOSITION 3

The proof of Proposition 3 mainly relies on Proposition 3.2 in Nemirovski et al. (2009). We just need to map our convex-concave stochastic saddle-point problem in Eq. 14, i.e.,

For our problem, the stochastic sub-gradient vector $G$ is defined as

This guarantees that the deterministic sub-gradient vector

is well-defined, i.e., $g_{\theta}(\theta,y)\in\partial_{\theta}L(\theta,y)$ and $g_{y}(\theta,y)\in\partial_{y}L(\theta,y)$.

modulus $1$ w.r.t. $||\cdot||_{2}$, and thus, $\Theta^{o}=\Theta$ and $Y^{o}=Y$ (see pp. 1581 and 1582 in Nemirovski et al. 2009). This allows us to equip the set $Z=\Theta\times Y$ with the distance generating function

where $D_{\theta}$ and $D_{y}$ defined in Assumption 2.

To bound these two quantities, we use the following equality that holds for any random variable $x$:

where these inequalities come from the definition of $\sigma_{1}$ in Eq. 20 and the boundedness of the feasible sets in Assumption 2. This means that in our case we can compute $M_{*,\theta}^{2},M_{*,y}^{2}$ as

where the inequality comes from the fact that $\forall a,b,c\geq 0,a^{2}+b^{2}+c^{2}\leq(a+b+c)^{2}$. Thus, we may write $M_{*}$ as

Now we have all the pieces ready to apply Proposition 3.2 in Nemirovski et al. (2009) and obtain a high-probability bound on ${\rm{Err}}({\bar{\theta}_{n}},{\bar{y}_{n}})$, where $\bar{\theta}_{n}$ and $\bar{y}_{n}$ (see Eq. 18) are the outputs of the revised GTD algorithm in Algorithm 1. From Proposition 3.2 in Nemirovski et al. (2009), if we set the step-size in Algorithm 1 (our revised GTD algorithm) to $\alpha_{t}=\frac{2c}{M_{*}\sqrt{5n}}$, where $c>0$ is a positive constant, $M_{*}$ is defined by Eq. 41, and $n$ is the number of training samples in $\mathcal{D}$, with probability of at least $1-\delta$, we have

Note that we obtain Eq. 42 by setting $c=1$ and the “light-tail” assumption in Eq. 4.2 guarantees that we satisfy the condition in Eq. 3.16 in Nemirovski et al. (2009), which is necessary for the high-probability bound in their Proposition 3.2 to hold. The proof is complete by replacing $||A||_{2}$ and $||b||_{2}$ from Lemma 2. ∎

Appendix C PROOF OF PROPOSITION 4

Since $P$ is the kernel matrix of the target policy $\pi$ and $\Pi$ is the orthogonal projection w.r.t. $\xi$, the stationary distribution of $\pi$, we may write

Moreover, we may upper-bound the term $||\Phi C^{-1}(b-A\bar{\theta}_{n})||_{\xi}$ in (43) using the following inequalities:

where the third inequality is the result of upper-bounding $||(b-A\bar{\theta}_{n})||_{M}^{-1}$ using Eq. 28 and the fact that $\nu=1/||{C^{-1}}||{{}^{2}_{2}}=1/{\lambda_{\max}}({C^{-1}})={\lambda_{\min}}(C)$ ($\nu$ is the smallest eigenvalue of the covariance matrix $C$). ∎

Appendix D PROOF OF PROPOSITION 5

Using the triangle inequality, we may write

The second term on the right-hand side of Eq. 44 can be upper-bounded by Lemma 4. Now we upper-bound the first term as follows:

where ${\tau_{C}}={\sigma_{\max}}(C)$ is the largest singular value of $C$, and ${\sigma_{\min}}({A^{\top}}{M^{-1}}A)$ is the smallest singular value of ${{A^{\top}}{M^{-1}}A}$. Using the result of Theorem 1, with probability at least $1-\delta$, we have

From Eqs. 44, 34, and 46, the result of Eq. 35 can be derived, which completes the proof. ∎