Bellman Equations and Dynamic Programming

← Back to document page

Part 6: Core Theory II: Bellman Equations and Dynamic ProgrammingIntroduction to Reinforcement LearningBellman Equations Recursive relationships among values that can be used to compute valuesThe tree of transition dynamicsa path, or trajectorystateactionpossible pathThe web of transition dynamicsa path, or trajectorystateactionpossible pathThe web of transition dynamicsbackup diagramstateactionpossible path4 Bellman -equation backup diagrams representing recursive relationships among valuesstate valuesaction valuespredictioncontrolmaxmaxmaxstateact ionpossible pathR. S. Sutton and A. G. Barto: Reinforcement Learning: An Introduction10Bellman Equation for a Policy Gt=Rt+1+ Rt+2+ 2Rt+3+ 3Rt+4L=Rt+1+ Rt+2+ Rt+3+ 2Rt+4L()=Rt+1+ Gt+1The basic idea: So: v (s)=E GtSt=s{}=E Rt+1+ v St+1()St=s{}Or, without the expectation operator.

The value function for π is its unique solution. Backup diagrams: ... The terminal state is shaded in the figure (although it is shown in two places, it is formally one state). The expected reward function is thus r(s,a,s0)=1forallstatess,s0 and actions a. Suppose the agent follows

  Value, Terminal