Bellman Expectation Equation leading to results where value iteration would not converge to the optimal policy

Question

When applying the bellman expectation equation:

$$v(s)=\mathbb{E}\left[R_{t+1}+\gamma v\left(S_{t+1}\right) \mid S_{t}=s\right]$$

to the MRP below, states further away from the terminal state will have the same value ${v(s)}$ as states closer to the terminal states. Even though it is clear that the expected total reward from states further away is lower. If the discount factor $\gamma$ would be even lower states further away would get a higher value. If we now make this an MDP where the agent can decide to go either direction from all states (with the first state having an action leading to itself), the agent would then choose to go further away from the terminal. Getting less reward over the whole episode. So, this seems to be an example where policy/value iteration would not converge to an optimal policy. I know there is something wrong with the reasoning here. I just cannot seem to figure out what.

What am I missing here?

EDIT: So, the problem actually was that I didn't take into account that the terminal state has to get a value of 0. If you put it at 0 at all times this will converge as expected because all the other states will get lower and lower values while, assuming a greedy policy, the one-to-last state will retain a value of -1. After a bit over 10 iterations (if gamma is close to 1) it will converge because the states further away will get a value less than -1.

Answer 1

What am I missing here?

You are not missing anything mathematically.

Potentially what you are missing is that the discount factor $\gamma$, is part of the problem definition. In reinforcement learning (RL), you do not always solve problems to obtain the highest total sum of rewards. Instead you solve problems to obtain the highest expected return on any action. If you use a discount factor, then it affects the return calculation, which in turn may affect which behaviours are optimal.

If you choose $gamma$ such that an agent would move away from a terminal state to receive the highest expected return, then you have defined the problem such that this behaviour is optimal.

This can be an issue when solving RL problems and you have taken a free choice for reward functions and definition of return (this is quite common, often it is the researcher's problem to set these values up to define the agent's goals). Often you can use a discount factor to make a problem more numerically stable, because it will keep sums of rewards over many time steps within bounds. Also, it can be used as a way to search for faster solutions - i.e. in less time steps to reach episode end - because the agent will prioritise reaching higher values sooner if it can. Your example MDP deliberately puts those two effects in opposition to each other.

Assuming you want the agent to find the terminal state by getting over the larger negative reward just before it: Probably you should not use a discount factor for your MDP. Alternatively, if the reward signal is more of a free choice for that problem, you could offset it (by $+0.1$) and then most values of discount factor will still resolve to reaching the terminal state as optimal behaviour.

There are a few common ways to mitigate or avoid the issue of changing problem definition by selecting $\gamma$:

• Use a value of $\gamma$ derived from the problem. In some cases, the value of $\gamma$ is a realistic physical part of a problem. For instance in financial problems, cash now is often preferable to cash later.

• Set $\gamma$ to relavtively high value, such as $0.99$ or $0.999$, depending on episode length and relative sizes of rewards. This can work well enough for a wide range of problems. It is a common solution when using DQN. Effectively this approximates the next approach (average rewards) for a low cost.

• Use average reward settings. There are separate Bellman equations, TD updates etc based on maximising expected average reward per time step as opposed to maximising expected discounted return.