CS598 Homework 1

Question 1

Solution

$\begin{align*} V^\pi_{M^{\prime}}(s) &= E[\sum_{t=1}^\infty\gamma^{t-1}R_t^{\prime}(s,a)] \\ &= E[\sum_{t=1}^{\infty}\gamma^{t-1}R_t(s,a) - c] \\ &= E[\sum_{t=1}^{\infty}\gamma^{t-1}R_t(s,a) ] - \sum_{t=1}^{\infty}\gamma^{t-1}c \\ &= V^\pi_M(s) - \frac{c}{1 - \gamma} \quad \quad \quad \quad \quad\quad\forall s \in S \end{align*}$
$\begin{align*} V^\star_{M^\prime}(s) &= \max_{a\in A} Q_{M^\prime}(s,a) \\ &= \max_{a\in A}[ Q_{M}(s,a) - \frac{c}{1 - \gamma}] \\ &= Q_M(s, a^{\star}) - \frac{c}{1 - \gamma} \end{align*}$
Thus, although there exists constant $c$ , it doesn't affect the optimal policy. That is, there is a constant difference between two models for state value, however the optimal action is the same. So in infinite MDP we can generalize that $R \in [0, R_{max}]$

Question 2

Solution

We denote subscript as the horizon. Like $s_1$ means the state of $h=1$
$\begin{align*} V^\pi_{M^{\prime}}(s_1) &= E[\sum_{t=1}^H\gamma^{t-1}R_t^{\prime}(s,a)] \\ &= E[\sum_{t=1}^{H}\gamma^{t-1}R_t(s,a) - c] \\ &= E[\sum_{t=1}^{H}\gamma^{t-1}R_t(s,a) ] - \sum_{t=1}^{H}\gamma^{t-1}c \\ &= V^\pi_M(s_1) - \frac{c(1 - \gamma^H)}{1 - \gamma} \quad \quad \quad \quad \quad\quad\forall s_1\in S \end{align*}$
$\begin{align*} V^\pi_{M^{\prime}}(s_2) &= E[\sum_{t=1}^{H-1}\gamma^{t-1}R_{t+1}^{\prime}(s,a)] \\ &= E[\sum_{t=1}^{H-1}\gamma^{t-1}R_{t+1}(s,a) - c] \\ &= E[\sum_{t=1}^{H-1}\gamma^{t-1}R_{t+1}(s,a) ] - \sum_{t=1}^{H-1}\gamma^{t-1}c \\ &= V^\pi_M(s_1) - \frac{c(1 - \gamma^{H-1})}{1 - \gamma} \quad \quad \quad \quad \quad\quad\forall s_2\in S \end{align*}$
Again for each state value of $h$ from $1$ to $H$ , there exists same but varied difference between two models. Thus, the optimal policy under two models are same.

Question 3.1

Solution

For reward is -1 per step, the optimal policy will choose the shortest paths.
For reward is 0 per step, it is trivial.
For reward is +1 per step, the optimal policy will choose the longest paths.
To sum up, in the case of indefinite-horizon MDP, the optimal policy will be affected if all rewards are added some numbers.

Question 3.2

Solution

Convert indefinite-horizon MDP into finite-horizon MDP

Let's assume the max horizon length is $H_0$ . For those trajectories that its length is strictly smaller than $H_0$ , it can add some absorbing states into its trajectory with reward zero such that its horizon length is $H_0$ . Note that the additional absorbing states will not change the primitive policy because it will not change the value function for this trajectory.

Add rewards like +1 or +2.

If these rewards do not be added into absorbing state, final result is the same as Q3.1

Question 4

Solution

Stationary MDP can be viewed as non-stationary MDP with $P_h$ and $R_h$ fixed along horizon.

We can augment the state representation by introducing horizon $h$ , which means that $S^\prime= \{S, h\}$ . And we can rewrite new transition probability as $P^\prime = P(S^\prime, a) = P(s, h, a)$ and new reward function as $R^\prime = R(S^\prime, a) = R(S, h, a)$ . In this way, $M^\prime = (S^\prime, A, P^\prime, R^\prime, H, \mu)$ is stationary. Finally, the size of new state space is $|S| \times |H|$ .

At the first glance, if we want to convert non-stationary dynamics into stationary as the above method indicates, the size of new state space will be infinite, which is trivial.

最后编辑于：2018.09.02 16:58:56