<p>In the case where the reward is undiscounted, there is no guarantee of convergence as the iteration procedure is not a strict contraction.</p>

<p>Unfortunately I can't find the math mode on the ai stackexchange so my answer can't be very precise.</p>

<p>But an easy example is the following: Take a 'running' reward R of 0 to make things simpler, and a MDP with two states a and b. Take a transition matrix with 0's on the diagonal and 1 off diagonal. You will see that the algorithm will always flip the values of V(a) and V(b), and hence no convergence.</p>

CC BY-SA 4.0
2018-05-14T22:40:47.527Z
2018-05-14T22:40:47.527Z
me47
<p>How does one prove the uniqueness of the value function obtained from <a href="http://artint.info/html/ArtInt_227.html" rel="nofollow noreferrer">value iteration</a> in the case of bounded and undiscounted rewards? I know that this can be proven for the discounted case pretty easily using the <a href="https://en.wikipedia.org/wiki/Banach_fixed-point_theorem" rel="nofollow noreferrer">Banach fixed point theorem</a>.</p>

<reinforcement-learning>
Proof of uniqueness of value function for MDPs with undiscounted rewards
moorepenrose
# Proof of uniqueness of value function for MDPs with undiscounted rewards

(Asked by: username_0 on 2018-03-08)

How does one prove the uniqueness of the value function obtained from [value iteration](http://artint.info/html/ArtInt_227.html) in the case of bounded and undiscounted rewards? I know that this can be proven for the discounted case pretty easily using the [Banach fixed point theorem](https://en.wikipedia.org/wiki/Banach_fixed-point_theorem).

**Tags:** reinforcement-learning


---

## 1 answers

### Answer by username_1 on 2018-05-14. Score: 1

In the case where the reward is undiscounted, there is no guarantee of convergence as the iteration procedure is not a strict contraction.

Unfortunately I can't find the math mode on the ai stackexchange so my answer can't be very precise.

But an easy example is the following: Take a 'running' reward R of 0 to make things simpler, and a MDP with two states a and b. Take a transition matrix with 0's on the diagonal and 1 off diagonal. You will see that the algorithm will always flip the values of V(a) and V(b), and hence no convergence.


---

