Discounted Rewards (policies)

Assume $0\le \gamma <1$ and rewards are bounded by $R_{\text{max}}$. With discounted rewards, the utility of an infinite sequence is finite:

$$\begin{array}{rl}{U}_r([s_0,s_1,\dots ,s_n])& =\sum _{t=0}^n{\gamma }^{t}R(s_t)\\ & \le \sum _{t=0}^{\infty }{\gamma }^{t}R(s_t)\\ & \le \sum _{t=0}^{\infty }{\gamma }^t{R}_{\text{max}}\\ & \le \frac{R_{\text{max}}}{(1-\gamma )}\end{array}$$

We can compare policies by computing their expected values. The expected utility of executing $\pi$ starting in $s$ is given by:

$$U^{\pi }(s)=E\left[\begin{array}{c}{\sum }_{t=0}^{\infty }{\gamma }^{t}R(s_t)\end{array}\right]$$

Where $S_t$ is the state the agent gets to at time $t$.

$S_t$ is a random variable and we compute the probability of all its values by looking at all the runs which end up there after $t$ steps.

The optimal policy is then:

$${\pi }^{\ast }=\text{arg }\underset{\pi }{\max }{U}^{\pi }(s)$$

This is independent of the state the agent starts in.