Skip to content

Commit 516eff0

Browse files
ad71norvig
ad71
authored and
norvig
committed
Enhanced explanation of value iteration (aimacode#736)
* Enhanced explanation of value iteration * Fixed minor typo
1 parent 25e4193 commit 516eff0

1 file changed

Lines changed: 149 additions & 10 deletions

File tree

‎mdp.ipynb‎

Lines changed: 149 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -61,7 +61,7 @@
6161
"source": [
6262
"## MDP\n",
6363
"\n",
64-
"To begin with let us look at the implementation of MDP class defined in mdp.py The docstring tells us what all is required to define a MDP namely - set of states,actions, initial state, transition model, and a reward function. Each of these are implemented as methods. Do not close the popup so that you can follow along the description of code below."
64+
"To begin with let us look at the implementation of MDP class defined in mdp.py The docstring tells us what all is required to define a MDP namely - set of states, actions, initial state, transition model, and a reward function. Each of these are implemented as methods. Do not close the popup so that you can follow along the description of code below."
6565
]
6666
},
6767
{
@@ -338,7 +338,7 @@
338338
"source": [
339339
"## GRID MDP\n",
340340
"\n",
341-
"Now we look at a concrete implementation that makes use of the MDP as base class. The GridMDP class in the mdp module is used to represent a grid world MDP like the one shown in in **Fig 17.1** of the AIMA Book. The code should be easy to understand if you have gone through the CustomMDP example."
341+
"Now we look at a concrete implementation that makes use of the MDP as base class. The GridMDP class in the mdp module is used to represent a grid world MDP like the one shown in in **Fig 17.1** of the AIMA Book. We assume for now that the environment is _fully observable_, so that the agent always knows where it is. The code should be easy to understand if you have gone through the CustomMDP example."
342342
]
343343
},
344344
{
@@ -553,25 +553,164 @@
553553
"\n",
554554
"Now that we have looked how to represent MDPs. Let's aim at solving them. Our ultimate goal is to obtain an optimal policy. We start with looking at Value Iteration and a visualisation that should help us understanding it better.\n",
555555
"\n",
556-
"We start by calculating Value/Utility for each of the states. The Value of each state is the expected sum of discounted future rewards given we start in that state and follow a particular policy pi.The algorithm Value Iteration (**Fig. 17.4** in the book) relies on finding solutions of the Bellman's Equation. The intuition Value Iteration works is because values propagate. This point will we more clear after we encounter the visualisation. For more information you can refer to **Section 17.2** of the book. \n"
556+
"We start by calculating Value/Utility for each of the states. The Value of each state is the expected sum of discounted future rewards given we start in that state and follow a particular policy _pi_. The value or the utility of a state is given by\n",
557+
"\n",
558+
"$$U(s)=R(s)+\\gamma\\max_{a\\epsilon A(s)}\\sum_{s'} P(s'\\ |\\ s,a)U(s')$$\n",
559+
"\n",
560+
"This is called the Bellman equation. The algorithm Value Iteration (**Fig. 17.4** in the book) relies on finding solutions of this Equation. The intuition Value Iteration works is because values propagate through the state space by means of local updates. This point will we more clear after we encounter the visualisation. For more information you can refer to **Section 17.2** of the book. \n"
557561
]
558562
},
559563
{
560564
"cell_type": "code",
561-
"execution_count": null,
562-
"metadata": {
563-
"collapsed": true
564-
},
565-
"outputs": [],
565+
"execution_count": 8,
566+
"metadata": {},
567+
"outputs": [
568+
{
569+
"data": {
570+
"text/html": [
571+
"<!DOCTYPE html PUBLIC \"-//W3C//DTD HTML 4.01//EN\"\n",
572+
" \"http://www.w3.org/TR/html4/strict.dtd\">\n",
573+
"\n",
574+
"<html>\n",
575+
"<head>\n",
576+
" <title></title>\n",
577+
" <meta http-equiv=\"content-type\" content=\"text/html; charset=None\">\n",
578+
" <style type=\"text/css\">\n",
579+
"td.linenos { background-color: #f0f0f0; padding-right: 10px; }\n",
580+
"span.lineno { background-color: #f0f0f0; padding: 0 5px 0 5px; }\n",
581+
"pre { line-height: 125%; }\n",
582+
"body .hll { background-color: #ffffcc }\n",
583+
"body { background: #f8f8f8; }\n",
584+
"body .c { color: #408080; font-style: italic } /* Comment */\n",
585+
"body .err { border: 1px solid #FF0000 } /* Error */\n",
586+
"body .k { color: #008000; font-weight: bold } /* Keyword */\n",
587+
"body .o { color: #666666 } /* Operator */\n",
588+
"body .ch { color: #408080; font-style: italic } /* Comment.Hashbang */\n",
589+
"body .cm { color: #408080; font-style: italic } /* Comment.Multiline */\n",
590+
"body .cp { color: #BC7A00 } /* Comment.Preproc */\n",
591+
"body .cpf { color: #408080; font-style: italic } /* Comment.PreprocFile */\n",
592+
"body .c1 { color: #408080; font-style: italic } /* Comment.Single */\n",
593+
"body .cs { color: #408080; font-style: italic } /* Comment.Special */\n",
594+
"body .gd { color: #A00000 } /* Generic.Deleted */\n",
595+
"body .ge { font-style: italic } /* Generic.Emph */\n",
596+
"body .gr { color: #FF0000 } /* Generic.Error */\n",
597+
"body .gh { color: #000080; font-weight: bold } /* Generic.Heading */\n",
598+
"body .gi { color: #00A000 } /* Generic.Inserted */\n",
599+
"body .go { color: #888888 } /* Generic.Output */\n",
600+
"body .gp { color: #000080; font-weight: bold } /* Generic.Prompt */\n",
601+
"body .gs { font-weight: bold } /* Generic.Strong */\n",
602+
"body .gu { color: #800080; font-weight: bold } /* Generic.Subheading */\n",
603+
"body .gt { color: #0044DD } /* Generic.Traceback */\n",
604+
"body .kc { color: #008000; font-weight: bold } /* Keyword.Constant */\n",
605+
"body .kd { color: #008000; font-weight: bold } /* Keyword.Declaration */\n",
606+
"body .kn { color: #008000; font-weight: bold } /* Keyword.Namespace */\n",
607+
"body .kp { color: #008000 } /* Keyword.Pseudo */\n",
608+
"body .kr { color: #008000; font-weight: bold } /* Keyword.Reserved */\n",
609+
"body .kt { color: #B00040 } /* Keyword.Type */\n",
610+
"body .m { color: #666666 } /* Literal.Number */\n",
611+
"body .s { color: #BA2121 } /* Literal.String */\n",
612+
"body .na { color: #7D9029 } /* Name.Attribute */\n",
613+
"body .nb { color: #008000 } /* Name.Builtin */\n",
614+
"body .nc { color: #0000FF; font-weight: bold } /* Name.Class */\n",
615+
"body .no { color: #880000 } /* Name.Constant */\n",
616+
"body .nd { color: #AA22FF } /* Name.Decorator */\n",
617+
"body .ni { color: #999999; font-weight: bold } /* Name.Entity */\n",
618+
"body .ne { color: #D2413A; font-weight: bold } /* Name.Exception */\n",
619+
"body .nf { color: #0000FF } /* Name.Function */\n",
620+
"body .nl { color: #A0A000 } /* Name.Label */\n",
621+
"body .nn { color: #0000FF; font-weight: bold } /* Name.Namespace */\n",
622+
"body .nt { color: #008000; font-weight: bold } /* Name.Tag */\n",
623+
"body .nv { color: #19177C } /* Name.Variable */\n",
624+
"body .ow { color: #AA22FF; font-weight: bold } /* Operator.Word */\n",
625+
"body .w { color: #bbbbbb } /* Text.Whitespace */\n",
626+
"body .mb { color: #666666 } /* Literal.Number.Bin */\n",
627+
"body .mf { color: #666666 } /* Literal.Number.Float */\n",
628+
"body .mh { color: #666666 } /* Literal.Number.Hex */\n",
629+
"body .mi { color: #666666 } /* Literal.Number.Integer */\n",
630+
"body .mo { color: #666666 } /* Literal.Number.Oct */\n",
631+
"body .sa { color: #BA2121 } /* Literal.String.Affix */\n",
632+
"body .sb { color: #BA2121 } /* Literal.String.Backtick */\n",
633+
"body .sc { color: #BA2121 } /* Literal.String.Char */\n",
634+
"body .dl { color: #BA2121 } /* Literal.String.Delimiter */\n",
635+
"body .sd { color: #BA2121; font-style: italic } /* Literal.String.Doc */\n",
636+
"body .s2 { color: #BA2121 } /* Literal.String.Double */\n",
637+
"body .se { color: #BB6622; font-weight: bold } /* Literal.String.Escape */\n",
638+
"body .sh { color: #BA2121 } /* Literal.String.Heredoc */\n",
639+
"body .si { color: #BB6688; font-weight: bold } /* Literal.String.Interpol */\n",
640+
"body .sx { color: #008000 } /* Literal.String.Other */\n",
641+
"body .sr { color: #BB6688 } /* Literal.String.Regex */\n",
642+
"body .s1 { color: #BA2121 } /* Literal.String.Single */\n",
643+
"body .ss { color: #19177C } /* Literal.String.Symbol */\n",
644+
"body .bp { color: #008000 } /* Name.Builtin.Pseudo */\n",
645+
"body .fm { color: #0000FF } /* Name.Function.Magic */\n",
646+
"body .vc { color: #19177C } /* Name.Variable.Class */\n",
647+
"body .vg { color: #19177C } /* Name.Variable.Global */\n",
648+
"body .vi { color: #19177C } /* Name.Variable.Instance */\n",
649+
"body .vm { color: #19177C } /* Name.Variable.Magic */\n",
650+
"body .il { color: #666666 } /* Literal.Number.Integer.Long */\n",
651+
"\n",
652+
" </style>\n",
653+
"</head>\n",
654+
"<body>\n",
655+
"<h2></h2>\n",
656+
"\n",
657+
"<div class=\"highlight\"><pre><span></span><span class=\"k\">def</span> <span class=\"nf\">value_iteration</span><span class=\"p\">(</span><span class=\"n\">mdp</span><span class=\"p\">,</span> <span class=\"n\">epsilon</span><span class=\"o\">=</span><span class=\"mf\">0.001</span><span class=\"p\">):</span>\n",
658+
" <span class=\"sd\">&quot;&quot;&quot;Solving an MDP by value iteration. [Figure 17.4]&quot;&quot;&quot;</span>\n",
659+
" <span class=\"n\">U1</span> <span class=\"o\">=</span> <span class=\"p\">{</span><span class=\"n\">s</span><span class=\"p\">:</span> <span class=\"mi\">0</span> <span class=\"k\">for</span> <span class=\"n\">s</span> <span class=\"ow\">in</span> <span class=\"n\">mdp</span><span class=\"o\">.</span><span class=\"n\">states</span><span class=\"p\">}</span>\n",
660+
" <span class=\"n\">R</span><span class=\"p\">,</span> <span class=\"n\">T</span><span class=\"p\">,</span> <span class=\"n\">gamma</span> <span class=\"o\">=</span> <span class=\"n\">mdp</span><span class=\"o\">.</span><span class=\"n\">R</span><span class=\"p\">,</span> <span class=\"n\">mdp</span><span class=\"o\">.</span><span class=\"n\">T</span><span class=\"p\">,</span> <span class=\"n\">mdp</span><span class=\"o\">.</span><span class=\"n\">gamma</span>\n",
661+
" <span class=\"k\">while</span> <span class=\"bp\">True</span><span class=\"p\">:</span>\n",
662+
" <span class=\"n\">U</span> <span class=\"o\">=</span> <span class=\"n\">U1</span><span class=\"o\">.</span><span class=\"n\">copy</span><span class=\"p\">()</span>\n",
663+
" <span class=\"n\">delta</span> <span class=\"o\">=</span> <span class=\"mi\">0</span>\n",
664+
" <span class=\"k\">for</span> <span class=\"n\">s</span> <span class=\"ow\">in</span> <span class=\"n\">mdp</span><span class=\"o\">.</span><span class=\"n\">states</span><span class=\"p\">:</span>\n",
665+
" <span class=\"n\">U1</span><span class=\"p\">[</span><span class=\"n\">s</span><span class=\"p\">]</span> <span class=\"o\">=</span> <span class=\"n\">R</span><span class=\"p\">(</span><span class=\"n\">s</span><span class=\"p\">)</span> <span class=\"o\">+</span> <span class=\"n\">gamma</span> <span class=\"o\">*</span> <span class=\"nb\">max</span><span class=\"p\">([</span><span class=\"nb\">sum</span><span class=\"p\">([</span><span class=\"n\">p</span> <span class=\"o\">*</span> <span class=\"n\">U</span><span class=\"p\">[</span><span class=\"n\">s1</span><span class=\"p\">]</span> <span class=\"k\">for</span> <span class=\"p\">(</span><span class=\"n\">p</span><span class=\"p\">,</span> <span class=\"n\">s1</span><span class=\"p\">)</span> <span class=\"ow\">in</span> <span class=\"n\">T</span><span class=\"p\">(</span><span class=\"n\">s</span><span class=\"p\">,</span> <span class=\"n\">a</span><span class=\"p\">)])</span>\n",
666+
" <span class=\"k\">for</span> <span class=\"n\">a</span> <span class=\"ow\">in</span> <span class=\"n\">mdp</span><span class=\"o\">.</span><span class=\"n\">actions</span><span class=\"p\">(</span><span class=\"n\">s</span><span class=\"p\">)])</span>\n",
667+
" <span class=\"n\">delta</span> <span class=\"o\">=</span> <span class=\"nb\">max</span><span class=\"p\">(</span><span class=\"n\">delta</span><span class=\"p\">,</span> <span class=\"nb\">abs</span><span class=\"p\">(</span><span class=\"n\">U1</span><span class=\"p\">[</span><span class=\"n\">s</span><span class=\"p\">]</span> <span class=\"o\">-</span> <span class=\"n\">U</span><span class=\"p\">[</span><span class=\"n\">s</span><span class=\"p\">]))</span>\n",
668+
" <span class=\"k\">if</span> <span class=\"n\">delta</span> <span class=\"o\">&lt;</span> <span class=\"n\">epsilon</span> <span class=\"o\">*</span> <span class=\"p\">(</span><span class=\"mi\">1</span> <span class=\"o\">-</span> <span class=\"n\">gamma</span><span class=\"p\">)</span> <span class=\"o\">/</span> <span class=\"n\">gamma</span><span class=\"p\">:</span>\n",
669+
" <span class=\"k\">return</span> <span class=\"n\">U</span>\n",
670+
"</pre></div>\n",
671+
"</body>\n",
672+
"</html>\n"
673+
],
674+
"text/plain": [
675+
"<IPython.core.display.HTML object>"
676+
]
677+
},
678+
"metadata": {},
679+
"output_type": "display_data"
680+
}
681+
],
566682
"source": [
567683
"psource(value_iteration)"
568684
]
569-
},
685+
},
570686
{
571687
"cell_type": "markdown",
572688
"metadata": {},
573689
"source": [
574-
"It takes as inputs two parameters, an MDP to solve and epsilon the maximum error allowed in the utility of any state. It returns a dictionary containing utilities where the keys are the states and values represent utilities. Let us solve the **sequencial_decision_enviornment** GridMDP."
690+
"It takes as inputs two parameters, an MDP to solve and epsilon the maximum error allowed in the utility of any state. It returns a dictionary containing utilities where the keys are the states and values represent utilities. <br> Value Iteration starts with arbitrary initial values for the utilities, calculates the right side of the Bellman equation and plugs it into the left hand side, thereby updating the utility of each state from the utilities of its neighbors. \n",
691+
"This is repeated until equilibrium is reached. \n",
692+
"It works on the principle of _Dynamic Programming_. \n",
693+
"If U_i(s) is the utility value for state _s_ at the _i_ th iteration, the iteration step, called Bellman update, looks like this:\n",
694+
"\n",
695+
"$$ U_{i+1}(s) \\leftarrow R(s) + \\gamma \\max_{a \\epsilon A(s)} \\sum_{s'} P(s'\\ |\\ s,a)U_{i}(s') $$\n",
696+
"\n",
697+
"As you might have noticed, `value_iteration` has an infinite loop. How do we decide when to stop iterating? \n",
698+
"The concept of _contraction_ successfully explains the convergence of value iteration. \n",
699+
"Refer to **Section 17.2.3** of the book for a detailed explanation. \n",
700+
"In the algorithm, we calculate a value _delta_ that measures the difference in the utilities of the current time step and the previous time step. \n",
701+
"\n",
702+
"$$\\delta = \\max{(\\delta, \\begin{vmatrix}U_{i + 1}(s) - U_i(s)\\end{vmatrix})}$$\n",
703+
"\n",
704+
"This value of delta decreases over time.\n",
705+
"We terminate the algorithm if the delta value is less than a threshold value determined by the hyperparameter _epsilon_.\n",
706+
"\n",
707+
"$$\\delta \\lt \\epsilon \\frac{(1 - \\gamma)}{\\gamma}$$\n",
708+
"\n",
709+
"To summarize, the Bellman update is a _contraction_ by a factor of `gamma` on the space of utility vectors. \n",
710+
"Hence, from the properties of contractions in general, it follows that `value_iteration` always converges to a unique solution of the Bellman equations whenever gamma is less than 1.\n",
711+
"We then terminate the algorithm when a reasonable approximation is achieved.\n",
712+
"In practice, it often occurs that the policy _pi_ becomes optimal long before the utility function converges. For the given 4 x 3 environment with _gamma = 0.9_, the policy _pi_ is optimal when _i = 4_, even though the maximum error in the utility function is stil 0.46.This can be clarified from **figure 17.6** in the book. Hence, to increase computational efficiency, we often use another method to solve MDPs called Policy Iteration which we will see in the later part of this notebook. \n",
713+
"<br>For now, let us solve the **sequential_decision_environment** GridMDP using `value_iteration`."
575714
]
576715
},
577716
{

0 commit comments

Comments
 (0)