3
$\begingroup$

I was going through an example of a Markov Decision Problem and I got the optimal value function with the value iteration algorithm described in Sutton Barto. In this algorithm I chose to initialise the value function with all zero for all states. Since the final state has no successors, the value of the final state is never updated and remains zero. At the end, when the algorithm returns the optimal value function I wanted to choose an optimal policy. But the agent would actually never choose to go to the final state, as all other reachable states have positive value.

How is this fixed in general? Do I have to introduce an extra reward for finishing or is this just a sign of badly formulated problem?

$\endgroup$

1 Answer 1

1
$\begingroup$

How is this fixed in general?

By having the reward function represent what you want the agent to achieve. If there is no differentiation in sum of rewards for any behaviour, then you have defined a problem where all behaviour is optimal and there is nothing to solve.

You might be missing here that the optimal policy $\pi^*(s)$ is derived from the optimal value function $V^*(s)$ like so:

$$\pi^*(s) = \text{argmax}_a \sum_{r,s'} p(r,s'|s,a)(r + \gamma V^*(s'))$$

or in other words, the expected immediate rewards for transitioning to next states are important and taken into account.

Do I have to introduce an extra reward for finishing or is this just a sign of badly formulated problem?

You don't have to introduce a reward for finishing, but it is normal to do so, if you are setting a problem where the goal is to finish an episode in a particular way. An absorbing terminal state, with $V^*(s) = 0$, would then be attractive because of the immediate reward associated with transitioning to it. If the problem is open-ended (the agent has control over whether to end the episode at all), then you may also need a discount factor $\gamma < 1$ to make it more attractive to take actions with a high probability of transitioning to it than to other states.

A common alternative, where the goal is to finish as quickly as possible is to set a fixed negative reward for all state, action pairs - except for transitions from the absorbing state to itself. An absorbing terminal state, with $V^*(s) = 0$, is then attractive because the other non-terminal states all have a negative value.

$\endgroup$
1
  • 1
    $\begingroup$ Thanks for your explanation. Indeed, i neglected the reward associated with the transition to the state that ends the episode! Now everything works. Thanks again :D $\endgroup$ Commented May 13, 2020 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.