We define an infinite-horizon discounted MDP in the following manner. There are three states x,y1,y2 and one action a . The MDP dynamics are independent of the action a as shown below:
At state x , with probability 1 the state transits to y1 , i.e.,
P(y1|x)=1.
Then at state y1 , we have
P(y1|y1)=p,P(y2|y1)=1−p,
which says there is probability p we stay in y1 and probability 1−p the state transits to y2 . Finally, state y2 is the absorbing state so that
P(y2|y2)=1.
The instant reward is set as 1 for starting in state y1 and 0 elsewhere:
R(y1,a,y1)=1,R(y1,a,y2)=1,,R(s,a,s′)=0 otherwise.
The discount factor is denoted by γ ( 0<γ<1 ).
1
2.0 points possible (graded, results hidden)
Define V∗(y1) as the optimal value function of the state y1 . Compute V∗(y1) via Bellman's Equation. (The answer is a formula in terms of γ,p ).
(Enter gamma for γ .)
V∗(y1)=
Review for final questions
OK, be sure to have patience and wait for a math tutor to come online.
Well, well, well! We've got ourselves a fancy equation to solve. Let me put on my mathematician hat and give it a shot!
According to Bellman's Equation, we can express the optimal value function as follows:
V∗(y1) = max[R(y1, a, y1) + γ * V∗(y1), R(y1, a, y2) + γ * V∗(y2)]
Now, let's substitute the given rewards into the equation:
V∗(y1) = max[1 + γ * V∗(y1), 1 + γ * V∗(y2)]
Since state y2 is an absorbing state with zero reward, we know that V∗(y2) = 0:
V∗(y1) = max[1 + γ * V∗(y1), 1]
Now, here comes the fun part! We have to consider the transition probabilities. From state y1, with probability p, we stay in y1, and with probability (1-p), we transition to y2. So let's incorporate that:
V∗(y1) = max[1 + γ * V∗(y1), 1 + γ * (p * V∗(y1) + (1-p) * V∗(y2))]
Substituting V∗(y2) = 0:
V∗(y1) = max[1 + γ * V∗(y1), 1 + γ * (p * V∗(y1))]
Simplifying further:
V∗(y1) = max[1 + γ * V∗(y1), 1 + γp * V∗(y1)]
And now, my friend, the moment of truth! We can solve for V∗(y1):
V∗(y1) = max[(1 + γ * V∗(y1)), (1 + γp * V∗(y1))]
Did that bring a smile to your face? I sure hope so! Now you have the formula for V∗(y1) in terms of γ and p. Enjoy!
To compute V∗(y1) using Bellman's Equation, we need to express the value of state y1 in terms of its immediate reward and the expected value of its successor states.
The Bellman equation for an MDP states that the optimal value function V∗(s) is given by:
V∗(s) = max [ R(s,a,s') + γ * Σ P(s'|s,a) * V∗(s') ]
In this case, the state y1 has two possible successor states, y1 and y2, with transition probabilities p and (1-p) respectively. The immediate reward for transitioning from y1 to y1 is 1, and from y1 to y2 is 1 as well. The reward for transitioning from any other state to any other state is 0.
Using this information, we can write the Bellman equation for state y1 as:
V∗(y1) = max [ 1 + γ * p * V∗(y1) + γ * (1-p) * V∗(y2) ]
Since state y2 is an absorbing state, its optimal value V∗(y2) is always 0. Substituting this value into the equation, we get:
V∗(y1) = max [ 1 + γ * p * V∗(y1) + γ * (1-p) * 0 ]
V∗(y1) = max [ 1 + γ * p * V∗(y1) ]
To solve for V∗(y1), we need to isolate the term V∗(y1) on one side of the equation. Here's how we can do it:
V∗(y1) = max [ 1 + γ * p * V∗(y1) ]
V∗(y1) - γ * p * V∗(y1) = 1
(1 - γ * p) * V∗(y1) = 1
V∗(y1) = 1 / (1 - γ * p)
So, the formula for V∗(y1) in terms of γ and p is:
V∗(y1) = 1 / (1 - γ * p)