Note / value-iteration.html
SteveZeyuZhang
Publish Note study website
5e1c603
Raw History Blame Contribute Delete
45.7 kB
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="color-scheme" content="light">
<title>Value iteration</title>
<link rel="stylesheet" href="styles.css">
<script src="gridworld-animation.js" defer></script>
</head>
<body>
<main class="topic chapter-page">
<a class="back" href="exact-solution-methods.html" aria-label="Back to Exact solution methods">
<svg width="20" height="20" viewBox="0 0 24 24" fill="none" aria-hidden="true">
<path d="m14 6-6 6 6 6M8 12h12" />
</svg>
</a>
<h1 class="topic-title"><a class="reference-link" href="https://inst.eecs.berkeley.edu/~cs188/textbook/mdp/value-iteration.html" target="_blank" rel="noopener noreferrer">Value iteration</a></h1>
<section class="value-intro" aria-labelledby="optimal-value-function">
<h2 id="optimal-value-function">Optimal Value Function <math aria-label="V star"><msup><mi>V</mi><mo>*</mo></msup></math></h2>
<div class="mdp-equation" tabindex="0" role="region" aria-label="Optimal value function equation">
<math display="block" aria-label="V star of s is the maximum over policies pi of the expected sum from t equals zero to H of gamma to the power t times R of s_t, a_t, s_(t+1), given pi and s zero equals s">
<mrow><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mo>=</mo>
<munder><mo>max</mo><mi>π</mi></munder>
<mi mathvariant="normal">E</mi><mo>[</mo>
<munderover><mo>∑</mo><mrow><mi>t</mi><mo>=</mo><mn>0</mn></mrow><mi>H</mi></munderover>
<msup><mi>γ</mi><mi>t</mi></msup>
<mrow><mi>R</mi><mo>(</mo><msub><mi>s</mi><mi>t</mi></msub><mo>,</mo><msub><mi>a</mi><mi>t</mi></msub><mo>,</mo><msub><mi>s</mi><mrow><mi>t</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>)</mo></mrow><mo>|</mo><mi>π</mi><mo>,</mo><msub><mi>s</mi><mn>0</mn></msub><mo>=</mo><mi>s</mi><mo>]</mo>
</math>
</div>
<p class="mdp-explanation">Expected sum of discounted rewards when starting from state <math aria-label="s"><mi>s</mi></math> and acting optimally.</p>
<div class="value-example-grid">
<figure class="gridworld-figure">
<a href="https://inst.eecs.berkeley.edu/~cs188/su24/assets/lectures/cs188-su24-lec14.pdf#page=8" target="_blank" rel="noopener noreferrer" aria-label="Berkeley Gridworld example">
<img src="assets/mdp/gridworld.png" alt="A four-column, three-row Gridworld with plus-one reward at (4,3) and minus-one reward at (4,2)" width="730" height="558">
</a>
</figure>
<div class="value-assumptions">
<h3>Let’s assume:</h3>
<p>Actions are deterministically successful.<br><math aria-label="gamma equals one, H equals one hundred"><mi>γ</mi><mo>=</mo><mn>1</mn><mo>,</mo><mi>H</mi><mo>=</mo><mn>100</mn></math></p>
<ul class="value-examples">
<li><math aria-label="V star of four, three equals one"><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>4</mn><mo>,</mo><mn>3</mn><mo>)</mo><mo>=</mo><mn>1</mn></math></li>
<li><math aria-label="V star of three, three equals one"><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>3</mn><mo>,</mo><mn>3</mn><mo>)</mo><mo>=</mo><mn>1</mn></math></li>
<li><math aria-label="V star of two, three equals one"><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>2</mn><mo>,</mo><mn>3</mn><mo>)</mo><mo>=</mo><mn>1</mn></math></li>
<li><math aria-label="V star of one, one equals one"><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>1</mn><mo>,</mo><mn>1</mn><mo>)</mo><mo>=</mo><mn>1</mn></math></li>
<li><math aria-label="V star of four, two equals minus one"><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>4</mn><mo>,</mo><mn>2</mn><mo>)</mo><mo>=</mo><mo>−</mo><mn>1</mn></math></li>
</ul>
</div>
</div>
<div class="value-exit-note">
<p class="mdp-explanation">From (4,2), the agent must <a class="reference-link" href="https://inst.eecs.berkeley.edu/~cs188/sp26/projects/proj3/#mdps" target="_blank" rel="noopener noreferrer">exit and receive −1</a>; the true terminal state reached afterward has value 0.</p>
<div class="mdp-equation">
<math display="block" aria-label="V star of four, two equals minus one plus one times zero, equals minus one">
<msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>4</mn><mo>,</mo><mn>2</mn><mo>)</mo><mo>=</mo><mo>−</mo><mn>1</mn><mo>+</mo><mn>1</mn><mo>×</mo><mn>0</mn><mo>=</mo><mo>−</mo><mn>1</mn>
</math>
</div>
</div>
</section>
<section class="value-case value-case--discounted" aria-labelledby="discounted-assumptions">
<h2 id="discounted-assumptions"><a class="reference-link" href="https://inst.eecs.berkeley.edu/~cs188/textbook/mdp/markov-decision-processes.html#411-finite-horizons-and-discounting" target="_blank" rel="noopener noreferrer">Let’s assume:</a></h2>
<p class="chapter-description">Actions are deterministically successful.<br><math aria-label="gamma equals zero point nine, H equals one hundred"><mi>γ</mi><mo>=</mo><mn>0.9</mn><mo>,</mo><mi>H</mi><mo>=</mo><mn>100</mn></math></p>
<ul class="value-examples">
<li><math aria-label="V star of four, three equals one"><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>4</mn><mo>,</mo><mn>3</mn><mo>)</mo><mo>=</mo><mn>1</mn></math></li>
<li><math aria-label="V star of three, three equals zero point nine"><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>3</mn><mo>,</mo><mn>3</mn><mo>)</mo><mo>=</mo><mn>0.9</mn></math></li>
<li class="value-expression"><math aria-label="V star of two, three equals zero point nine times zero point nine, equals zero point eight one"><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>2</mn><mo>,</mo><mn>3</mn><mo>)</mo><mo>=</mo><mn>0.9</mn><mo>×</mo><mn>0.9</mn><mo>=</mo><mn>0.81</mn></math></li>
<li class="value-expression value-expression--wrap">
<math aria-label="V star of one, one equals"><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>1</mn><mo>,</mo><mn>1</mn><mo>)</mo><mo>=</mo></math>
<math aria-label="zero point nine multiplied by itself five times"><mn>0.9</mn><mo>×</mo><mn>0.9</mn><mo>×</mo><mn>0.9</mn><mo>×</mo><mn>0.9</mn><mo>×</mo><mn>0.9</mn></math>
<math aria-label="approximately zero point five nine"><mo>≈</mo><mn>0.59</mn></math>
</li>
<li><math aria-label="V star of four, two equals minus one"><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>4</mn><mo>,</mo><mn>2</mn><mo>)</mo><mo>=</mo><mo>−</mo><mn>1</mn></math></li>
</ul>
</section>
<section class="value-case value-case--stochastic" aria-labelledby="stochastic-assumptions">
<h2 id="stochastic-assumptions"><a class="reference-link" href="https://inst.eecs.berkeley.edu/~cs188/sp26/projects/proj3/#mdps" target="_blank" rel="noopener noreferrer">Let’s assume:</a></h2>
<p class="chapter-description">Actions successful w/probability 0.8.<br><math aria-label="gamma equals zero point nine, H equals one hundred"><mi>γ</mi><mo>=</mo><mn>0.9</mn><mo>,</mo><mi>H</mi><mo>=</mo><mn>100</mn></math></p>
<ul class="value-examples">
<li><math aria-label="V star of four, three equals one"><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>4</mn><mo>,</mo><mn>3</mn><mo>)</mo><mo>=</mo><mn>1</mn></math></li>
</ul>
<!-- The slide uses stationary V* notation; a strict finite-horizon recurrence uses V_H and V_(H-1). -->
<div class="mdp-equation value-stochastic-equation" tabindex="0" role="region" aria-label="Stochastic Gridworld value equation">
<math display="block" aria-label="V star of three, three equals zero point eight times zero point nine times V star of four, three, plus zero point one times zero point nine times V star of three, three, plus zero point one times zero point nine times V star of three, two">
<mtable columnalign="left left" rowspacing="0.35em">
<mtr>
<mtd><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>3</mn><mo>,</mo><mn>3</mn><mo>)</mo></mtd>
<mtd><mo>=</mo><mn>0.8</mn><mo>×</mo><mn>0.9</mn><mo>×</mo><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>4</mn><mo>,</mo><mn>3</mn><mo>)</mo></mtd>
</mtr>
<mtr>
<mtd></mtd>
<mtd><mo>+</mo><mn>0.1</mn><mo>×</mo><mn>0.9</mn><mo>×</mo><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>3</mn><mo>,</mo><mn>3</mn><mo>)</mo></mtd>
</mtr>
<mtr>
<mtd></mtd>
<mtd><mo>+</mo><mn>0.1</mn><mo>×</mo><mn>0.9</mn><mo>×</mo><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mn>3</mn><mo>,</mo><mn>2</mn><mo>)</mo></mtd>
</mtr>
</mtable>
</math>
</div>
</section>
<section class="value-case value-recursion" aria-label="Value iteration recurrence">
<div class="value-horizon">
<p class="value-horizon-definition"><math aria-label="V zero star of s equals"><msubsup><mi>V</mi><mn>0</mn><mo>*</mo></msubsup><mo>(</mo><mi>s</mi><mo>)</mo><mo>=</mo></math> <a class="reference-link" href="https://inst.eecs.berkeley.edu/~cs188/textbook/mdp/value-iteration.html" target="_blank" rel="noopener noreferrer">optimal value</a> for state <math aria-label="s"><mi>s</mi></math> when <math aria-label="H equals zero"><mi>H</mi><mo>=</mo><mn>0</mn></math></p>
<div class="mdp-equation" tabindex="0" role="region" aria-label="Zero-step value equation">
<math display="block" aria-label="V zero star of s equals zero for all states s">
<mrow><msubsup><mi>V</mi><mn>0</mn><mo>*</mo></msubsup><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mo>=</mo><mn>0</mn><mspace width="1em"/><mo>∀</mo><mi>s</mi>
</math>
</div>
</div>
<div class="value-horizon">
<p class="value-horizon-definition"><math aria-label="V one star of s equals"><msubsup><mi>V</mi><mn>1</mn><mo>*</mo></msubsup><mo>(</mo><mi>s</mi><mo>)</mo><mo>=</mo></math> optimal value for state <math aria-label="s"><mi>s</mi></math> when <math aria-label="H equals one"><mi>H</mi><mo>=</mo><mn>1</mn></math></p>
<div class="mdp-equation" tabindex="0" role="region" aria-label="One-step value equation">
<math display="block" aria-label="V one star of s equals the maximum over actions a of the sum over next states s prime of P of s prime given s and a times the reward plus gamma times V zero star of s prime">
<mrow><msubsup><mi>V</mi><mn>1</mn><mo>*</mo></msubsup><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mo>=</mo>
<munder><mo>max</mo><mi>a</mi></munder><munder><mo>∑</mo><msup><mi>s</mi><mo>′</mo></msup></munder>
<mrow><mi>P</mi><mo>(</mo><msup><mi>s</mi><mo>′</mo></msup><mo>|</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>)</mo></mrow>
<mrow><mo>(</mo><mrow><mi>R</mi><mo>(</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>,</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>+</mo><mi>γ</mi><mrow><msubsup><mi>V</mi><mn>0</mn><mo>*</mo></msubsup><mo>(</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>)</mo></mrow>
</math>
</div>
</div>
<div class="value-horizon">
<p class="value-horizon-definition"><math aria-label="V k star of s equals"><msubsup><mi>V</mi><mi>k</mi><mo>*</mo></msubsup><mo>(</mo><mi>s</mi><mo>)</mo><mo>=</mo></math> optimal value for state <math aria-label="s"><mi>s</mi></math> when <math aria-label="H equals k"><mi>H</mi><mo>=</mo><mi>k</mi></math></p>
<div class="mdp-equation" tabindex="0" role="region" aria-label="K-step value equation">
<math display="block" aria-label="V k star of s equals the maximum over actions a of the sum over next states s prime of P of s prime given s and a times the reward plus gamma times V k minus one star of s prime">
<mrow><msubsup><mi>V</mi><mi>k</mi><mo>*</mo></msubsup><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mo>=</mo>
<munder><mo>max</mo><mi>a</mi></munder><munder><mo>∑</mo><msup><mi>s</mi><mo>′</mo></msup></munder>
<mrow><mi>P</mi><mo>(</mo><msup><mi>s</mi><mo>′</mo></msup><mo>|</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>)</mo></mrow>
<mrow><mo>(</mo><mrow><mi>R</mi><mo>(</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>,</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>+</mo><mi>γ</mi><mrow><msubsup><mi>V</mi><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow><mo>*</mo></msubsup><mo>(</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>)</mo></mrow>
</math>
</div>
</div>
</section>
<section class="value-case value-bellman" aria-labelledby="bellman-update">
<h2 id="bellman-update"><a class="reference-link" href="https://inst.eecs.berkeley.edu/~cs188/textbook/mdp/value-iteration.html" target="_blank" rel="noopener noreferrer">Bellman Update</a></h2>
<div class="value-algorithm">
<h3>Algorithm:</h3>
<p>Start with <math aria-label="V zero star of s equals zero"><msubsup><mi>V</mi><mn>0</mn><mo>*</mo></msubsup><mo>(</mo><mi>s</mi><mo>)</mo><mo>=</mo><mn>0</mn></math> for all <math aria-label="s"><mi>s</mi></math>.</p>
<p>For <math aria-label="k equals one through H"><mi>k</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>H</mi></math>:</p>
<div class="value-algorithm-loop">
<p>For all states <math aria-label="s in S"><mi>s</mi><mo>∈</mo><mi>S</mi></math>:</p>
<div class="mdp-equation" tabindex="0" role="region" aria-label="Bellman value update">
<math display="block" aria-label="V k star of s is updated to the maximum over actions a of the expected reward plus gamma times V k minus one star of the next state">
<mrow><msubsup><mi>V</mi><mi>k</mi><mo>*</mo></msubsup><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mo>←</mo>
<munder><mo>max</mo><mi>a</mi></munder><munder><mo>∑</mo><msup><mi>s</mi><mo>′</mo></msup></munder>
<mrow><mi>P</mi><mo>(</mo><msup><mi>s</mi><mo>′</mo></msup><mo>|</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>)</mo></mrow>
<mrow><mo>(</mo><mrow><mi>R</mi><mo>(</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>,</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>+</mo><mi>γ</mi><mrow><msubsup><mi>V</mi><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow><mo>*</mo></msubsup><mo>(</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>)</mo></mrow>
</math>
</div>
<div class="mdp-equation" tabindex="0" role="region" aria-label="Optimal policy update">
<math display="block" aria-label="Pi k star of s is updated to an action that maximizes the expected reward plus gamma times V k minus one star of the next state">
<mrow><msubsup><mi>π</mi><mi>k</mi><mo>*</mo></msubsup><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mo>←</mo>
<munder><mrow><mo>arg</mo><mspace width="0.15em"/><mo>max</mo></mrow><mi>a</mi></munder><munder><mo>∑</mo><msup><mi>s</mi><mo>′</mo></msup></munder>
<mrow><mi>P</mi><mo>(</mo><msup><mi>s</mi><mo>′</mo></msup><mo>|</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>)</mo></mrow>
<mrow><mo>(</mo><mrow><mi>R</mi><mo>(</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>,</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>+</mo><mi>γ</mi><mrow><msubsup><mi>V</mi><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow><mo>*</mo></msubsup><mo>(</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>)</mo></mrow>
</math>
</div>
</div>
<p>This is called a value update or Bellman update/back-up.</p>
</div>
<p class="mdp-explanation"><a class="reference-link" href="https://inst.eecs.berkeley.edu/~cs188/textbook/mdp/value-iteration.html#431-policy-extraction" target="_blank" rel="noopener noreferrer">max returns the best value; argmax returns the action that achieves it.</a> Since the remaining steps use optimal values, choosing this action in each state gives the optimal policy for the remaining horizon.</p>
</section>
<section class="value-case value-convergence" aria-labelledby="value-iteration-convergence">
<h2 id="value-iteration-convergence"><a class="reference-link" href="https://inst.eecs.berkeley.edu/~cs188/textbook/mdp/value-iteration.html" target="_blank" rel="noopener noreferrer">Value Iteration Convergence</a></h2>
<div class="value-theorem">
<p class="mdp-explanation"><strong>Theorem.</strong> For a finite MDP with bounded rewards and <math aria-label="zero is less than or equal to gamma, which is less than one"><mn>0</mn><mo>≤</mo><mi>γ</mi><mo>&lt;</mo><mn>1</mn></math>, value iteration converges to the optimal value function <math aria-label="V star"><msup><mi>V</mi><mo>*</mo></msup></math> for the discounted infinite-horizon problem, which satisfies the Bellman optimality equation:</p>
<div class="mdp-equation" tabindex="0" role="region" aria-label="Bellman optimality equation">
<math display="block" aria-label="For every state s in S, V star of s equals the maximum over actions a of the sum over next states s prime of T of s, a, s prime times the reward plus gamma times V star of s prime">
<mo>∀</mo><mi>s</mi><mo>∈</mo><mi>S</mi><mo>:</mo><mspace width="0.5em"/>
<mrow><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mo>=</mo>
<munder><mo>max</mo><mi>a</mi></munder><munder><mo>∑</mo><msup><mi>s</mi><mo>′</mo></msup></munder>
<mrow><mi>T</mi><mo>(</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>,</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow>
<mrow><mo>[</mo><mrow><mi>R</mi><mo>(</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>,</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>+</mo><mi>γ</mi><mrow><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>]</mo></mrow>
</math>
</div>
</div>
<div class="mdp-equation" tabindex="0" role="region" aria-label="Transition probability notation">
<math display="block" aria-label="T of s, a, s prime equals P of s prime given s and a">
<mrow><mi>T</mi><mo>(</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>,</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>=</mo><mrow><mi>P</mi><mo>(</mo><msup><mi>s</mi><mo>′</mo></msup><mo>|</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>)</mo></mrow>
</math>
</div>
<p class="mdp-explanation">T is the transition probability used in every update. At convergence, both <math aria-label="V k"><msub><mi>V</mi><mi>k</mi></msub></math> and <math aria-label="V k minus one"><msub><mi>V</mi><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msub></math> approach <math aria-label="V star"><msup><mi>V</mi><mo>*</mo></msup></math>, so the update becomes the Bellman optimality equation.</p>
<p class="mdp-explanation">The <a class="reference-link" href="https://inst.eecs.berkeley.edu/~cs188/textbook/mdp/value-iteration.html" target="_blank" rel="noopener noreferrer">Bellman update</a> contracts the maximum value error by a factor of at most <math aria-label="gamma"><mi>γ</mi></math> each iteration.</p>
<section class="value-intuition" aria-labelledby="convergence-intuition">
<h3 id="convergence-intuition"><a class="reference-link" href="https://inst.eecs.berkeley.edu/~cs188/textbook/mdp/markov-decision-processes.html#411-finite-horizons-and-discounting" target="_blank" rel="noopener noreferrer">Convergence: Intuition</a></h3>
<p class="mdp-explanation">As in the slide, assume <math aria-label="zero is less than or equal to R of s, which is at most R max"><mn>0</mn><mo>≤</mo><mrow><mi>R</mi><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mo>≤</mo><msub><mi>R</mi><mtext>max</mtext></msub></math> and <math aria-label="zero is less than or equal to gamma, which is less than one"><mn>0</mn><mo>≤</mo><mi>γ</mi><mo>&lt;</mo><mn>1</mn></math>. Here, H is the last included reward index.</p>
<div class="mdp-equation proof-equation proof-series" tabindex="0" role="region" aria-label="The additional rewards are bounded by a geometric series">
<math display="block" aria-label="Gamma to the power H plus one times R of s H plus one, plus gamma to the power H plus two times R of s H plus two, and so on, is at most gamma to the power H plus one times R max, plus gamma to the power H plus two times R max, and so on, which equals gamma to the power H plus one divided by one minus gamma, times R max">
<msup><mi>γ</mi><mrow><mi>H</mi><mo>+</mo><mn>1</mn></mrow></msup><mrow><mi>R</mi><mo>(</mo><msub><mi>s</mi><mrow><mi>H</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>)</mo></mrow><mo>+</mo>
<msup><mi>γ</mi><mrow><mi>H</mi><mo>+</mo><mn>2</mn></mrow></msup><mrow><mi>R</mi><mo>(</mo><msub><mi>s</mi><mrow><mi>H</mi><mo>+</mo><mn>2</mn></mrow></msub><mo>)</mo></mrow><mo>+</mo><mo>…</mo>
<mover accent="false">
<mo>≤</mo>
<mstyle scriptlevel="0"><mtable class="proof-label" rowspacing="0.1em">
<mtr><mtd><mrow><mi>R</mi><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mo>≤</mo><msub><mi>R</mi><mtext>max</mtext></msub></mtd></mtr>
<mtr><mtd><mo class="proof-arrow">↓</mo></mtd></mtr>
</mtable></mstyle>
</mover>
<msup><mi>γ</mi><mrow><mi>H</mi><mo>+</mo><mn>1</mn></mrow></msup><msub><mi>R</mi><mtext>max</mtext></msub><mo>+</mo>
<msup><mi>γ</mi><mrow><mi>H</mi><mo>+</mo><mn>2</mn></mrow></msup><msub><mi>R</mi><mtext>max</mtext></msub><mo>+</mo><mo>…</mo>
<mover accent="false">
<mo>=</mo>
<mstyle scriptlevel="0"><mtable class="proof-label" rowspacing="0.1em">
<mtr><mtd><mtext>Geometric series</mtext></mtd></mtr>
<mtr><mtd><mo class="proof-arrow">↓</mo></mtd></mtr>
</mtable></mstyle>
</mover>
<mfrac><msup><mi>γ</mi><mrow><mi>H</mi><mo>+</mo><mn>1</mn></mrow></msup><mrow><mn>1</mn><mo>−</mo><mi>γ</mi></mrow></mfrac><msub><mi>R</mi><mtext>max</mtext></msub>
</math>
</div>
<div class="mdp-equation proof-equation proof-limit" tabindex="0" role="region" aria-label="The tail bound tends to zero: the numerator tends to zero and the denominator is fixed and positive">
<math display="block" aria-label="Gamma to the power H plus one divided by one minus gamma, times R max, tends to zero as H tends to infinity. The numerator tends to zero; the denominator is fixed and positive">
<munderover>
<mfrac><msup><mi>γ</mi><mrow><mi>H</mi><mo>+</mo><mn>1</mn></mrow></msup><mrow><mn>1</mn><mo>−</mo><mi>γ</mi></mrow></mfrac>
<mstyle scriptlevel="0"><mtable class="proof-label" rowspacing="0.1em">
<mtr><mtd><mo class="proof-arrow">↑</mo></mtd></mtr>
<mtr><mtd><mtext>Fixed and positive</mtext></mtd></mtr>
</mtable></mstyle>
<mstyle scriptlevel="0"><mtable class="proof-label" rowspacing="0.1em">
<mtr><mtd><msup><mi>γ</mi><mrow><mi>H</mi><mo>+</mo><mn>1</mn></mrow></msup><mo>→</mo><mn>0</mn></mtd></mtr>
<mtr><mtd><mo class="proof-arrow">↓</mo></mtd></mtr>
</mtable></mstyle>
</munderover>
<msub><mi>R</mi><mtext>max</mtext></msub>
<mover accent="false"><mo>⟶</mo><mrow><mi>H</mi><mo>→</mo><mo>∞</mo></mrow></mover><mn>0</mn>
</math>
</div>
<p class="mdp-explanation">This bound holds for every policy, so it also bounds the difference between the optimal values:</p>
<div class="mdp-equation proof-equation" tabindex="0" role="region" aria-label="The optimal value error is squeezed to zero by the tail bound">
<math display="block" aria-label="Zero is less than or equal to the absolute difference between V star of s and V H plus one star of s, which is at most gamma to the power H plus one times R max divided by one minus gamma, tending to zero">
<mn>0</mn><mo>≤</mo>
<mrow><mo>|</mo><mrow><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mo>−</mo><mrow><msubsup><mi>V</mi><mrow><mi>H</mi><mo>+</mo><mn>1</mn></mrow><mo>*</mo></msubsup><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mo>|</mo></mrow>
<mo>≤</mo>
<mfrac><mrow><msup><mi>γ</mi><mrow><mi>H</mi><mo>+</mo><mn>1</mn></mrow></msup><msub><mi>R</mi><mtext>max</mtext></msub></mrow><mrow><mn>1</mn><mo>−</mo><mi>γ</mi></mrow></mfrac>
<mover accent="false"><mo>⟶</mo><mrow><mi>H</mi><mo>→</mo><mo>∞</mo></mrow></mover><mn>0</mn>
</math>
</div>
<p class="mdp-explanation">The error is squeezed to 0, so the finite-horizon optimal value converges to <math aria-label="V star"><msup><mi>V</mi><mo>*</mo></msup></math>.</p>
<p class="mdp-explanation">If rewards can be negative, use the maximum absolute reward and bound the error from both sides.</p>
</section>
<section class="value-contractions" aria-labelledby="convergence-contractions">
<h3 id="convergence-contractions"><a class="reference-link" href="https://inst.eecs.berkeley.edu/~cs188/textbook/mdp/value-iteration.html" target="_blank" rel="noopener noreferrer">Convergence and Contractions</a></h3>
<p class="mdp-explanation">For the same finite MDP with bounded rewards, take <math aria-label="zero is less than gamma, which is less than one"><mn>0</mn><mo>&lt;</mo><mi>γ</mi><mo>&lt;</mo><mn>1</mn></math>. The idea is that each update brings value estimates closer together, until they reach the same answer.</p>
<ol class="contraction-list">
<li>
<h4>Definition: max-norm</h4>
<div class="mdp-equation" tabindex="0" role="region" aria-label="Definition of the max norm">
<math display="block" aria-label="The norm of U equals the maximum over states s of the absolute value of U of s">
<mrow><mo>∥</mo><mi>U</mi><mo>∥</mo></mrow><mo>=</mo><munder><mo>max</mo><mi>s</mi></munder><mrow><mo>|</mo><mrow><mi>U</mi><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mo>|</mo></mrow>
</math>
</div>
<p class="mdp-explanation">Think of U as a table with one value per state. Take the absolute value of every entry, then pick the largest. If the entries are 1, −3, and 2, the max-norm is 3.</p>
<p class="mdp-explanation">For <math aria-label="the norm of U minus V"><mo>∥</mo><mi>U</mi><mo>−</mo><mi>V</mi><mo>∥</mo></math>, compare the two tables state by state and take the largest absolute difference. It measures their biggest disagreement.</p>
</li>
<li>
<h4>Definition: An update operation is a γ-contraction in max-norm if and only if</h4>
<div class="mdp-equation" tabindex="0" role="region" aria-label="Definition of a gamma contraction for every pair of value estimates">
<math display="block" aria-label="For all U i and V i, the norm of U i plus one minus V i plus one is at most gamma times the norm of U i minus V i">
<mtext>for all</mtext><mspace width="0.25em"/><msub><mi>U</mi><mi>i</mi></msub><mo>,</mo><msub><mi>V</mi><mi>i</mi></msub><mo>:</mo><mspace width="0.5em"/>
<mrow><mo>∥</mo><msub><mi>U</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>−</mo><msub><mi>V</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>∥</mo></mrow><mo>≤</mo><mi>γ</mi><mrow><mo>∥</mo><msub><mi>U</mi><mi>i</mi></msub><mo>−</mo><msub><mi>V</mi><mi>i</mi></msub><mo>∥</mo></mrow>
</math>
</div>
<p class="mdp-explanation">Start with any two value tables, Uᵢ and Vᵢ, and apply the same update to both. Their biggest disagreement afterward is at most γ times what it was before. The index i counts update rounds.</p>
<p class="mdp-explanation">With γ = 0.9, a disagreement of 10 becomes at most 9 after one update, then at most 8.1 after another. “For all” means this must hold for every pair of tables; “if and only if” says this inequality is exactly the definition.</p>
</li>
<li>
<h4>Theorem: A contraction converges to a unique fixed point, no matter initialization.</h4>
<p class="mdp-explanation">A fixed point is a value table that stays unchanged when the update is applied again. “Converges” means the tables approach it as updates continue. You can initialize the values to 0, 10, or any other finite values and still approach the same table.</p>
<p class="mdp-explanation">There cannot be two different fixed points: the update would have to leave both unchanged while also shrinking the distance between them. Both conditions can hold only when that distance is zero.</p>
</li>
<li>
<h4>Fact: the value iteration update is a γ-contraction in max-norm</h4>
<p class="mdp-explanation">The Bellman update has exactly this shrinking property. Both tables use the same rewards, so their differences come from the future-value estimates. Taking a probability-weighted average and choosing the best action cannot enlarge the biggest disagreement; multiplying the future value by γ shrinks its bound.</p>
</li>
<li>
<h4>Corollary: value iteration converges to a unique fixed point</h4>
<p class="mdp-explanation">Combine the theorem with the fact: value iteration is a contraction, so it approaches one fixed point from any finite initialization. That fixed point satisfies the Bellman optimality equation and is the optimal value function V*. The value function is unique; equally good actions can still give multiple optimal policies.</p>
</li>
<li>
<h4>Additional fact:</h4>
<div class="mdp-equation" tabindex="0" role="region" aria-label="A small change between successive iterations gives an upper bound on the remaining value error">
<math display="block" aria-label="If the norm of V i plus one minus V i is less than epsilon, then the norm of V i plus one minus V star is less than two epsilon gamma divided by one minus gamma">
<mrow><mo>∥</mo><msub><mi>V</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>−</mo><msub><mi>V</mi><mi>i</mi></msub><mo>∥</mo></mrow><mo>&lt;</mo><mi>ε</mi><mo>,</mo><mo>⇒</mo>
<mrow><mo>∥</mo><msub><mi>V</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>−</mo><msup><mi>V</mi><mo>*</mo></msup><mo>∥</mo></mrow><mo>&lt;</mo><mn>2</mn><mi>ε</mi><mi>γ</mi><mo>/</mo><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mi>γ</mi><mo>)</mo></mrow>
</math>
</div>
<p class="mdp-explanation">The left side is something we can measure: every state changed by less than ε between the last two rounds. The right side bounds something we do not yet know: the biggest difference between the current table and the optimal table.</p>
<p class="mdp-explanation">Later updates can still change the values, but each change is at most γ times the previous one. Adding all those possible future changes gives the geometric-series factor γ/(1 − γ). The factor 2 makes the slide’s upper bound more conservative.</p>
<p class="mdp-explanation">For γ = 0.9 and ε = 0.001, the slide guarantees an error below 0.018. This gives a stopping rule. As γ gets closer to 1, later changes fade more slowly, so the same ε gives a larger error bound.</p>
</li>
</ol>
</section>
<section class="value-gridworld" aria-labelledby="gridworld-iterations">
<h3 id="gridworld-iterations"><a class="reference-link" href="https://inst.eecs.berkeley.edu/~cs188/sp26/projects/proj3/#mdps" target="_blank" rel="noopener noreferrer">Example: Gridworld</a></h3>
<div class="iteration-layout" data-gridworld-animation>
<div class="iteration-context">
<figure class="gridworld-figure">
<a href="https://inst.eecs.berkeley.edu/~cs188/su24/assets/lectures/cs188-su24-lec14.pdf#page=8" target="_blank" rel="noopener noreferrer" aria-label="Berkeley Gridworld example">
<img src="assets/mdp/gridworld.png" alt="Gridworld with a wall at (2,2), plus-one exit at (4,3), and minus-one exit at (4,2)" width="730" height="558">
</a>
</figure>
<p class="iteration-settings">Noise = 0.2<br>Discount = 0.9</p>
</div>
<div class="iteration-player" data-playing="false">
<p class="iteration-step"><math aria-label="Iteration k equals zero"><mi>k</mi><mo>=</mo><mn data-iteration-step>0</mn></math></p>
<table class="iteration-grid" aria-label="Gridworld values after 0 iterations">
<tbody>
<tr>
<td aria-label="(1,3): 0.00"><span>0.00</span></td>
<td aria-label="(2,3): 0.00"><span>0.00</span></td>
<td aria-label="(3,3): 0.00"><span>0.00</span></td>
<td class="iteration-exit" aria-label="(4,3): 0.00"><span>0.00</span></td>
</tr>
<tr>
<td aria-label="(1,2): 0.00"><span>0.00</span></td>
<td class="iteration-wall" aria-label="Wall at (2,2)"><span></span></td>
<td aria-label="(3,2): 0.00"><span>0.00</span></td>
<td class="iteration-exit" aria-label="(4,2): 0.00"><span>0.00</span></td>
</tr>
<tr>
<td aria-label="(1,1): 0.00"><span>0.00</span></td>
<td aria-label="(2,1): 0.00"><span>0.00</span></td>
<td aria-label="(3,1): 0.00"><span>0.00</span></td>
<td aria-label="(4,1): 0.00"><span>0.00</span></td>
</tr>
</tbody>
</table>
<div class="iteration-controls" hidden>
<button class="iteration-toggle" type="button" aria-label="Play animation">
<svg class="iteration-icon--play" width="20" height="20" viewBox="0 0 24 24" aria-hidden="true"><path d="m9 5 11 7-11 7Z" fill="currentColor"/></svg>
<svg class="iteration-icon--pause" width="20" height="20" viewBox="0 0 24 24" fill="none" aria-hidden="true"><path d="M8 5v14M16 5v14" stroke="currentColor" stroke-width="2" stroke-linecap="round"/></svg>
</button>
<input class="iteration-range" type="range" min="0" max="12" step="1" value="0" aria-label="Gridworld iteration" aria-valuetext="k = 0">
</div>
</div>
<script type="application/json" id="gridworld-frames">[{"k":0,"rows":[[0,0,0,0],[0,null,0,0],[0,0,0,0]]},{"k":1,"rows":[[0,0,0,1],[0,null,0,-1],[0,0,0,0]]},{"k":2,"rows":[[0,0,0.72,1],[0,null,0,-1],[0,0,0,0]]},{"k":4,"rows":[[0.373248,0.658368,0.829188,1],[0,null,0.513612,-1],[0,0,0.308448,0]]},{"k":5,"rows":[[0.50761728,0.7155216,0.840852,1],[0.26873856,null,0.55324044,-1],[0,0.22208256,0.36980064,0.13208256]]},{"k":6,"rows":[[0.5850475776,0.734207328,0.8454683196,1],[0.4138573824,null,0.5652050796,-1],[0.2134791936,0.3062313216,0.4302079776,0.1881438912]]},{"k":7,"rows":[[0.61853072256,0.740894509152,0.846960605928,1],[0.495728584704,null,0.569605647276,-1],[0.344751261696,0.36487138176,0.451441426464,0.23668269408]]},{"k":8,"rows":[[0.6337273842432,0.74317264791552,0.84749096278836,1],[0.53457326548992,null,0.571076144523,-1],[0.42079061889792,0.39071467577088,0.46425593286432,0.25633926952128]]},{"k":9,"rows":[[0.6402313649751552,0.7439645698324128,0.8476710396580224,1],[0.5525069044432896,null,0.5715903462146892,-1],[0.4579282276729344,0.4045929133010688,0.4694096791328544,0.2673348059192256]]},{"k":10,"rows":[[0.6430009345269972,0.7442367711236104,0.847733524728544,1],[0.5604178255819039,null,0.5717662797130981,-1],[0.4754318738868288,0.41080169336984756,0.47201854400440274,0.27203510150838545]]},{"k":11,"rows":[[0.6441581636188006,0.7443307566068016,0.8477549823997478,1],[0.5638358814641807,null,0.5718271029787305,-1],[0.4832618554720717,0.4162552540050893,0.47312703293247166,0.27433651081892463]]},{"k":12,"rows":[[0.6446376088143655,0.7443631235170427,0.8477623876840631,1],[0.5652843364690889,null,0.5718480265959042,-1],[0.4869183745071546,0.42287448166080766,0.4738687729788473,0.2753417496850828]]},{"k":100,"rows":[[0.6449692376239592,0.7443801465395762,0.8477662780034063,1],[0.5663144525478666,null,0.5718590331455522,-1],[0.49068396358124516,0.4308444558274348,0.475471130441591,0.2772958394702698]]}]</script>
</div>
<p class="mdp-explanation">The speed of convergence often depends on the <a class="reference-link" href="https://inst.eecs.berkeley.edu/~cs188/textbook/mdp/value-iteration.html" target="_blank" rel="noopener noreferrer">discount factor</a>: as it gets closer to 0, value iteration generally converges faster.</p>
</section>
<p class="mdp-explanation">Run value iteration until convergence, then extract the policy:</p>
<div class="mdp-equation" tabindex="0" role="region" aria-label="Optimal stationary policy equation">
<math display="block" aria-label="Pi star of s is an action in A that maximizes the expected reward plus gamma times V star of the next state">
<mrow><msup><mi>π</mi><mo>*</mo></msup><mo>(</mo><mi>s</mi><mo>)</mo></mrow><mo>=</mo>
<munder><mrow><mo>arg</mo><mspace width="0.15em"/><mo>max</mo></mrow><mrow><mi>a</mi><mo>∈</mo><mi>A</mi></mrow></munder><munder><mo>∑</mo><msup><mi>s</mi><mo>′</mo></msup></munder>
<mrow><mi>T</mi><mo>(</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>,</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow>
<mrow><mo>[</mo><mrow><mi>R</mi><mo>(</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>,</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>+</mo><mi>γ</mi><mrow><msup><mi>V</mi><mo>*</mo></msup><mo>(</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>]</mo></mrow>
</math>
</div>
<p class="mdp-explanation">An optimal policy can be chosen stationary: the selected action at a state is the same at all times.</p>
</section>
<section class="value-case value-exercise" aria-labelledby="discount-noise-exercise">
<h2 id="discount-noise-exercise"><a class="reference-link" href="https://inst.eecs.berkeley.edu/~cs188/sp26/projects/proj3/#question-3-6-points-policies" target="_blank" rel="noopener noreferrer">Exercise 1: Effect of Discount and Noise</a></h2>
<figure class="exercise-gridworld">
<a href="https://inst.eecs.berkeley.edu/~cs188/sp26/projects/proj3/#question-3-6-points-policies" target="_blank" rel="noopener noreferrer" aria-label="Berkeley DiscountGrid exercise">
<img src="assets/mdp/discount-noise-gridworld.png" alt="DiscountGrid with a yellow starting square, a close plus-one exit, a distant plus-ten exit, and a minus-ten cliff. The red path runs near the cliff; the green path travels along the top." width="806" height="799">
</a>
</figure>
<div class="exercise-matches" tabindex="0" role="region" aria-label="Correct discount and noise settings for each behavior">
<table>
<thead>
<tr><th scope="col">Behavior</th><th scope="col">γ</th><th scope="col">Noise</th></tr>
</thead>
<tbody>
<tr><th scope="row">(a) Prefer the close exit (+1), risking the cliff (−10)</th><td>0.1</td><td>0</td></tr>
<tr><th scope="row">(b) Prefer the close exit (+1), but avoiding the cliff (−10)</th><td>0.1</td><td>0.5</td></tr>
<tr><th scope="row">(c) Prefer the distant exit (+10), risking the cliff (−10)</th><td>0.99</td><td>0</td></tr>
<tr><th scope="row">(d) Prefer the distant exit (+10), avoiding the cliff (−10)</th><td>0.99</td><td>0.5</td></tr>
</tbody>
</table>
</div>
</section>
<section class="value-case value-q-values" aria-labelledby="q-values">
<h2 id="q-values"><a class="reference-link" href="https://inst.eecs.berkeley.edu/~cs188/textbook/mdp/value-iteration.html#432-q-value-iteration" target="_blank" rel="noopener noreferrer">Q-Values</a></h2>
<p class="mdp-explanation"><math aria-label="Q star of s, a equals"><mrow><msup><mi>Q</mi><mo>*</mo></msup><mo>(</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>)</mo></mrow><mo>=</mo></math> expected utility starting in s, taking action a, and (thereafter) acting optimally.</p>
<h3>Bellman Equation:</h3>
<div class="mdp-equation" tabindex="0" role="region" aria-label="Bellman optimality equation for Q-values">
<math display="block" aria-label="Q star of s, a equals the sum over next states s prime of P of s prime given s and a, times the reward plus gamma times the maximum over next actions a prime of Q star of s prime, a prime">
<mrow><msup><mi>Q</mi><mo>*</mo></msup><mo>(</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>)</mo></mrow><mo>=</mo>
<munder><mo>∑</mo><msup><mi>s</mi><mo>′</mo></msup></munder>
<mrow><mi>P</mi><mo>(</mo><msup><mi>s</mi><mo>′</mo></msup><mo>|</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>)</mo></mrow>
<mrow><mo>(</mo><mrow><mi>R</mi><mo>(</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>,</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>+</mo><mi>γ</mi><munder><mo>max</mo><msup><mi>a</mi><mo>′</mo></msup></munder><mrow><msup><mi>Q</mi><mo>*</mo></msup><mo>(</mo><msup><mi>s</mi><mo>′</mo></msup><mo>,</mo><msup><mi>a</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>)</mo></mrow>
</math>
</div>
<p class="mdp-explanation">The first action a is fixed. After reaching s′, choose the action a′ with the highest Q-value. Average the immediate reward plus the discounted future value over all possible next states.</p>
<h3>Q-Value Iteration:</h3>
<div class="mdp-equation" tabindex="0" role="region" aria-label="Q-value iteration update">
<math display="block" aria-label="Q k plus one star of s, a is updated to the sum over next states s prime of P of s prime given s and a, times the reward plus gamma times the maximum over next actions a prime of Q k star of s prime, a prime">
<mrow><msubsup><mi>Q</mi><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow><mo>*</mo></msubsup><mo>(</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>)</mo></mrow><mo>←</mo>
<munder><mo>∑</mo><msup><mi>s</mi><mo>′</mo></msup></munder>
<mrow><mi>P</mi><mo>(</mo><msup><mi>s</mi><mo>′</mo></msup><mo>|</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>)</mo></mrow>
<mrow><mo>(</mo><mrow><mi>R</mi><mo>(</mo><mi>s</mi><mo>,</mo><mi>a</mi><mo>,</mo><msup><mi>s</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>+</mo><mi>γ</mi><munder><mo>max</mo><msup><mi>a</mi><mo>′</mo></msup></munder><mrow><msubsup><mi>Q</mi><mi>k</mi><mo>*</mo></msubsup><mo>(</mo><msup><mi>s</mi><mo>′</mo></msup><mo>,</mo><msup><mi>a</mi><mo>′</mo></msup><mo>)</mo></mrow><mo>)</mo></mrow>
</math>
</div>
<p class="mdp-explanation">The Bellman equation describes the converged Q-values. Q-value iteration computes them: update every state-action pair using the previous round’s Q-values on the right-hand side, and repeat until convergence.</p>
<section class="q-value-example" aria-labelledby="q-gridworld-example">
<h3 id="q-gridworld-example">Example: Gridworld</h3>
<figure class="q-gridworld">
<figcaption><math aria-label="Iteration k equals one hundred"><mi>k</mi><mo>=</mo><mn>100</mn></math></figcaption>
<a href="https://inst.eecs.berkeley.edu/~cs188/fa25/assets/lectures/cs188-fa25-lec08.pdf#page=34" target="_blank" rel="noopener noreferrer" aria-label="Berkeley Q-value iteration example">
<img src="assets/mdp/gridworld-q-values.png" alt="Gridworld Q-values after 100 iterations. Each ordinary cell has four triangles for up, right, down, and left. At (3,2), the values are 0.57, minus 0.60, 0.30, and 0.53, respectively." width="671" height="597">
</a>
</figure>
<p class="mdp-explanation">Noise = 0.2, Discount = 0.9, Living reward = 0.</p>
<p class="mdp-explanation">The top, right, bottom, and left triangles show the Q-values for moving up, right, down, and left. At (3,2), their values are approximately 0.57, −0.60, 0.30, and 0.53. Moving up has the highest Q-value.</p>
</section>
</section>
</main>
</body>
</html>