#### Blog Stats

• 131,400 hits

# Hierarchical Policy Gradient Algorithms

### Notation

: the overall task MDP.

{M0, M1, M2 , M3 , . . . , Mn } : a finite set of subtask MDPs.

M: subtask, models a subtask in the hierarchy.

M0 : root task and solving it solves the entire MDP M.

i : non-primitive subtask, paper uses subtask to refer to non-primitive subtask.

Si : state space for non-primitive subtask i.

Ii : initiation set.

Ti : set of terminal state.

Ai : action space.

Pi : transition probability function.

Ri : reward function.

a : primitive action, is a primitive subtask in this decomposition, it terminates immediately after execution.

μi : subtask i policy.

μ={μ0 , μμμ, . . . , μn} : hierarchical policy

μi(θi) : randomized stationary policies parameterized in terms of a vector θ ℜK .

μi(s, a, θi: probability of taking action a in state s under the policy corresponding to θi.

s*i : absorbing state, all terminal states (s  Ti ) transit with probability 1 and reward 0 to an absorbing state s*i .

$\bar{\color{Red}&space;{\pi}}&space;^i({\color{Blue}&space;s})$ : The probability that subtask i starts at state s.

$M_{\bar{{\color{Red}&space;\pi}}^{\color{Magenta}&space;i}}^{\color{Magenta}&space;i}$ : MDP for subtask i .

$P^{\color{Magenta}&space;i}_{\bar{\color{Red}&space;\pi}^{\color{Magenta}&space;i}}(s'&space;\mid&space;s,&space;{\color{Magenta}&space;a})&space;=\left\{\begin{matrix}&space;P{\color{Magenta}^i&space;}({\color{DarkBlue}&space;s'}&space;\mid{\color{Blue}&space;s},{\color{Magenta}&space;a})&space;&&space;s\neq&space;s^*^i&space;\\&space;\bar&space;{\color{Red}&space;\pi}^{\color{Magenta}&space;i}({\color{DarkBlue}&space;s'})&space;&&space;s&space;=&space;{\color{Golden}&space;s^*^i}&space;\end{matrix}\right.$ : MDP for subtask transition probabilities.

$\mathbb{P}^i_{\bar&space;{\color{Red}&space;\pi}}$ : the set of all transition matrices $P^{\color{Magenta}&space;i}_{\bar{\color{Red}&space;\pi}^{\color{Magenta}&space;i}}(s'&space;\mid&space;s,&space;{\color{red}&space;\mu^i(\theta^i)})$.

${\color{Blue}&space;\chi}&space;^{\color{Magenta}&space;i}({\color{Red}&space;\theta}^{\color{Magenta}&space;i})$ : weighted reward-to-go, the performance measure of subtask i formulated by parameterized policy μi(θi).

${\color{Blue}&space;J}^{\color{Magenta}&space;i}({\color{Blue}&space;s},{\color{Red}&space;\theta}^{\color{Magenta}&space;i})$ : reward-to-go of state s.

$T=min\left&space;\{&space;{\color{Red}&space;k}&space;>0&space;\mid&space;s_{\color{Red}&space;k}={\color{Golden}&space;s^*^i}&space;\right&space;\}$ : the first future time that state s*i is visited.

${\color{Golden}&space;\bigtriangledown}&space;{\color{Blue}&space;\chi}^{\color{Magenta}&space;i}(&space;{\color{Red}&space;\theta}&space;^{\color{Magenta}&space;i})$ : gradient of the weighted reward-to-go ${\color{Blue}&space;\chi}&space;^{\color{Magenta}&space;i}({\color{Red}&space;\theta}^{\color{Magenta}&space;i})$ with respect to ${\color{Red}&space;\theta}^{\color{Magenta}&space;i}$.

${\color{Red}&space;\pi}^i_{\bar\pi}(s,{\color{Red}&space;\theta}^i)$ : steady state probability distribution of being in state s.

$E_{\bar\pi,&space;\theta&space;^i}\left&space;[T&space;\right&space;]=E_{\bar\pi^i,\theta^i}&space;\left[&space;\&space;T&space;\mid&space;s_0={\color{Golden}&space;s^*^i}\&space;\right&space;]$ : mean recurrence time.

${\color{Blue}&space;Q}^i(s,a,\theta^i)=E_{\bar\pi^i,\theta^i}&space;\left[&space;\&space;\sum_{{\color{Red}&space;k=0}}^{T-1}&space;{\color{Blue}&space;R}^i_{\bar\pi^i}&space;(s_{\color{Red}&space;k},&space;\theta^i)&space;\mid&space;s_0=s,&space;a_0=a\&space;\right&space;]$ : usual action-value function.

$F_m^i(\theta^i)$ : estimate gradient of the weighted reward-to-go ${\color{Blue}&space;\chi}&space;^{\color{Magenta}&space;i}({\color{Red}&space;\theta}^{\color{Magenta}&space;i})$ with respect to ${\color{Red}&space;\theta}^{\color{Magenta}&space;i}$ , i.e., ${\color{Golden}&space;\bigtriangledown}&space;{\color{Blue}&space;\chi}^{\color{Magenta}&space;i}(&space;{\color{Red}&space;\theta}&space;^{\color{Magenta}&space;i})$ .

tm : the time of the mth visit at the recurrent state s*i .

$\tilde{{\color{Blue}&space;Q}}^i(s_n,a_n,{\color{Red}&space;\theta}^i)=\sum_{k=n}^{{\color{Red}&space;t_{m+1}}-1}{\color{Blue}&space;R}^i(s_n,a_n)$ : an estimate of Qi .

${\color{Golden}&space;\alpha}$ : step size parameter.

### Policy Gradient Formulation

After decomposing the overall problem into a set of subtasks, the paper formulates each subtask as policy gradient reinforcement learning problem. The paper focus on episodic problems, so it assume that the overall task (root of the hierarchy) is episodic.

### Assumption 1

For every state s ∈ Si and every action a ∈ Ai μi(s, a, θias a function of θi , is bounded and has bounded first and second derivatives. Furthermore, we have

${\color{DarkGreen}&space;\bigtriangledown}&space;{\color{Red}&space;\mu^i}({\color{Blue}&space;s},{\color{Magenta}&space;a},{\color{red}&space;\theta^i})={\color{Red}&space;\mu^i}({\color{Blue}&space;s},{\color{Magenta}&space;a},{\color{Red}&space;\theta^i})\&space;{\color{Blue}&space;\psi^i}({\color{Blue}&space;s},{\color{Magenta}&space;a},{\color{Red}&space;\theta^i})$

where ${\color{Blue}&space;\psi^i}({\color{Blue}&space;s},{\color{Magenta}&space;a},{\color{Red}&space;\theta^i})$ is bounded, differential and has bounded first derivatives.

### Subtask Termination

There exists a state s*∈ Si such that, for every action a ∈ Awe have

${\color{Blue}&space;R}^i({\color{Blue}&space;s^*}^i,{\color{Magenta}&space;a})=0$

${\color{Red}&space;P}^i({\color{Blue}&space;s^*}^i&space;\mid&space;{\color{Blue}&space;s^*}^i,{\color{Magenta}&space;a})=1$

and for all stationary polices μi(θiand all states s∈ Si, we have

${\color{Red}&space;P}^i({\color{Blue}&space;s^*}^i,&space;{\color{Blue}&space;N}&space;\mid&space;{\color{Blue}&space;s},&space;{\color{Red}&space;\mu}&space;^i&space;({\color{Red}&space;\theta}^i))>0$

${\color{Blue}&space;N}=\left&space;|&space;{\color{Blue}&space;S}^i&space;\right&space;|$

Under this model, we define a new MDP $M_{\bar{{\color{Red}&space;\pi}}^{\color{Magenta}&space;i}}^{\color{Magenta}&space;i}$ for subtask i transition probabilities:

$P^{\color{Magenta}&space;i}_{\bar{\color{Red}&space;\pi}^{\color{Magenta}&space;i}}(s'&space;\mid&space;s,&space;{\color{Magenta}&space;a})&space;=\left\{\begin{matrix}&space;P{\color{Magenta}^i&space;}({\color{DarkBlue}&space;s'}&space;\mid{\color{Blue}&space;s},{\color{Magenta}&space;a})&space;&&space;s\neq&space;s^*^i&space;\\&space;\bar&space;{\color{Red}&space;\pi}^{\color{Magenta}&space;i}({\color{DarkBlue}&space;s'})&space;&&space;s&space;=&space;{\color{Golden}&space;s^*^i}&space;\end{matrix}\right.$

where

$\bar{\color{Red}&space;{\pi}}&space;^{\color{Magenta}&space;i}({\color{Blue}&space;s})$: the probability that subtask i starts at state s.

Let $\mathbb{P}^i_{\bar&space;{\color{Red}&space;\pi}}$ be the set of all transition matrices $P^{\color{Magenta}&space;i}_{\bar{\color{Red}&space;\pi}^{\color{Magenta}&space;i}}(s'&space;\mid&space;s,&space;{\color{red}&space;\mu^i(\theta^i)})$ . We have the following result for subtask i.

### Lemma 1

Let assumptions A1 and A2 hold. Then for every $P^i_{\bar&space;{\color{Red}&space;\pi}^i}&space;\in&space;\mathbb{P}^i_{\bar&space;{\color{Red}&space;\pi}}$ , and every state ${\color{Blue}&space;s}&space;\in&space;{\color{Blue}&space;S}^{\color{Magenta}&space;i}$ , we have

$\sum_{n=1}^N&space;P^i_{\bar{\color{Red}&space;\pi}}({\color{Golden}&space;s^*^i},&space;{\color{Blue}&space;n&space;\mid&space;s},&space;{\color{Red}&space;\mu}^{\color{Magenta}&space;i}({\color{Red}&space;\theta}^{\color{Magenta}&space;i}))>0$where

${\color{Blue}&space;N}=\left&space;|&space;{\color{Blue}&space;S}^i&space;\right&space;|$

Lemma 1 is equivalent to assume that the MDP $M_{\bar{{\color{Red}&space;\pi}}^{\color{Magenta}&space;i}}^{\color{Magenta}&space;i}$ is recurrent, i.e., the underlying Markov chain for every policy μi(θiin this MDP has a single recurrent class and the state s*i is recurrent state.

### Performance Measure Definition

Paper defines weighted reward-to-go ${\color{Blue}&space;\chi}&space;^{\color{Magenta}&space;i}({\color{Red}&space;\theta}^{\color{Magenta}&space;i})$, the performance measure of subtask i formulated by parameterized policy μi(θi).

Assumption A2 holds

${\color{Blue}&space;\chi}^i(\theta^i)=\sum_{s&space;\in&space;S^i}&space;\bar&space;{\color{Red}&space;\pi}^i(s){\color{Blue}&space;J}^i(s,{\color{Red}&space;\theta}^i)$

where ${\color{Blue}&space;J}^{\color{Magenta}&space;i}({\color{Blue}&space;s},{\color{Red}&space;\theta}^{\color{Magenta}&space;i})$ is reward-to-go of state s.

${\color{Blue}&space;J}{\color{Magenta}&space;^i}({\color{Blue}&space;s},{\color{Red}&space;\theta}^{\color{Magenta}&space;i})=E_{\theta{\color{Magenta}&space;^i}}\left&space;[&space;\&space;\sum_{k=0}^{T-1}&space;{\color{Blue}&space;R}{\color{Magenta}&space;^i}({\color{Blue}&space;s}_k,{\color{Red}&space;\theta}{\color{Magenta}&space;^i})&space;\mid&space;s_0={\color{Blue}&space;s}&space;\&space;\right&space;]$

$J{\color{Magenta}&space;^i}(s,&space;\theta^{\color{Magenta}&space;i})=E_{\theta{\color{Magenta}&space;^i}}\left&space;[&space;\&space;\sum_{{\color{Red}&space;k}=0}^{T-1}&space;R{\color{Magenta}&space;^i}(&space;s_{\color{Red}&space;k},&space;\theta{\color{Magenta}&space;^i})&space;\mid&space;s_0=&space;s&space;\&space;\right&space;]$

where $T$ is the first future time that state s*i is visited.

$T=min\left&space;\{&space;{\color{Red}&space;k}&space;>0&space;\mid&space;s_{\color{Red}&space;k}={\color{Golden}&space;s^*^i}&space;\right&space;\}$

### Proposition 1

If assumptions A1 and A2 hold

${\color{Golden}&space;\bigtriangledown}&space;{\color{Blue}&space;\chi}&space;^i({\color{Red}&space;\theta}^i)=E_{\bar&space;\pi^i}\left&space;[T&space;\right&space;]\sum_{s&space;\in&space;S^i}&space;\sum_{a&space;\in&space;A^i}&space;{\color{Red}&space;\pi}_{\bar&space;\pi^i}^i(s,{\color{Red}&space;\theta}^i)&space;\bigtriangledown&space;{\color{Red}&space;\mu}^i(s,a,\theta^i){\color{Blue}&space;Q}^i(s,a,{\color{Red}&space;\theta}^i)$

Cycle between consecutive visits to recurrent state s*i = renewal cycle

${\color{Golden}&space;\bigtriangledown}&space;{\color{Blue}&space;\chi}^{\color{Magenta}&space;i}(&space;{\color{Red}&space;\theta}&space;^{\color{Magenta}&space;i})$ can be estimated over a renewal cycle as

$F_m^i(\theta^i)=\sum_{n=t_m}^{t_{m+1}-1}&space;{\color{Blue}&space;\tilde{Q}}^i(s_n,a_n,\theta^i)\frac{\bigtriangledown&space;\mu^i(s_n,a_n,\theta^i)}{\mu^i(s_n,a_n,\theta^i)}$  (P1)

$\tilde{{\color{Blue}&space;Q}}^i(s_n,a_n,{\color{Red}&space;\theta}^i)=\sum_{k=n}^{{\color{Red}&space;t_{m+1}}-1}{\color{Blue}&space;R}^i(s_n,a_n)$

where tm is the time of the mth visit at the recurrent state s*i .

From P1, the paper obtains the following procedure to update the parameter vector along the approximate gradient direction at every time step.

\begin{align*}&space;{\color{Magenta}&space;z^i}_{k+1}&=\left\{\begin{matrix}&space;0&space;&&space;s_k=s^*^i\\&space;z_k^i+\psi^i(s_k,a_k,\theta_k^i)&space;&&space;otherwise&space;\end{matrix}\right.\\&space;{\color{Red}&space;\theta^i}_{k+1}&=\theta^i_k+{\color{Golden}&space;\alpha}_k^i{\color{Blue}&space;R}^i(s_k,a_k){\color{Magenta}&space;z^i}_{k+1}&space;\end{align*}  (P2)

P2 provides an unbiased estimate of ${\color{Golden}&space;\bigtriangledown}&space;{\color{Blue}&space;\chi}^{\color{Magenta}&space;i}(&space;{\color{Red}&space;\theta}&space;^{\color{Magenta}&space;i})$ . For systems involving a large state space, the interval between visits to state s*i can be large. As a consequence, the estimate of ${\color{Golden}&space;\bigtriangledown}&space;{\color{Blue}&space;\chi}^{\color{Magenta}&space;i}(&space;{\color{Red}&space;\theta}&space;^{\color{Magenta}&space;i})$ might have a large variance.

${\color{Golden}&space;\alpha}$ : step size parameter and satisfies the following assumptions.

### Assumption 4

${\color{Golden}&space;\alpha}_k$ ‘s are deterministic, nonnegative and satisfy

$\sum_{k=1}^{\infty}&space;{\color{Golden}&space;\alpha}_k&space;=\infty&space;\&space;and\&space;\sum_{k=1}^{\infty}&space;{\color{Golden}&space;\alpha}_k^2&space;<&space;\infty$

### Assumption 5

${\color{Golden}&space;\alpha}_k$ ‘s are non-increasing and there exists a positive integer p and a positive scalar A such that

$\sum_{k={\color{Magenta}&space;n}}^{{\color{Magenta}&space;n}+{\color{Red}&space;t}}({\color{Golden}&space;\alpha}_{\color{Magenta}&space;n}-{\color{Golden}&space;\alpha}_k)\leq&space;{\color{DarkGreen}&space;A}&space;{\color{Red}&space;t}^{\color{Blue}&space;p}{\color{Golden}&space;\alpha}_{\color{Magenta}&space;n}^2$

for all positive integers n and t.

The paper has the following convergence result for the iterative procedure in P2 to update the parameters.

### Proposition 2

Let assumption A1, A2, A4 and A5 hold, and let $\left&space;(&space;{\color{Red}&space;\theta}^i_k&space;\right&space;)$ be the sequence of parameter vectors generated by P2. Then, ${\color{Blue}&space;\chi}^i({\color{Red}&space;\theta}_k^i)$ converges and

$lim_{k&space;\to&space;\infty}{\color{Golden}&space;\bigtriangledown}&space;{\color{Blue}&space;\chi}^i({\color{Red}&space;\theta}^i_k)=0$

with probability 1.

Sidebar