Yafei Zhao^1*, Long Yang^2
1Department of Mathematics, Zhejiang International Studies University, Hangzhou, China.
²Chinese Academy of Sciences, Beijing, China.
DOI: 10.4236/jamp.2026.146117   PDF    HTML   XML   2 Downloads   31 Views   Citations

Abstract

In this paper, we propose a unification of gradient temporal difference (GTD) learning algorithm $\text{GQ}\left(\sigma ,\lambda \right)$ for off-policy learning. The proposed $\text{GQ}\left(\sigma ,\lambda \right)$ ranges from gradient $\text{Tree?Backup}\left(\lambda \right)$ to $\text{GQ}\left(\lambda \right)$ when $\sigma$ ranges from 0 to 1. We investigate the structure of TD fixed-point of $\text{GQ}\left(\sigma ,\lambda \right)$ , and prove $\text{GQ}\left(\sigma ,\lambda \right)$ converges to its TD fixed-point with probability one. Furthermore, we prove that $\text{GQ}\left(\sigma ,\lambda \right)$ converges to an arbitrarily small neighborhood of the optimal solution with probability one. Empirical results show the $\text{GQ}\left(\sigma ,\lambda \right)$ with a value $\sigma \in \left(0,1\right)$ that creates a mixture of $\text{GQ}\left(\lambda \right)$ and gradient $\text{Tree?Backup}\left(\lambda \right)$ achieves a better performance than both the extreme end $\sigma =0$ and $\sigma =1$ .

Keywords

Reinforcement Learning, Off-Policy Learning

Share and Cite:

1. Introduction

In reinforcement learning (RL), unifying some disparate ideas not only providing a better understanding of existing algorithms but also creating better performing algorithms.

For example, $\text{TD}\left(\lambda \right)$ [1] unifies one-step temporal difference learning (if $\lambda =0$ ) and Monte Carlo method (if $\lambda =1$ ) through the trace-decay parameter $\lambda$ . Results show that the unified algorithm $\text{TD}\left(\lambda \right)$ performs best at an intermediate value $\lambda \in \left(0,1\right)$ rather than the extreme cases of $\lambda =0$ and $\lambda =1$ .

The work [2] [3] propose a multi-step $\text{Q}\left(\sigma \right)$ that unifies $n$ -step Sarsa [4] (if $\sigma =1$ , full-sampling) and $n$ -step Tree-Backup [5] ($\sigma =0$ , pure-expectation), where the parameter $\sigma \in \left[0,1\right]$ denotes the degree of the sampling. The work [2] have conducted experiments to show that for some value $\sigma \in \left(0,1\right)$ , $\text{Q}\left(\sigma \right)$ creates a mixture of full-sampling and pure-expectation approach, which performs better than the extreme case $\sigma =0$ and $\sigma =1$ . Later, the work [6] [7] inherit the key idea of unification of $\text{TD}\left(\lambda \right)$ and $\text{Q}\left(\sigma \right)$ , they propose $\text{Q}\left(\sigma ,\lambda \right)$ unifies $\text{Sarsa}\left(\lambda \right)$ [4] and $\text{Tree-Backup}\left(\lambda \right)$ [5]. The previous works [6] [7] show that $\text{Q}\left(\sigma ,\lambda \right)$ performs best at an intermediate value $\sigma \in \left(0,1\right)$ .

It is noteworthy that the theoretical analysis of the work [2] [6] [7] only consider the tabular learning, which requires a very large table to store the estimated value function when the state space is huge. That implies the previous methods of [2] [6] [7] are considerably expensive for high-dimensional RL, which is the main focus of this work.

Our Main Works

A practical way to address the high-dimensional curse is using a parametric function to estimate the value function. In this paper, we focus on extending $\text{Q}\left(\sigma ,\lambda \right)$ with linear function approximation. Since the divergence of semi-gradient with multi-step bootstrapping for off-policy learning are well-documented in the existing literature (e.g., [3] [8]), which could also happen in semi-gradient $\text{Q}\left(\sigma ,\lambda \right)$ . To propose a convergent gradient-based algorithm, we derive the $\text{GQ}\left(\sigma ,\lambda \right)$ algorithm via the mean square projected Bellman error (MSPBE) objective function [9], that inspired by weight-duplication trick (also known as “two-timescale stochastic approximation”) [9] [10]. When $\sigma$ ranges from 0 to 1, $\text{GQ}\left(\sigma ,\lambda \right)$ ranges from gradient $\text{Tree Backup}\left(\lambda \right)$ ($\text{TB}\left(\lambda \right)$ ) to $\text{GQ}\left(\lambda \right)$ [11], i.e., our $\text{GQ}\left(\sigma ,\lambda \right)$ unifies gradient $\text{Tree Backup}\left(\lambda \right)$ and $\text{GQ}\left(\lambda \right)$ .

Although ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =0}$ is a natural algorithm to extend $\text{TB}\left(\lambda \right)$ with linear function approximation, to the best of our knowledge, the update rule of ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =0}$ has not been proposed in the existing literatures. It is worth to notice that Touati et al., [12] have proposed another version of gradient $\text{TB}\left(\lambda \right)$ ($\text{GTB}\left(\lambda \right)$ ), which is different from the proposed ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =0}$ , we have clarified this point in Remark 3.

Then, we provide the convergence analysis of the proposed $\text{GQ}\left(\sigma ,\lambda \right)$ . Theorem 1 shows that $\text{GQ}\left(\sigma ,\lambda \right)$ converges to its TD fixed-point with probability one. Additionally, Theorem 1 illustrates the structure of such TD fixed-point: it is the global asymptotically stable equilibrium of its corresponding ordinary differential equation (ODE). For more discussion, see Remark 4. Furthermore, Theorem 2 shows that $\text{GQ}\left(\sigma ,\lambda \right)$ converges to an arbitrarily small neighborhood of the optimal solution with probability one.

Finally, our experiments show that when $\sigma$ ranges from 0 to 1, $\text{GQ}\left(\sigma ,\lambda \right)$ achieves the best performance of off-policy evaluation or control within a certain $\sigma \in \left(0,1\right)$ , neither $\sigma =0$ , nor $\sigma =1$ , which implies that with a certain value $\sigma \in \left(0,1\right)$ , $\text{GQ}\left(\sigma ,\lambda \right)$ creates a mixture between $\text{GQ}\left(\lambda \right)$ and gradient $\text{TB}\left(\lambda \right)$ reaches a better performance than the extreme ends ($\sigma =0$ and $\sigma =1$ ).

2. Preliminary

In this section, we briefly review the basics of reinforcement learning and off-policy evaluation.

2.1. Reinforcement Learning

Reinforcement learning (RL) [3] is often formalized as Markov decision processes (MDP) that considers a tuple $ℳ=\left(\mathcal{S},\mathcal{A},P,R,\gamma \right)$ ; $\mathcal{S}$ is a set with finite states, $\mathcal{A}$ is a set with finite actions; $P:\mathcal{S}\times \mathcal{A}\times \mathcal{S}\to \left[0,1\right]$ , $p_{s{s}^{\prime }}^a=P\left(S_t=s^{\prime }|S_{t-1}=s,A_{t-1}=a\right)$ is the probability of state transition from $s$ to $s^{\prime }$ under playing the action $a$ ; $R\left(\cdot ,\cdot \right):\mathcal{S}\times \mathcal{A}\to {ℝ}^1$ is the expected reward function; $\gamma \in \left(0,1\right)$ .

A policy $\pi$ is a probability distribution on $\mathcal{S}\times \mathcal{A}$ , and $\pi \left(a|s\right)$ denotes the probability of playing $a$ in state $s$ . Let ${\left\{S_t,A_t,R_{t+1}\right\}}_{t\ge 0}$ be generated by $\pi$ , its state-action value function is: $q^{\pi }\left(s,a\right)={\mathbb{E}}_{\pi }\left[{\displaystyle {\sum }_{t=0}^{\infty }{\gamma }^t{R}_{t+1}}|S_0=s,A_0=a\right]$ , where ${\mathbb{E}}_{\pi }\left[\cdot |\cdot \right]$ is conditional expectation on the actions selected according to $\pi$ . Let ${ℬ}^{\pi }:{ℝ}^{\left|\mathcal{S}\right|}\to {ℝ}^{\left|\mathcal{S}\right|}$ denote Bellman operator with respect to policy $\pi$ :

${ℬ}^{\pi }:q\mapsto R^{\pi }+\gamma P^{\pi }q,$ (1)

where $P^{\pi }\in {ℝ}^{\left|\mathcal{S}\right|\times \left|\mathcal{S}\right|}$ , $R^{\pi }\in {ℝ}^{\left|\mathcal{S}\right|\times \left|\mathcal{A}\right|}$ , their corresponding elements are: ${\left[P^{\pi }\right]}_{s,s^{\prime }}={\displaystyle {\sum }_{a\in \mathcal{A}}\pi \left(a|s\right)p_{s{s}^{\prime }}^a}$ , ${\left[R^{\pi }\right]}_{s,a}=R\left(s,a\right)$ . It is well-known that $q^{\pi }$ is the unique fixed point of ${ℬ}^{\pi }$ , i.e., ${ℬ}^{\pi }{q}^{\pi }=q^{\pi }$ , which is known as Bellman equation.

2.2. Off-Policy Evaluation

Let us consider the trajectory $\tau =:{\left\{S_t,A_t,R_{t+1}\right\}}_{t\ge 0}$ generated by the behavior policy $\mu$ , where $A_t~\mu \left(\cdot |S_t\right)$ , $S_{t+1}~P\left(\cdot |S_t,A_t\right)$ . Off-policy evaluation is the task to estimate the value function of the target policy $\pi$ via the data that is generated by the behavior policy $\mu$ , where $\mu \ne \pi$ .

Assumption 1 (Ergodicity). The Markov chain induced by behavior policy $\mu$ is ergodic, i.e., there exists a stationary distribution $\xi \left(\cdot ,\cdot \right)$ over $\mathcal{S}\times \mathcal{A}$ : for $\forall \left(S_0,A_0\right)$ ,

$\frac{1}{n}{\displaystyle \sum }_{k=1}^n\mathbb{P}\left(S_k=s,A_k=a|S_0,A_0\right)\stackrel{n\to \infty }{\to }\xi \left(s,a\right)>0.$(2)

The ergodicity of behavior policy $\mu$ is a standard assumption in off-policy learning [3], and it implies each-action pair is visited under this behavior policy $\mu$ . We use $\Xi$ to denote a diagonal matrix whose diagonal element is $\xi \left(s,a\right)$ , i.e., $\text{Ξ}=\text{diag}\left\{\cdots ,\xi \left(s,a\right),\cdots \right\}$ .

2.3. Temporal Difference Learning and λ-Return

TD learning updates value function as follows, $\forall t\ge 0$ ,

$Q\left(S_t,A_t\right)\leftarrow Q\left(S_t,A_t\right)+{\alpha }_t{\delta }_t,$ (3)

where $Q\left(\cdot ,\cdot \right)$ is an estimator of $q^{\pi }$ , ${\alpha }_t$ is step-size and ${\delta }_t$ is TD error. Let $Q_t=:Q\left(S_t,A_t\right)$ , if

${\delta }_t={\delta }_t^{\text{S}}=:R_{t+1}+\gamma Q_{t+1}-Q_t,$ (4)

then update (3) is Sarsa [4]. If ${\delta }_t$ is expected TD error:

${\delta }_t^{\text{ES}}=R_{t+1}+\gamma {\displaystyle \sum }_{a\in \mathcal{A}}\pi \left(a|S_{t+1}\right)Q\left(S_{t+1},a\right)-Q_t,$ (5)

then update (3) is Expected Sarsa [4].

The $\lambda$ -return is an average contains all the $n$ -step returns by weighting proportionally to ${\lambda }^{n-1}$ , where $\lambda \in \left[0,1\right]$ . In this paper, we mainly consider two classic $\lambda$ -return: $\text{Tree Backup}\left(\lambda \right)$ ($\text{TB}\left(\lambda \right)$ ) and $\text{Expected Sarsa}\left(\lambda \right)$ .

Tree Backup($\lambda$ ). For each pair $\left(S_t,A_t\right)$ in the trajectory $\tau$ , $\text{TB}\left(\lambda \right)$ [5] estimates $q^{\pi }\left(S_t,A_t\right)$ by

$G_t^{\lambda }=Q_t+{\displaystyle \sum }_{k=t}^{\infty }{\left(\gamma \lambda \right)}^{k-t}{\delta }_k^{\text{ES}}{\displaystyle \prod }_{i=t+1}^k\pi \left(A_i|S_i\right),$ (6)

where ${\delta }_k^{\text{ES}}$ is expected TD error. Precup et al., [5] have proved the iteration (6) converges to $q^{\pi }$ with probability one under some certain conditions.

Expected Sarsa($\lambda$ ). Sutton and Barto [3] have proposed a multi-step TD learning extends Expected Sarsa to $\lambda$ -return version: for each $t\ge 0$ ,

$G_t^{\lambda }=Q_t+{\displaystyle \sum }_{k=t}^{\infty }{\left(\gamma \lambda \right)}^{k-t}{\delta }_k^{\text{ES}}{\displaystyle \prod }_{i=t+1}^k\frac{\pi \left(A_i|S_i\right)}{\mu \left(A_i|S_i\right)}.$ (7)

For the convenience, in the following paragraph, we consider the following notations,

${\rho }_i=:\frac{\pi \left(A_i|S_i\right)}{\mu \left(A_i|S_i\right)},{\displaystyle \prod }_{i=t}^k{\rho }_i=:{\rho }_{t:k},{\rho }_{t:t+1}=1.$

2.4. A Unified View

In this section, we review an approach to unify $\text{TB}\left(\lambda \right)$ and $\text{Expected Sarsa}\left(\lambda \right)$ .

$\text{Q}\left(\sigma \right)$ Algorithm. Recently, De Asis et al., [2] propose $\text{Q}\left(\sigma \right)$ unifies multi-step Sarsa and multi-step $\text{TB}\left(0\right)$ . Concretely, according to a mixed TD error ${\delta }_t^{\pi ,\sigma }$ :

${\delta }_t^{\pi ,\sigma }=\sigma {\delta }_t^{\text{S}}+\left(1-\sigma \right){\delta }_t^{\text{ES}},$ (8)

De Asis et al., [2] construct a multi-step estimator:

$G_t^{\sigma }=Q_t+{\displaystyle \sum }_{k=t}^{\infty }{\gamma }^{k-t}{\delta }_k^{\pi ,\sigma }{\displaystyle \prod }_{i=t+1}^k\left[\left(1-\sigma \right)\pi \left(A_i|S_i\right)+\sigma \right],$ (9)

where $\sigma \in \left[0,1\right]$ is sampling parameter. When $\sigma$ ranges from 0 to 1, the update (9) ranges from multi-step $\text{TB}\left(0\right)$ to multi-step Sarsa. Experimental results show that a certain $\sigma \in \left(0,1\right)$ results in a mixture of $\text{TB}\left(0\right)$ and Sarsa performs better than both $\sigma =0$ and $\sigma =1$ [2], which implies unifying some seemingly disparate algorithmic ideas can create better performing algorithms.

Off-Policy $\text{Q}\left(\sigma ,\lambda \right)$ . Later, De Asis, [7] proposes a multi-step returns as follows,

$\begin{array}{c}{G}_t^{\sigma ,\lambda }=Q_t+{\displaystyle \sum }_{k=t}^{\infty }{\delta }_k^{\text{ES}}{\displaystyle \prod }_{i=t+1}^k\gamma \lambda \left(\left(1-\sigma \right)\pi \left(A_i|S_i\right)+\sigma {\rho }_i\right)\\ =Q_t+{\displaystyle \sum }_{k=t}^{\infty }{\delta }_k^{\text{ES}}{\displaystyle \prod }_{i=t+1}^k\gamma \lambda c_{i,\sigma },\end{array}$ (10)

where

$c_{i,\sigma }=\left(1-\sigma \right)\pi \left(A_i|S_i\right)+\sigma {\rho }_i.$ (11)

When $\sigma$ ranges from 0 to 1, the estimator (10) ranges from $\text{TB}\left(\lambda \right)$ (6) to $\text{Expected Sarsa}\left(\lambda \right)$ (7).

We introduce a $\lambda$ -operator ${ℬ}_{\sigma ,\lambda }^{\pi ,\mu }(\cdot ):{ℝ}^{\left|\mathcal{S}\right|\times \left|\mathcal{A}\right|}\to {ℝ}^{\left|\mathcal{S}\right|\times \left|\mathcal{A}\right|}$ that is a high level view of the $\lambda$ -return (10),

$\begin{array}{l}{ℬ}_{\sigma ,\lambda }^{\pi ,\mu }(\cdot ):q\mapsto q+{\mathbb{E}}_{\mu }\left[{\displaystyle \sum }_{k=0}^{\infty }{\delta }_k^{\text{ES}}{\displaystyle \prod }_{i=1}^k\gamma \lambda c_{i,\sigma }\right]\\ =q+\sigma {\left(I-\lambda \gamma P^{\pi }\right)}^{-1}\left({ℬ}^{\pi }q-q\right)\\ +\left(1-\sigma \right){\left(I-\lambda \gamma P^{\pi ,\mu }\right)}^{-1}\left({ℬ}^{\pi }q-q\right),\end{array}$ (12)

where ${ℬ}^{\pi }$ is Bellman operator (1), $P^{\pi ,\mu }\in {ℝ}^{\left|\mathcal{S}\right|\times \left|\mathcal{S}\right|}$ , and whose elements are: ${\left[P^{\pi ,\mu }\right]}_{s,s^{\prime }}={\displaystyle {\sum }_{a\in \mathcal{A}}\pi \left(a|s\right)\mu \left(a|s\right)p_{s{s}^{\prime }}^a}$ .

Remark 1. Yang et al. [6] propose another version of $\text{Q}\left(\sigma ,\lambda \right)$ algorithm that extends $\text{Q}\left(\sigma \right)$ (9) with eligibility trace:

${\tilde{G}}_t^{\sigma ,\lambda }=Q_t+{\displaystyle \sum }_{k=t}^{\infty }{\left(\lambda \gamma \right)}^{k-t}{\delta }_k^{\pi ,\sigma }.$ (13)

It is noteworthy that at one extreme end $\sigma =1$ , both $\text{Q}\left(\sigma \right)$ (9) and ${\tilde{G}}_t^{\sigma ,\lambda }$ (13) reduce to on-policy learning. Particularly, [6] prove that the performance of ${\tilde{G}}_t^{\sigma ,\lambda }$ for off-policy evaluation is determined by parameter $\sigma$ :

${\Vert {\mathbb{E}}_{\mu }\left[{\tilde{G}}_t^{\sigma ,\lambda }|\left(S_t,A_t\right)=\left(s,a\right)\right]-q^{\pi }\left(s,a\right)\Vert }_{\infty }\le \sigma C,$ (14)

where $C$ is a positive constant never reaches 0 no matter how we choose the starting time $t$ . The upper error bound of (14) illustrates the capacity of ${\tilde{G}}_t^{\sigma ,\lambda }$ for off-policy evaluation decays monotonously when $\sigma$ ranges from 0 to 1. At the extreme end $\sigma =1$ , ${\tilde{G}}_t^{\sigma ,\lambda }$ achieves the worst performance of off-policy evaluation. We think this is a natural result since ${{\tilde{G}}_t^{\sigma ,\lambda }|}_{\sigma =1}$ is an on-policy algorithm exactly. Thus, in this paper, we mainly concern (10) for off-policy learning.

2.5. Linear Function Approximation

TD learning (3) requires a very huge table to store the estimate value function $Q\left(\cdot ,\cdot \right)$ when $\left|\mathcal{S}\right|$ is very large, which implies tabular TD learning is considerably expensive for high-dimensional RL. We often use a parametric function $Q_{\theta }\left(\cdot ,\cdot \right)$ to approximate

$q^{\pi }\left(s,a\right)\approx {\varphi }^{\top }\left(s,a\right)\theta =:Q_{\theta }\left(s,a\right),$ (15)

where $\theta \in {ℝ}^p$ is the parameter need to be learned, $\varphi \left(s,a\right)={\left({\phi }_1\left(s,a\right),{\phi }_2\left(s,a\right),\cdots ,{\phi }_p\left(s,a\right)\right)}^{\top }$ , and each ${\phi }_i:\mathcal{S}\times \mathcal{A}\to ℝ$ . Furthermore, $Q_{\theta }$ can be rewritten as a version of matrix

$Q_{\theta }=\Phi \theta \approx q^{\pi },$ (16)

where $\Phi$ is a matrix whose rows are the state-action feature vectors ${\varphi }^{\top }\left(s,a\right)$ .

3. Divergence of $Q\left(\sigma ,\lambda \right)$ with Semi-Gradient

In this section, firstly, we derive the semi-gradient $\text{Q}\left(\sigma ,\lambda \right)$ algorithm; then we briefly analyze the divergence of extending $\text{Q}\left(\sigma ,\lambda \right)$ (10) with semi-gradient method. In fact, the divergence of semi-gradient off-policy TD methods are well-documented in the literature (e.g., [8] [12] [13]), which are not specific to $\text{Q}\left(\sigma ,\lambda \right)$ .

3.1. Semi-Gradient $Q\left(\sigma ,\lambda \right)$

Recall $\tau ={\left\{\left(S_t,A_t,R_{t+1}\right)\right\}}_{t\ge 0}$ is generated by behavior policy $\mu$ , let ${\varphi }_t=\varphi \left(S_t,A_t\right)$ , we define semi-gradient $\text{Q}\left(\sigma ,\lambda \right)$ as follows:

$\begin{array}{c}{\theta }_{t+1}={\theta }_t-{{\alpha }_t{\nabla }_{\theta }{\left(G_t^{\lambda }\left(\theta \right)-{\theta }^{\top }{\varphi }_t\right)}^2|}_{\theta ={\theta }_t}\\ ={\theta }_t-{{\alpha }_t\left(G_t^{\lambda }\left({\theta }_t\right)-{\theta }_t^{\top }{\varphi }_t\right){\nabla }_{\theta }\left(-Q_{\theta }\left(S_t,A_t\right)\right)|}_{\theta ={\theta }_t}\\ ={\theta }_t+{\alpha }_t\left({\displaystyle \sum }_{k=t}^{\infty }{\delta }_k^{\text{ES}}\left({\theta }_t\right){\displaystyle \prod }_{i=t+1}^k\gamma \lambda c_{i,\sigma }\right){\varphi }_t,\end{array}$ (17)

where

$G_t^{\lambda }\left({\theta }_t\right)={\theta }_t^{\top }{\varphi }_t+{\displaystyle \sum }_{k=t}^{\infty }{\delta }_k^{\text{ES}}\left({\theta }_t\right){\displaystyle \prod }_{i=t+1}^k\gamma \lambda c_{i,\sigma }$

is an off-line estimator of value function according to Equation (10), TD error ${\delta }_k^{\text{ES}}\left({\theta }_t\right)=R_{k+1}+\gamma {\mathbb{E}}_{\pi }\left[{\theta }_t^{\top }\varphi \left(S_{k+1},\cdot \right)\right]-{\theta }_t^{\top }{\varphi }_k$ , and ${\alpha }_t$ is step-size. Let

$A_t={\varphi }_t{\displaystyle \sum }_{k=t}^{\infty }{\left(\gamma {\mathbb{E}}_{\pi }\left[\varphi \left(S_{k+1},\cdot \right)\right]-{\varphi }_k\right)}^{\top }{\displaystyle \prod }_{i=t+1}^k\gamma \lambda c_{i,\sigma },$ (18)

$b_t={\varphi }_t{\displaystyle \sum }_{k=t}^{\infty }{R}_{k+1}{\displaystyle \prod }_{i=t+1}^k\gamma \lambda c_{i,\sigma }.$ (19)

Then update (17) can be rewritten as follows,

${\theta }_{t+1}={\theta }_t+{\alpha }_t\left(A_t{\theta }_t+b_t\right).$ (20)

Furthermore, we have

$A_{\sigma }=:{\mathbb{E}}_{\mu }\left[A_t\right]={\Phi }^{\top }\Xi P_{\sigma }^{\pi ,\mu }\left(\gamma P^{\pi }-I\right)\Phi ,$ (21)

$b_{\sigma }=:{\mathbb{E}}_{\mu }\left[b_t\right]={\Phi }^{\top }\Xi P_{\sigma }^{\pi ,\mu }R,$ (22)

where $P_{\sigma }^{\pi ,\mu }=\sigma {\left(I-\lambda \gamma P^{\pi }\right)}^{-1}+\left(1-\sigma \right){\left(I-\lambda \gamma P^{\pi ,\mu }\right)}^{-1}.$

3.2. Divergence Analysis

Now, we only briefly discuss the divergence lies in the iteration (17). Under the conditions of Proposition 4.8 presented by Bertsekas and Tsitsiklis [14], ${\left\{{\theta }_t\right\}}_{t\ge 0}$ (17) converges to a certain point if and only if $A_{\sigma }$ is a negative matrix. Furthermore, if iteration (17) converges, then it converges to its unique TD fixed point ${\theta }_{\star }$ that satisfes

$A_{\sigma }{\theta }_{\star }+b_{\sigma }=0.$ (23)

Unfortunately, since the steady state-action distribution doesn’t match the transition probability during off-policy learning, we can not guarantee the negative definiteness of $A_{\sigma }$ , thus ${\left\{{\theta }_t\right\}}_{t\ge 0}$ may diverge. To clarify this point, we use the classic counterexample [12] to show the divergence of semi-gradient TD algorithms (17) for off-policy learning.

Figure 1. Counterexample from [12]: Two-State MDP.

For the MDP in Figure 1, the behavior policy $\mu \left(\text{right}|\cdot \right)=0.5$ , and target policy $\pi \left(\text{right}|\cdot \right)=1$ . We assign the features $\left\{{\left(1,0\right)}^{\top },{\left(2,0\right)}^{\top },{\left(0,1\right)}^{\top },{\left(0,2\right)}^{\top }\right\}$ to the state-action pairs $\left\{\left(s_1,\text{right}\right),\left(s_2,\text{right}\right),\left(s_1,\text{left}\right),\left(s_2,\text{left}\right)\right\}$ , From the dynamic transition shown in Figure 1, we have

$P^{\pi }=\left(\begin{array}{llll}0\hfill & 1\hfill & 0\hfill & 0\hfill \\ 0\hfill & 1\hfill & 0\hfill & 0\hfill \\ 1\hfill & 0\hfill & 0\hfill & 0\hfill \\ 1\hfill & 0\hfill & 0\hfill & 0\hfill \end{array}\right),\Phi =\left(\begin{array}{ll}1\hfill & 0\hfill \\ 2\hfill & 0\hfill \\ 0\hfill & 1\hfill \\ 0\hfill & 2\hfill \end{array}\right),\Xi =\frac{1}{2}{I}_{4\times 4}.$

Then, according to (21), we have

$\begin{array}{c}{A}_{\sigma }={\Phi }^{\top }\Xi P_{\sigma }^{\pi ,\mu }\left(\gamma P^{\pi }-I\right)\Phi \\ =\left(\begin{array}{cc}\frac{6\left(2-\sigma \right)\gamma -\gamma \lambda -5\left(2-\sigma \right)}{2\left(1-\gamma \lambda \right)}& 0\\ \frac{3\gamma }{2}& -5\left(1-\frac{\sigma }{2}\right)\end{array}\right),\end{array}$

and the eigenvalues of $A$ are: $\frac{6\left(2-\sigma \right)\gamma -\gamma \lambda -5\left(2-\sigma \right)}{2\left(1-\gamma \lambda \right)}$ and $-5\left(1-\frac{\sigma }{2}\right)$ . For any initial ${\theta }_0={\left(\begin{array}{l}{\theta }_{0,1},{\theta }_{0,2}\hfill \end{array}\right)}^{\top }$ , let $\mathbb{E}\left[{\theta }_{t+1}\right]=:{\left({\theta }_{t+1,1},{\theta }_{t+1,2}\right)}^{\top }$ , according to (20), the first component of the term $\mathbb{E}\left[{\theta }_{t+1}|{\theta }_t\right]$ is:

${\theta }_{t+1,1}={\theta }_{0,1}{\displaystyle \prod }_{i=0}^t\left(1+{\alpha }_i\frac{6\left(2-\sigma \right)\gamma -\gamma \lambda -5\left(2-\sigma \right)}{2\left(1-\gamma \lambda \right)}\right).$ (24)

For any $\lambda \in \left(0,1\right)$ , if $\gamma \in \left(\frac{10-5\sigma }{12-6\sigma -\lambda },1\right)$ , then $\frac{6\left(2-\sigma \right)\gamma -\gamma \lambda -5\left(2-\sigma \right)}{2\left(1-\gamma \lambda \right)}$ is a positive scalar, which implies $A_{\sigma }$ can not be a negative matrix. Furthermore, if step size ${\alpha }_t:{\displaystyle {\sum }_{i\ge 0}{\alpha }_t}=\infty$ , we have

$\left|{\theta }_{t+1,1}\right|=\left|{\theta }_{0,1}\right|{\displaystyle \prod }_{i=0}^t\left(\frac{6\left(2-\sigma \right)\gamma -\gamma \lambda -5\left(2-\sigma \right)}{2\left(1-\gamma \lambda \right)}\right)\to +\infty ,$ (25)

Equation (25) is a direct result of the following conclusion that could be found in any calculus textbook. Let $p_i=1+a_i$ , where $a_i>0$ , if ${\displaystyle {\sum }_{i=1}^{\infty }{a}_i}=+\infty$ , then ${\displaystyle {\prod }_{i=1}^{\infty }{p}_i}={\displaystyle {\prod }_{i=1}^{\infty }}\left(1+a_i\right)=+\infty$ , which implies the way (17) to extend $\text{Q}\left(\sigma \right)$ with linear function approximation via off-line estimate is unstable for off-policy learning.

4. Gradient $Q\left(\sigma ,\lambda \right)$

In this section, we derive the gradient $\text{Q}\left(\sigma ,\lambda \right)$ ($\text{GQ}\left(\sigma ,\lambda \right)$ ) algorithm. The proposed $\text{GQ}\left(\sigma ,\lambda \right)$ unifies $\text{GQ}\left(\lambda \right)$ [11] if $\sigma =1$ . For more discussion, see Remark 2. At another extreme end $\sigma =0$ , the proposed ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =0}$ can be seen as a new way to extend $\text{TB}\left(\lambda \right)$ (6) with linear function approximation. Although ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =0}$ is a natural algorithm extends $\text{TB}\left(\lambda \right)$ (6) with linear function approximation, to the best of our knowledge, the update rule of ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =0}$ has not been proposed in the existing literature. For more discussion, see Remark 3.

We derive the gradient the $\text{GQ}\left(\sigma ,\lambda \right)$ algorithm via mean square projected Bellman error (MSPBE) [9] objective function as follows,

$J\left(\theta \right)=\frac{1}{2}{\Vert \Phi \theta -\Pi {ℬ}_{\sigma ,\lambda }^{\pi ,\mu }\left(\Phi \theta \right)\Vert }_{\Xi }^2,$ (26)

where

$\Pi =\Phi {\left({\Phi }^{\top }\Xi \Phi \right)}^{-1}{\Phi }^{\top }\Xi$

is an $\left|\mathcal{S}\right|\times \left|\mathcal{S}\right|$ projection matrix, ${\Vert \cdot \Vert }_{\text{Ξ}}^2$ is the weighted Euclidean norm: ${\Vert x\Vert }_{\Xi }^2=x^{\top }\Xi x$ . Furthermore, we can rewrite ${\text{min}}_{\theta }$ $J\left(\theta \right)$ as follows,

$\underset{\theta }{\text{min}}J\left(\theta \right)=\underset{\theta }{\text{min}}\frac{1}{2}{\Vert A_{\sigma }\theta +b_{\sigma }\Vert }_{M^{-1}}^2,$ (27)

where $M={\mathbb{E}}_{\mu }\left[{\varphi }_t{\varphi }_t^{\top }\right]={\Phi }^{\top }\Xi \Phi$ .

The gradient method is a natural approach to solve problem (27), however, it is worth to notice that the challenges are two-fold: (I) Firstly, since the invertible matrix $M^{-1}$ is involved in $\nabla J\left(\theta \right)$ , so it is too expensive to apply stochastic gradient to solve the problem (27) directly. (II) Since $\nabla J\left(\theta \right)=A_{\sigma }^{\top }{M}^{-1}\left(A_{\sigma }\theta +b_{\sigma }\right)$ involves the product of expectations, then the unbiased estimate of $\nabla J\left(\theta \right)$ cannot be obtained via a single sample. It needs to sample twice, so it is a double-sampling problem, which is the second bottleneck of applying gradient to solve the problem (27). Additionally, $M^{-1}=\mathbb{E}{\left[{\varphi }_t{\varphi }_t^{\top }\right]}^{-1}$ cannot also be estimated via a single sample. The above analysis pushes us to find a new practical way to solve the problem (27).

Let $e_{-1,\sigma }=0$ , $e_{t,\sigma }=\lambda \gamma c_{t,\sigma }{e}_{t-1}+{\varphi }_t$ , ${\overline{\varphi }}_{t+1}={\mathbb{E}}_{\pi }\left[\varphi \left(S_{t+1,\cdot }\right)\right]$ , then we have the following equation:

$-\frac{1}{2}\nabla J\left({\theta }_t\right)=-{\mathbb{E}}_{\mu }\left[\left(\gamma {\overline{\varphi }}_{t+1}-{\varphi }_t\right)e_{t,\sigma }^{\top }\right]\varpi$ (28)

$-\frac{1}{2}\nabla J\left({\theta }_t\right)={\mathbb{E}}_{\mu }\left[{\delta }_t^{\text{ES}}{e}_{t,\sigma }\right]-\mathbb{E}\left[\gamma \left(1-\lambda \right){\overline{\varphi }}_{t+1}{e}_{t,\sigma }^{\top }\right]\varpi ,$(29)

where

$\varpi ={\mathbb{E}}_{\mu }{\left[{\varphi }_t{\varphi }_t^{\top }\right]}^{-1}\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_{t,\sigma }\right],{\delta }_t^{\text{ES}}=R_{t+1}+\gamma {\theta }_t^{\top }{\overline{\varphi }}_{t+1}-{\theta }_t^{\top }{\varphi }_t.$

For the limitation of space, we provide the derivation of (28)-(29) in Appendix A. We use the sign convention that the mean update of $\theta$ follows the negative gradient $-\nabla J\left({\theta }_t\right)$ . The term (31) provides its unbiased stochastic approximation, while the auxiliary recursion (30) tracks $\varpi =M^{-1}{\mathbb{E}}_{\mu }\left[{\delta }_t^{\text{ES}}{e}_{t,\sigma }\right]$ , circumventing the double-sampling issue.

Let’s consider the term $\varpi ={\mathbb{E}}_{\mu }{\left[{\varphi }_t{\varphi }_t^{\top }\right]}^{-1}\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_{t,\sigma }\right]$ that is a solution of a least-squares problem, and a typical least mean square (LMS) update rule to find the vector $\varpi$ is:

${\omega }_{t+1}={\omega }_t+{\beta }_t\left({\delta }_t^{\text{ES}}{e}_{t,\sigma }-{\varphi }_t{\omega }_t^{\top }{\varphi }_t\right),$ (30)

where ${\beta }_t$ is step-size. Then, by directly sampling from (29) with (30), we define the update rule of $\theta$ as follows,

${\theta }_{t+1}={\theta }_t+{\alpha }_t\left({\delta }_t^{\text{ES}}{e}_{t,\sigma }-\gamma \left(1-\lambda \right){\overline{\varphi }}_{t+1}{e}_{t,\sigma }^{\top }{\omega }_t\right),$(31)

where ${\alpha }_t$ is step-size. We provide the details in Algorithm 1.

Remark 2 (Case of $\sigma =1$ ). When $\sigma =1$ , we regard ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =1}$ as an approach to extend $\text{Expected Sarsa}\left(\lambda \right)$ (7) with linear function approximation. A more interesting result is that the proposed ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =1}$ is reduced to $\text{GQ}\left(\lambda \right)$ [12] exactly. Now, we provide two fresh interpretations to the proposed $\text{GQ}\left(\lambda \right)$ :

• $\text{GQ}\left(\lambda \right)$ is at one extreme end ($\sigma =1$ ) of the proposed $\text{GQ}\left(\sigma ,\lambda \right)$ , i.e., the proposed $\text{GQ}\left(\sigma ,\lambda \right)$ contains $\text{GQ}\left(\lambda \right)$ .

• Furthermore, just because $\text{GQ}\left(\lambda \right)$ is same as ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =1}$ , $\text{GQ}\left(\lambda \right)$ can be seen as an extension of the tabular $\text{Expected Sarsa}\left(\lambda \right)$ (7) with linear function approximation, while the original motivation of Maei and Sutton [11] to propose $\text{GQ}\left(\lambda \right)$ is to introduce eligibility trace to gradient temporal difference learning for off-policy evaluation. Thus, the proposed ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =1}$ provides a fresh understanding for the $\text{GQ}\left(\lambda \right)$ [11].

Computational complexity. The computational complexity of Algorithm 1 is $O\left(\left|\mathcal{A}\right|p\right)$ per step in time, and $O\left(p\right)$ in memory, where $p$ is the feature dimension and $\left|\mathcal{A}\right|$ is the number of actions. This maintains the same asymptotic efficiency as the baseline $\text{GQ}\left(\lambda \right)$ and gradient $\text{TB}\left(\lambda \right)$ methods.

Remark 3 (Case of $\sigma =0$ ). When $\sigma =0$ , the algorithm ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =0}$ is reduced to a version of extending $\text{TB}\left(\lambda \right)$ (6) with linear function approximation. Although ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =0}$ is a natural algorithm extends $\text{TB}\left(\lambda \right)$ (6) with linear function approximation, to the best of our knowledge, the update rule of ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =0}$ has not been proposed in the existing literatures. It is worth to notice that [12] have also proposed another version of gradient $\text{TB}\left(\lambda \right)$ ($\text{GTB}\left(\lambda \right)$ ), while the difference between the proposed ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =0}$ and $\text{GTB}\left(\lambda \right)$ [12] is reflected at least two aspects:

• Firstly, the proposed gradient ${\text{Q}\left(\sigma ,\lambda \right)|}_{\sigma =0}$ and $\text{GTB}\left(\lambda \right)$ [12] share the same update rule of $e_t$ and ${\omega }_t$ , but instead of (31), $\text{GTB}\left(\lambda \right)$ updates the parameter $\theta$ as follows,

${\theta }_{t+1}={\theta }_t+{\alpha }_t\left(-\gamma {\overline{\varphi }}_{t+1}+{\varphi }_t\right)e_t^{\top }{\omega }_t,$ (32)

where $e_t={e_{t,\sigma }|}_{\sigma =0}=\lambda \gamma \pi \left(A_t|S_t\right)e_{t-1}$ .

• Secondly, Touati et al., [12] derive the update rule (32) of their $\text{GTB}\left(\lambda \right)$ via the convex-concave saddle-point framework [15], while our $\text{GQ}\left(\sigma ,\lambda \right)$ is based on the weight-duplication trick¹ of (29)-(31).

5. Convergence Analysis

In this section, we prove the convergence of the proposed $\text{GQ}\left(\sigma ,\lambda \right)$ . Theorem 1 shows that $\text{GQ}\left(\sigma ,\lambda \right)$ converges to its TD fixed-point (23) with probability one. Besides, Theorem 1 illustrates the structure of this TD fixed-point: it is the global asymptotically stable equilibrium of its corresponding ordinary differential equation (ODE). For more discussion, we provide in Remark 4. Theorem 2 shows that $\text{GQ}\left(\sigma ,\lambda \right)$ converges to an arbitrarily small neighborhood of the optimal solution with probability one. While we rely on the standard two-timescale ODE method for the general convergence mechanism, our novel theoretical step is verifying that the proposed $\sigma$ -dependent trace coefficient $c_{t,\sigma }$ yields a stable equilibrium structure for the ODEs.

5.1. Additional Assumptions

We need some additional assumptions to present the convergent of $\text{GQ}\left(\sigma ,\lambda \right)$ , those assumptions are widely used in reinforcement learning [13] [17]-[19].

Assumption 2 (Diminishing Step-size). The positive sequences ${\left\{{\alpha }_t\right\}}_{t\ge 0}$ , ${\left\{{\beta }_t\right\}}_{t\ge 0}$ satisfy the following conditions with probability one,

${\displaystyle \sum }_{t=0}^{\infty }{\alpha }_t={\displaystyle \sum }_{t=0}^{\infty }{\beta }_t=\infty ,{\displaystyle \sum }_{t=0}^{\infty }{\alpha }_t^2<\infty ,{\displaystyle \sum }_{t=0}^{\infty }{\beta }_t^2<\infty .$

Assumption 3. The features ${\left\{{\varphi }_t\right\}}_{t\ge 0}$ is uniformly bounded by ${\varphi }_{\max }$ . The reward function is uniformly bounded by $R_{\max }$ . The importance sampling ${\rho }_t=\frac{\pi \left(A_t|S_t\right)}{\mu \left(A_t|S_t\right)}$ is uniformly bounded by ${\rho }_{\max }$ .

Assumption 4 (Solvability of Problem). The matrix $A_{\sigma }$ is non-singular and $\text{rank}\left(\Phi \right)=p$ .

Assumption 4 requires the non-singular matrix $A_{\sigma }$ , which implies the optimal parameter ${\theta }^{\star }=-A^{-1}b$ is well defined. The feature matrix $\Phi$ has linearly independent columns implies the matrix $M={\Phi }^{\top }\Xi \Phi$ is positive defined.

5.2. Main Results and Discussion

Theorem 1 (Convergence of Algorithm 1). Under Assumption 1-4, we consider the iteration ${\left\{\left({\theta }_t,{\omega }_t\right)\right\}}_{t\ge 0}$ that is generated according to (30)-(31). The step-size ${\alpha }_t$ , ${\beta }_t$ satisfy Assumption 2 and ${\eta }_t=\frac{{\beta }_t}{{\alpha }_t}\to 0$ , as $t\to \infty$ . We define two functions $G\left(\theta \right)$ , $H\left(\omega ,\theta \right)$ as follows,

$G\left(\theta \right)=-A_{\sigma }^{\top }{M}^{-1}\left(A_{\sigma }\theta +b_{\sigma }\right),$ (33)

$H\left(\omega ,\theta \right)=A_{\sigma }\theta +b_{\sigma }-M\omega .$ (34)

Then $\left({\theta }_t,{\omega }_t\right)\stackrel{w.p.1}{\to }\left({\theta }_{\star },{\omega }_{\star }\right)$ , as $t\to \infty$ , where $\left({\theta }_{\star },{\omega }_{\star }\right)$ is the unique global asymptotically stable equilibrium with respect to the following ODE correspondingly:

$\{\begin{array}{l}\dot{\theta }\left(t\right)=:\frac{\text{d}}{\text{d}t}\theta \left(t\right)=G\left(\theta \left(t\right)\right)\hfill \\ \dot{\omega }\left(t\right)=:\frac{\text{d}}{\text{d}t}\omega \left(t\right)=H\left(\omega \left(t\right),\theta \left(t\right)\right),\hfill \end{array}$(35)

where $\theta \left(t\right),\omega \left(t\right)\in {ℝ}^p$ are the functions are defined on continuous time $\left(0,\infty \right)$ .

Proof. We provide its proof in Appendix B. □

Remark 4 (TD-Fixed Point of $\text{GQ}\left(\sigma ,\lambda \right)$ ). Theorem 1 illustrates that the sequence ${\left\{\left({\theta }_t,{\omega }_t\right)\right\}}_{t\ge 0}$ generated by $\text{GQ}\left(\sigma ,\lambda \right)$ converges to the global asymptotically stable equilibrium of its corresponding ODE (35). Furthermore, from the details of the proof in Appendix B, we know since $A_{\sigma }$ is invertible and $M^{-1}$ is positive definite, then $A_{\sigma }^{\top }{M}^{-1}{A}_{\sigma }$ is also positive defined. Because the ODE uses the negative MSPBE-gradient direction, the Jacobian at the equilibrium is $-A_{\sigma }^{\top }{M}^{-1}{A}_{\sigma }$ , whose eigenvalues have negative real parts. So the following ODE

$\dot{\theta }\left(t\right)=-A_{\sigma }^{\top }{M}^{-1}\left(A_{\sigma }\theta \left(t\right)+b_{\sigma }\right)=G\left(\theta \left(t\right)\right),$ (36)

has a unique global asymptotically stable equilibrium ${\theta }^{\star }$ satisfies the equation

$A_{\sigma }{\theta }_{\star }+b_{\sigma }=0,$ (37)

which implies the global asymptotically stable equilibrium ${\theta }^{\star }$ of the ODE $\dot{\theta }\left(t\right)=G\left(\theta \left(t\right)\right)$ is also the TD fixed point of (23). That means ${\theta }_t$ converges to its TD fixed point:

${\theta }_t\to {\theta }_{\star }=-A_{\sigma }^{-1}{b}_{\sigma },w.p\mathrm{.1.}$

Remark 5 (Unification of TD-Fixed Point). If $\sigma =0$ , the matrix $A_{\sigma }$ is reduced to

${A_{\sigma }|}_{\sigma =0}={\Phi }^{\top }\Xi {\left(I-\lambda \gamma P^{\pi ,\mu }\right)}^{-1}\left(\gamma P^{\pi }-I\right)\Phi ,$

which implies ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =0}$ converges to the TD-fixed point of $\text{GTB}\left(\lambda \right)$ [12], i.e., ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =0}$ shares the same TD-fixed point of $\text{GTB}\left(\lambda \right)$ [12] as follows

${\theta }_{\star }=-{A_{\sigma }^{-1}{b}_{\sigma }|}_{\sigma =0}.$

If $\sigma =1$ , then the key matrix $A_{\sigma }$ is reduced to

${A_{\sigma }|}_{\sigma =1}={\Phi }^{\top }\Xi {\left(I-\lambda \gamma P^{\pi }\right)}^{-1}\left(\gamma P^{\pi }-I\right)\Phi ,$

which illustrates the TD-fixed point of ${\text{GQ}\left(\sigma ,\lambda \right)|}_{\sigma =1}$ (i.e., $\text{GQ}\left(\lambda \right)$ ) algorithm as follows

${\theta }_{\star }=-{A_{\sigma }^{-1}{b}_{\sigma }|}_{\sigma =1}.$

Theorem 1 presents an asymptotic result, which holds only in the limit as the number of iterations increases to infinity. Now, we present a result shows the distance between ${\theta }_t$ and the optimal solution ${\theta }^{\star }$ convergence to 0 in probability. For any $T>0$ , and $t\ge 0$ , we introduce a notation

$\kappa \left(t;T\right)=\text{min}\left\{k\ge t|{\displaystyle \sum }_{i=t}^{k+1}{\alpha }_i>T\right\}$

to denote the last iteration before the sum of step-size ${\alpha }_i$ between it and the $t$ -th iteration exceeds $T$ . Since we consider the Assumption 2, the notation $\kappa \left(t;T\right)$ is well-defined.

Theorem 2. Under Assumption 1-4, we consider the iteration ${\left\{\left({\theta }_t,{\omega }_t\right)\right\}}_{t\ge 0}$ generated by (30)-(31). The step-size ${\alpha }_t$ , ${\beta }_t$ satisfy Assumption 2. Moreover, for the integers $m_t\to \infty$ , ${m^{\prime }}_t\to \infty$ , as $t\to \infty$ ,

$\underset{t\to \infty }{\text{lim}}\underset{0<j\le m_t}{\text{sup}}\left|\frac{{\alpha }_{t+j}}{{\alpha }_t}-1\right|=0,\underset{t\to \infty }{\text{lim}}\underset{0<j\le {m^{\prime }}_t}{\text{sup}}\left|\frac{{\beta }_{t+j}}{{\beta }_t}-1\right|=0.$

Then there exists a sequence of positive numbers $T_t\to \infty$ (as $t\to \infty$ ) such that for any $ϵ>0$ ,

$\underset{t\to \infty }{\text{lim}}\mathbb{P}\left[{\theta }_i\notin N_{ϵ}\left({\theta }^{\star }\right),\exists i\in \left[t,\kappa \left(t,T_t\right)\right]\right]=0,$ (38)

where we use $N_{ϵ}\left({\theta }^{\star }\right)=\left\{\theta :{\Vert \theta -{\theta }^{\star }\Vert }_2\le ϵ\right\}$ to denote the $ϵ$ -neighborhood of ${\theta }^{\star }$ .

Proof. We provide its proof in Appendix C. □

Remark 6 Theorem 2 shows that as $t\to \infty$ , the sequence ${\left\{{\theta }_i\right\}}_{i=t}^{\kappa \left(t,T_t\right)}$ collects to an arbitrarily small neighborhood of the optimal solution ${\theta }^{\star }$ with probability one, i.e.,

$\underset{t\to \infty }{\text{lim}}\mathbb{P}\left({\displaystyle {\cap }_{i=t}^{\kappa \left(t,T_t\right)}\left\{{\theta }_i\in N_{ϵ}\left({\theta }^{\star }\right)\right\}}\right)=1.$

In fact, the results (38) implies

$\underset{t\to \infty }{\text{lim}}\mathbb{P}\left({\theta }_i\notin \mathcal{N}\left({\theta }_{\star },ϵ\right),\exists i\in \left[t,\kappa \left(t,T_t\right)\right]\right)=0,$

then we know

$\begin{array}{l}1-\underset{t\to \infty }{\text{lim}}\mathbb{P}\left({\theta }_i\notin \mathcal{N}\left({\theta }_{\star },ϵ\right),\exists i\in \left[t,\kappa \left(t,T_t\right)\right]\right)\\ =\underset{t\to \infty }{\text{lim}}\mathbb{P}\left(\overline{{\theta }_i\notin \mathcal{N}\left({\theta }_{\star },ϵ\right),\exists i\in \left[t,\kappa \left(t,T_t\right)\right]}\right)\\ =\underset{t\to \infty }{\text{lim}}\mathbb{P}\left(\overline{{\displaystyle {\cup }_{i=t}^{\kappa \left(t,T_t\right)}\left\{{\theta }_i\notin \mathcal{N}\left({\theta }_{\star },ϵ\right)\right\}}}\right)\\ =\underset{t\to \infty }{\text{lim}}\mathbb{P}\left({\displaystyle {\cap }_{i=t}^{\kappa \left(t,T_t\right)}\left\{{\theta }_i\in \mathcal{N}\left({\theta }_{\star },ϵ\right)\right\}}\right).\end{array}$

That is ${\lim }_{t\to \infty }\mathbb{P}\left({\displaystyle {\cap }_{i=t}^{\kappa \left(t,T_t\right)}\left\{{\theta }_i\in \mathcal{N}\left({\theta }_{\star },ϵ\right)\right\}}\right)=1$ .

6. Experiments

In this section, we test the capacity of $\text{GQ}\left(\sigma ,\lambda \right)$ for two typical tasks: off-policy evaluation and control.

• For off-policy evaluation, we compare $\text{GQ}\left(\sigma ,\lambda \right)$ with four state-of-art algorithms: $\text{GQ}\left(\lambda \right)$ [11], $\text{ABQ}\left(\zeta \right)$ [20], $\text{GTB}\left(\lambda \right)$ , $\text{GRetrace}\left(\lambda \right)$ [12] over two typical measurements: MSPBE and mean square error (MSE). It is worth noting that if $\sigma =0$ , $\text{GQ}\left(\sigma ,\lambda \right)$ is reduced to a new version of $\text{GTB}\left(\lambda \right)$ (we denote it as $\text{GTB}\left(\lambda \right)$ -v0), thus, we also show its comparison to $\text{GTB}\left(\lambda \right)$ [12] (we denote it as $\text{GTB}\left(\lambda \right)$ -v1).

• For the control task, our goal is to show the the trade-off between $\sigma =0$ and $\sigma =1$ . Empirical results show the $\text{GQ}\left(\sigma ,\lambda \right)$ with a value $\sigma \in \left(0,1\right)$ that creates a mixture of $\text{GQ}\left(\lambda \right)$ and gradient $\text{Tree Backup}\left(\lambda \right)$ achieves a better performance than both the extreme end $\sigma =0$ and $\sigma =1$ .

These domains are standard diagnostic benchmarks intended to isolate the off-policy instability under linear function approximation. Scaling to very high-dimensional environments is left as future work.

6.1. Off-Policy Evaluation Experiments

We present the domains in the experiments as follows.

(1) Two State MDP [12]. This MDP is shown in Figure 1, the behavior policy $\mu \left(\text{right}|\cdot \right)=0.5$ , and target policy $\pi \left(\text{right}|\cdot \right)=1$ . We assign the features $\left\{{\left(1,0\right)}^{\top },{\left(2,0\right)}^{\top },{\left(0,1\right)}^{\top },{\left(0,2\right)}^{\top }\right\}$ to the state-action pairs $\left\{\left(s_1,\text{right}\right),\left(s_2,\text{right}\right),\left(s_1,\text{left}\right),\left(s_2,\text{left}\right)\right\}$ , i.e.,

$\Phi ={\left(\begin{array}{llll}1\hfill & 2\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 1\hfill & 2\hfill \end{array}\right)}^{\top }.$

(2) Baird Star [21]. The Baird Star is an episodic seven states MDP with two actions: dashed action and solid action. In this example, the behavior policy $\mu \left(\cdot |\text{dashed}\right)=\frac{6}{7}$ , $\mu \left(\cdot |\text{solid}\right)=\frac{1}{7}$ and target policy $\pi \left(\cdot |\text{solid}\right)=1$ . We choose the feature map matrix as follows

$\Phi =\left(\begin{array}{ccc}2I_{7\times 7}& 1_{7\times 1}& 0_{7\times 8}\\ 0_{7\times 8}& 2I_{7\times 7}& 1_{7\times 1}\end{array}\right),$

where $I$ denotes the identity matrix, $0$ denotes a matrix whose elements are all 0, and $1_{7\times 1}$ denotes a vector whose elements are all 1. We used ${\theta }_0={\left(1,1,1,1,1,1,10,1\right)}^{\text{T}}$ as initial parameter vector for the methods that allow specifying a start estimate, TD-learning is known to diverge for this initialization of the parameter-vector [3] [22].

(3) Cliff Walking. This is a standard undiscounted, episodic task, with start and goal states, and the usual actions causing movement up, down, right, and left.

(4) Grid World. This environment from ([3], Chapter 4), where the agent on an 4 × 4 grid and your goal is to reach the terminal state at the top left or the bottom right corner.

(5) Windy Gridworld. This environment from ([3], Chapter 6). Windy Gridworld problem for reinforcement learning. Actions include going up, down, right, and left. In each column the wind pushes you up a specific number of steps (for the next action). If an action would take you off the grid, you remain in the previous state. For each step you get a reward of −1, until the agent reach into a terminal state.

We summarize the domains, feature settings, target policy and behavior policy below.

Two Measurements for Off-Policy Evaluation. In this section, we use empirical $\text{RMSPBE}=\frac{1}{2}{\Vert \widehat{b}+\widehat{A}\theta \Vert }_{{\widehat{M}}^{-1}}^2$ to evaluate the performance, where we evaluate $\widehat{A}$ , $\widehat{b}$ , and $\widehat{M}$ according to their unbiased estimators. Additionally, we also compare the performance over a common measurement empirical MSE: $\text{MSE}={\Vert \Phi \theta -q^{\pi }\Vert }_{\Xi }^2$ , where $q^{\pi }$ is estimated by simulating the target policy $\pi$ and averaging the discounted cumulative rewards over trajectories.

Hyper-parameter Setting. We run the hyper parameter $\sigma$ as follows: $\sigma$ ranges from 0 to 1 with step of 0.02, i.e.,

$\Sigma =\left\{0,0.02,0.04,\cdots ,0.98,1.0\right\}.$

It collects 51 results w.r.t. $\text{GQ}\left(\sigma ,\lambda \right)$ . We set $\lambda =0.99$ , $\gamma =0.99$ , and run the step-size ${\alpha }_t=\left\{{10}^{-2},2\times {10}^{-2},{10}^{-3},2\times {10}^{-3}\right\}$ , ${\eta }_t={\beta }_t/{\alpha }_t=\left\{2^0,2^{-1},\cdots ,2^{-10}\right\}$ .

Results Report. All the results shown in Figure 2 and Figure 3 are the average of 5 runs, where we choose the best $\sigma$ among the 51 results w.r.t. the space $\Sigma$ The results the proposed $\text{GQ}\left(\sigma ,\lambda \right)$ outperforms the the baseline algorithms. The results of Figure 2 and Figure 3 also show $\text{GQ}\left(\sigma ,\lambda \right)$ with an intermediate $\sigma$ (between 0 and 1) has a better performance than the extreme case ($\sigma =0$ and 1). This experiment further validates that unifying some existing algorithms can create a better algorithm.

Figure 2. RMSPBE comparison with different baseline algorithms.

Figure 3. MSE comparison with with different baseline algorithms.

6.2. Control Domain: Off-Policy Evaluation

In this section, we test the off-policy evaluation behavior of $\text{GQ}\left(\sigma ,\lambda \right)$ algorithm on mountain car domain, where the agent considers the task of driving an underpowered car up a steep mountain road. The agent receives a reward of -1 at every step until it reaches the goal region at the top of the hill. Since the state space of this domain is continuous, we use the open tile coding software² to extract feature of states. Recall the states and actions of MountainCar:

$\mathcal{S}=\left\{\left(\text{Velocity},\text{Position}\right)\right\}=\left[-0.07,0.07\right]\times \left[-1.2,0.6\right],$

$\mathcal{A}=\left\{\text{left},\text{neutral},\text{right}\right\}.$

In this experiment, if $\text{Velocity}>0$ , we use behavior policy

$\mu =\left(\frac{1}{100},\frac{1}{100},\frac{98}{100}\right),\pi =\left(\frac{1}{10},\frac{1}{10},\frac{8}{10}\right);$

else

$\mu =\left(\frac{98}{100},\frac{1}{100},\frac{1}{100}\right),\pi =\left(\frac{8}{10},\frac{1}{10},\frac{1}{10}\right).$

Note that the target policy $\pi$ is fixed throughout. Thus, this experiment acts as an off-policy evaluation within the Mountain Car domain. In this experiment, we set the number of tilings to be 4, and there are no white noise features. As suggested by Sutton and Barto [3], we set all the initial parameters to be 0, which is optimistic about causing extensive exploration.

As before, we run the hyper parameter $\sigma$ as follows: $\sigma$ ranges from 0 to 1 with step of 0.02. It collects 51 results w.r.t. $\text{GQ}\left(\sigma ,\lambda \right)$ . We also set $\lambda =0.99$ , $\gamma =0.99$ , and run the step-size ${\alpha }_t=\left\{{10}^{-2},2\times {10}^{-2},{10}^{-3},2\times {10}^{-3}\right\}$ , ${\eta }_t={\beta }_t/{\alpha }_t=\left\{2^0,2^{-1},\cdots ,2^{-10}\right\}$ , the dimension of feature $p=\left\{512,1024,2048\right\}$ .

Overall Presentation. We give more comprehensive results of the trade-off between $\sigma =0$ and $\sigma =1$ . We statistic of the number of $\sigma$ happens for the following three case:

• (I) $\text{GQ}\left(\sigma ,\lambda \right)$ performs better than both $\sigma =0$ and $\sigma =1$ .

• (II) $\text{GQ}\left(\sigma ,\lambda \right)$ performs better than $\sigma =0$ or $\sigma =1$ .

• (III) $\text{GQ}\left(\sigma ,\lambda \right)$ performs worse than $\sigma =0$ and $\sigma =1$ .

The setting of $\sigma$ is the same as the previous section, and the total number of $\sigma$ reaches 51.

Table 1. Returns under various parameters.

Case

$\sigma =0$

$\sigma =1$

$\sigma =0.1$

$\sigma =0.2$

$\sigma =0.3$

$\sigma =0.4$

$\sigma =0.5$

$\sigma =0.6$

$\sigma =0.7$

$\sigma =0.8$

$\sigma =0.9$

$\alpha =0.001$

$p=512$

−122.0

−123.6

− 123.5

−119.8

−117.4

−120.8

−119.1

−120.5

−119.2

−119.3

−120.1

$p=1024$

−119.9

−121.9

−127.8

−120.2

−122.4

−122.0

−118.4

−121.6

−121.6

−124.0

−120.1

$p=2048$

−122.3

−121.4

−122.6

−121.9

−120.1

−122.3

−122.6

−119.6

−120.9

−121.4

−122.5

$\alpha =0.002$

$p=512$

−126.9

−124.2

−124.2

−127.5

−125.3

−125.2

−124.0

−121.6

−125.4

−125.8

−120.2

$p=1024$

−124.1

−123.1

−122.4

−126.3

−122.3

−123.0

−121.4

−126.2

−121.3

−123.6

−126.0

$p=2048$

−124.8

−124.0

−126.4

−124.6

−122.7

−123.9

−125.1

−122.5

−123.6

−126.4

−122.7

Table 2. Percentage under various parameters.

Case		$p=512$	$p=1024$	$p=2048$
$\alpha =0.001$	I	69.8%	20.4%	55.1%
	II	14.1%	36.7%	20.4%
	III	16.1%	42.9%	24.5%
$\alpha =0.002$	I	53.1%	6.1%	49.0%
	II	38.8%	16.3%	18.4%
	III	8.1%	77.6%	32.6%

Results Report. The results shown in Figure 2 and Table 1 are average of 5 runs, and each run contains 400 episodes. The result in Figure 2 shows that $\text{GQ}\left(\sigma ,\lambda \right)$ with an intermediate $\sigma$ (between 0 and 1) has a better performance than the extreme case ($\sigma =0$ and 1). This experiment further validates that unifying some existing algorithms can create a better algorithm for reinforcement. Table 1 shows the returns mountaincar reaches the goal region at the top of the hill. As shown in Table 2, those results also show $\text{GQ}\left(\sigma ,\lambda \right)$ achieves the best performance at a $\sigma \in \left(0,1\right)$ , which implies the trade-off between $\sigma =0$ and $\sigma =1$ . That is to see the $\text{GQ}\left(\sigma ,\lambda \right)$ with a value $\sigma \in \left(0,1\right)$ that creates a mixture of $\text{GQ}\left(\lambda \right)$ and gradient $\text{Tree Backup}\left(\lambda \right)$ achieves a better performance than both the extreme end $\sigma =0$ and $\sigma =1$ .

7. Conclusion

In this paper, we extend tabular $\text{Q}\left(\sigma ,\lambda \right)$ with function approximation, and propose $\text{GQ}\left(\sigma ,\lambda \right)$ . We analyze the convergence of $\text{GQ}\left(\sigma ,\lambda \right)$ . Our theory analysis shows that $\text{GQ}\left(\sigma ,\lambda \right)$ converges to its TD fixed-point with probability one. Then, we show $\text{GQ}\left(\sigma ,\lambda \right)$ converges to the optimal solution of the minimizing MSPBE problem. Finally, we conduct experiments on some standard domains to confirm the effectiveness of the proposed $\text{GQ}\left(\sigma ,\lambda \right)$ . Result show that the best performance of $\text{GQ}\left(\sigma ,\lambda \right)$ achieved with a $\sigma \in \left(0,1\right)$ , neither $\sigma =0$ , nor $\sigma =1$ . Extending this framework to non-linear function approximation is an important future direction. Such an extension faces theoretical hurdles, such as the parameter-dependence of the Jacobian and the loss of a fixed linear least-squares structure, which may require techniques like target networks or compatible gradients to stabilize.

Funding

The project was partially supported by Scientific Research Fund of Zhejiang Provincial Education Department under Grant No. Y202456228.

Appendix

A. Derivation of (28)-(29)

Proof. Let us calculate $\text{MSPBE}\left(\theta ,\lambda \right)$ directly,

$\begin{array}{c}-\frac{1}{2}J\left({\theta }_t\right)=-\frac{1}{2}{{\nabla }_{\theta }\text{MSPBE}\left(\theta ,\lambda \right)|}_{\theta ={\theta }_t}\\ =-\frac{1}{2}{\nabla }_{\theta }\left(\mathbb{E}{\left[{\delta }_t{e}_{t,\sigma }\right]}^{\top }\mathbb{E}{\left[{\varphi }_t{\varphi }_t^{\top }\right]}^{-1}\mathbb{E}\left[{\delta }_t{e}_{t,\sigma }\right]\right)\\ =-\left({\nabla }_{\theta }\mathbb{E}{\left[{\delta }_t{e}_{t,\sigma }\right]}^{\top }\right)\mathbb{E}{\left[{\varphi }_t{\varphi }_t^{\top }\right]}^{-1}\mathbb{E}\left[{\delta }_t{e}_{t,\sigma }\right]\\ =-\mathbb{E}\left[\left(\gamma {\mathbb{E}}_{\pi }\varphi \left(S_{t+1},\cdot \right)-{\varphi }_t\right)e_{t,\sigma }^{\top }\right]\mathbb{E}{\left[{\varphi }_t{\varphi }_t^{\top }\right]}^{-1}\mathbb{E}\left[{\delta }_t{e}_{t,\sigma }\right]\\ =-\mathbb{E}\left[\gamma {\mathbb{E}}_{\pi }\varphi \left(S_{t+1},\cdot \right)e_{t,\sigma }^{\top }-{\varphi }_t{e}_{t,\sigma }^{\top }\right]\mathbb{E}{\left[{\varphi }_t{\varphi }_t^{\top }\right]}^{-1}\mathbb{E}\left[{\delta }_t{e}_{t,\sigma }\right]\\ =\mathbb{E}\left[{\varphi }_t{\varphi }_t^{\top }+{\varphi }_{t+1}\gamma \lambda e_{t,\sigma }^{\top }-\gamma {\mathbb{E}}_{\pi }\varphi \left(S_{t+1},\cdot \right)e_{t,\sigma }^{\top }\right]\underset{=:\varpi }{\underbrace{\mathbb{E}{\left[{\varphi }_t{\varphi }_t^{\top }\right]}^{-1}\mathbb{E}\left[{\delta }_t{e}_{t,\sigma }\right]}}\\ =\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_{t,\sigma }\right]-\mathbb{E}\left[\gamma \left(1-\lambda \right){\overline{\varphi }}_{t+1}{e}_{t,\sigma }^{\top }\right]\varpi .\end{array}$(39)

□

B. Proof of Theorem 1

The ODE method (see Lemma 1) is our is our main tool to prove Theorem 1. We refer the reader to that reference for further technical details.

Lemma 1 ([25]). For the stochastic recursion of $x_n,y_n$ given by

$x_{n+1}=x_n+a_n\left[g\left(x_n,y_n\right)+M_{n+1}^{\left(1\right)}\right],$ (40)

$y_{n+1}=y_n+b_n\left[h\left(x_n,y_n\right)+M_{n+1}^{\left(2\right)}\right],n\in \mathbb{N}$ (41)

if the following assumptions are satisfied:

• (A1) Step-sizes $\left\{a_n\right\},\left\{b_n\right\}$ are positive, satisfying

${\displaystyle \sum }_n{a}_n={\displaystyle \sum }_n{b}_n=\infty ,{\displaystyle \sum }_n{a}_n^2+b_n^2<\infty ,\frac{b_n}{a_n}\to 0\text{as}n\to \infty .$

• (A2) The map $g:{ℝ}^{d+k}\to {ℝ}^d,h:{ℝ}^{d+k}\to {ℝ}^k$ are Lipschitz.

• (A3) The sequence ${\left\{M_{n+1}^{\left(1\right)}\right\}}_{n\in \mathbb{N}},{\left\{M_{n+1}^{\left(2\right)}\right\}}_{n\in \mathbb{N}}$ are martingale difference sequences w.r.t. the increasing $\sigma$ -fields ${ℱ}_n\stackrel{\text{def}}{=}\sigma \left(x_m,y_m,M_m^{\left(1\right)},M_m^{\left(2\right)},m\le n\right),n\in \mathbb{N},$ satisfying

$\mathbb{E}\left[M_{n+1}^{\left(i\right)}|{ℱ}_n\right]=0,i=1,2,n\in \mathbb{N}.$

Furthermore, ${\left\{M_{n+1}^{\left(i\right)}\right\}}_{n\in \mathbb{N}},i=1,2$ , are square-integrable with

$\mathbb{E}\left[{\Vert M_{n+1}^{\left(i\right)}\Vert }^2|{ℱ}_n\right]\le K\left(1+{\Vert x_n\Vert }^2+{\Vert y_n\Vert }^2\right),$

for some constant $K>0$ .

• (A4) For each $x\in {ℝ}^d$ , the o.d.e.

$\dot{y}\left(t\right)=h\left(x,y\left(t\right)\right)$

has a global asymptotically stable equilibrium $\Omega \left(x\right)$ such that: $\Omega \left(x\right):{ℝ}^d\to {ℝ}^k$ is Lipschitz.

• (A5) The o.d.e.

$\dot{x}\left(t\right)=g\left(x\left(t\right),\Omega \left(x\left(t\right)\right)\right)$

has a global asymptotically stable equilibrium $x^{\text{*}}$ .

Then, the iterates (40), (41) converge to $\left(x^{*},\Omega \left(x^{*}\right)\right)$ a.s. on the set $Q\stackrel{\text{def}}{=}\left\{{\sup }_n{x}_n<\infty ,{\sup }_n{y}_n<\infty \right\}$.

Proof. Now, we apply Lemma 1 to prove results.

Step 1: On Convergence of ω_t.

We consider the following ODE:

$\dot{\theta }\left(t\right)=0,\dot{\omega }\left(t\right)=\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_t|\theta \left(t\right)\right]-M\omega \left(t\right).$

The equation $\dot{\theta }\left(t\right)=0$ implies there exists a constant vector $\theta$ such that: $\theta \left(t\right)=\theta$ , thus we can rewrite the above ODE associated $\omega \left(t\right)$ as follows,

$\dot{\omega }\left(t\right)=\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_t|\theta \right]-M\omega \left(t\right)=A_{\sigma }\theta +b_{\sigma }-M\omega \left(t\right).$(42)

Then, for any given $\theta$ ,

${\omega }_{\star }=M^{-1}\left(A_{\sigma }\theta +b_{\sigma }\right)$

is the unique globally asymptotically stable equilibrium for the ODE (42). Let

$H\left(\omega ,\theta \right)=A_{\sigma }\theta +b_{\sigma }-M\omega ,$

for a fixed $\theta$ , let

$H_{\infty }\left(\omega ,\theta \right)=\underset{r\to \infty }{\text{lim}}\frac{H\left(r\omega \left(t\right),\theta \right)}{r}=-M\omega \left(t\right).$

Since $M$ is a positive definite matrix, then 0 is a globally asymptotically stable equilibrium for the following ODE

$\dot{\omega }\left(t\right)=H_{\infty }\left(\omega \left(t\right),\theta \right).$

Let the $\sigma$ -field ${ℱ}_t=\sigma \left({\left\{{\theta }_k,{\omega }_k,{\varphi }_k,R_k\right\}}_{k<t}\right)$ be generated by the set ${\left\{{\theta }_k,{\omega }_k,{\varphi }_k,R_k\right\}}_{k<t}$ , where $t\ge 1$ . Let

$M_{t+1}={\delta }_t^{\text{ES}}{e}_t-{\varphi }_t{\omega }_t^{\top }{\varphi }_t-\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_t-{\varphi }_t{\omega }_t^{\top }{\varphi }_t|{ℱ}_t\right],$

then for each $t\ge 0$ , we have $\mathbb{E}\left[M_{t+1}|{ℱ}_t\right]=0$ . Furthermore, since Assumption 3 holds, there exists a non-negative constant $K_1>0$ , s.t. ${\left\{M_t\right\}}_{t\in \mathbb{N}}$ is square-integrable with

$\mathbb{E}\left[{\Vert M_t\Vert }^2|{ℱ}_t\right]\le K_1\left(1+{\Vert {\theta }_t\Vert }^2+{\Vert {\omega }_t\Vert }^2\right).$

Since then, we have verified the conditions (A2)-(A5) of Lemma 1, thus

${\omega }_k-{\omega }_{\star }\to 0,w.p.1$

where $w.p.1$ is short for with probability one.

Step 2: On Convergence of θ_t.

Let the $\sigma$ -field ${\mathcal{G}}_t=\sigma \left({\left\{{\theta }_k,{\varphi }_k,R_k\right\}}_{k<t}\right)$ be generated by the set ${\left\{{\omega }_k,{\varphi }_k,R_k\right\}}_{k<t}$ , where $t\ge 1$ . The iteration (31) that can be rewritten as:

${\theta }_{t+1}={\theta }_t+{\alpha }_t\left({\delta }_t^{\text{ES}}{e}_t-\gamma \left(1-\lambda \right){\overline{\varphi }}_{t+1}{e}_t^{\top }{M}^{-1}\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_t|{\theta }_t\right]\right).$

Furthermore, we define a random variable $N_t$ as follows,

$\begin{array}{c}{N}_t={\delta }_t^{\text{ES}}{e}_t-\gamma \left(1-\lambda \right){\overline{\varphi }}_{t+1}{e}_t^{\top }{M}^{-1}\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_t|{\theta }_t\right]\\ -\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_t-\gamma \left(1-\lambda \right){\overline{\varphi }}_{t+1}{e}_t^{\top }{M}^{-1}\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_t|{\theta }_t\right]|{\mathcal{G}}_t\right],\end{array}$

then for each $t\ge 0$ , we have $\mathbb{E}\left[N_{t+1}|{\mathcal{G}}_t\right]=0$ . Now, we rewrite $N_t$ as follows,

$\begin{array}{c}{N}_t={\delta }_t^{\text{ES}}{e}_t-\gamma \left(1-\lambda \right){\overline{\varphi }}_{t+1}{e}_t^{\top }{M}^{-1}\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_t{\theta }_t\right]-\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_t{\theta }_t\right]\\ +\gamma \left(1-\lambda \right)\mathbb{E}\left[{\overline{\varphi }}_{t+1}{e}_t^{\top }\right]M^{-1}\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_t|{\theta }_t\right].\end{array}$

Under Assumption 3, for each $t\ge 0$ , there exists a non-negative constant $K_2>0$ such that,

$\mathbb{E}\left[{\Vert N_t\Vert }^2|{\mathcal{G}}_t\right]\le K_2\left(1+{\Vert {\theta }_t\Vert }^2\right).$

We consider the iteration (31) associated with the ODE

$\dot{\theta }\left(t\right)=\left(I-\gamma \left(1-\lambda \right)\mathbb{E}\left[{\overline{\varphi }}_{t+1}{e}_t^{\top }\right]M^{-1}\right)\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_t|\theta \left(t\right)\right].$(43)

Recall $M=\mathbb{E}\left[{\varphi }_t{\varphi }_t^{\top }\right]$ , from Equation (28), the ODE (43) can be rewritten as follows,

$\dot{\theta }\left(t\right)=-A_{\sigma }^{\top }{M}^{-1}\left(A_{\sigma }\theta \left(t\right)+b_{\sigma }\right)\stackrel{\left(33\right)}{=}G\left(\theta \left(t\right)\right).$ (44)

Since $A_{\sigma }$ is invertible, then ${\theta }_{\star }=-A_{\sigma }^{-1}{b}_{\sigma }$ is the unique global asymptotically stable equilibrium of ODE (44). Let

$G_{\infty }\left(\theta \right)=\underset{r\to \infty }{\text{lim}}\frac{G\left(r\theta ,\omega \right)}{r}=-A_{\sigma }^{\top }{M}^{-1}{A}_{\sigma }\theta .$

We consider the following ODE

$\dot{\theta }\left(t\right)=G_{\infty }\left(\theta \left(t\right)\right)=-A_{\sigma }^{\top }{M}^{-1}{A}_{\sigma }\theta \left(t\right).$ (45)

Since $A_{\sigma }$ is invertible and $M^{-1}$ is positive definite, then $A_{\sigma }^{\top }{M}^{-1}{A}_{\sigma }$ is a positive defined matrix. Equivalently, $-A_{\sigma }^{\top }{M}^{-1}{A}_{\sigma }$ is negative definite. Thus the vector 0 is the unique global asymptotically stable equilibrium of (45). According to Lemma 1,

${\theta }_k-{\theta }_{\star }\to 0,w.p\mathrm{.1.}$

Therefore the proof is completed. □

C. Proof of Theorem 2

Proof. Let ${\zeta }_t=\left(e_t,S_t,A_t,S_{t+1}\right)\in {ℝ}^p\times \mathcal{S}\times \mathcal{A}\times \mathcal{S}$ , then we rewrite the iteration (31) and (30) as follows

${\theta }_{t+1}={\theta }_t+{\alpha }_t\left(g\left({\theta }_t,{\omega }_t,{\zeta }_t\right)+e_t{\iota }_t\right),$

${\omega }_{t+1}={\omega }_t+{\beta }_t\left(h\left({\theta }_t,{\omega }_t,{\zeta }_t\right)+e_t{\nu }_t\right),$

where

$g\left({\theta }_t,{\omega }_t,{\zeta }_t\right)=\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_t-\gamma \left(1-\lambda \right){\mathbb{E}}_{\pi }\left[\varphi \left(S_{t+1,\cdot }\right)\right]e_t^{\top }{\omega }_t\right],$

$e_t{\iota }_t={\delta }_t^{\text{ES}}{e}_t-\gamma \left(1-\lambda \right){\mathbb{E}}_{\pi }\left[\varphi \left(S_{t+1,\cdot }\right)\right]e_t^{\top }{\omega }_t-g\left({\theta }_t,{\omega }_t,{\zeta }_t\right)$

satisfies $\mathbb{E}\left[e_t{\iota }_t\right]=0$ ; $h\left({\theta }_t,{\omega }_t,{\zeta }_t\right)=\mathbb{E}\left[{\delta }_t^{\text{ES}}{e}_t-{\varphi }_t{\omega }_t^{\top }{\varphi }_t\right]$ and $e_t{\nu }_t={\delta }_t^{\text{ES}}{e}_t-{\varphi }_t{\omega }_t^{\top }{\varphi }_t-h\left({\theta }_t,{\omega }_t,{\zeta }_t\right)$ .

Now, we apply ([26], Theorem 2.3 of Chapter 8) twice, once for each time-scale. We refer the reader to that reference for further technical details in ([26], Theorem 2.3 of Chapter 8), which requires us to verify the following conditions of (i)-(iv):

(i) The random variables $g\left({\theta }_t,{\omega }_t,{\zeta }_t\right)$ and $h\left({\theta }_t,{\omega }_t,{\zeta }_t\right)$ are uniformly integrable (UI), i.e.,

$\underset{a\to \infty }{\text{lim}}\underset{t\in \mathbb{N}}{\text{sup}}\mathbb{E}\left[\Vert g\left({\theta }_t,{\omega }_t,{\zeta }_t\right)\Vert \mathbb{I}\left\{\Vert g\left({\theta }_t,{\omega }_t,{\zeta }_t\right)\Vert \ge a\right\}\right]=0,$

$\underset{a\to \infty }{\text{lim}}\underset{t\in \mathbb{N}}{\text{sup}}\mathbb{E}\left[\Vert h\left({\theta }_t,{\omega }_t,{\zeta }_t\right)\Vert \mathbb{I}\left\{\Vert h\left({\theta }_t,{\omega }_t,{\zeta }_t\right)\Vert \ge a\right\}\right]=0,$

where $\mathbb{I}\{\cdot \}$ is the indicator function.

In fact, the uniform integrability of both $g\left({\theta }_t,{\omega }_t,{\zeta }_t\right)$ and $h\left({\theta }_t,{\omega }_t,{\zeta }_t\right)$ are ensured by the the UI property of $e_t=\lambda \gamma c_{t,\sigma }{e}_{t-1}+{\varphi }_t$ , and according to the same analysis of Proposition 2 from [27], we have $g\left({\theta }_t,{\omega }_t,{\zeta }_t\right)$ and $h\left({\theta }_t,{\omega }_t,{\zeta }_t\right)$ are UI.

(ii) The set of random variables $\left\{{\zeta }_t\right\}$ is tight, i.e, for each positive scalar $\delta$ , there exists a compact set $D_{\delta }\in {ℝ}^p\times \mathcal{S}\times \mathcal{A}\times \mathcal{S}$ such that

$\underset{t\in \mathbb{N}}{\text{inf}}\mathbb{P}\left[{\zeta }_t\in D_{\delta }\right]\ge 1-\delta .$

In fact, recall the Assumption 3 implies the trace vector $e_t$ satisfies ${\text{sup}}_{t\in \mathbb{N}}\Vert e_t\Vert <\infty$ , i.e.,

$\begin{array}{c}{\Vert e_t\Vert }_2^2={\Vert {\displaystyle \sum }_{k=0}^t{\left(\gamma \lambda \right)}^{t-k}{\displaystyle \prod }_{i=k+1}^t{c}_{i,\sigma }{\varphi }_k\Vert }_2^2\\ \le \frac{{\varphi }_{\text{max}}^2}{1-{\left(\gamma \lambda \left(\left(1-\sigma \right)+\sigma {\rho }_{\text{max}}\right)\right)}^2}.\end{array}$ (46)

For each $a>0$ , according to Markov inequality, we have

$\mathbb{P}\left[\Vert e_t\Vert \ge a\right]\le \frac{\underset{t\in \mathbb{N}}{\text{sup}}\Vert e_t\Vert }{a}\to 0,a\to \infty ,$

which implies $\left\{e_t\right\}$ is tight. Since we consider the MDPs with finite state space and action space, so the sequence ${\left\{{\zeta }_t=\left(e_t,S_t,A_t,S_{t+1}\right)\right\}}_{t\ge 0}$ is also tight.

(iii) Let $D_{\zeta }\in {ℝ}^p\times \mathcal{S}\times \mathcal{A}\times \mathcal{S}$ be a compact set, for each $\zeta \in D_{\zeta }$ , both $g\left(\theta ,\omega ,{\zeta }_0\right)$ and $h\left(\theta ,\omega ,{\zeta }_0\right)$ are continuous with respect to $\left(\theta ,\omega \right)$ .

Recall the definitions of $g\left(\theta ,\omega ,{\zeta }_0\right)$ and $h\left(\theta ,\omega ,{\zeta }_0\right)$ , then we have

$g\left(\theta ,\omega ,{\zeta }_0\right)=A_{\sigma }^{\top }{M}^{-1}\left(A_{\sigma }\theta +b_{\sigma }\right),$

$h\left(\theta ,\omega ,{\zeta }_0\right)=A_{\sigma }\theta +b_{\sigma }-M\omega .$

The Assumption 3 implies $A_{\sigma },M$ , and $b_{\sigma }$ are bounded, thus both $g\left(\theta ,\omega ,{\zeta }_0\right)$ and $h\left(\theta ,\omega ,{\zeta }_0\right)$ are continuous with respect to $\left(\theta ,\omega \right)$ .

(iv) Recall the notation $\varpi =\mathbb{E}{\left[{\varphi }_t{\varphi }_t^{\top }\right]}^{-1}\mathbb{E}\left[{\delta }_t^{ES}{e}_t\right]$ , for each compact set $D_{\zeta }\in {ℝ}^p\times \mathcal{S}\times \mathcal{A}\times \mathcal{S}$ , let

$H_{m,n}=\frac{1}{m}{\displaystyle \sum }_{t=n}^{n+m-1}\left(h\left(\theta ,\omega ,{\zeta }_t\right)-H\left(\theta ,\omega \right)\right)\mathbb{I}\left({\zeta }_t\in D_{\zeta }\right),$

$G_{m,n}=\frac{1}{m}{\displaystyle \sum }_{t=n}^{n+m-1}\left(g\left(\theta ,\varpi ,{\zeta }_t\right)-G\left(\theta \right)\right)\mathbb{I}\left({\zeta }_t\in D_{\zeta }\right),$

$X_{m,n}=\frac{1}{m}{\displaystyle \sum }_{t=n}^{n+m-1}\frac{{\alpha }_t}{{\beta }_t}g\left(\theta ,\omega ,{\zeta }_t\right),$

then for each $\left(\theta ,\omega \right)\in {ℝ}^p\times {ℝ}^p$ , we have:

$\underset{m,n\to \infty }{\text{lim}}\mathbb{E}\left[H_{m,n}\right]=\underset{m,n\to \infty }{\text{lim}}\mathbb{E}\left[G_{m,n}\right]=\underset{m,n\to \infty }{\text{lim}}\mathbb{E}\left[X_{m,n}\right]=0.$

By the Jensen’s inequality, it is sufficient that

$H_{m,n}\to 0,G_{m,n}\to 0,X_{m,n}\to 0,$

as $m,n\to \infty$ . With the fact

$\mathbb{E}\left[h\left(\theta ,\omega ,{\zeta }_0\right)\right]=A_{\sigma }\theta +b_{\sigma }-M\omega$

and following the same analysis of Proposition 2.3 in [28], we have $H_{m,n}\to 0$ , as $m,n\to \infty$ . Similarly, we have $G_{m,n}\to 0$ , as $m,n\to \infty$ .

Note that $g\left(\theta ,\omega ,{\zeta }_t\right)$ is Lipschitz continuous with respect to the trace variable $e_t$ , where $e_t\in {\zeta }_t$ . Thus, there exists a positive scalar $L$ such that $\Vert g\left(\theta ,\omega ,{\zeta }_t\right)\Vert \le L\Vert e_t\Vert$ . From Assumption 3, we have ${\text{sup}}_{t\in \mathbb{N}}\Vert e_t\Vert <\infty$ and ${\lim }_{t\to \infty }{\alpha }_t/{\beta }_t=0$ , then we have

$X_{m,n}\to 0,$

as $m,n\to \infty$ . □

NOTES

¹The term “weight-duplication trick” we use here is coming from [10] [11], while some other literatures may call it “two-timescale stochastic approximation”, e.g., [18].

²http://incompleteideas.net/rlai.cs.ualberta.ca/RLAI/RLtoolkit/tilecoding.html