PG metric

Two metric of policy gradient

Metric 1: Average value

The first metric is the average state value or simply called $\text{average value}$:

$${\bar{v}}_{\pi }=\sum _{s\in \mathcal{S}}d(s)v_{\pi }(s)$$

• ${\bar{v}}_{\pi }$ is a weighted average of the state values.
• $d(s)$ is the weight for state $s$. Since ${\sum }_{s\in \mathcal{S}}d(s)=1$, we can interpret $d(s)$ as a probability distribution.
• Then, the metric can be written as

$${\bar{v}}_{\pi }={\mathbb{E}}_{S\sim d}[v_{\pi }(S)]$$

How to select the distribution $d$?

Case 1: $d$ is independent of the policy $\pi$.

• easy to calculate the gradient of the metric. $${\nabla }_{\theta }{\bar{v}}_{\pi }=d^T{\nabla }_{\theta }{v}_{\pi }$$
• In this case, we specifically denote $d$ as $d_0$ and ${\bar{v}}_{\pi }$ as ${\bar{v}}_{\pi }^0$.
• How to select $d_0$?
  • Uniform(All is same): One trivial way is to treat all the states equally important and hence select $$d_0(s)=\frac{1}{|\mathcal{S}|}$$
  • Onehot(Only one): Another important case is that we are only interested in a specific state $s_0$. For example, the episodes in some tasks always start from the same state $s_0$. Then, we only care about the long-term return starting from $s_0$. In this case, $$d_0(s)=\{\begin{array}{ll}1& \text{if }s=s_0\\ 0& \text{otherwise}\end{array}$$ In this case, ${\bar{v}}_{\pi }=v_{\pi }(s_0)$.

Case 2: $d$ depends on the policy $\pi$.

• A common way is to select $d$ as $d_{\pi }(s)$, which is the stationary distribution under $\pi$.
• The interpretation of selecting $d$ is as follows:
  • $d_{\pi }$ reflects the long-run behavior of the Markov decision process under a given policy $\pi$.
  • If one state is frequently visited in the long run, it is more important and deserves more weight.
  • If a state is hardly visited, then we give it less weight.

An important equivalent expression of average value

You will see the following metric often in the literature:

$$J(\theta )=\underset{n\to \infty }{\lim }\mathbb{E}\left[\sum _{t=0}^n{\gamma }^t{R}_{t+1}\right]=\mathbb{E}\left[\sum _{t=0}^{\infty }{\gamma }^t{R}_{t+1}\right]$$

• Question: What is its relationship to the metric we introduced just now?
• Answer: They are the same. That is because $$\begin{array}{rl}J(\theta )& =\mathbb{E}\left[\sum _{t=0}^{\infty }{\gamma }^t{R}_{t+1}\right]\\ & =\sum _{s\in \mathcal{S}}d(s)\underset{v_{\pi }(s)}{\underbrace{\mathbb{E}\left[\sum _{t=0}^{\infty }{\gamma }^t{R}_{t+1}\mid S_0=s\right]}}\\ & =\sum _{s\in \mathcal{S}}d(s)v_{\pi }(s)\\ & ={\bar{v}}_{\pi }\end{array}$$

Metric 2: Average reward

The second metric is the average one-step reward or simply called $\text{average reward}$:

$${\bar{r}}_{\pi }\doteq \sum _{s\in \mathcal{S}}{d}_{\pi }(s)r_{\pi }(s)={\mathbb{E}}_{S\sim d_{\pi }}[r_{\pi }(S)]$$

where

$$\begin{array}{rl}{r}_{\pi }(s)& =\sum _{a\in \mathcal{A}}\pi (a|s)r(s,a)\\ r(s,a)& =\mathbb{E}[R|s,a]=\sum _{r}rp(r|s,a)\end{array}$$

Remarks:

• ${\bar{r}}_{\pi }$ is simply a weighted average of immediate rewards.
• $r_{\pi }(s)$ is the average immediate reward that can be obtained from state $s$.
• $d_{\pi }$ is the stationary distribution under policy $\pi$.

An important equivalent expression of average reward

Suppose an agent follows a given policy and generates a trajectory with the rewards as $R_1,R_2,\dots$.

The average single-step reward along this trajectory is

$$\begin{array}{rl}& \underset{n\to \infty }{\lim }\frac{1}{n}\mathbb{E}[R_1+R_2+\cdots +R_n|S_0=s_0]\\ =& \underset{n\to \infty }{\lim }\frac{1}{n}\mathbb{E}[\sum _{t=0}^{n-1}{R}_{t+1}|S_0=s_0]\end{array}$$

where $s_0$ is the starting state of the trajectory.

An important fact(more detail, see proof) is that

$${\bar{r}}_{\pi }=\underset{n\to \infty }{\lim }\frac{1}{n}\mathbb{E}[\sum _{t=0}^{n-1}{R}_{t+1}|S_0=s_0]$$

这个事实告诉我们什么？

告诉我们了一个快速计算average reward的好方法，这里的$\mathbb{E}$是为我们天然使用Monte Carlo方法而准备出现在这里的，我们最后会一步一步大名鼎鼎的REINFORCE算法其实就是Monte Carlo Policy Gradient。

Summary

$$\begin{array}{rl}{\bar{v}}_{\pi }& =\sum _{s\in \mathcal{S}}d(s)v_{\pi }(s)={\mathbb{E}}_{S\sim d}[v_{\pi }(S)]=\underset{n\to \infty }{\lim }\mathbb{E}\left[\sum _{t=0}^n{\gamma }^t{R}_{t+1}\right]\\ {\bar{r}}_{\pi }& =\sum _{s\in \mathcal{S}}{d}_{\pi }(s)r_{\pi }(s)={\mathbb{E}}_{S\sim d_{\pi }}[r_{\pi }(S)]=\underset{n\to \infty }{\lim }\frac{1}{n}\mathbb{E}[\sum _{t=0}^{n-1}{R}_{t+1}]\end{array}$$

Remarks:

About $\pi$ and $\theta$:

1. all these metrics are functions of $\pi$
2. since $\pi$ is parameterized by $\theta$, these metrics are functions of $\theta$
3. different values of $\theta$ can generate different metric values
4. we can search for the optimal values of $\theta$ to maximize these metrics

Basic idea of policy gradient methods

我们的policy是用参数$\theta$通过函数化的方法来表示的，所以查找optimal policy的过程自然变成了查找optimal $\theta$的过程，对于$\theta$的optimality，我们又提出了两个metrics

About discounting:

1. the metrics can be defined in either the discounted case where $\gamma <1$ or the undiscounted case where $\gamma =1$
2. the undiscounted case is nontrivial
3. we only consider the discounted case so far.

About the relationship between $\bar{r}$ and $\bar{v}$:

1. the two metrics are equivalent (not equal) to each other
2. specifically, in the discounted case where $\gamma <1$, it holds that $${\bar{r}}_{\pi }=(1-\gamma ){\bar{v}}_{\pi }$$
3. they can be maximized simultaneously

关于 $\bar{r}$和$\bar{v}$的关系

先明确两个定义：

$$\begin{array}{rl}{\bar{v}}_{\pi }& =d^T{v}_{\pi }\\ {\bar{r}}_{\pi }& =d_{\pi }^T{r}_{\pi }\end{array}$$

然后推导如下：

$$\begin{array}{rlrl}{\bar{v}}_{\pi }& =d^T{v}_{\pi }=d_{\pi }^T{v}_{\pi }& & (\text{Just special case})\\ & =d_{\pi }^T(r_{\pi }+\gamma P_{\pi }{v}_{\pi })& & (\text{Bellman equation})\\ & =d_{\pi }^T{r}_{\pi }+\gamma d_{\pi }^T{P}_{\pi }{v}_{\pi }& & \\ & ={\bar{r}}_{\pi }+\gamma d_{\pi }^T{P}_{\pi }{v}_{\pi }& & ({\bar{r}}_{\pi }=d_{\pi }^T{r}_{\pi })\\ & ={\bar{r}}_{\pi }+\gamma d_{\pi }^T{v}_{\pi }& & (d_{\pi }^T=d_{\pi }^T{P}_{\pi })\\ & ={\bar{r}}_{\pi }+\gamma {\bar{v}}_{\pi }& & \end{array}$$

所以我们有${\bar{r}}_{\pi }=(1-\gamma ){\bar{v}}_{\pi }$。