Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-14T22:40:47.527Z
Answers.LastActivityDate: 2018-05-14T22:40:47.527Z
Answers.UserDisplayName: me47
Body: <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>
  
Tags: <reinforcement-learning>
Title: Proof of uniqueness of value function for MDPs with undiscounted rewards
UserDisplayName: moorepenrose
ThreadText: # 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.
  
  
  ---
  
  