8  Applications to reinforcement learning

Reinforcement learning (RL) refers to a class of model-free algorithms that have become widely popular for problems of decision making under uncertainty. In most real-life situations, it is hard to have precise knowledge of the system model, and this is where RL algorithms are immensely useful as these are largely data-driven algorithms.

In this chapter, we consider specifically two settings of reinforcement learning algorithms, both involving policy gradient (PG) based approaches (Richard S. Sutton et al. 1999) for reinforcement learning. These algorithms typically assume that the decision making policy is parameterized and have traditionally involved obtaining unbiased gradient estimators of the performance objective, many times the value function, w.r.t the aforementioned policy parameters. However, recent work suggests that zeroth order gradient estimators can result in improved performance, see for instance, (Salimans et al. 2017; Mania, Guy, and Recht 2018). In many other situations, such as in the case of actor-critic algorithms that also involve policy gradient algorithms but where the algorithm’s parameters are updated as soon as a data sample becomes available, using zeroth order methods prove to be particularly effective, see for instance, (Bhatnagar and Kumar 2004; Abdulla and Bhatnagar 2007).

8.1 REINFORCE with an SPSA Gradient Estimate

REINFORCE is one of the popular algorithms in reinforcement learning that is based on Monte-Carlo or trajectory-based estimates of the value function. It has been first presented in (Williams 1992), see also (R. S. Sutton and Barto 2018, chap. 13). We however study an application of zeroth-order gradient estimation in this setting. The work that we present in this section is based on (Bhatnagar 2023).

8.1.1 The Basic Setting

By a Markov decision process, we mean a controlled stochastic process \(\{X_n\}\) whose evolution is governed by an associated control-valued sequence \(\{Z_n\}\). It is assumed that the random variables \(X_n,n\geq 0\) take values in a set \(S\) called the state-space. Let \(A(s)\) denote the set of all feasible actions in state \(s\in S\) and \({\displaystyle A \stackrel{\triangle}{=} \cup_{s\in S} A(s)}\) denote the set of all actions. When the state (\(X_n\)) is say \(s\) and a feasible action \(a\) is chosen, the next state (\(X_{n+1}\)) seen is \(s'\) with a probability \(p(s'|s,a) \stackrel{\triangle}{=} P(X_{n+1}=s'\mid X_n=s, Z_n=a)\), \(\forall n\). We assume these probabilities do not depend on \(n\). Such a process satisfies the controlled Markov property, i.e.,

\[ P(X_{n+1}=s' \mid X_n, Z_n, \ldots, X_0, Z_0) = p(s'\mid X_n, Z_n) \mbox{ a.s.} \]

By an admissible policy or simply a policy, we mean a sequence of functions \(\pi=\{\mu_0,\mu_1,\mu_2,\ldots\}\), with each \(\mu_i:S\rightarrow A\), \(i\geq 0\), such that \(\mu_i(s) \in A(s)\), \(\forall s\in S\). The policy \(\pi\) is a decision rule which specifies that if at instant \(k\), the state is \(i\), then the action chosen under \(\pi\) would be \(\mu_k(i)\). A stationary policy \(\pi\) is one for which \(\mu_k = \mu_l \stackrel{\triangle}{=} \mu\), \(\forall k,l=0,1,\ldots\). In other words, under a stationary policy, the function that decides the action-choice in a given state does not depend on time instant \(n\). Many times, instead of calling \(\pi=\{\mu,\mu,\mu,\ldots\}\) a stationary policy, we simply refer to the function \(\mu\) itself as the stationary policy.

Associated with any transition to a state \(s'\) from a state \(s\) under action \(a\), is a ‘single-stage’ cost \(g(s,a,s')\) where \(g:S\times A\times S\rightarrow \mathbb{R}\) is called the cost function. The goal of the decision maker is to select actions \(a_k, k\geq 0\), in response to the system states \(s_k,k\geq 0\), so as to minimize a long-term cost objective. We assume here that the number of states and actions is finite. In particular, we let \(1,\ldots,p\) denote the set of non-terminal or regular states and \(t\) be the terminal or goal state. We let \(S=\{1,2,\ldots,p\}\) denote the set of all non-terminal states. Further, let \(S^+=\{1,\ldots,p,t\}=S\cup\{t\}\).

In this section, we are concerned with the stochastic shortest path problem, see (D. P. Bertsekas 2012; D. Bertsekas 2019), where we assume that under any policy, there is a positive probability of hitting the terminal state in at most \(p\) steps starting from any initial state, that would in turn signify that the problem would terminate in a finite though random amount of time. Such policies are called proper policies (see Definition 8.1 and Assumption A8.1).

Under a given policy \(\pi\), define

\[ V_\pi(s) = E_\pi\left[\sum_{k=0}^{T} g(X_k,\mu_k(X_k),X_{k+1})\mid X_0=s\right], \mbox{ } s\in S, \]

where \(0<T<\infty\) is a finite random time at which the process enters the terminal state. Here \(E_\pi[\cdot]\) indicates that all actions are chosen according to policy \(\pi\) depending on the system state. We assume that there is no action that is feasible in the terminal state \(t\) and thus once the process reaches \(t\), it terminates.

Let \(\Pi\) denote the set of all admissible policies. The goal here is to find the optimal value function \(V^*(i), i\in S\), defined by

\[ V^*(i) = \min_{\pi\in \Pi} V_\pi(i) = V_{\pi^*}(i), \mbox{ } i\in S, \]

where \(\pi^*\) denotes the optimal policy, i.e., the one that minimizes \(V_\pi(i)\), \(i\in S\), over all policies \(\pi\). A related goal here would be to find the policy \(\pi^*\). It turns out that in these problems, there exist stationary policies that are optimal. Thus, it is sufficient to search for an optimal policy within the class of stationary policies.

Definition 8.1.

A stationary policy \(\mu\) is called a proper policy if

\[ \hat{p}_\mu \stackrel{\triangle}{=} \max_{s=1,\ldots,p}P(X_p \not= t\mid X_0=s, \mu) <1. \]

In other words, regardless of the initial state \(s\) (assumed non-terminal for obvious reasons), there is a positive probability of termination after at most \(p\) stages when using a proper policy.

Assuming that all stationary policies are proper, the optimal value function satisfies the Bellman equation

\[ V^*(s) = \min_{a\in A(s)} \sum_{j\in S^+} p(j\mid s,a)(g(s,a,j) + V^*(j)), \mbox{ } s\in S, \tag{8.1} \]

where by convention \(V^*(t)=0\). It can be shown, see (D. P. Bertsekas 2012), that an optimal stationary proper policy exists.

An admissible policy (and so also a stationary policy) can be randomized as well. A randomized admissible policy or simply a randomized policy is a sequence of distributions \(\psi =\{\phi_0,\phi_1,\ldots\}\) with each \(\phi_i:S\rightarrow P(A)\). Even though \(A\) is the set of all actions, for any \(s\in S\), a randomized policy would provide a distribution \(\phi_i(s) = (\phi_i(s,a), a\in A(s))\) with \(\phi_i(s,a)\geq 0,\forall a\in A(s)\), and \(\sum_{a\in A(s)} \phi_i(s,a)=1\). This also implies that \(\phi_i(s,a)=0\), \(\forall a\not\in A(s)\). A stationary randomized policy is one for which \(\phi_j=\phi_k\stackrel{\triangle}{=} \phi\), \(\forall j,k=0,1,\ldots\). In this case, we simply call \(\phi\) to be a stationary randomized policy. By the foregoing, since an optimal stationary proper policy exists, an optimal stationary randomized policy that is also proper would exist as well.

8.1.2 The Reinforcement Learning Problem

We consider now the RL setting where we do not assume any knowledge of the system model, i.e., the transition probabilities \(p(s'\mid s,a)\), and in their place, we assume that we have access to data (either real or simulated). The data that is available is over trajectories of states, actions, single-stage costs and next states until termination.

We assume that trajectories of states and actions are available either as real data or from a simulation device. Let \(G_k\) denote the sum of costs until termination on a trajectory starting from instant \(k\). In other words, \({\displaystyle G_k = \sum_{j=k}^{T-1} g_j}\) where \(g_j\equiv g(s_j,a_j,s_{j+1})\), where \(s_j,s_{j+1}\) are the states visited on this trajectory at time instants \(j,j+1\), and \(a_j\) is the action chosen at instant \(j\) in the trajectory. Note that if all actions are chosen according to a policy \(\phi\), then the value function (under \(\phi\)) would be obtained as

\[ V_\phi(s) = E_\phi[G_k \mid X_k=s], \mbox{ } s\in S. \tag{8.2} \]

Further, by convention (cf. (D. Bertsekas 2019; R. S. Sutton and Barto 2018)), we let \(V_\phi(t)=0\), for any policy \(\phi\).

We consider here a class of stationary randomized policies that are parameterized by a parameter \(\theta=(\theta_1,\ldots,\theta_d)\tr \in C\subset \mathbb{R}^d\) where \(C\) is a compact and convex subset of \(\mathbb{R}^d\). We shall denote such a policy \(\phi_\theta \stackrel{\triangle}{=} (\phi_\theta(s),s\in S)\), where for any \(s\in S\), \(\phi_\theta(s) =(\phi_\theta(s,a),a\in A(s))\) is a distribution over \(A(s)\) when \(\theta\) is the given parameter. We make the following assumption:

Assumption A8.1.

All stationary randomized policies \(\phi_\theta\) parameterized by \(\theta\in C\) are proper.

The REINFORCE algorithm of (R. S. Sutton and Barto 2018) is a Monte-Carlo procedure based on the policy gradient method. The original algorithm uses a procedure for estimating the performance gradient that is based on an interchange of the gradient and expectation operators. We apply here a two-simulation but one-sided SPSA-based procedure for estimating the performance gradient that does not require the aforementioned interchange of operators. As mentioned, this procedure will however require two system simulations. We explain the algorithm in more detail below.

Let \(\Gamma:{\cal R}^d\rightarrow C\) denote a projection operator that projects any \(x=(x_1,\ldots,x_d)\tr \in {\cal R}^d\) to its nearest point in \(C\). Thus, if \(x\in C\), then \(\Gamma(x)\in C\) as well. For ease of exposition, let’s assume that \(C\) is a \(d\)-dimensional rectangle having the form \({\displaystyle C = \prod_{i=1}^{d} [a_{i,\min}, a_{i,\max}]}\), where \(-\infty< a_{i,\min} < a_{i,\max} <\infty\), \(\forall i=1,\ldots,d\). A convenient way to identify \(\Gamma(x)\) is as follows: Note that \(\Gamma(x)=(\Gamma_1(x_1),\ldots,\Gamma_N(x_N))\tr\), where the \(i\)th component operator \(\Gamma_i:{\cal R}\rightarrow [a_{i,\min},a_{i,\max}]\) is specified by \({\displaystyle \Gamma_i(x_i) = \min(a_{i,\max}, \max(a_{i,\min},x_i))}\), \(i=1,\ldots,d\). Also, let \({\cal C}(C)\) denote the space of all continuous functions from \(C\) to \({\cal R}^d\).

Let \(\theta(n)\) and \((\theta(n)+\delta\Delta(n)), n\geq 0\) be two parameter sequences where \(\theta(n)=(\theta_1(n),\ldots,\theta_d(n))\tr \in \mathcal{R}^d\), \(\delta>0\) is a small constant and \(\Delta(n)=(\Delta_1(n),\ldots,\Delta_d(n))\tr, n\geq 0\), with \(\Delta_i(n),i=1,\ldots,d,n\geq 0\) being independent random variables distributed according to \(\Delta_i(n)=\pm 1\) w.p. 1/2. The updates \(\theta(n)\) of the parameter \(\theta\) are obtained using an algorithm that will be explained below. Algorithm (8.3) below is used to update the parameter \(\theta \in C \subset \mathbb{R}^d\). For a given \(n\geq 0\), let \(\chi^n\) and \(\chi^{n+}\) respectively denote the state-action trajectories \(\chi^{n} = \{s^{n}_0,a^{n}_0,s^{n}_1,a^{n}_1,\ldots,s^{n}_{T-1},a^{n}_{T-1},s^{n}_T\}\) and \(\chi^{n+} = \{s^{n+}_0,a^{n+}_0,s^{n+}_1,a^{n+}_1,\ldots,s^{n+}_{T^+-1},a^{n+}_{T^+-1},s^{n+}_{T^+}\}\), respectively, where \(\chi^n\) is governed by the parameter \(\theta(n)\) and \(\chi^{n+}\) is governed by \(\theta(n)+\delta\Delta(n)\). The instant \(T\) (resp. \(T^+\)) denotes the termination instant in the trajectory \(\chi^n\) (resp. \(\chi^{n+}\)). Thus, in both \(\chi^n\), \(\chi^{n+}\), \(s^n_T = s^{n+}_{T+}=t\), i.e., each episode ends once the terminal or goal state is reached. Note that the various actions in the trajectory \(\chi^n\) are chosen according to the policy \(\phi_{\theta(n)}\) (depending on the states visited in the trajectory). Similarly, the actions in the trajectory \(\chi^{n+}\) are chosen according to the policy \(\phi_{\theta(n)+\delta\Delta(n)}\). The initial states in the two trajectories are kept the same, i.e., \(s^n_0=s^{n+}_0\), and sampled from a given initial distribution \(\nu = (\nu(i),i\in S)\) over states.

Let \({\displaystyle G^n = \sum_{k=0}^{T-1} g^n_k}\) and \({\displaystyle G^{n+} = \sum_{k=0}^{T^+-1} g_k^{n+}}\) denote the sums of costs until termination on the two trajectories that are governed with parameters \(\theta(n)\) and \(\theta(n)+\delta\Delta(n)\), respectively, where \(g^n_k \equiv g(s^n_k,a^n_k,s^n_{k+1})\) and \(g^{n+}_k \equiv g(s^{n+}_k,a^{n+}_k,s^{n+}_{k+1})\).

The update rule that we consider here is the following:

For \(n\geq 0, i=1,\ldots,d\),

\[ \theta_i(n+1) = \Gamma_i\left(\theta_i(n) -a(n) \left( \frac{G^{n+}-G^n}{\delta\Delta_i(n)} \right)\right). \tag{8.3} \]

We assume here that \(\{a(n)\}\) satisfy the following assumption:

Assumption A8.2.

The step-size sequence \(\{a(n)\}\) satisfies \(a(n)>0\), \(\forall n\). Further,

\[ \sum_n a(n)=\infty, \mbox{ } \sum_n a(n)^2 <\infty. \]

Assumption A8.3.

The stationary randomized policy \(\phi_\theta\), \(\forall \theta\in C\) is twice continuously differentiable in \(\theta\) and has a bounded third derivative.

While A8.2 is a standard requirement on the step-sizes, see the previous chapters, A8.3 is a requirement on the smoothness of the parameterized stationary randomized policies that can be seen to be satisfied by many classes of policies. For instance, the popularly used parameterized Gibbs or Boltzmann policy given by

\[ \phi_\theta(s,a) = \frac{\exp(\theta\tr\psi_{s,a})}{\sum_{b\in A(s)}\exp(\theta\tr\psi_{s,b})}, \]

with prescribed state-action features \(\psi_{s,a}\in \mathbb{R}^d\), \(s\in S\), \(a\in A(s)\), can be seen to satisfy this requirement.

As soon as a parameter update is available, two trajectories – governed by the nominal and perturbed parameters, respectively, are generated with the initial state in the perturbed trajectory the same as that in the nominal trajectory and with the initial state sampled according to a given distribution \(\nu\).

8.1.3 Convergence Analysis

We begin by rewriting the algorithm (8.3) as follows:

\[ \theta_i(n+1) = \Gamma_i\left(\theta_i(n) -a(n) E\left[ \frac{G^{n+}-G^n}{\delta\Delta_i(n)} \mid \mathcal{F}_n\right] + M^i_{n+1}\right), \tag{8.4} \]

where

\[ M^i_{n+1} = \frac{G^{n+}-G^n}{\delta\Delta_i(n)} - E\left[ \frac{G^{n+}-G^n}{\delta\Delta_i(n)} \mid \mathcal{F}_n\right]. \]

Here, we let \(\mathcal{F}_n \stackrel{\triangle}{=} \sigma(\theta(m), m\leq n, \Delta(m), \chi^m, \chi^{m+}, m<n), n\geq 1\) be a sequence of increasing sigma fields and with \(\mathcal{F}_0 = \sigma(\theta(0))\). Let \(M_n=(M^1_n,\ldots,M^d_n)\tr\), \(n\geq 0\). Here we let \(\norm{\cdot}\) denote the Euclidean norm.

Lemma 8.1.

\((M_n,\mathcal{F}_n),n\geq 0\) is a martingale difference sequence.

Proof.

Notice that

\[ M_{n} = \frac{G^{(n-1)+}-G^{(n-1)}}{\delta\Delta_i(n-1)} - E\left[ \frac{G^{(n-1)+}-G^{(n-1)}}{\delta\Delta_i(n)} \mid \mathcal{F}_{n-1}\right]. \]

The first term on the RHS above is clearly measurable \(\mathcal{F}_n\) while the second term is measurable \(\mathcal{F}_{n-1}\) and hence measurable \(\mathcal{F}_n\) as well. Further, from Assumption A8.1, each \(M_n\) is integrable. Finally, it is easy to verify that

\[ E[M_{n+1}\mid \mathcal{F}_n] =0. \]

The claim follows.

\(\square\)

In the following, for simplicity, we denote \(V_{\phi_\theta}(s)\) as \(V_\theta(s)\) itself for any \(\theta\in C\). If \(\phi_\theta\) is a twice continuously differentiable function of \(\theta\), it can be shown that \(V_\theta(s)\) is also a twice continuously differentiable function of \(\theta\) for any state \(s\).

Proposition 8.1.

We have

\[ E\left[ \frac{G^{n+}-G^n}{\delta\Delta_i(n)} \mid \mathcal{F}_n\right] = \sum_{s\in S} \nu(s)\nabla_i V_{\theta(n)}(s) + o(\delta) \mbox{ a.s.} \]

Proof.

Note that

\[ E\left[ \frac{G^{n+}-G^n}{\delta\Delta_i(n)} \mid \mathcal{F}_n\right] = E\left[E\left[ \frac{G^{n+}-G^n}{\delta\Delta_i(n)} \mid \mathcal{G}_n\right]\mid \mathcal{F}_n \right], \]

where \(\mathcal{G}_n \stackrel{\triangle}{=} \sigma(\theta(m), \Delta(m), m\leq n, \chi^m, \chi^{m+}, m<n), n\geq 1\) be a sequence of increasing sigma fields with \(\mathcal{G}_0 = \sigma(\theta(0),\Delta(0))\). It is clear that \(\mathcal{F}_n \subset \mathcal{G}_n, \forall n\geq 0\). Now,

\[ E\left[ \frac{G^{n+}-G^n}{\delta\Delta_i(n)} \mid \mathcal{G}_n\right] = \frac{1}{\delta\Delta_i(n)} \left( E[G^{n+}\mid \mathcal{G}_n] - E[G^n\mid \mathcal{G}_n] \right). \]

Let \(s^n_0=s^{n+}_0=s\) denote the initial state in both the trajectories \(\chi^n\) and \(\chi^{n+}\), respectively. Recall that the initial state \(s\) is chosen randomly from the distribution \(\nu\). Thus,

\[ E[G^n\mid\mathcal{G}_n] = \sum_s \nu(s) E[G^n\mid s^n_0=s, \phi_{\theta(n)}] \]

\[ = \sum_s \nu(s) V_{\theta(n)}(s). \]

Similarly,

\[ E[G^{n+}\mid\mathcal{G}_n] = \sum_s \nu(s) E[G^{n+}\mid s^{n+}_0=s, \phi_{\theta(n)+\delta\Delta(n)}] \]

\[ = \sum_s \nu(s) V_{\theta(n)+\delta\Delta(n)}(s). \]

Thus,

\[ E\left[ \frac{G^{n+}-G^n}{\delta\Delta_i(n)} \mid \mathcal{G}_n\right] = \sum_{s} \nu(s)\left(\frac{V_{\theta(n)+\delta\Delta(n)}(s) - V_{\theta(n)}(s)}{\delta\Delta_i(n)}\right) \mbox{ a.s.} \]

Thus,

\[ E\left[ \frac{G^{n+}-G^n}{\delta\Delta_i(n)} \mid \mathcal{F}_n\right] = \sum_s \nu(s) E\left[ \frac{V_{\theta(n)+\delta\Delta(n)}(s) - V_{\theta(n)}(s)}{\delta\Delta_i(n)} \mid \mathcal{F}_n\right]. \]

Using a Taylor’s expansion of \(V_{\theta(n)+\delta\Delta(n)}(s)\) around \(\theta(n)\) gives us

\[ V_{\theta(n)+\delta\Delta(n)}(s_n) = V_{\theta(n)}(s_n) + \delta \Delta(n)\tr \nabla V_{\theta(n)}(s_n) \]

\[ + \frac{\delta^2}{2} \Delta(n)\tr \nabla^2 V_{\theta(n)}(s_n) \Delta(n) + o(\delta^2). \]

Thus,

\[ \frac{V_{\theta(n)+\delta\Delta(n)}(s_n)-V_{\theta(n)}(s_n)}{\delta\Delta_i(n)} = \nabla_i V_{\theta(n)}(s_n) + \sum_{k\not=i} \frac{\Delta_k(n)}{\Delta_i(n)} \nabla_k V_{\theta(n)}(s_n) \]

\[ + \frac{\delta}{2} \sum_{j,k=1}^{d} \frac{\Delta_j(n)\nabla^2_{j,k}V_{\theta(n)(s_n)}\Delta_k(n)}{\Delta_i(n)} + o(\delta). \tag{8.5} \]

Now,

\[ E\left[\left(\frac{V_{\theta(n)+\delta\Delta(n)}(s_n)-V_{\theta(n)}(s_n)}{\delta\Delta_i(n)} \right)\mid \mathcal{F}_n \right] = \nabla_i V_{\theta(n)}(s_n) + o(\delta). \tag{8.6} \]

This follows from the following two observations:

  1. The second term on the RHS of (8.5) gives us

    \[ E\left[\sum_{k\not=i} \frac{\Delta_k(n)}{\Delta_i(n)}\nabla_k V_{\theta(n)}(s_n) \mid \mathcal{F}_n \right] = E\left[\sum_{k\not=i} \frac{\Delta_k(n)}{\Delta_i(n)} \right] \nabla_k V_{\theta(n)}(s_n) =0, \]

    from the properties of the sequence \(\Delta_l(n),l=1,\ldots,d\).

  2. The third term on the RHS of (8.5) gives us

    \[ \frac{\delta}{2} E\left[\sum_{j,k=1}^{d} \frac{\Delta_j(n)\nabla^2_{j,k}V_{\theta(n)}\Delta_k(n)}{\Delta_i(n)} \mid \mathcal{F}_n\right] \]

    \[ = \frac{\delta}{2} \sum_{j,k=1}^{d} E\left[\frac{\Delta_j(n)\Delta_k(n)}{\Delta_i(n)}\right] \nabla^2_{j,k} V_{\theta(n)}(s_n) =0. \]

    This can be seen by analysing all the cases in the summation: (i) \(j\not=k\not=i\), (ii) \(j\not=k=i\), (iii) \(j=i\not=k\), (iv) \(j=k\not=i\), and (v) \(j=k=i\), respectively, using again the properties of the sequence \(\Delta_l(n),l=1,\ldots,d\).

The claim follows.

\(\square\)

In the light of (8.6), we can rewrite (8.3) as follows:

\[ \theta(n+1) = \Gamma(\theta(n) - a(n)(\sum_{s}\nabla V_{\theta(n)}(s) + \eta(n)+\beta(n))), \tag{8.7} \]

where

\[ \eta(n) = \left(\frac{G_n^+-G_n}{\delta\Delta_i(n)}\right) - E\left[\left(\frac{G_n^+-G_n}{\delta\Delta_i(n)}\right)\mid \mathcal{F}_n \right] \]

and \(\beta(n) = (\beta_1(n),\ldots,\beta_d(n))\) with

\[ \beta_i(n) = E\left[\left(\frac{G_n^+-G_n}{\delta\Delta_i(n)}\right)\mid \mathcal{F}_n \right] -\sum_{s} \nu(s) \nabla_i V_{\theta(n)}(s). \]

From Proposition 8.1, it can be seen that \(\beta(n) = o(\delta)\). It is now easy to see that (8.7) has the same form as (4.2).

Lemma 8.2.

The function \(\nabla v_\theta(s)\) is Lipschitz continuous in \(\theta\). Further, \(\exists\) a constant \(K_1>0\) such that \(\norm{\nabla v_\theta(s)} \leq K_1(1+\norm{\theta})\).

Proof.

It can be shown under A8.3 (see for instance Chapter 13 of (R. S. Sutton and Barto 2018) that \(v_\theta(s)\) is continuously differentiable in \(\theta\) and satisfies

\[ \nabla v_\theta(s) = \sum_{y\in S}\sum_{k=0}^{\infty} P_{\theta}^k(s,y) \sum_{a\in A(y)} \nabla \phi_\theta(a\mid y) q_\theta(y,a), \]

where \(P_{\theta}^k(s,y)\) is the probability of going from state \(s\) to state \(y\) in \(k\) steps under policy \(\phi_\theta\) and \(q_\theta(y,a) = E_\theta[G_n\mid X_n=y, Z_n=a]\) is the value of the state-action tuple \((y,a)\) when actions in states subsequent to state \(y\) follow the policy \(\phi_\theta\). It can also be shown as in Theorem 3 of (Furmston, Lever, and Barber 2016) that \(\nabla^2 v_\theta(s)\) exists and is continuous. Since \(\theta\) takes values in \(C\), a compact set, it follows that \(\nabla^2 v_\theta(s)\) is bounded and thus \(\nabla v_\theta(s)\) is Lipschitz continuous.

Finally, let \(L_1^s>0\) denote the Lipschitz constant for the function \(\nabla v_\theta(s)\). Then, for a given \(\theta_0\in C\),

\[ \norm{ \nabla v_\theta(s)} - \norm{\nabla v_{\theta_0}(s)} \leq \norm{\nabla v_\theta(s)-\nabla v_{\theta_0}(s)} \]

\[ \leq L_1^s \norm{\theta-\theta_0} \]

\[ \leq L_1^s \norm{\theta} + L_1^s\norm{\theta_0}. \]

Thus,

\[ \norm{\nabla v_\theta(s)} \leq \norm{\nabla v_{\theta_0}(s)} + L^s_1 \norm{\theta_0} + L^s_1\norm{\theta}. \]

Let \(K_s \stackrel{\triangle}{=} \norm{\nabla v_{\theta_0}(s)} + L^s_1\norm{\theta_0}\) and \(K_1 \stackrel{\triangle}{=} \max(K_s, L^s_1, s\in S)\). Since \(|S|<\infty\), \(K_1<\infty\). Thus, \(\norm{\nabla v_\theta(s)} \leq K_1(1+\norm{\theta})\).

\(\square\)

Lemma 8.3.

The martingale sequence \((M_n,\mathcal{F}_n)\), \(n\geq 0)\) satisfies

\[ E[\norm{M_{n+1}}^2\mid \mathcal{F}_n] \leq \hat{L}(1+\norm{\theta(n)}^2), \]

for some constant \(\hat{L}>0\).

Proof.

Note that

\[ \begin{align*} \norm{M_{n+1}}^2 &= \sum_{i=1}^d (M^i_{n+1})^2 \\ &= \frac{(G^{n+}-G^n)^2}{\delta^2} +\frac{1}{\delta^2} \left(E\left[\frac{G^{n+}-G^n}{\Delta_i(n)}\mid \mathcal{F}_n\right]\right)^2 \\ &\quad - 2 \frac{G^{n+}-G^n}{\delta\Delta_i(n)} E\left[\frac{G^{n+}-G^n}{\delta\Delta_i(n)}\mid \mathcal{F}_n\right]. \end{align*} \]

Thus,

\[ E[\norm{M_{n+1}}^2\mid \mathcal{F}_n] = E\left[\frac{(G^{n+}-G^n)^2}{\delta^2} \mid \mathcal{F}_n\right] - \left(E\left[\frac{G^{n+}-G^n}{\delta\Delta_i(n)}\mid \mathcal{F}_n\right]\right)^2. \]

It now follows from Assumption A8.1 and the fact that all single-stage costs are bounded, that \(E[\norm{M_{n+1}}^2 \mid \mathcal{F}_n] \leq \check{K}\) almost surely. In fact from Proposition 8.1 and Lemma 8.2, it follows that

\[ \left(E\left[\frac{G^{n+}-G^n}{\delta\Delta_i(n)}\mid \mathcal{F}_n\right]\right)^2 = \left(\sum_{s\in S} \nu(s)\nabla_i V_{\theta(n)}(s)\right)^2 + o(\delta) \leq K_\delta, \]

for some \(K_\delta <\infty\). It will thus follow that

\[ E[\norm{M_{n+1}}^2 \mid \mathcal{F}_n] \leq \check{K}(1+\norm{\theta(n)}^2. \]

\(\square\)

Define now a sequence \(Z_n,n\geq 0\) according to

\[ Z_n = \sum_{m=0}^{n-1} a(m)M_{m+1}, \]

\(n\geq 1\) with \(Z_0=0\).

Lemma 8.4.

\((Z_n,\mathcal{F}_n)\), \(n\geq 0\) is an almost surely convergent martingale sequence.

Proof.

It is easy to see that \(Z_n\) is \(\mathcal{F}_n\)-measurable \(\forall n\). Further, it is integrable for each \(n\) and moreover \(E[Z_{n+1}\mid \mathcal{F}_n] = Z_n\) almost surely since \((M_{n+1},\mathcal{F}_n)\), \(n\geq 0\) is a martingale difference sequence by Lemma 8.1. It is also square integrable from Lemma 8.3. The quadratic variation process of this martingale will be convergent almost surely if

\[ \sum_{n=0}^{\infty} E[\norm{Z_{n+1}-Z_n}^2 \mid \mathcal{F}_n] <\infty \mbox{ a.s.} \]

Note that

\[ E[\norm{Z_{n+1}-Z_n}^2 \mid \mathcal{F}_n] = a(n)^2 E[ \norm{M_{n+1}}^2 \mid \mathcal{F}_n]. \]

Thus,

\[ \begin{align*} \sum_{n=0}^{\infty} E[\norm{Z_{n+1}-Z_n}^2 \mid \mathcal{F}_n]& = \sum_{n=0}^{\infty} a(n)^2 E[ \norm{M_{n+1}}^2 \mid \mathcal{F}_n] \\ &\leq \check{K} \sum_{n=0}^{\infty} a(n)^2 (1+\norm{ \theta(n)}^2), \end{align*} \]

by Lemma 8.3. The claim now follows from Assumption A8.2 and the fact that \(\theta(n)\in C, \forall n\), a compact set. Now \((Z_n,\mathcal{F}_n)\), \(n\geq 0\) can be seen to be convergent from the martingale convergence theorem for square integrable martingales (see Theorem B.7).

\(\square\)

Consider now the following ODE:

\[ \dot{\theta}(t) = \bar{\Gamma}\left(-\sum_{s}\nu(s) \nabla V_{\theta}(s)\right), \tag{8.8} \]

where \(\bar{\Gamma}: {\cal C}(C)\rightarrow {\cal C}({\cal R}^d)\) is as defined in (2.32).

Let \(H\stackrel{\triangle}{=} \{\theta\,|\,\bar{\Gamma}\left(-\sum_{s}\nu(s) \nabla V_{\theta}(s)\right)\}\) denote the set of asymptotically stable attractors of (8.8). Let \(H^\epsilon \stackrel{\triangle}{=} N^\epsilon(H)\cap C\) denote the \(\epsilon\)-neighborhood of \(H\) within the set \(C\). Here, \(N^\epsilon(H) = \{\theta\mid\) \(\norm{\theta-\theta_0} <\epsilon\), \(\theta_0\in H\}\).

The following is the main result of this section.

Theorem 8.5.

Given \(\epsilon>0\), \(\exists \delta_0>0\) such that \(\forall \delta \in [0,\delta_0)\), the stochastic sequence \(\{\theta(n)\}\) obtained from (8.3) converges with probability one to \(H^\epsilon\).

Proof.

We shall proceed by verifying Assumptions A2.9-A2.12. Note that Assumption A2.9 has been shown in Lemma 8.2. Assumption A2.10 is an assumption on the step-size sequence \(\{a(n)\}\) that has also been made for the iterates (8.3), see A8.2. Now from Lemma 8.2, it follows that \(\sum_s\) \(\nu(s) \nabla v_\theta(s)\) is uniformly bounded since \(\theta\in C\), a compact set. Assumption A2.11 is now verified from Proposition 8.1. Assumption A2.12 is easy to see as a consequence of Lemma 8.4. Now note that for the ODE (8.8), \(F(\theta)=\sum_s \nu(s) V_\theta(s)\) serves as an associated Lyapunov function and in fact

\[ \begin{align*} &\nabla F(\theta)\tr \bar{\Gamma}\left(-\sum_{s}\nu(s) \nabla V_{\theta}(s)\right) \\ &= \left(\sum_s \nu(s) \nabla_\theta V_\theta(s)\right)\tr\bar{\Gamma}\left(-\sum_{s}\nu(s) \nabla V_{\theta}(s)\right) \\ &\leq 0. \end{align*} \]

For \(\theta\in C^o\) (the interior of \(C\)), it is easy to see that \(\bar{\Gamma}(\sum_s \nu(s) \nabla V_\theta(s))\) \(=\sum_s \nu(s)\nabla V_\theta(s)\), and

\[ \begin{align*} \nabla F(\theta)\tr \bar{\Gamma}(-\sum_{s}\nu(s) \nabla V_{\theta}(s)) &< 0 \mbox{ if } \theta \in H^c \cap C \\ &= 0 \mbox{ otherwise.} \end{align*} \]

For \(\theta\in \delta C\) (the boundary of \(C\)), there can be spurious attractors on the boundary of \(C\), see (Kushner and Yin 2003), that are also contained in \(H\). The claim now follows from Theorem 2.5.

\(\square\)

8.2 Simultaneous perturbation-based risk-sensitive policy gradient

We again consider a stochastic shortest path (SSP) problem, with a special cost-free absorbing state, say \(0\). We restrict our attention to proper policies (see Definition 8.1), which ensure state \(0\) is recurrent, and the remaining states are transient in the Markov chain underlying the policy considered. We define an episode as a sample path \(\{x_0, \ldots, x_\tau\}\), where \(x_\tau=0\), and \(\tau\) is the first passage time to state \(0\).

Consider a smoothly parameterized class of policies \(\{\pi_\theta \mid \theta\in \R^d \}\). Suppose that the policy \(\pi_\theta\) is a continuously differentiable function of the parameter \(\theta\): a standard assumption in policy gradient literature. Let \(K_\theta(x_0)\) denote the total discounted cost r.v. under policy \(x\) starting in state \(x_0\), i.e., \(K_\theta ( x_0 ) = \sum _ { t = 0 } ^ { \tau -1 } \gamma^t k(x_t,a_t)\), where \(0 < \gamma < 1\) is the discount factor and \(k(x_t,a_t)\) is the single-stage cost incurred at time instant \(t\) in state \(x_t\) on choosing action \(a_t\). Here actions \(a_t\) are chosen according to policy \(\pi_\theta\), which is parameterized by \(\theta\).

The classic objective in RL is to find a policy that minimizes, in expectation, the total discounted cost. We consider a risk-sensitive RL setting, where the goal is to find a policy that optimizes a certain risk measure, i.e., the following problem:

\[ \begin{align*} \min_{\theta \in \R^d} \left\{ \rho(K_{ \theta }(x_0))\right\}, \tag{8.9} \end{align*} \]

where \(\theta \in \R^d\) parameterizes the policy \(\pi_{ \theta }\), and \(\rho\) is a risk measure. As examples, we define three risk measures below for a random variable \(X\) with CDF \(F\).

CVaR:

Recall that the VaR and CVaR at level \(\alpha\in (0,1)\) are defined as

\[ \begin{align*} \text{VaR}_{\alpha}(X)&=\inf\left\{\xi \mbox{ }|\mbox{ }\mathbb{P}\left(X\leq \xi\right)\geq\alpha\right\}, \tag{8.10} \\ \text{CVaR}_{\alpha}(X) &=\inf_{\xi} \left\lbrace \xi + \frac{1}{(1-\alpha)}\E\left( X -\xi\right)_+ \right\rbrace. \tag{8.11} \end{align*} \]

As mentioned earlier in Subsection 2.2.6, VaR is not a coherent risk measure, while CVaR is. Coherency includes properties, namely monotonicity, sub-additivity, positive homogeneity and translation invariance. These properties are desirable for any risk measures, esp. in the context of finance, and VaR is not sub-additive. In financial context, sub-additivity relates to diversification, which is performed to reduce the risk, e.g., a financial portfolio.

Spectral risk measure (SRM):

This risk measure, proposed in (Acerbi 2002), is defined as

\[ \begin{align*} M_{\phi}(X) = \int_{0}^{1}\phi(\beta)F^{-1}(\beta)\mathrm{d}\beta, \tag{8.12} \end{align*} \]

where \(\phi:[0,1]\rightarrow [0,\infty)\) is the risk spectrum. SRM is a coherent risk measure, when the risk spectrum is positive, increasing and integrates to one. Moreover, SRM generalizes CVaR after observing the following equivalent form, known as Acerbi’s formula:

\[ \begin{align*} \text{CVaR}_{\alpha}(X) = \frac{1}{1-\alpha}\int_{\alpha}^{1}\mathrm{VaR}_{\beta}(X)\,d\beta. \tag{8.13} \end{align*} \]

In particular, CVaR is an SRM with \(\varphi(\beta) = \frac{1}{1-\alpha}\indic{\beta>\alpha},\, \alpha \in (0,1).\) As an example, one could consider \(\phi(\beta) = \frac{\kappa\,e^{-\kappa(1-\beta)}}{1-e^{-\kappa}}, \beta \in [0,1]\) for some \(\kappa>0\). From an attitude towards risk viewpoint, assuming \(X\) models the loss associated with a financial position, SRM with an exponential risk spectrum defined above, is preferable over CVaR as it assigns a higher weight to larger losses, whereas CVaR the same weight for all losses beyond a certain quantile.

Utility-based shortfall risk (UBSR):

UBSR, proposed in (Föllmer and Schied 2002), for a given loss function \(l\) and threshold parameter \(\lambda\), is defined as

\[ \begin{align*} S_\alpha(X) = \inf\left\{\xi \in \R \mid \E\left( l(-X-\xi)\right)\le \alpha\right\}. \tag{8.14} \end{align*} \]

UBSR belongs to the class of convex risk measures, which subsumes coherent risk measures, since sub-additivity and positive homogeneity imply convexity. As examples of loss functions in the definition of UBSR above, one could consider the following: (i) \(l(x)=\exp(\beta x)\); and (ii) \(l(x)=x^2\). For the first candidate loss, UBSR turns out to be the entropic risk measure. For the second candidate loss, i.e., the square loss, UBSR can be related to CVaR, see (Giesecke, Schmidt, and Weber 2008).

Notice that the optimization problem in (8.9) is non-convex in nature. For solving the problem defined above using gradient-based methods, one requires (i) an estimate of the risk measure for any given policy \(\pi_\theta\); and (ii) an estimate of the gradient of the risk measure w.r.t. the policy parameter \(\theta\). We elaborate on these two parts below.

We simulate \(m\) episodes simulated using the policy \(\pi_{ \theta }\), and collect samples of the total cost \(K_{ \theta }(x_0)\). Let \(\{K_1,\ldots,K_m\}\) denote the i.i.d. samples from the distribution of \(K_{ \theta }(x_0)\). We define the empirical distribution function (EDF) \(F_m\) of \(K_\theta ( x_0 )\) as follows:

\[ F_m(\theta)=\frac{1}{m} \sum_{i=1}^m \indic{K_i \leq x}, \,\forall x\in \R. \]

Using the EDF, we form the estimate \(\rho_{m}\) of \(\rho(K_{ \theta }(x_0))\) as follows:

\[ \begin{align*} \rho_m = \rho(F_m). \tag{8.15} \end{align*} \]

Such an estimation scheme for an abstract risk measure has been considered earlier in (Prashanth and Bhat 2022).

Next, we present a bound in expectation for the estimation error associated with (8.15).

Proposition 8.2.

Suppose the risk measure \(\rho\) satisfies the following continuity requirement for any two distributions \(F,G\) for some \(L>0\):

\[ \begin{align*} \left| \rho(F) - \rho(G)\right| \le L W_1(F,G), \tag{8.16} \end{align*} \]

where \(W_1(F,G)\) is the Wasserstein distance1 between distributions \(F\) and \(G\). Suppose the r.v. \(K_\theta(x_0)\) satisfies \(\E[ K_\theta(x_0)^2] \le B < \infty\), for any \(x \in \R^d\). Then,

\[ \E \left| \rho_m - \rho(K_\theta(x_0)) \right| \le \frac{c}{\sqrt{m}}, \]

for some constant \(c\) that depends on \(B\).

Proof.

Let \(F\) denote the distribution of \(K_\theta(x_0)\). Then, we have

\[ \begin{align*} \E\left| \rho_m - \rho(K_\theta(x_0))\right| &= \E\left| \rho(F_m) - \rho(F)\right| \le L W_1(F_m,F) \le \frac{c_1 L B}{\sqrt{m}}, \end{align*} \]

where the final inequality follows by using Theorem 3.1 of (Lei 2020).

\(\square\)

The continuity requirement in (8.16) is satisfied by the three popular risk measures CVaR, UBSR and SRM, and the reader is referred to (Prashanth and Bhat 2022) for details.

To construct an estimate of the gradient of the risk measure \(\rho(K_\theta(x_0))\), one could employ the simultaneous perturbation method, e.g., the estimate in (3.15). Using this gradient estimate, and the template of RSG-BGO algorithm, we arrive at the following update iteration for the risk-sensitive policy gradient (risk-PG) algorithm:

\[ \begin{align*} \theta _ { k + 1 } = \theta _ { k } - a(k) \widehat \nabla \rho(\theta_k), \tag{8.17} \end{align*} \]

where \(\gamma_k\) is the stepsize, and \(\widehat \nabla \rho(\theta_k)\) is an estimate of the gradient of the risk measure \(\rho(K_{\theta_k}(x_0))\). To elaborate on the gradient estimation aspect of the algorithm above, we first simulate \(m_k\) trajectories of the underlying MDP with policy parameters \(\theta_k + \delta_k \Delta_k\) and \(\theta_k - \delta_k \Delta_k\), respectively. Here \(\delta_k\) is the perturbation constant, and \(\Delta_k\) is a standard Gaussian vector. Other random perturbations are feasible, see Chapter 3. Using (8.15), we estimate the risk measures \(\rho(K_{\theta_k \pm \delta_k \Delta_k}(x_0))\) corresponding to the aforementioned policy parameters, and then, use (3.15) to form \(\widehat \nabla \rho(\theta_k)\).

For a non-asymptotic analysis of (8.17), we require smoothness of \(\rho\) as a funciton of \(\theta\). We verify this assumption for the special case of CVaR below. Let \(\text{C}_\alpha(K_{ \theta }(x_0))\) denote the CVaR associated with a policy \(\pi\) that is parameterized by \(\theta\). Then, using the likelihood ratio method, we arrive at the following variant of the policy gradient theorem under the CVaR objective (cf. (Tamar et al. 2015)):

\[ \begin{align*} &\nabla_\theta C_\alpha(K_\theta(x_0)) = \mathbb{E}\bigg[ [ K_\theta(x_0)- \text{VaR}_{\alpha}(K_\theta(x_0)) ] \\ & \quad \times \underbrace{\sum\limits_{m=0}^{\tau-1} \nabla \log \pi_\theta(a_m |x_m) }_{(I)} \bigg{|} K_\theta(x_0) \geq \text{VaR}_{\alpha}(K_\theta(x_0)) \bigg]. \end{align*} \]

In the above, \(K_\theta(x_0)\) and term (I) on the RHS are Lipschitz functions due to the policy gradient assumption mentioned above. In addition, if we assume that the distribution, say \(F_\theta\), of \(K_\theta(x_0)\) is a Lipschitz function in \(\theta\), then we can infer that \(\nabla_\theta C_\alpha(K_\theta(x_0))\) is sum of product of Lipschitz functions, implying smoothness of CVaR as a function of \(\theta\). One could generalize this argument to the case when \(\rho\) is a coherent risk measure, and the reader is referred to (Tamar et al. 2015) for details.

Using the non-asymptotic bounds for a RSG algorithm, see Section 5.5, we can infer that the iteration complexity for the risk-sensitive policy gradient algorithm (8.17) is \(\mathcal{ O} \left(\frac{1}{\epsilon^3}\right)\).

8.3 Bibliographic remarks

Reinforcement learning has been found to be extremely useful in problems of dynamic decision making under uncertainly when the decision maker has access to data (either from a real system or alternatively a simulation) but not the transition model. Textbook treatments of RL are available in (R. S. Sutton and Barto 2018; D. P. Bertsekas and Tsitsiklis 1996; D. Bertsekas 2019; Meyn 2022). We considered two different RL settings in this chapter: (i) finding optimal policies for stochastic shortest path problems and (ii) finding optimal policies for risk sensitive control, again in the stochastic shortest path case. Both the algorithms that we presented fall under the broad category of policy gradient algorithms. For (i), we specifically considered the REINFORCE algorithm developed originally in (Williams 1992), see also (R. S. Sutton and Barto 2018, chap. 13), (Richard S. Sutton et al. 1999) for a detailed treatment. Whereas the original algorithm required a single simulation and involved unbiased function gradients, we presented in this chapter a zeroth-order algorithm based on two-simulation SPSA gradient estimates. This algorithm has been presented and analysed in (Bhatnagar 2023). An alternative to using trajectory-based Reinforce type policy gradient algorithms for finding the optimal policy is to use two-timescale actor-critic algorithms, where on the faster timescale, the critic recursion estimates the value function corresponding to the most recent policy parameter update most often using a temporal difference (TD) learning procedure, while along the slower recursion, the policy parameter is updated using policy gradients.

Zeroth-order stochastic gradient estimation based procedures have been found to be efficient and are not new to the literature, see for instance, (Bhatnagar and Kumar 2004; Abdulla and Bhatnagar 2007) in the context of actor-critic algorithms. In the context of trajectory-based policy gradient algorithms (like REINFORCE), (Salimans et al. 2017; Mania, Guy, and Recht 2018) have proposed generating multiple trajectories of data for a given parameter update and then selecting the best candidate directions over which an additional layer of sample averaging is performed which then is used as an increment for the parameter update. Even though the latter can be computationally tedious, it is found to improve the performance of the algorithm. In (Choromanski et al. 2018), zeroth order algorithms based on evolutionary strategies for policy optimization again for reinforcement learning are presented. They make use of random orthogonal matrices and study specifically two constructions for the random perturbations - one based on Gaussian perturbations and another on random Hadamard Rademacher matrices.

Zeroth-order gradient-based methods have been employed for solving risk-sensitive RL problems through the policy gradient solution approach. A variety of risk measures have been tackled using zeroth-order policy gradients, and we list a few representative works in the following: (i) SPSA for mean-variance optimization in a discounted MDP in (Prashanth and Ghavamzadeh 2016); (ii) SF for distortion risk measures in (Vijayan and Prashanth 2023); (iii) A simultaneous perturbation-based oracle for optimizing smooth risk measures in (Bhavsar and Prashanth 2022). Our presentation in Section 8.2 is based the contributions from the aforementioned reference.

  1. Given two cumulative distribution functions (CDFs) \(F\) and \(G\) on \(\R\), let \(\Gamma(F , G )\) denote the set of all joint distributions on \(\R^2\) having \(F\) and \(G\) as marginals. Then the Wasserstein distance between \(F\) and \(G\) is defined by \(W_{1}\left(F, G\right) = \left[\inf _{C \in \Gamma\left(F, G\right)} \int_{\mathbb{R}^{2}}|x-y| d C(x, y)\right].\)↩︎