Action-Value Implementation of Linear Approximation
If we update the techniques from Chapter 9 to accomodate action-value estimates, then all of the linear techniques explored there can be used for these control algorihtms. Previously, we only considered state value estimates, but we can adapt all of those techniques to action values in the linear case quite easily. The main difference is that the action index needs to be included as an argument to the parameter update function.
mimetext/htmlrootassigneelast_run_timestampA6CFEpersist_js_state·has_pluto_hook_features§cell_id$54b92594-04b8-4a8a-82c2-773b4a24680ddepends_on_disabled_cells§runtime T5published_object_keysdepends_on_skipped_cells§errored$7d21c4cd-ab79-4f40-9b8b-f637b3efcab0queued¤logsrunning¦outputbodymsg~UndefVarError: `π_greedy_dp` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.stacktracecall_shorttop-level scopeinlined£urlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#7d21c4cd-ab79-4f40-9b8b-f637b3efcab0source_packagecalltop-level scopelinfo_typeCore.CodeInfolinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#7d21c4cd-ab79-4f40-9b8b-f637b3efcab0functop-level scopeparent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6mfpersist_js_state·has_pluto_hook_features§cell_id$7d21c4cd-ab79-4f40-9b8b-f637b3efcab0depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cellsçerrored$c316c5d3-f484-4e8e-bd56-be1e236d96bcqueued¤logsrunning¦outputbodykApplying the derivation of discount independence to the MDP in exercise 3.22 who's optimal policy depends on $\gamma$
$$J(\pi) = \sum_s \mu_\pi(s)v_\pi^\gamma(s)$$
Consider $\pi_{left}$: $J(\pi_{left})=0.5 \times (1 + 0 + \gamma^2 + 0 + \gamma^4 + 0 + \cdots) + 0.5 \times(0 + \gamma + 0 + \gamma^3 + 0 + \gamma^5 + \cdots)$ $J(\pi_{left}) = 0.5 \times (1 + \gamma + \gamma^2 + \gamma^3 + \gamma^4 + \gamma^5 + \cdots)$
Consider $\pi_{right}$: $J(\pi_{right})=0.5 \times (0 + 2\gamma + 0 + 2\gamma^3 + 0 + \cdots) + 0.5 \times(2 + 0 + 2\gamma^2 + 0 + 2\gamma^4 + \cdots)$ $J(\pi_{right}) = 0.5 \times 2 \times (1 + \gamma + \gamma^2 + \gamma^3 + \gamma^4 + \gamma^5 + \cdots)$
So both average reward values have the same factor for the discount rate and thus the right policy appears better since the average reward value is higher. Previously, we had calculated that a discount rate less than 0.5 made the left policy favorable since the reward was obtained sooner going left vs right. In the original problem we can consider the value of the top state for both left and right policies: $v_{\pi_{left}} (top) = 1 + 0 + \gamma^2 + 0 + \gamma^4 + \cdots = 1 + \gamma^2 + \gamma^4 + \cdots$ $v_{\pi_{right}} (top) = 0 + 2\gamma + 0 + 2\gamma^3 + \cdots = 2 \times (\gamma + \gamma^3 + \cdots) = 2\gamma(v_{\pi_{left}}(top))$
Clearly for $\gamma > 0.5$ the right policy is better.
Similarly, we can consider the value of the left state for both left and right policies: $v_{\pi_{left}} (left) = 0 + \gamma + 0 + \gamma^3 + \cdots = \gamma + \gamma^3 + \cdots$ $v_{\pi_{right}} (left) = 0 + 0 + 2\gamma^2 + 0 + 2\gamma^4 + \cdots = 2 \times (\gamma^2 + \gamma^4 + \cdots) = 2\gamma(v_{\pi_{left}}(left))$
Again, for $\gamma > 0.5$ the right policy is better.
And finally for the right state: $v_{\pi_{left}} (right) = 2 + \gamma + 0 + \gamma^3 + 0 + \gamma^5 \cdots = 2+\gamma(1 + \gamma^2 + \gamma^4 + \cdots)=2 + \frac{\gamma}{1-\gamma^2}$ $= \frac{2(1-\gamma^2) + \gamma}{1-\gamma^2} = \frac{2 - 2\gamma^2 + \gamma}{1-\gamma^2}$ $v_{\pi_{right}} (right) = 2 + 0 + 2\gamma^2 + 0 + 2\gamma^4 + \cdots = 2 \times (1+\gamma^2 + \gamma^4 + \cdots) = \frac{2}{1-\gamma^2}$
$$\frac{v_{\pi_{left}} (right)}{v_{\pi_{right}} (right)}=\frac{2 - 2\gamma^2 + \gamma}{2}$$
For $\gamma=0$ this quantity is 1 meaning the policies are equal and for $\gamma=1$ this quantity is 0.5 meaning that the right policy is better. At $\gamma=0.5$ the quantity is $\frac{2 - 0.5 + 0.5}{2}=\frac{2}{2}=1$ meaning they are equal. The maximum value occurs at $2\gamma = 0.5 \implies \gamma = 0.25$ with a ratio value of $\frac{2 - 0.125 + 0.25}{2}=\frac{2.125}{2}=1.0625$ meaning that the left policy is slightly better or equal from $0 \leq \gamma \leq 0.5$ and worse at $\gamma > 0.5$ which matches the earlier states.
Non-linear Neural Network
Compared to tile coding, the feature vector for non-linear learning will simply be two values: one for the position and another for the velocity. Both values will be scaled so the mean value is 0 and the variance is approximately 1.
Visualizing Policies in Tabular Mountain Car
mimetext/htmlrootassigneelast_run_timestampA6Dpersist_js_state·has_pluto_hook_features§cell_id$39c63495-36c3-4e62-b8fb-36865f2c6243depends_on_disabled_cells§runtime Եpublished_object_keysdepends_on_skipped_cells§errored$d42bb733-07e2-4932-aab4-09229ff67492queued¤logsrunning¦outputbodymsgUndefVarError: `runepisode` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.
Hint: a global variable of this name may be made accessible by importing TabularRL in the current active module Mainstacktracecall_shortIshow_mountaincar_trajectory(π::Function, max_steps::Int64, name::String)inlined£urlhttps://github.com/jekyllstein/RL-Deploy-Test/tree/cccdbd59a290bd4aaf6a8c0e27aad843d2b4b2f3//Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#cc9197e0-f5bd-4742-bea3-b54e0b8e3b93#L1pathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#cc9197e0-f5bd-4742-bea3-b54e0b8e3b93source_packageMaincallIshow_mountaincar_trajectory(π::Function, max_steps::Int64, name::String)linfo_typeCore.MethodInstancelinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#cc9197e0-f5bd-4742-bea3-b54e0b8e3b93funcshow_mountaincar_trajectoryparent_moduleMain.var"workspace#5"from_ccall_shorttop-level scopeinlinedãurlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#d42bb733-07e2-4932-aab4-09229ff67492source_packagecalltop-level scopelinfo_typeNothinglinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#d42bb733-07e2-4932-aab4-09229ff67492func##function_wrapped_cell#414parent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6J persist_js_state·has_pluto_hook_features§cell_id$d42bb733-07e2-4932-aab4-09229ff67492depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cellsçerrored$58a0b622-1b51-4b42-a416-24109ae41a90queued¤logsrunning¦outputbodymsgٯUndefVarError: `tabular_mountaincar_mdp` not defined in `Main.var"workspace#5"`
Suggestion: add an appropriate import or assignment. This global was declared but not assigned.stacktracecall_shorttop-level scopeinlined£urlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#58a0b622-1b51-4b42-a416-24109ae41a90source_packagecalltop-level scopelinfo_typeCore.CodeInfolinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#58a0b622-1b51-4b42-a416-24109ae41a90functop-level scopeparent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6$persist_js_state·has_pluto_hook_features§cell_id$58a0b622-1b51-4b42-a416-24109ae41a90depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cellsçerrored$954848db-6dcc-4666-90f8-b5a900203242queued¤logsrunning¦outputbodymsgUndefVarError: `runepisode` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.
Hint: a global variable of this name may be made accessible by importing TabularRL in the current active module Mainstacktracecall_shortIshow_mountaincar_trajectory(π::Function, max_steps::Int64, name::String)inlined£urlhttps://github.com/jekyllstein/RL-Deploy-Test/tree/cccdbd59a290bd4aaf6a8c0e27aad843d2b4b2f3//Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#cc9197e0-f5bd-4742-bea3-b54e0b8e3b93#L1pathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#cc9197e0-f5bd-4742-bea3-b54e0b8e3b93source_packageMaincallIshow_mountaincar_trajectory(π::Function, max_steps::Int64, name::String)linfo_typeCore.MethodInstancelinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#cc9197e0-f5bd-4742-bea3-b54e0b8e3b93funcshow_mountaincar_trajectoryparent_moduleMain.var"workspace#5"from_ccall_shorttop-level scopeinlined£urlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#954848db-6dcc-4666-90f8-b5a900203242source_packagecalltop-level scopelinfo_typeCore.CodeInfolinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#954848db-6dcc-4666-90f8-b5a900203242functop-level scopeparent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6Ȱpersist_js_state·has_pluto_hook_features§cell_id$954848db-6dcc-4666-90f8-b5a900203242depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cellsçerrored$df07524f-b3fe-4a66-98ac-8f80df66bcffqueued¤logsrunning¦outputbody7mountain_car_dist_step (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA6lh'persist_js_state·has_pluto_hook_features§cell_id$df07524f-b3fe-4a66-98ac-8f80df66bcffdepends_on_disabled_cells§runtime ۵published_object_keysdepends_on_skipped_cells§errored$c85033e1-3ee6-42ad-9ef0-144ce6238ce4queued¤logsrunning¦outputbody-smooth_error (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA6persist_js_state·has_pluto_hook_features§cell_id$c85033e1-3ee6-42ad-9ef0-144ce6238ce4depends_on_disabled_cells§runtime 2published_object_keysdepends_on_skipped_cellsçerrored$f6e08689-040f-4565-9dfb-e9a65d1c1f18queued¤logsrunning¦outputbody>Visualizing Trajectories
mimetext/htmlrootassigneelast_run_timestampA6D8Gpersist_js_state·has_pluto_hook_features§cell_id$f6e08689-040f-4565-9dfb-e9a65d1c1f18depends_on_disabled_cells§runtime |published_object_keysdepends_on_skipped_cells§errored$e7372e2b-a2db-4a93-9efc-f75aa74c197bqueued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampA6 !6persist_js_state·has_pluto_hook_features§cell_id$e7372e2b-a2db-4a93-9efc-f75aa74c197bdepends_on_disabled_cells§runtime }published_object_keysdepends_on_skipped_cells§errored$dc2cffeb-9adf-4956-afa3-ac82af377c59queued¤logsrunning¦outputbody)Finally we can create the action-value function and parameter update for the generic linear case. If a vector of action values is provided as the first argument to the value function, that vector will be updated with all of the action values for a given state.
Monte Carlo Gradient Control
mimetext/htmlrootassigneelast_run_timestampA6Hհpersist_js_state·has_pluto_hook_features§cell_id$50f6ff51-d81b-4e97-9f8a-0daf03af7192depends_on_disabled_cells§runtime ҵpublished_object_keysdepends_on_skipped_cells§errored$5cbaeb8e-bc02-47c9-87b4-57df554cea9dqueued¤logsrunning¦outputbodymsgUndefVarError: `runepisode` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.
Hint: a global variable of this name may be made accessible by importing TabularRL in the current active module Mainstacktracecall_shortIshow_mountaincar_trajectory(π::Function, max_steps::Int64, name::String)inlined£urlhttps://github.com/jekyllstein/RL-Deploy-Test/tree/cccdbd59a290bd4aaf6a8c0e27aad843d2b4b2f3//Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#cc9197e0-f5bd-4742-bea3-b54e0b8e3b93#L1pathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#cc9197e0-f5bd-4742-bea3-b54e0b8e3b93source_packageMaincallIshow_mountaincar_trajectory(π::Function, max_steps::Int64, name::String)linfo_typeCore.MethodInstancelinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#cc9197e0-f5bd-4742-bea3-b54e0b8e3b93funcshow_mountaincar_trajectoryparent_moduleMain.var"workspace#5"from_ccall_shorttop-level scopeinlinedãurlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#5cbaeb8e-bc02-47c9-87b4-57df554cea9dsource_packagecalltop-level scopelinfo_typeNothinglinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#5cbaeb8e-bc02-47c9-87b4-57df554cea9dfunc##function_wrapped_cell#526parent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6YKpersist_js_state·has_pluto_hook_features§cell_id$5cbaeb8e-bc02-47c9-87b4-57df554cea9ddepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cellsçerrored$b094bf9f-bb97-4f23-acdc-f39411a07fb9queued¤logsrunning¦outputbody7π_mountain_car2_fcann (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA6ðpersist_js_state·has_pluto_hook_features§cell_id$b094bf9f-bb97-4f23-acdc-f39411a07fb9depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cellsçerrored$1d417a66-205f-4883-b49c-a6fc900af4cequeued¤logsrunning¦outputbodyz500-element LinRange{Float32, Int64}:
-1.2, -1.19659, -1.19319, -1.18978, -1.18637, …, 0.48978, 0.493186, 0.496593, 0.5mimetext/plainrootassigneeconst mountaincar_positionslast_run_timestampA6gpersist_js_state·has_pluto_hook_features§cell_id$1d417a66-205f-4883-b49c-a6fc900af4cedepends_on_disabled_cells§runtime }published_object_keysdepends_on_skipped_cellsçerrored$17d11fea-883b-4ddb-bec2-c4ad491b39ddqueued¤logsrunning¦outputbodymsgUndefVarError: `StateMDP` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.
Hint: a global variable of this name may be made accessible by importing TabularRL in the current active module Mainstacktracecall_shorttop-level scopeinlined£urlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#17d11fea-883b-4ddb-bec2-c4ad491b39ddsource_packagecalltop-level scopelinfo_typeCore.CodeInfolinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#17d11fea-883b-4ddb-bec2-c4ad491b39ddfunctop-level scopeparent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6persist_js_state·has_pluto_hook_features§cell_id$17d11fea-883b-4ddb-bec2-c4ad491b39dddepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$b4af8d87-a6e5-4e09-92b4-b07757f58f7fqueued¤logsrunning¦outputbodyFrun_access_control_differential_sarsa (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA6}䂰persist_js_state·has_pluto_hook_features§cell_id$b4af8d87-a6e5-4e09-92b4-b07757f58f7fdepends_on_disabled_cells§runtime E;εpublished_object_keysdepends_on_skipped_cells§errored$d6ad1ff1-8fbf-4799-8b1b-ae1e3ce88c5bqueued¤logsrunning¦outputbody
Exercise 10.3
Why do the results shown in Figure 10.4 have higher standard errors at large n than at small n?
At large n more of the reward function comes from the actual trajectory observed during a run. Since random actions are taken initially there will be more spread in the observed reward estimates than with 1 step bootstrapping which is more dependent on the initialization of the action value function. If ties are broken randomly then you would select random actions for the first n-steps of bootstrapping thus experience more spread in the early trajectories for higher n.
Connection to Chapter 3
mimetext/htmlrootassigneelast_run_timestampA6Hpersist_js_state·has_pluto_hook_features§cell_id$0e66a941-1ec1-4d3b-b064-e5f25cc93bafdepends_on_disabled_cells§runtime rpublished_object_keysdepends_on_skipped_cells§errored$c5c839f7-1806-463d-b63a-bd7e1384f203queued¤logsrunning¦outputbodyThe action value calculation also depends on how parameters are represented. Either a dot product is used by extracting the appropriate parameter vector, or the parameter matrix needs to be iterated over the appropriate column
Solving Mountain Car Tabular Problem with Value Iteration
mimetext/htmlrootassigneelast_run_timestampA6Dϰpersist_js_state·has_pluto_hook_features§cell_id$72f575ee-d656-4af6-bf78-aab42bf1debddepends_on_disabled_cells§runtime Lpublished_object_keysdepends_on_skipped_cells§errored$2c620fe4-2f62-40f8-a666-8dced1e0b84aqueued¤logsrunning¦outputbodymsgUndefVarError: `StateMDP` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.
Hint: a global variable of this name may be made accessible by importing TabularRL in the current active module Mainstacktracecall_shorttop-level scopeinlined£urlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#2c620fe4-2f62-40f8-a666-8dced1e0b84asource_packagecalltop-level scopelinfo_typeCore.CodeInfolinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#2c620fe4-2f62-40f8-a666-8dced1e0b84afunctop-level scopeparent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6˰persist_js_state·has_pluto_hook_features§cell_id$2c620fe4-2f62-40f8-a666-8dced1e0b84adepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$bd1f42e5-94cc-4aef-b82a-9bffd1c951d8queued¤logsrunning¦outputbodymsgقUndefVarError: `v̂_mountain_car` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.stacktracecall_shorttop-level scopeinlined£urlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#bd1f42e5-94cc-4aef-b82a-9bffd1c951d8source_packagecalltop-level scopelinfo_typeCore.CodeInfolinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#bd1f42e5-94cc-4aef-b82a-9bffd1c951d8functop-level scopeparent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6Qpersist_js_state·has_pluto_hook_features§cell_id$bd1f42e5-94cc-4aef-b82a-9bffd1c951d8depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cellsçerrored$b8c031ca-7995-4501-a1e3-df3f34e5f0daqueued¤logsrunning¦outputbody10.3 Average Reward: A New Problem Setting for Continuing Tasks
We now introduce an alternative to the discount setting for solving continuing problems (MDPs without a terminal state). The average-reward setting is more commonly used in the classical theory of dynamic programming. The purpose of introducing the average-reward is because discounting is problematic with function approximation in a way it was not problematic for tabular problems.
In the average-reward setting the quality of a policy $\pi$ is defined as the average rate of reward, or simply average reward, while following that policy, which we denote as $r(\pi)$:
$$\begin{flalign}
r(\pi) &\doteq \lim_{h \rightarrow \infty} \frac{1}{h}\sum_{t=1}^h \mathbb{E}[R_t \mid S_0,A_{0:t-1} \sim \pi] \tag{10.6}\\
&= \lim_{h \rightarrow \infty} \mathbb{E} [R_t \mid S_0,A_{0:t-1} \sim \pi] \tag{10.7}\\
&= \sum_s \mu_\pi(s)\sum_a\pi(a \vert s) \sum_{s^\prime,r} p(s^\prime,r \vert s, a)r
\end{flalign}$$
where the expectations are conditioned on the initial state, $S_0$, and on the subsequent actions, $A_0, A_1, \dots,A_{t-1}$, being taken according to $\pi$. The second and third equations hold if the state-state distribution $\mu_\pi(s) \doteq \lim_{t\rightarrow \infty} \Pr \{S_t = s \mid A_{0:t-1} \sim \pi \}$, exists and is independent of $S_0$, in other words, if the MDP is ergodic. In an ergodic MDP, the starting state and any early decision made by the agent can only have a temporary effect; in the long run the expectation of being in a state depends on the policy and the MDP transition probabilities. Ergodicity is sufficient but not necessary to guarantee the existence of the limit in (10.6).
In this setting, we consider all policies that obtain the maximum value of $r(\pi)$ or the reward rate to be optimal. Note that the steady state distribution $\mu_\pi$ is the special distribution under which, if you select actions according to $\pi$, you remain in the same distribution. That is, for which
$$\sum_s \mu_\pi(s) \sum_a \pi(a\vert s)p(s^\prime \vert s, a) = \mu_\pi(s^\prime) \tag{10.8}$$
In the average-reward setting, returns are defined in terms of differences between rewards and the average reward:
$$G_t \doteq R_{t+1} - r(\pi) + R_{t+2} - r(\pi) + R_{t+3} - r(\pi) + \cdots \tag{10.9}$$
This is known as the differential return, and th corresponding value functions are known as differential value functions. Differential value functions are defined in terms of the new return just as conventional value functions were defined in terms of the discounted return; thus we will use the same notation, $v_\pi (s) \doteq \mathbb{E}_\pi[G_t \vert S_t = s]$ and $q_\pi (s, a) \doteq \mathbb{E}_\pi[G_t \vert S_t = s, A_t = a]$ (similarly for $v_*$ and $q_*$), for differential value functions. Differential value functions also have Bellman equations, just slightly different from those we have seen earlier. We simply remove all $\gamma$s and replace all rewards by the difference between the reward and the true average reward:
$$\begin{flalign}
&v_\pi(s) = \sum_a \pi(a\vert s) \sum_{r, s^\prime}p(s^\prime, r \vert s, a) \left [ r - r(\pi) + v_\pi(s^\prime) \right ] \\
&q_\pi(s, a) = \sum_{r, s^\prime}p(s^\prime, r \vert s, a) \left [ r - r(\pi) + \sum_{a^\prime} \pi(a^\prime \vert s^\prime) q_\pi(s^\prime, a^\prime) \right ] \\
&v_* = \max_a \sum_{r, s^\prime}p(s^\prime, r \vert s, a) \left [ r - r(\pi) + v_*(s^\prime) \right ] \\
&q_* = \sum_{r, s^\prime}p(s^\prime, r \vert s, a) \left [ r - \max_{\pi}r(\pi) + \max_a q_\pi(s^\prime, a^\prime) \right ] \\
\end{flalign}$$
There is also a differential form of the two TD errors:
$$\delta_t \doteq R_{t+1} - \bar{R}_t+ \hat v (S_{t+1}, \mathbf{w}_t) - \hat v(S_t, \mathbf{w}_t) \tag{10.10}$$
and
$$\delta_t \doteq R_{t+1} - \bar{R}_t+ \hat q (S_{t+1}, A_{t+1}, \mathbf{w}_t) - \hat q(S_t, A_t, \mathbf{w}_t) \tag{10.11}$$
where $\bar{R}_t$ is an estimate at time $t$ of the average reward $r(\pi)$. With these alternate definitions, most of our algorithms and many theoretical results carry through to the average_reward setting without any change.
For example, an average reward version of semi-gradient Sarsa could be defined just as in (10.2) except with the differential version of the TD error. That is by
$$\mathbf{w}_{t+1} \doteq \mathbf{w}_t + \alpha \delta_t \nabla \hat q(S_t, A_t, \mathbf{w}_t)$$
with $\delta_t$ given by (10.11). See a full implementation below. One limitation of this algorithm is that it does not converge to the differential values but to the differential values plut an arbitrary offset. Notice that the Bellman equations and TD errors given above are unaffected if all the values are shifted by the same amount. Thus, the offset may not matter in practice.
Exercise 10.1
We have not explicitely considered or given pseudocode for any Monte Carlo methods in this chapter. What would they be like? Why is it reasonable not to give pseudocode for them? How would they perform on the Mountain Car task?
Monte Carlo methods require an episode to terminate prior to updating any action value estimates. After the final reward is retrieved then all the action value pairs visited along the trajectory can be updated and the policy can be updated prior to starting the next episode. For tasks such as the Mountain Car task where a random policy will likely never terminate, such a method will never be able to complete a single episode worth of updates. We saw in earlier chapters with the racetrack and gridworld examples that for some environments a bootstrap method is the only suitable one given this possibility of an episode never terminating.
Mountain Car Linear Approximation with Tile Coding
mimetext/htmlrootassigneelast_run_timestampA6D persist_js_state·has_pluto_hook_features§cell_id$1a5acfb0-3b35-41b1-98f8-ffce941c587fdepends_on_disabled_cells§runtime 1published_object_keysdepends_on_skipped_cells§errored$7bc49107-9de5-4985-8750-979f36b3aa81queued¤logsrunning¦outputbody1π_mountain_car2 (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA6Rkpersist_js_state·has_pluto_hook_features§cell_id$7bc49107-9de5-4985-8750-979f36b3aa81depends_on_disabled_cells§runtime %published_object_keysdepends_on_skipped_cellsçerrored$4d392303-4681-4ea1-8dcc-e002a78ea0a1queued¤logsrunning¦outputbodyPolicy Improvement
The purpose of the value function lies in the Policy Improvement Theorem which provides a way to iteratively improve a given policy towards the optimal policy. Consider a policy $\pi(s)$ and its associated value functions $v_\pi(s)$ and $q_\pi(s, a)$. Now consider a new policy $\pi^\prime(s)$ that would select a different action $a^\prime$ at state $s$ than the original policy $\pi$ such that $q_\pi(s, a^\prime) \geq v_\pi(s)$. The theorem proves that if the former is true, then $v_{\pi^\prime}(s) \geq v_\pi(s) \forall s \in \mathcal{S}$. In other words, the new policy is superior to the old one since it has a higher value value at every state. There is also an easy way to construct a policy which meets the necessary criteria of the policy improvement theorem:
$$\begin{flalign}
\pi^\prime(s) &\doteq \mathrm{argmax}_a q_\pi(s, a) \\
& = \mathrm{argmax}_a \mathbb{E} [R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s, A_t = a] \\
& = \mathrm{argmax}_a \sum_{s^\prime, r} p(s^\prime, r \vert s, a) [r + \gamma v_\pi(s^\prime)] \\
\end{flalign}$$
If we have the state-action value function $q_\pi(s, a)$, then the construction is trivial. If we only have $v_\pi(s)$, then we must also have the probability transition function for the environment in order to reconstruct the state-action values. In the absence of $p$ we must rely on $q_\pi$. Consider some future policy such that $\pi(s) = \mathrm{argmax}_a q_\pi(s, a) \: \forall s$. In this case, the updated policy will be identical to the original policy and the process will have converged. The policy at convergence will also be the optimal policy $\pi_*$ whose value functions fulfill the following properties:
$$\begin{flalign}
v_*(s) &\doteq \max_\pi v_\pi(s) \: \forall \: s \in \mathcal{S} \tag{3.15} \\
&= \max_{a \in \mathcal{A}(s)} q_{*}(s, a) \: \forall \: s \in \mathcal{S} \tag{meaning of optimal}\\
&= \max_{a \in \mathcal{A}(s)} \sum_{s^\prime, r} p(s^\prime, r \vert s, a) \left [ r + γ v_* (s^\prime) \right ] \quad \forall s \in \mathcal{S} \tag{Used by Value Iteration when p is available}\\
q_*(s, a) &\doteq \max_\pi q_\pi(s, a) \: \forall \: s \in \mathcal{S} \text{ and } a \in \mathcal{A}(s) \tag{3.16} \\
&=\mathbb{E} \left [ R_{t+1} + \gamma v_* (S_{t+1}) \mid S_t = s, A_t = a \right ] \tag{3.17} \\
&= \sum_{s^\prime, r} p(s^\prime, r \vert s, a) \left [ r + γ v_* (s^\prime) \right ] \tag{exp value def (3.21)} \\
&= \sum_{s^\prime, r} p(s^\prime, r \vert s, a) \left [ r + γ \max_{a^\prime} q_*(s^\prime, a^\prime) \right ] \tag{Used by Q Value Iteration when p is available} \\
&= \mathbb{E} \left [ R_t + γ \max_{a^\prime} q_*(s^\prime, a^\prime) \mid S_t = s, A_t = a \right ] \tag{Used by Q Learning when p is not available} \\
\end{flalign}$$
The policy improvement theorem suggests an approach where we initialize a random policy, find its value function, and then derive an improved policy until the process has converged. If we have the probability transition function, we can use dynamic programming to calculate the value function for a policy as well as the improved policy. Repeating this process until convergence is called Policy Iteration. Alternatively, we can use the properties of the optimal value function without explicitely considering a sequence of policies. That is only possible when the probability transition function is known and is called Value Iteration.
Finding the Optimal Policy
Depending on the nature of the problem and the available information, different techniques are available. Below is a summary of the conditions and available techniques for different scenarios starting with the ideal case where all information is available.
Idealized Tabular Case
Problem conditions
All states and actions can be enumerated: $\mathcal{S} = \{s_1, s_2, \cdots, s_n\}$ and $\mathcal{A} = \{a_1, a_2, \cdots, a_m\}$
$p(s^\prime, r \vert s, a)$ is available for all states and actions
In order to verify that we have the correct value function or the optimal one, we need to confirm the conditions for every state or state-action pair. In short we require $p(s^\prime, r \vert s, a) \: \forall s, a$ which also implies the ability to check all the state action pairs. If this is possible, then the problem is tabular since we can tabulate all of the necessary values. It is only in this best case scenario that we can definitively verify the correct solution.
Solution Techniques
Value Iteration
initialize a list of state values: $[v_1, v_2, \cdots, v_n]$, one for each state
perform the following update accross all states until the values converge: $v_i = \max_{a \in \mathcal{A}} \sum_{s_j, r} p(s_j, r \vert s_i, a) \left [ r + γ v_j \right ]$
Policy Iteration
initialize a random policy $\pi$ (probability distribution over actions for each state, could be a matrix)
initialize a list of state values: $[v_1, v_2, \cdots, v_n]$, one for each state
repeat the following until the values converge
Semi-gradient Dynamic Programming Implementation
mimetext/htmlrootassigneelast_run_timestampA6C' persist_js_state·has_pluto_hook_features§cell_id$57a6510f-bd42-4d1d-a550-d1442f79569fdepends_on_disabled_cells§runtime Zpublished_object_keysdepends_on_skipped_cells§errored$b0761704-5447-4e64-8270-708d9dccef60queued¤logsrunning¦outputbodymsgUndefVarError: `StateMDPTransitionDistribution` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.
Hint: a global variable of this name may be made accessible by importing TabularRL in the current active module Mainstacktracecall_shorttop-level scopeinlined£urlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#b0761704-5447-4e64-8270-708d9dccef60source_packagecalltop-level scopelinfo_typeCore.CodeInfolinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#b0761704-5447-4e64-8270-708d9dccef60functop-level scopeparent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6Apersist_js_state·has_pluto_hook_features§cell_id$b0761704-5447-4e64-8270-708d9dccef60depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$a6c5ec28-b2d5-4893-a118-95c1318d1f7fqueued¤logsrunning¦outputbodyC
Exercise 10.6
Suppose there is an MDP that under any policy produces the deterministic sequence of rewards +1, 0, +1, 0, +1, 0, . . . going on forever. Technically, this violates ergodicity; there is no stationary limiting distribution $μ_\pi$ and the limit (10.7) does not exist. Nevertheless, the average reward (10.6) is well defined. What is it? Now consider two states in this MDP. From A, the reward sequence is exactly as described above, starting with a +1, whereas, from B, the reward sequence starts with a 0 and then continues with +1, 0, +1, 0, . . .. We would like to compute the differential values of A and B. Unfortunately, the differential return (10.9) is not well defined when starting from these states as the implicit limit does not exist. To repair this, one could alternatively define the differential value of a state as $v_\pi (s) \doteq \lim_{\gamma \rightarrow 1} \lim_{h \rightarrow \infty} \sum_{t=0}^h \gamma^t \left ( \mathbb{E_\pi} [R_{t+1}|S_0=s]-r(\pi) \right )$. Under this definition what are the differential values of states A and B?
Exercise 10.7
Consider a Markov reward process consisting of a ring of three states A, B, and C, with state transitions going deterministically around the ring. A reward of +1 is received upon arrival in A and otherwise the reward is 0. What are the differential values of the three states, using (10.13)
From 10.13 we have
$$v_\pi (s) \doteq \lim_{\gamma \rightarrow 1} \lim_{h \rightarrow \infty} \sum_{t=0}^h \gamma^t \left ( \mathbb{E_\pi} [R_{t+1}|S_0=s]-r(\pi) \right )$$
The average reward per step is $\frac{1}{3}$ so we can apply the same method used in exercise 10.6 where the elements inside the parentheses of the sum are: $\frac{2}{3}$ for $C \rightarrow A$ and $-\frac{1}{3}$ for the other two. Starting in state A we transition twice and then on the third arrive in state A leading to the following mean corrected values of $-\frac{1}{3}$, $-\frac{1}{3}$, and $\frac{2}{3}$. The other states will have these values cyclically permuted leading to the following infinite sums:
For state A: $-\frac{1}{3} - \frac{1}{3}\gamma + \frac{2}{3}\gamma^2 - \frac{1}{3}\gamma^3 - \frac{1}{3}\gamma^4 + \cdots$
For state B: $-\frac{1}{3} + \frac{2}{3}\gamma - \frac{1}{3}\gamma^2 - \frac{1}{3}\gamma^3 + \frac{2}{3}\gamma^4 + \cdots$
For state C: $\frac{2}{3} - \frac{1}{3}\gamma - \frac{1}{3} \gamma^2 + \frac{2}{3}\gamma^3 + \cdots = 3 \times (2 - \gamma - \gamma^2 + 2\gamma^3 + \cdots)$
Comparing these sequences we have:
$$\gamma \times v(A) = v(C) - \frac{2}{3} \implies v(A) = \frac{v(C) - \frac{2}{3}}{\gamma}$$
$$\gamma \times v(B) = v(A) + \frac{1}{3} \implies v(A) = \gamma \times v(B) - \frac{1}{3}$$
so
$$\frac{v(C) - \frac{2}{3}}{\gamma} = \gamma \times v(B) - \frac{1}{3} \implies v(C) = \gamma \left ( \gamma \times v(B) - \frac{1}{3} \right ) + \frac{2}{3}$$
also
$$\gamma \times v(C) = v(B) + \frac{1}{3} \implies v(C) = \frac{v(B) + \frac{1}{3}}{\gamma}$$
Equation the two sides for $v(C)$ that only contain $v(B)$ terms we have:
$$\frac{v(B) + \frac{1}{3}}{\gamma} = \gamma \left ( \gamma \times v(B) - \frac{1}{3} \right ) + \frac{2}{3}$$
$$v(B) = \gamma \left ( \gamma \left ( \gamma \times v(B) - \frac{1}{3} \right ) + \frac{2}{3} \right ) - \frac{1}{3} = \gamma^3 v(B) - \gamma^2 \frac{1}{3} + \gamma\frac{2}{3} - \frac{1}{3}$$
$$v(B) \left ( 1 - \gamma^3 \right ) = - \gamma^2 \frac{1}{3} + \gamma\frac{2}{3} - \frac{1}{3} \implies v(B) = \frac{- \gamma^2 \frac{1}{3} + \gamma\frac{2}{3} - \frac{1}{3}}{1 - \gamma^3}$$
$$v(B) = -\frac{1}{3} \frac{\gamma^2 - 2\gamma + 1}{1 - \gamma^3} = -\frac{1}{3} \frac{(\gamma - 1)^2}{-(\gamma - 1)(\gamma^2 + \gamma + 1)} = \frac{1}{3} \frac{\gamma - 1}{\gamma^2 + \gamma + 1}$$
Therefore,
$$\begin{flalign}
\lim_{\gamma \rightarrow 1} v(B) &= \frac{1}{3} \frac{1 - 1}{3} = 0 \\
\lim_{\gamma \rightarrow 1} v(A) &= \gamma \times 0 - \frac{1}{3} = -\frac{1}{3} \\
$\lim_{\gamma \rightarrow 1} v(C) &= \frac{0 + \frac{1}{3}}{\gamma} = \frac{1}{3}
\end{flalign}$$
Two options to represent parameters for use with action-values is to simply have a unique set of parameters for each action each of which matches the size of the state representation vector. Using this technique means we do not need to encode the action space into the representation. The parameters could be represented by a vector of vectors or a matrix in which each column is assigned to an action. Below are the update rules for both of these cases.
In order to use (10.6): $r(\pi) \doteq \lim_{h \rightarrow \infty} \frac{1}{h} \sum_{t = 1}^h \mathbb{E} [R_t \mid S_0, A_{0:t-1} \sim \pi]$ we need to compute $\mathbb{E} [R_t \mid S_0, A_{0:t-1} \sim \pi]$. In this case, we are told that regardless of the policy, the reward sequence will be +1, 0, +1, 0, .... We can therefore replace the expected values in the equation with this sequence since the rewards at each time step are known with 100% probability.
the average reward can be computed as $r(\pi) = \lim_{h \rightarrow \infty} \frac{1}{2h}\sum_{t=1}^h (-1)^{t+1} + 1 = \lim_{h \rightarrow \infty} \frac{h}{2h} + \frac{1}{2h} \sum_{t=1}^h (-1)^{t+1}$
The sum left in the expression is $1 - 1 + 1 - 1 \cdots$ which is 1 for even h and 0 for odd h. Either way, when divided by $2h$ that term goes to 0 leaving only the term $\frac{h}{2h} = \frac{1}{2}$ so $r(\pi) = \frac{1}{2}$
To compute the differential value function for state A and B, consider the alternative definition above using the fact that $r(\pi) = 0.5$.
For state A, each parenthetical term in the sum will be: $1 - 0.5, 0 - 0.5, 1 - 0.5, 0 - 0.5, \dots = 0.5, -0.5, 0.5, -0.5, \dots$
For state B, each parenthetical term in the sum will be: $0 - 0.5, 1 - 0.5, 0 - 0.5, 1 - 0.5, \dots = -0.5, 0.5, -0.5, 0.5, \dots$
$$\begin{flalign}
v_\pi (A) &= \lim_{\gamma \rightarrow 1} \lim_{h \rightarrow \infty} 0.5 - 0.5\gamma + 0.5 \gamma^2 - 0.5\gamma^3 + \cdots \\
&=0.5\lim_{\gamma \rightarrow 1} \lim_{h \rightarrow \infty}\sum_{t=0}^h (-\gamma)^t \\
&=0.5\lim_{\gamma \rightarrow 1}\frac{1}{\gamma +1 } = 0.25
\end{flalign}$$
$$\begin{flalign}
v_\pi (B) &= \lim_{\gamma \rightarrow 1} \lim_{h \rightarrow \infty} -0.5 + 0.5\gamma - 0.5 \gamma^2 + 0.5\gamma^3 + \cdots \\
&=-0.5\lim_{\gamma \rightarrow 1} \lim_{h \rightarrow \infty}\sum_{t=0}^h (-\gamma)^t \\
&=-0.5\lim_{\gamma \rightarrow 1}\frac{1}{\gamma +1 } = -0.25
\end{flalign}$$
We can use these to create a sampling transition function, although it will be deterministic. The positions and velocities are still defined by two real numbers so the state space is unbounded and we cannot use a tabular method.
Exercise 10.8
The pseudocode in the box on page 251 updates $\bar R_t$ using $\delta_t$ as an error rather than simply $R_{t+1} - \bar R_t$. Both errors work, but using $\delta_t$ is better. To see why, consider the ring MRP of three states from Exercise 10.7. The estimate of the average reward should tend towards its true value of $\frac{1}{3}$. Suppose it was already there and was held stuck there. What would the sequence of $R_{t+1} - \bar R_t$ errors be? What would the sequence of $\delta_t$ errors be (using Equation 10.10)? Which error sequence would produce a more stable estimate of the average reward if the estimate were allowed to change in response to the errors? Why?
The sequence of $R_{t+1} - \bar R_t$ would be given by the cyclical sequence of rewards. Let's assume we start the sequence at state A. Then our reward sequence will be 0, 0, 1, 0, 0, 1... so the error sequence will be $-\frac{1}{3}$, $-\frac{1}{3}$, $\frac{2}{3}$,... If we update the average error estimate using these corrections it would remain centered at the correct value but fluctuate up and down with each correction.
In order to calculate $\delta_t$ we must use the definition given by 10.10:
$$\delta_t = R_{t+1} - \bar R_t + \hat v(S_{t+1}, \mathbf{w}_t) - \hat v(S_t, \mathbf{w}_t)$$
This equation requires us to have value estimates for each state which we can assume have converged to the true values as we have for the average reward estimate: $\hat v(A) = -\frac{1}{3}$, $\hat v(B) = 0$, and $\hat v(C) = \frac{1}{3}$. Starting at state A, $\delta_t = 0 - \frac{1}{3} + 0 - -\frac{1}{3} = 0$. For the following state we have $0 - \frac{1}{3} + \frac{1}{3} = 0$. Finally we have $1 - \frac{1}{3} + -\frac{1}{3} - \frac{1}{3} = 0$. So if we use the TD error to update our average reward estimate, at equilibrium all the values will remain unchanged. Using $\delta$ provides a lower variance estimator than simply using the reward.
10.2 Semi-gradient n-step Sarsa
We can obtain an $n$-step version of semi-gradient Sarsa by using an $n$-step return as the update target for the semi-gradient Sarsa update equation (10.1). The $n$-step return immediately generalizes from its tabular form (7.4) to a function approximation form:
$$G_{t:t+n} \doteq R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n \hat q(S_{t+n}, A_{t+n}, \mathbf{w}_{t+n-1}), \quad t+n \lt T \tag{10.4}$$
with $G_{t:t+n} \doteq G_t$ if $t+n \geq T$, as usual. The $n$-step update equation is
$$\mathbf{w}_{t+n} \doteq \mathbf{w}_{t+n-1} + \alpha \left [ G_{t:t+n} - \hat q(S_t, A_t, \mathbf{w}_{t+n-1}) \right ] \nabla \hat q(S_t, A_t, \mathbf{w}_{t+n-1}), \quad 0 \leq t \lt T \tag{10.5}$$
As we have seen before, performance is often best with an $n$ that is some intermediate value between the 1-step sarsa method and Monte Carlo; however, we will not create a full implementation of this algorithm here as it will be replaced by semi-gradient Sarsa($\lambda$) in Chapter 12 which is a much more efficient version of the same concept.
Exercise 10.5
What equations are needed (beyond 10.10) to specify the differential version of TD(0)?
10.10 includes a reward estimate at time t, $\bar R_t$, which also needs to be updated. The TD error represents the newly observed reward the was experienced in excess of the estimated average so the update equation should move $\bar R$ in the direction of the TD error. After each step, the following updates should occur.
$$\begin{flalign}
\delta &\leftarrow R - \bar R + \hat v(S^\prime, \mathbf{w}) - \hat v(S, \mathbf{w}) \\
\bar R &\leftarrow \bar R + \beta \delta \\
\mathbf{w} &\leftarrow \mathbf{w} + \alpha \delta \nabla \hat v(S, \mathbf{w}) \\
S & \leftarrow S^\prime \\
\end{flalign}$$
Dependencies
mimetext/htmlrootassigneelast_run_timestampA6Hlpersist_js_state·has_pluto_hook_features§cell_id$6cea9e69-bf8c-4079-9884-663a728d7b08depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$b0cc6ff8-7296-461c-9db7-e52fa518e2e2queued¤logsrunning¦outputbody6mountaincar_dist_test (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA6hpersist_js_state·has_pluto_hook_features§cell_id$b0cc6ff8-7296-461c-9db7-e52fa518e2e2depends_on_disabled_cells§runtime ",?published_object_keysdepends_on_skipped_cellsçerrored$30ab21ba-3f5b-46a8-8b8c-753f2755d419queued¤logsrunning¦outputbodymsgكUndefVarError: `tile_coding_setup` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.stacktracecall_shortCsetup_mountain_car_tiles(tile_size::Tuple{…}, num_tilings::Int64)inlined£urlhttps://github.com/jekyllstein/RL-Deploy-Test/tree/cccdbd59a290bd4aaf6a8c0e27aad843d2b4b2f3//Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#742100ba-c38e-4840-8988-40990039b527#L1pathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#742100ba-c38e-4840-8988-40990039b527source_packageMaincallPsetup_mountain_car_tiles(tile_size::Tuple{Float32, Float32}, num_tilings::Int64)linfo_typeCore.MethodInstancelinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#742100ba-c38e-4840-8988-40990039b527funcsetup_mountain_car_tilesparent_moduleMain.var"workspace#5"from_ccall_shortxmountaincar_test(max_episodes::Int64, α::Float32, ϵ::Float32; num_tiles::Int64, num_tilings::Int64, kwargs::@Kwargs{})inlined£urlhttps://github.com/jekyllstein/RL-Deploy-Test/tree/cccdbd59a290bd4aaf6a8c0e27aad843d2b4b2f3//Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#7c5fb569-81f0-4b70-ae95-1fce0c51b6f4#L1pathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#7c5fb569-81f0-4b70-ae95-1fce0c51b6f4source_packageMaincallxmountaincar_test(max_episodes::Int64, α::Float32, ϵ::Float32; num_tiles::Int64, num_tilings::Int64, kwargs::@Kwargs{})linfo_typeCore.MethodInstancelinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#7c5fb569-81f0-4b70-ae95-1fce0c51b6f4func#mountaincar_test#92parent_moduleMain.var"workspace#5"from_ccall_short?mountaincar_test(max_episodes::Int64, α::Float32, ϵ::Float32)inlined£urlhttps://github.com/jekyllstein/RL-Deploy-Test/tree/cccdbd59a290bd4aaf6a8c0e27aad843d2b4b2f3//Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#7c5fb569-81f0-4b70-ae95-1fce0c51b6f4#L1pathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#7c5fb569-81f0-4b70-ae95-1fce0c51b6f4source_packageMaincall?mountaincar_test(max_episodes::Int64, α::Float32, ϵ::Float32)linfo_typeCore.MethodInstancelinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#7c5fb569-81f0-4b70-ae95-1fce0c51b6f4funcmountaincar_testparent_moduleMain.var"workspace#5"from_ccall_shorttop-level scopeinlinedãurlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#30ab21ba-3f5b-46a8-8b8c-753f2755d419source_packagecalltop-level scopelinfo_typeNothinglinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#30ab21ba-3f5b-46a8-8b8c-753f2755d419func##function_wrapped_cell#598parent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6ܰpersist_js_state·has_pluto_hook_features§cell_id$30ab21ba-3f5b-46a8-8b8c-753f2755d419depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cellsçerrored$1478745a-634d-4f31-8a70-b74f0e536201queued¤logsrunning¦outputbodyPart of the Sarsa algorithm requires us to identify the maximizing action. These functions update a vector of action-values using the parameters and state representation. By computing all of the action values at once, the maximum can be identified, and these functions compute all the action values more efficiently than using the above function for each action individually.
Example 10.2: An Access-Control Queuing Task
mimetext/htmlrootassigneelast_run_timestampA6Gסpersist_js_state·has_pluto_hook_features§cell_id$a9b74949-9392-4048-bcb6-5fd48c1d9b98depends_on_disabled_cells§runtime {published_object_keysdepends_on_skipped_cells§errored$565c53ee-7ad5-44e2-bce5-4ff1f5f162c0queued¤logsrunning¦outputbodyKdifferential_semi_gradient_expected_sarsa! (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA6cpersist_js_state·has_pluto_hook_features§cell_id$565c53ee-7ad5-44e2-bce5-4ff1f5f162c0depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$12f5065b-5bed-4d03-a0f0-72a942492394queued¤logsrunning¦outputbody9make_tabular_mountaincar (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA6{Spersist_js_state·has_pluto_hook_features§cell_id$12f5065b-5bed-4d03-a0f0-72a942492394depends_on_disabled_cells§runtime u1published_object_keysdepends_on_skipped_cells§errored$4afbb723-340b-4d85-9115-027a0ff8dfadqueued¤logsrunning¦outputbodymsgقUndefVarError: `q̂_mountain_car` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.stacktracecall_shorttop-level scopeinlined£urlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#4afbb723-340b-4d85-9115-027a0ff8dfadsource_packagecalltop-level scopelinfo_typeCore.CodeInfolinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#4afbb723-340b-4d85-9115-027a0ff8dfadfunctop-level scopeparent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6 Dpersist_js_state·has_pluto_hook_features§cell_id$4afbb723-340b-4d85-9115-027a0ff8dfaddepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cellsçerrored$00399548-b21c-43b5-90e2-30656ab1541equeued¤logsrunning¦outputbodymsgَUndefVarError: `mountaincar_fcann_dp_results` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.stacktracecall_shorttop-level scopeinlined£urlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#00399548-b21c-43b5-90e2-30656ab1541esource_packagecalltop-level scopelinfo_typeCore.CodeInfolinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#00399548-b21c-43b5-90e2-30656ab1541efunctop-level scopeparent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6?persist_js_state·has_pluto_hook_features§cell_id$00399548-b21c-43b5-90e2-30656ab1541edepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cellsçerrored$c75dc51c-cbff-48b1-b0fd-108828929b51queued¤logsrunning¦outputbodymsgUndefVarError: `StateMDP` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.
Hint: a global variable of this name may be made accessible by importing TabularRL in the current active module Mainstacktracecall_shorttop-level scopeinlined£urlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#c75dc51c-cbff-48b1-b0fd-108828929b51source_packagecalltop-level scopelinfo_typeCore.CodeInfolinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#c75dc51c-cbff-48b1-b0fd-108828929b51functop-level scopeparent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6{İpersist_js_state·has_pluto_hook_features§cell_id$c75dc51c-cbff-48b1-b0fd-108828929b51depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$7a47a518-dfc7-4310-a0b5-6f0d151c8263queued¤logsrunning¦outputbodyUNeural Network Mountain Car Semi-gradient Sarsa
mimetext/htmlrootassigneelast_run_timestampA6E=persist_js_state·has_pluto_hook_features§cell_id$7a47a518-dfc7-4310-a0b5-6f0d151c8263depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$a22e5d34-4b8d-479c-985c-d6abd41a6c80queued¤logsrunning¦outputbodyEExample 10.1: Mountain Car Task
mimetext/htmlrootassigneelast_run_timestampA6Cpersist_js_state·has_pluto_hook_features§cell_id$a22e5d34-4b8d-479c-985c-d6abd41a6c80depends_on_disabled_cells§runtime Lpublished_object_keysdepends_on_skipped_cells§errored$b990ba67-42c8-4ab9-943d-085392204fddqueued¤logsrunning¦outputbodyEDefining Car State and Dynamics
mimetext/htmlrootassigneelast_run_timestampA6Dİpersist_js_state·has_pluto_hook_features§cell_id$b990ba67-42c8-4ab9-943d-085392204fdddepends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$7c5fb569-81f0-4b70-ae95-1fce0c51b6f4queued¤logsrunning¦outputbody1mountaincar_test (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA6Npersist_js_state·has_pluto_hook_features§cell_id$7c5fb569-81f0-4b70-ae95-1fce0c51b6f4depends_on_disabled_cells§runtime Ǭpublished_object_keysdepends_on_skipped_cellsçerrored$0e3e506d-1959-47fd-8da9-b3dfd294be67queued¤logsrunning¦outputbodymsgكUndefVarError: `q̂_mountain_car2` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.stacktracecall_shorttop-level scopeinlined£urlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#0e3e506d-1959-47fd-8da9-b3dfd294be67source_packagecalltop-level scopelinfo_typeCore.CodeInfolinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#0e3e506d-1959-47fd-8da9-b3dfd294be67functop-level scopeparent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6V~persist_js_state·has_pluto_hook_features§cell_id$0e3e506d-1959-47fd-8da9-b3dfd294be67depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cellsçerrored$af97f222-08d1-4200-a10b-8da178182175queued¤logsrunning¦outputbody9Dynamic Programming
mimetext/htmlrootassigneelast_run_timestampA6D1persist_js_state·has_pluto_hook_features§cell_id$af97f222-08d1-4200-a10b-8da178182175depends_on_disabled_cells§runtime Opublished_object_keysdepends_on_skipped_cells§errored$b5273dfa-2262-487a-856b-441f007bd163queued¤logsrunning¦outputbodymsgUndefVarError: `runepisode` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.
Hint: a global variable of this name may be made accessible by importing TabularRL in the current active module Mainstacktrace call_short(::var"#32#33")(i::Int64)inlined£urlhttps://github.com/jekyllstein/RL-Deploy-Test/tree/cccdbd59a290bd4aaf6a8c0e27aad843d2b4b2f3//Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#b5273dfa-2262-487a-856b-441f007bd163#L1pathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#b5273dfa-2262-487a-856b-441f007bd163source_packageMaincall(::var"#32#33")(i::Int64)linfo_typeCore.MethodInstancelinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#b5273dfa-2262-487a-856b-441f007bd163func#32parent_moduleMain.var"workspace#5"from_ccall_shortnextinlinedãurlpath=/home/runner/.julia/packages/Transducers/fnznF/src/library.jlsource_packagecallnextlinfo_typeNothingline6filelibrary.jlfuncnextparent_modulefrom_ccall_shortnextinlinedãurlpath:/home/runner/.julia/packages/Transducers/fnznF/src/core.jlsource_packagecallnextlinfo_typeNothinglinefilecore.jlfuncnextparent_modulefrom_ccall_shortmacro expansioninlinedãurlpath:/home/runner/.julia/packages/Transducers/fnznF/src/core.jlsource_packagecallmacro expansionlinfo_typeNothingline̵filecore.jlfuncmacro expansionparent_modulefrom_ccall_short_foldl_arrayinlinedãurlpath?/home/runner/.julia/packages/Transducers/fnznF/src/processes.jlsource_packagecall_foldl_arraylinfo_typeNothingline̻fileprocesses.jlfunc_foldl_arrayparent_modulefrom_ccall_short__foldl__inlinedãurlpath?/home/runner/.julia/packages/Transducers/fnznF/src/processes.jlsource_packagecall__foldl__linfo_typeNothingline̶fileprocesses.jlfunc__foldl__parent_modulefrom_ccall_shortfoldl_basecaseinlinedãurlpath?/home/runner/.julia/packages/Transducers/fnznF/src/processes.jlsource_packagecallfoldl_basecaselinfo_typeNothinglineifileprocesses.jlfuncfoldl_basecaseparent_modulefrom_ccall_short{_reduce_basecase(rf::Transducers.Reduction{…}, init::Transducers.InitOf{…}, reducible::Transducers.SizedReducible{…})inlined£urlLfile:///home/runner/.julia/packages/Transducers/fnznF/src/threading_utils.jlpathE/home/runner/.julia/packages/Transducers/fnznF/src/threading_utils.jlsource_packageTransducerscall_reduce_basecase(rf::Transducers.Reduction{Transducers.Map{var"#32#33"}, Transducers.BottomRF{Transducers.Completing{typeof(+)}}}, init::Transducers.InitOf{Transducers.DefaultInitOf}, reducible::Transducers.SizedReducible{UnitRange{Int64}, Int64})linfo_typeCore.MethodInstanceline:filethreading_utils.jlfunc_reduce_basecaseparent_moduleTransducersfrom_ccall_shortٚ_reduce(ctx::Transducers.CancellableDACContext, rf::Transducers.Reduction{…}, init::Transducers.InitOf{…}, reducible::Transducers.SizedReducible{…})inlined£urlCfile:///home/runner/.julia/packages/Transducers/fnznF/src/reduce.jlpath(x::Transducers.Eduction{…}, f::Transducers.var"#264#265"{…})inlined£urlghttps://github.com/JuliaLang/julia/tree/8f5b7ca12ad48c6d740e058312fc8cf2bbe67848/base/operators.jl#L926path./operators.jlsource_packageMaincall|>(x::Transducers.Eduction{Transducers.Reduction{Transducers.Map{var"#32#33"}, Transducers.BottomRF{Transducers.Completing{typeof(BangBang.push!!)}}}, UnitRange{Int64}}, f::Transducers.var"#264#265"{@Kwargs{}, typeof(+)})linfo_typeCore.MethodInstancelinefileoperators.jlfunc|>parent_moduleBasefrom_ccall_shorttop-level scopeinlined£urlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#b5273dfa-2262-487a-856b-441f007bd163source_packagecalltop-level scopelinfo_typeCore.CodeInfolinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#b5273dfa-2262-487a-856b-441f007bd163functop-level scopeparent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6հpersist_js_state·has_pluto_hook_features§cell_id$b5273dfa-2262-487a-856b-441f007bd163depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cellsçerrored$b5409b69-a254-4355-b2b9-99394eceb2f7queued¤logsrunning¦outputbodymsgكUndefVarError: `π_mountain_car_q` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.stacktracecall_shorttop-level scopeinlined£urlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#b5409b69-a254-4355-b2b9-99394eceb2f7source_packagecalltop-level scopelinfo_typeCore.CodeInfolinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#b5409b69-a254-4355-b2b9-99394eceb2f7functop-level scopeparent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6>yJpersist_js_state·has_pluto_hook_features§cell_id$b5409b69-a254-4355-b2b9-99394eceb2f7depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cellsçerrored$b9ebd6bb-90a1-4945-85ed-023206e2420aqueued¤logsrunning¦outputbodymsgUndefVarError: `StateMDP` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.
Hint: a global variable of this name may be made accessible by importing TabularRL in the current active module Mainstacktracecall_shorttop-level scopeinlined£urlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#b9ebd6bb-90a1-4945-85ed-023206e2420asource_packagecalltop-level scopelinfo_typeCore.CodeInfolinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#b9ebd6bb-90a1-4945-85ed-023206e2420afunctop-level scopeparent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6persist_js_state·has_pluto_hook_features§cell_id$b9ebd6bb-90a1-4945-85ed-023206e2420adepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$d0cf3806-05c6-4a50-94c8-55c9042d51b7queued¤logsrunning¦outputbodymsgكUndefVarError: `tile_coding_setup` not defined in `Main.var"workspace#5"`
Suggestion: check for spelling errors or missing imports.stacktracecall_shortCsetup_mountain_car_tiles(tile_size::Tuple{…}, num_tilings::Int64)inlined£urlhttps://github.com/jekyllstein/RL-Deploy-Test/tree/cccdbd59a290bd4aaf6a8c0e27aad843d2b4b2f3//Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#742100ba-c38e-4840-8988-40990039b527#L1pathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#742100ba-c38e-4840-8988-40990039b527source_packageMaincallPsetup_mountain_car_tiles(tile_size::Tuple{Float32, Float32}, num_tilings::Int64)linfo_typeCore.MethodInstancelinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#742100ba-c38e-4840-8988-40990039b527funcsetup_mountain_car_tilesparent_moduleMain.var"workspace#5"from_ccall_shortُmountaincar_dist_test(max_episodes::Int64, α::Float32, ϵ::Float32; num_tiles::Int64, num_tilings::Int64, max_steps::Int64, kwargs::@Kwargs{})inlined£urlhttps://github.com/jekyllstein/RL-Deploy-Test/tree/cccdbd59a290bd4aaf6a8c0e27aad843d2b4b2f3//Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#b0cc6ff8-7296-461c-9db7-e52fa518e2e2#L1pathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#b0cc6ff8-7296-461c-9db7-e52fa518e2e2source_packageMaincallُmountaincar_dist_test(max_episodes::Int64, α::Float32, ϵ::Float32; num_tiles::Int64, num_tilings::Int64, max_steps::Int64, kwargs::@Kwargs{})linfo_typeCore.MethodInstancelinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#b0cc6ff8-7296-461c-9db7-e52fa518e2e2func#mountaincar_dist_test#63parent_moduleMain.var"workspace#5"from_ccall_shortDmountaincar_dist_test(max_episodes::Int64, α::Float32, ϵ::Float32)inlined£urlhttps://github.com/jekyllstein/RL-Deploy-Test/tree/cccdbd59a290bd4aaf6a8c0e27aad843d2b4b2f3//Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#b0cc6ff8-7296-461c-9db7-e52fa518e2e2#L1pathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#b0cc6ff8-7296-461c-9db7-e52fa518e2e2source_packageMaincallDmountaincar_dist_test(max_episodes::Int64, α::Float32, ϵ::Float32)linfo_typeCore.MethodInstancelinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#b0cc6ff8-7296-461c-9db7-e52fa518e2e2funcmountaincar_dist_testparent_moduleMain.var"workspace#5"from_ccall_shorttop-level scopeinlinedãurlpathٕ/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#d0cf3806-05c6-4a50-94c8-55c9042d51b7source_packagecalltop-level scopelinfo_typeNothinglinefileZChapter_10_On_policy_Control_with_Approximation.jl#==#d0cf3806-05c6-4a50-94c8-55c9042d51b7func##function_wrapped_cell#454parent_modulefrom_c¤mime'application/vnd.pluto.stacktrace+objectrootassigneelast_run_timestampA6kʎpersist_js_state·has_pluto_hook_features§cell_id$d0cf3806-05c6-4a50-94c8-55c9042d51b7depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cellsçerroredñcell_dependencies $f68952bd-4c0b-4331-a09c-5b118c8fa5a9precedence_heuristic cell_id$f68952bd-4c0b-4331-a09c-5b118c8fa5a9downstream_cells_map'state_aggregation_action_gradient_setup$62839b2a-398a-4445-87d1-b15ff2acc1d1upstream_cells_mapRealget_action_value$4271151d-d5a6-4a29-96c3-f2102b142b95update_parameters!$5f8b0254-88f4-4d19-ade1-8e7c40941b43$96548352-cd4d-4448-8312-ed10057f4359update_action_values!$5534526a-d790-4379-98b0-8e4ee981fd9fFunctionVector$9df1a18d-137c-4ea5-8d15-05697f7bbf07precedence_heuristic cell_id$9df1a18d-137c-4ea5-8d15-05697f7bbf07downstream_cells_mapupstream_cells_map@md_strgetindex$c11aa069-93c2-435a-8f0e-353ced9633b6precedence_heuristic cell_id$c11aa069-93c2-435a-8f0e-353ced9633b6downstream_cells_mapmountaincar_fcann_test$5fdbce61-ca25-45e0-b07d-94adf7138446upstream_cells_maprun_fcann_semi_gradient_sarsa$39b0f100-a7e7-4633-b296-ccc87a5a35abmountain_car_mdp$1e9c537a-a731-4b81-8f6a-cb658b52c5bezerosIntegerVector-Float32/NTuple*fill$7812e801-70fd-4331-ad0a-fad02c1a399fprecedence_heuristic cell_id$7812e801-70fd-4331-ad0a-fad02c1a399fdownstream_cells_mapsemi_gradient_expected_sarsa!upstream_cells_mapcompute_expected_sarsa_value$8ed6f8fd-8574-4d5a-9964-ce8a32629c6fsemi_gradient_sarsa!$991492f4-7dfc-43aa-ab6c-a6b1f3e38225$2f685ee2-6ad8-4bb1-b326-e5de7c15eb18precedence_heuristic cell_id$2f685ee2-6ad8-4bb1-b326-e5de7c15eb18downstream_cells_mapupstream_cells_map@md_strgetindex$dae59fd9-0397-4307-afd8-bafb6f0bfa52precedence_heuristic cell_id$dae59fd9-0397-4307-afd8-bafb6f0bfa52downstream_cells_mapupstream_cells_map:nsamples$e86bc86f-9909-458d-b86d-0a4ac4b9d43d/|>+foldxtmountain_car_mdp$1e9c537a-a731-4b81-8f6a-cb658b52c5beMaprunepisode$c678846c-aaff-4266-8b2c-07a3a92445efprecedence_heuristic cell_id$c678846c-aaff-4266-8b2c-07a3a92445efdownstream_cells_mapfcann_action_gradient_setup$39b0f100-a7e7-4633-b296-ccc87a5a35ab$b5d2776f-4b93-4eaa-8873-c1c4e610e6b0$c75dc51c-cbff-48b1-b0fd-108828929b51upstream_cells_map update_nn_parameters!typemin!>FCANN.zeroParams!islessStateMDPlengthBase.get@bind=>SliderBasePlutoRunnerPlutoRunner.create_bondconfirmCore.applicablePlutoUI.combineSelectgetindex$cafb20b4-a2bd-46a9-9660-b0ace84d6e4cprecedence_heuristic cell_id$cafb20b4-a2bd-46a9-9660-b0ace84d6e4cdownstream_cells_mapinitialize_car_state$ac80958a-73ec-4342-b553-b33df6612a50$f9abf433-8ce3-4520-9b47-f17f8f07b4cb$1e9c537a-a731-4b81-8f6a-cb658b52c5be$5b2ffd90-ead0-42ce-999a-584ed8995910$12f5065b-5bed-4d03-a0f0-72a942492394$e5ad765a-341f-4f11-9ae8-37d81cb349d2$bc1d7cce-c0f4-47a8-b674-8acb82491c7fupstream_cells_map-Float32*rand$66d6a4b0-ddf8-4781-b3b4-20f02b25199aprecedence_heuristic cell_id$66d6a4b0-ddf8-4781-b3b4-20f02b25199adownstream_cells_mapupstream_cells_mapshow_mountaincar_trajectory$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93$1054cfa3-9f58-4a93-a318-c2d21cf23220policy_num$e2cd69c5-eda7-4897-9e64-0adf940d4d96mountaincar_policy_iteration$3c300a2b-4139-4df0-906b-4cae3592cc2btabular_mountaincar_mdp$9d65285f-d49e-40ce-acea-1f565bcd4108$b0265b93-ae5f-48f2-a9fd-44fd6115164bprecedence_heuristic cell_id$b0265b93-ae5f-48f2-a9fd-44fd6115164bdownstream_cells_mapupstream_cells_map@md_strgetindex$57659c52-de1b-46e6-a863-8eeec0cee601precedence_heuristic cell_id$57659c52-de1b-46e6-a863-8eeec0cee601downstream_cells_mapπ_optimal_value_iteration$cbf1e5ed-8308-486e-a9b7-6cf7fb441fe3upstream_cells_mapmountaincar_value_iteration$57ea3538-33be-4673-b914-8191d35426a9sample_action:&assign_state_index_tabular_mountaincar$9d65285f-d49e-40ce-acea-1f565bcd4108view$a9fdb1fd-3f62-4e1c-9157-c4eee6215261precedence_heuristic cell_id$a9fdb1fd-3f62-4e1c-9157-c4eee6215261downstream_cells_map!differential_semi_gradient_sarsa!$565c53ee-7ad5-44e2-bce5-4ff1f5f162c0$c9759bd9-ec9b-47a1-9080-a7fc332be565$065b2626-01f1-443f-8be4-3036003a2772$b5d2776f-4b93-4eaa-8873-c1c4e610e6b0$b4af8d87-a6e5-4e09-92b4-b07757f58f7fupstream_cells_map zeroTupleonecompute_sarsa_value$fc0b88f3-fbf9-450d-b770-b34357ffad49StateMDPlengthsample_actionVectoreachindexReal/zerosrandIntegerFunction<=Int64push!-+*make_ϵ_greedy_policy!$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93precedence_heuristic cell_id$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93downstream_cells_mapshow_mountaincar_trajectory$d42bb733-07e2-4932-aab4-09229ff67492$864450b9-1319-4426-961f-ee6df93463d8$99e3ec39-24f0-43d6-b6fd-9910b738ce2c$a97e3b12-b7a5-4f88-bdb9-c3158203e0ff$cbf1e5ed-8308-486e-a9b7-6cf7fb441fe3$66d6a4b0-ddf8-4781-b3b4-20f02b25199a$78087a57-33a0-4581-81de-926476090931$f2201afe-8952-4dde-9e39-02beeb920f6f$7d21c4cd-ab79-4f40-9b8b-f637b3efcab0$1e224a46-91ef-4a5f-ae35-ef4062147f2d$5cbaeb8e-bc02-47c9-87b4-57df554cea9d$b5409b69-a254-4355-b2b9-99394eceb2f7$ab4cb3db-3a2d-4145-826b-b1001114eeff$b191d3f9-cf25-4fb4-8f5a-8da86e96e125$954848db-6dcc-4666-90f8-b5a900203242upstream_cells_map@md_strsummountain_car_actions$d577b393-4b40-4c90-9993-4ffbcbd9df6dmountain_car_mdp$1e9c537a-a731-4b81-8f6a-cb658b52c5beIntegerFunctionMarkdown.parsescatterplotMarkdownLayoutrunepisodegetindex$e86bc86f-9909-458d-b86d-0a4ac4b9d43dprecedence_heuristic cell_id$e86bc86f-9909-458d-b86d-0a4ac4b9d43ddownstream_cells_mapnsamples$b5273dfa-2262-487a-856b-441f007bd163$dae59fd9-0397-4307-afd8-bafb6f0bfa52upstream_cells_mapCore:|>Base.get@bindBasePlutoRunnerPlutoRunner.create_bondNumberFieldconfirmCore.applicable$bc1d7cce-c0f4-47a8-b674-8acb82491c7fprecedence_heuristic cell_id$bc1d7cce-c0f4-47a8-b674-8acb82491c7fdownstream_cells_mapmountain_car_differential_mdp$49e43d51-05d6-415b-a685-76e50904c5bc$d3ba78fa-f032-4bb9-9359-ef3bcff2252dupstream_cells_mapmountain_car_actions$d577b393-4b40-4c90-9993-4ffbcbd9df6dinitialize_car_state$cafb20b4-a2bd-46a9-9660-b0ace84d6e4c==$mountain_car_differential_transition$e5ad765a-341f-4f11-9ae8-37d81cb349d2StateMDP$7e8c89aa-8a5e-4ff4-afd2-df8f5c77b5b2precedence_heuristic cell_id$7e8c89aa-8a5e-4ff4-afd2-df8f5c77b5b2downstream_cells_mapmountaincar_velocities$c799ffe4-f4af-487d-b557-8b50d13632b7$58a0b622-1b51-4b42-a416-24109ae41a90upstream_cells_maptabular_mountaincar_args$33ea5f09-3a1f-476d-875a-1f3635a40295LinRange$c12070a9-df63-4b25-99e6-26ff876af1b4precedence_heuristic cell_id$c12070a9-df63-4b25-99e6-26ff876af1b4downstream_cells_map"update_mountaincar_feature_vector!$0f958535-6b18-46de-a1ba-81f64c217ee0upstream_cells_map-Float32/NTuple*Vector$991492f4-7dfc-43aa-ab6c-a6b1f3e38225precedence_heuristic cell_id$991492f4-7dfc-43aa-ab6c-a6b1f3e38225downstream_cells_mapsemi_gradient_sarsa!$2c620fe4-2f62-40f8-a666-8dced1e0b84a$39b0f100-a7e7-4633-b296-ccc87a5a35ab$7812e801-70fd-4331-ad0a-fad02c1a399f$5be866c3-0fb2-4d1f-9c31-b85aba332905upstream_cells_map zeroTuple>islessonecompute_sarsa_value$fc0b88f3-fbf9-450d-b770-b34357ffad49StateMDPlengthsample_actionmountaincar_test$7c5fb569-81f0-4b70-ae95-1fce0c51b6f4mapscatter-/plot+foldxtMapLayout$99e3ec39-24f0-43d6-b6fd-9910b738ce2cprecedence_heuristic cell_id$99e3ec39-24f0-43d6-b6fd-9910b738ce2cdownstream_cells_mapupstream_cells_maptabular_mountaincar_args$33ea5f09-3a1f-476d-875a-1f3635a40295show_mountaincar_trajectory$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93$1054cfa3-9f58-4a93-a318-c2d21cf23220tabular_policies$e48af9f4-0b47-4a45-b0ad-8f53b094e712tabular_mountaincar_mdp$9d65285f-d49e-40ce-acea-1f565bcd4108$f11787a1-57f8-4077-8d60-bc760ece7cc6precedence_heuristic cell_id$f11787a1-57f8-4077-8d60-bc760ece7cc6downstream_cells_mapcalculate_action_value$b9ebd6bb-90a1-4945-85ed-023206e2420aupstream_cells_map zeropopisless@inboundsnothingVectorislessFloat64zerosend-plot+undefLayout$6351304f-50ac-4755-86e1-cd4680f2d803precedence_heuristic cell_id$6351304f-50ac-4755-86e1-cd4680f2d803downstream_cells_mapupstream_cells_map@md_strgetindex$05e2fff5-4871-4468-a00e-9c1b7ba0ffc6precedence_heuristic cell_id$05e2fff5-4871-4468-a00e-9c1b7ba0ffc6downstream_cells_mapupstream_cells_map@md_strgetindex$bc220d14-97fd-486d-9880-6908135fe036precedence_heuristic cell_id$bc220d14-97fd-486d-9880-6908135fe036downstream_cells_mapupstream_cells_map@md_strgetindex$e48af9f4-0b47-4a45-b0ad-8f53b094e712precedence_heuristic cell_id$e48af9f4-0b47-4a45-b0ad-8f53b094e712downstream_cells_maptabular_policies$99e3ec39-24f0-43d6-b6fd-9910b738ce2cupstream_cells_maptabular_mountaincar_πrand$1b15efa9-c331-46bf-93db-f96dee026fe2accelerate_mountaincar_π$e338be2b-05f1-43f4-a194-45ffd710777e$5534526a-d790-4379-98b0-8e4ee981fd9fprecedence_heuristic cell_id$5534526a-d790-4379-98b0-8e4ee981fd9fdownstream_cells_mapupdate_action_values!$f68952bd-4c0b-4331-a09c-5b118c8fa5a9upstream_cells_map zerotypemin!>popisless@inboundsnothingVectorBase.get@bind=>BasePlutoRunnerPlutoRunner.create_bondNumberFieldconfirmCore.applicablePlutoUI.combineSelectgetindex$318b398a-d8f2-4f39-a45d-fd9023961bf8precedence_heuristiccell_id$318b398a-d8f2-4f39-a45d-fd9023961bf8downstream_cells_mapupstream_cells_mapjoinpath@__DIR__include$be77b538-d106-4ca0-a974-289415588c47precedence_heuristic cell_id$be77b538-d106-4ca0-a974-289415588c47downstream_cells_mapupstream_cells_map@md_strgetindex$5bc2eda5-5f4c-4165-9afb-16920f30b0c5precedence_heuristic cell_id$5bc2eda5-5f4c-4165-9afb-16920f30b0c5downstream_cells_mapπ_optimal_policy_iterationupstream_cells_mapsample_action:&assign_state_index_tabular_mountaincar$9d65285f-d49e-40ce-acea-1f565bcd4108viewmountaincar_policy_iteration$3c300a2b-4139-4df0-906b-4cae3592cc2bend$f9ee13e8-7406-4fba-9a30-1e2714bd7cfcprecedence_heuristic cell_id$f9ee13e8-7406-4fba-9a30-1e2714bd7cfcdownstream_cells_mapupstream_cells_mapplot_mountaincar_action_values$8a5d9e3d-e8ef-4cea-8cd8-6975f797d7bd$d8d5db17-d89c-47db-b258-6ad1635478b7$5db29488-a150-42ee-aedb-380a3a4fd548q̂_mountain_car_q$cbac1927-b087-4c4c-98ae-6aa5f0b824ad$afee7bc9-aff0-4c71-a227-9845cb23d4e9precedence_heuristic cell_id$afee7bc9-aff0-4c71-a227-9845cb23d4e9downstream_cells_maprand_nsteps$864450b9-1319-4426-961f-ee6df93463d8upstream_cells_map@md_strCore:Base.get@bindSliderBasePlutoRunnerPlutoRunner.create_bondconfirmCore.applicablegetindex$4775126e-4374-49be-b25f-4597401f3642precedence_heuristic cell_id$4775126e-4374-49be-b25f-4597401f3642downstream_cells_mapupstream_cells_mapepisode_steps2$db189316-e880-4cc8-9070-ccfe2b4fc545:-scatterplotattrviewLayoutaverage_step_reward$db189316-e880-4cc8-9070-ccfe2b4fc545end$d291541d-ddba-4b71-a4eb-37fef758b71bprecedence_heuristic cell_id$d291541d-ddba-4b71-a4eb-37fef758b71bdownstream_cells_mapupstream_cells_map@md_strgetindex$e2cd69c5-eda7-4897-9e64-0adf940d4d96precedence_heuristic cell_id$e2cd69c5-eda7-4897-9e64-0adf940d4d96downstream_cells_mappolicy_num$66d6a4b0-ddf8-4781-b3b4-20f02b25199a$78087a57-33a0-4581-81de-926476090931$58a0b622-1b51-4b42-a416-24109ae41a90upstream_cells_mapCoreBasePlutoRunner.create_bondPlutoRunnereachindexCore.applicable@bindBase.getmountaincar_policy_iteration$3c300a2b-4139-4df0-906b-4cae3592cc2bSelect$cbac1927-b087-4c4c-98ae-6aa5f0b824adprecedence_heuristic cell_id$cbac1927-b087-4c4c-98ae-6aa5f0b824addownstream_cells_mapepisode_rewards_q$09088eee-4cb3-40ac-b127-658ce1332fbaπ_mountain_car_q$b5409b69-a254-4355-b2b9-99394eceb2f7q̂_mountain_car_q$f9ee13e8-7406-4fba-9a30-1e2714bd7cfcepisode_steps_qupstream_cells_mapmountaincar_test$7c5fb569-81f0-4b70-ae95-1fce0c51b6f4/compute_q_learning_value$1410db13-4b73-4a87-af34-30a5232af4ba$ee59176e-24b6-4213-8f8e-759a70bc1d5eprecedence_heuristic cell_id$ee59176e-24b6-4213-8f8e-759a70bc1d5edownstream_cells_mapmountaincar_fcann_dp_results$b3658e4d-ee8e-45cd-906a-06dd512a6921$1e224a46-91ef-4a5f-ae35-ef4062147f2d$00399548-b21c-43b5-90e2-30656ab1541eupstream_cells_mapmountaincar_fcann_dp$0f958535-6b18-46de-a1ba-81f64c217ee0$54b92594-04b8-4a8a-82c2-773b4a24680dprecedence_heuristic cell_id$54b92594-04b8-4a8a-82c2-773b4a24680ddownstream_cells_mapupstream_cells_map@md_strgetindex$7d21c4cd-ab79-4f40-9b8b-f637b3efcab0precedence_heuristic cell_id$7d21c4cd-ab79-4f40-9b8b-f637b3efcab0downstream_cells_mapupstream_cells_mapshow_mountaincar_trajectory$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93$1054cfa3-9f58-4a93-a318-c2d21cf23220π_greedy_dp$d0cf3806-05c6-4a50-94c8-55c9042d51b7$c316c5d3-f484-4e8e-bd56-be1e236d96bcprecedence_heuristic cell_id$c316c5d3-f484-4e8e-bd56-be1e236d96bcdownstream_cells_mapupstream_cells_map@md_strgetindex$f2201afe-8952-4dde-9e39-02beeb920f6fprecedence_heuristic cell_id$f2201afe-8952-4dde-9e39-02beeb920f6fdownstream_cells_mapupstream_cells_mapπ_mountain_car$30ab21ba-3f5b-46a8-8b8c-753f2755d419show_mountaincar_trajectory$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93$1054cfa3-9f58-4a93-a318-c2d21cf23220$31fb07d2-1c34-44ec-b932-a598e78ec8dcprecedence_heuristic cell_id$31fb07d2-1c34-44ec-b932-a598e78ec8dcdownstream_cells_mapupstream_cells_map@md_strgetindex$5db29488-a150-42ee-aedb-380a3a4fd548precedence_heuristic cell_id$5db29488-a150-42ee-aedb-380a3a4fd548downstream_cells_mapplot_mountaincar_action_values$c799ffe4-f4af-487d-b557-8b50d13632b7$58a0b622-1b51-4b42-a416-24109ae41a90$4afbb723-340b-4d85-9115-027a0ff8dfad$fc3e0577-45aa-4bba-a275-fa7a352fc5cc$f9ee13e8-7406-4fba-9a30-1e2714bd7cfc$0e3e506d-1959-47fd-8da9-b3dfd294be67$c44dd6c6-8213-49fb-8d33-ba8f2c766b2e$b55d50a4-b039-4240-b434-42f7b724d24dupstream_cells_mapenumeratemountain_car_actions$d577b393-4b40-4c90-9993-4ffbcbd9df6dFloat32plotheatmapzerosLinRangeLayout$39c63495-36c3-4e62-b8fb-36865f2c6243precedence_heuristic cell_id$39c63495-36c3-4e62-b8fb-36865f2c6243downstream_cells_mapupstream_cells_map@md_strgetindex$d42bb733-07e2-4932-aab4-09229ff67492precedence_heuristic cell_id$d42bb733-07e2-4932-aab4-09229ff67492downstream_cells_mapupstream_cells_mapconstant_params$528533f7-68f1-4d19-9a37-6d4d0d7c38e2show_mountaincar_trajectory$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93$1054cfa3-9f58-4a93-a318-c2d21cf23220mountain_car_action_names$28e0d632-0df3-4a5b-85c4-571c845ff827$58a0b622-1b51-4b42-a416-24109ae41a90precedence_heuristic cell_id$58a0b622-1b51-4b42-a416-24109ae41a90downstream_cells_mapupstream_cells_mapmountaincar_velocities$7e8c89aa-8a5e-4ff4-afd2-df8f5c77b5b2plot_mountaincar_action_values$8a5d9e3d-e8ef-4cea-8cd8-6975f797d7bd$d8d5db17-d89c-47db-b258-6ad1635478b7$5db29488-a150-42ee-aedb-380a3a4fd548policy_num$e2cd69c5-eda7-4897-9e64-0adf940d4d96mountaincar_policy_iteration$3c300a2b-4139-4df0-906b-4cae3592cc2btabular_mountaincar_mdp$9d65285f-d49e-40ce-acea-1f565bcd4108mountaincar_positions$1d417a66-205f-4883-b49c-a6fc900af4ce$954848db-6dcc-4666-90f8-b5a900203242precedence_heuristic cell_id$954848db-6dcc-4666-90f8-b5a900203242downstream_cells_mapupstream_cells_mapshow_mountaincar_trajectory$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93$1054cfa3-9f58-4a93-a318-c2d21cf23220mc_test$0714a1cf-9288-4f1e-ba72-d82608704d69mc_test.π_ϵ_greedy$df07524f-b3fe-4a66-98ac-8f80df66bcffprecedence_heuristic cell_id$df07524f-b3fe-4a66-98ac-8f80df66bcffdownstream_cells_mapmountain_car_dist_step$f9abf433-8ce3-4520-9b47-f17f8f07b4cbupstream_cells_mapInt64mountain_car_step$b07460f1-0461-4f63-b145-c4e1818a497eFloat32Tuple$c85033e1-3ee6-42ad-9ef0-144ce6238ce4precedence_heuristic cell_id$c85033e1-3ee6-42ad-9ef0-144ce6238ce4downstream_cells_mapsmooth_error$5c920177-8e46-49c9-9b95-1a657fdcae4e$4ccb8a52-c6af-445d-a39e-d4d9b10c0d6a$09088eee-4cb3-40ac-b127-658ce1332fba$b76551e0-c027-4682-b5ae-bba7ea2b987aupstream_cells_maplength:-+mean$f6e08689-040f-4565-9dfb-e9a65d1c1f18precedence_heuristic cell_id$f6e08689-040f-4565-9dfb-e9a65d1c1f18downstream_cells_mapupstream_cells_map@md_strgetindex$e7372e2b-a2db-4a93-9efc-f75aa74c197bprecedence_heuristic cell_id$e7372e2b-a2db-4a93-9efc-f75aa74c197bdownstream_cells_mapAccessControlState$014339eb-5b23-4ac5-a551-8eeb2238366f$62839b2a-398a-4445-87d1-b15ff2acc1d1$b4af8d87-a6e5-4e09-92b4-b07757f58f7fupstream_cells_mapInt64Float32$dc2cffeb-9adf-4956-afa3-ac82af377c59precedence_heuristic cell_id$dc2cffeb-9adf-4956-afa3-ac82af377c59downstream_cells_mapupstream_cells_map@md_strgetindex$fc0b88f3-fbf9-450d-b770-b34357ffad49precedence_heuristic cell_id$fc0b88f3-fbf9-450d-b770-b34357ffad49downstream_cells_mapcompute_sarsa_value$991492f4-7dfc-43aa-ab6c-a6b1f3e38225$8b7e1031-9864-439c-86eb-11aa08f53b90$5fdbce61-ca25-45e0-b07d-94adf7138446$a9fdb1fd-3f62-4e1c-9157-c4eee6215261upstream_cells_mapRealIntegerVector$50f6ff51-d81b-4e97-9f8a-0daf03af7192precedence_heuristic cell_id$50f6ff51-d81b-4e97-9f8a-0daf03af7192downstream_cells_mapupstream_cells_map@md_strgetindex$5cbaeb8e-bc02-47c9-87b4-57df554cea9dprecedence_heuristic cell_id$5cbaeb8e-bc02-47c9-87b4-57df554cea9ddownstream_cells_mapupstream_cells_mapπ_mountain_car_fcann$b9125c5b-01d6-451e-84b5-a419e38425b5show_mountaincar_trajectory$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93$1054cfa3-9f58-4a93-a318-c2d21cf23220$b094bf9f-bb97-4f23-acdc-f39411a07fb9precedence_heuristic cell_id$b094bf9f-bb97-4f23-acdc-f39411a07fb9downstream_cells_mapπ_mountain_car2_fcann$b191d3f9-cf25-4fb4-8f5a-8da86e96e125upstream_cells_mapislessoneStateMDPTransitionDistributionStateMDPlengthsample_action=$1054cfa3-9f58-4a93-a318-c2d21cf23220precedence_heuristic cell_id$1054cfa3-9f58-4a93-a318-c2d21cf23220downstream_cells_mapshow_mountaincar_trajectory$d42bb733-07e2-4932-aab4-09229ff67492$864450b9-1319-4426-961f-ee6df93463d8$99e3ec39-24f0-43d6-b6fd-9910b738ce2c$a97e3b12-b7a5-4f88-bdb9-c3158203e0ff$cbf1e5ed-8308-486e-a9b7-6cf7fb441fe3$66d6a4b0-ddf8-4781-b3b4-20f02b25199a$78087a57-33a0-4581-81de-926476090931$f2201afe-8952-4dde-9e39-02beeb920f6f$7d21c4cd-ab79-4f40-9b8b-f637b3efcab0$1e224a46-91ef-4a5f-ae35-ef4062147f2d$5cbaeb8e-bc02-47c9-87b4-57df554cea9d$b5409b69-a254-4355-b2b9-99394eceb2f7$ab4cb3db-3a2d-4145-826b-b1001114eeff$b191d3f9-cf25-4fb4-8f5a-8da86e96e125$954848db-6dcc-4666-90f8-b5a900203242upstream_cells_map@md_strsummountain_car_actions$d577b393-4b40-4c90-9993-4ffbcbd9df6dIntegerRealMarkdown.parsescatterplotMatrixMarkdownLayoutrunepisodegetindex$8ed6f8fd-8574-4d5a-9964-ce8a32629c6fprecedence_heuristic cell_id$8ed6f8fd-8574-4d5a-9964-ce8a32629c6fdownstream_cells_mapcompute_expected_sarsa_value$7812e801-70fd-4331-ad0a-fad02c1a399f$565c53ee-7ad5-44e2-bce5-4ff1f5f162c0upstream_cells_mapRealdotIntegerVector$f9abf433-8ce3-4520-9b47-f17f8f07b4cbprecedence_heuristic cell_id$f9abf433-8ce3-4520-9b47-f17f8f07b4cbdownstream_cells_map$mountain_car_transition_distribution$5b2ffd90-ead0-42ce-999a-584ed8995910upstream_cells_mapmountain_car_dist_step$df07524f-b3fe-4a66-98ac-8f80df66bcffinitialize_car_state$cafb20b4-a2bd-46a9-9660-b0ace84d6e4cStateMDPTransitionDistribution$59ec5223-f23f-4f32-9e5f-8a08e450da85precedence_heuristic cell_id$59ec5223-f23f-4f32-9e5f-8a08e450da85downstream_cells_mapupstream_cells_map@md_strgetindex$0c7f5742-6c51-4c6a-b67f-217163935ba5precedence_heuristic cell_id$0c7f5742-6c51-4c6a-b67f-217163935ba5downstream_cells_mapupstream_cells_map@md_strgetindex$c697e0b6-d3e4-4f5f-96e9-b9486c9d7efcprecedence_heuristic cell_id$c697e0b6-d3e4-4f5f-96e9-b9486c9d7efcdownstream_cells_mapfill_action_values!$b9ebd6bb-90a1-4945-85ed-023206e2420aupstream_cells_mapAbstractVectormul!pop@inboundsadjointVectorRealdoteachindexMatrixconj$9fb5dace-a799-4424-bcb3-8542e508dd4bprecedence_heuristiccell_id$9fb5dace-a799-4424-bcb3-8542e508dd4bdownstream_cells_mapPlutoUI$528533f7-68f1-4d19-9a37-6d4d0d7c38e2$33ea5f09-3a1f-476d-875a-1f3635a40295HypertextLiteral$8a5d9e3d-e8ef-4cea-8cd8-6975f797d7bd$dd472c0f-7b43-4abe-ada9-9dc8004a18cbPlutoProfileBenchmarkToolsPlutoPlotlyLaTeXStringsupstream_cells_map$c1388562-0708-4a6a-acfe-927413dab5d2precedence_heuristic cell_id$c1388562-0708-4a6a-acfe-927413dab5d2downstream_cells_mapupstream_cells_map-scatterplotLayoutepisode_rewards$30ab21ba-3f5b-46a8-8b8c-753f2755d419$cbf1e5ed-8308-486e-a9b7-6cf7fb441fe3precedence_heuristic cell_id$cbf1e5ed-8308-486e-a9b7-6cf7fb441fe3downstream_cells_mapupstream_cells_mapπ_optimal_value_iteration$57659c52-de1b-46e6-a863-8eeec0cee601show_mountaincar_trajectory$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93$1054cfa3-9f58-4a93-a318-c2d21cf23220$6cea9e69-bf8c-4079-9884-663a728d7b08precedence_heuristic cell_id$6cea9e69-bf8c-4079-9884-663a728d7b08downstream_cells_mapupstream_cells_map@md_strgetindex$b0cc6ff8-7296-461c-9db7-e52fa518e2e2precedence_heuristic cell_id$b0cc6ff8-7296-461c-9db7-e52fa518e2e2downstream_cells_mapmountaincar_dist_test$d0cf3806-05c6-4a50-94c8-55c9042d51b7upstream_cells_maplengthInt64typemaxmountain_car_dist_mdp$5b2ffd90-ead0-42ce-999a-584ed8995910Float32/zerossetup_mountain_car_tiles$742100ba-c38e-4840-8988-40990039b527Integerrun_linear_semi_gradient_dp$56b0d69b-b7c3-4365-9b02-e0d5e8a85f94$30ab21ba-3f5b-46a8-8b8c-753f2755d419precedence_heuristic cell_id$30ab21ba-3f5b-46a8-8b8c-753f2755d419downstream_cells_mapepisode_stepsπ_mountain_car$f2201afe-8952-4dde-9e39-02beeb920f6fepisode_rewards$c1388562-0708-4a6a-acfe-927413dab5d2q̂_mountain_car$4afbb723-340b-4d85-9115-027a0ff8dfadupstream_cells_mapmountaincar_test$7c5fb569-81f0-4b70-ae95-1fce0c51b6f4/$1478745a-634d-4f31-8a70-b74f0e536201precedence_heuristic cell_id$1478745a-634d-4f31-8a70-b74f0e536201downstream_cells_mapupstream_cells_map@md_strgetindex$b07460f1-0461-4f63-b145-c4e1818a497eprecedence_heuristic cell_id$b07460f1-0461-4f63-b145-c4e1818a497edownstream_cells_mapmountain_car_step$df07524f-b3fe-4a66-98ac-8f80df66bcff$ac80958a-73ec-4342-b553-b33df6612a50$12f5065b-5bed-4d03-a0f0-72a942492394upstream_cells_mapInt64-mountain_car_actions$d577b393-4b40-4c90-9993-4ffbcbd9df6dFloat32Tuple+clamp*==cos$a9b74949-9392-4048-bcb6-5fd48c1d9b98precedence_heuristic cell_id$a9b74949-9392-4048-bcb6-5fd48c1d9b98downstream_cells_mapupstream_cells_map@md_strgetindex$565c53ee-7ad5-44e2-bce5-4ff1f5f162c0precedence_heuristic cell_id$565c53ee-7ad5-44e2-bce5-4ff1f5f162c0downstream_cells_map*differential_semi_gradient_expected_sarsa!upstream_cells_mapcompute_expected_sarsa_value$8ed6f8fd-8574-4d5a-9964-ce8a32629c6f!differential_semi_gradient_sarsa!$a9fdb1fd-3f62-4e1c-9157-c4eee6215261$12f5065b-5bed-4d03-a0f0-72a942492394precedence_heuristic cell_id$12f5065b-5bed-4d03-a0f0-72a942492394downstream_cells_mapmake_tabular_mountaincar$9d65285f-d49e-40ce-acea-1f565bcd4108upstream_cells_map :mountain_car_step$b07460f1-0461-4f63-b145-c4e1818a497esearchsortedfirstLinRangemountain_car_actions$d577b393-4b40-4c90-9993-4ffbcbd9df6dinitialize_car_state$cafb20b4-a2bd-46a9-9660-b0ace84d6e4czeroslengthInt64-enumerateFloat32TabularDeterministicTransition^+*==TabularMDP$4afbb723-340b-4d85-9115-027a0ff8dfadprecedence_heuristic cell_id$4afbb723-340b-4d85-9115-027a0ff8dfaddownstream_cells_mapupstream_cells_mapplot_mountaincar_action_values$8a5d9e3d-e8ef-4cea-8cd8-6975f797d7bd$d8d5db17-d89c-47db-b258-6ad1635478b7$5db29488-a150-42ee-aedb-380a3a4fd548q̂_mountain_car$30ab21ba-3f5b-46a8-8b8c-753f2755d419$00399548-b21c-43b5-90e2-30656ab1541eprecedence_heuristic cell_id$00399548-b21c-43b5-90e2-30656ab1541edownstream_cells_mapupstream_cells_map-scatterplotmountaincar_fcann_dp_results$ee59176e-24b6-4213-8f8e-759a70bc1d5eLayout$c75dc51c-cbff-48b1-b0fd-108828929b51precedence_heuristic cell_id$c75dc51c-cbff-48b1-b0fd-108828929b51downstream_cells_map&run_fcann_gradient_monte_carlo_controlupstream_cells_map AbstractVectorInfzerosislessrandIntegerStateMDPVector+foldxtmountain_car_mdp$1e9c537a-a731-4b81-8f6a-cb658b52c5be==runepisodeMap$b5409b69-a254-4355-b2b9-99394eceb2f7precedence_heuristic cell_id$b5409b69-a254-4355-b2b9-99394eceb2f7downstream_cells_mapupstream_cells_mapπ_mountain_car_q$cbac1927-b087-4c4c-98ae-6aa5f0b824adshow_mountaincar_trajectory$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93$1054cfa3-9f58-4a93-a318-c2d21cf23220$b9ebd6bb-90a1-4945-85ed-023206e2420aprecedence_heuristic cell_id$b9ebd6bb-90a1-4945-85ed-023206e2420adownstream_cells_map%linear_features_action_gradient_setup$2c620fe4-2f62-40f8-a666-8dced1e0b84a$065b2626-01f1-443f-8be4-3036003a2772$17d11fea-883b-4ddb-bec2-c4ad491b39ddupstream_cells_map calculate_action_value$f11787a1-57f8-4077-8d60-bc760ece7cc6AbstractVectoriszeroAbstractArrayfindmaxIntegerStateMDPnothingVectorRealcopy-Functionfill_action_values!$c697e0b6-d3e4-4f5f-96e9-b9486c9d7efcupdate_parameters!$5f8b0254-88f4-4d19-ade1-8e7c40941b43$96548352-cd4d-4448-8312-ed10057f4359UnionStateMRP$d0cf3806-05c6-4a50-94c8-55c9042d51b7precedence_heuristic cell_id$d0cf3806-05c6-4a50-94c8-55c9042d51b7downstream_cells_mapv̂_mountain_car$bd1f42e5-94cc-4aef-b82a-9bffd1c951d8π_greedy_dp$bd1f42e5-94cc-4aef-b82a-9bffd1c951d8$7d21c4cd-ab79-4f40-9b8b-f637b3efcab0episode_rewards_dp$5c920177-8e46-49c9-9b95-1a657fdcae4eepisode_steps_dpupstream_cells_map/mountaincar_dist_test$b0cc6ff8-7296-461c-9db7-e52fa518e2e2cell_execution_order $69fb26ed-763e-44ad-9b70-193e5a1a09b9$3f7484b3-272d-410d-92b1-ca13e5d7a8b7$9fb5dace-a799-4424-bcb3-8542e508dd4b$318b398a-d8f2-4f39-a45d-fd9023961bf8$35d59eae-77fd-11ef-2790-35dd5a834060$b0265b93-ae5f-48f2-a9fd-44fd6115164b$47710ddd-79d9-464d-b5dd-27180f2d6b31$4d392303-4681-4ea1-8dcc-e002a78ea0a1$a3cf270b-b309-44f0-9972-bd84228bcf17$2f685ee2-6ad8-4bb1-b326-e5de7c15eb18$14fe2253-cf2c-4159-a360-1e65f1c82b09$6351304f-50ac-4755-86e1-cd4680f2d803$e7bf61d7-c362-433d-9b83-6537d308c255$fc0b88f3-fbf9-450d-b770-b34357ffad49$991492f4-7dfc-43aa-ab6c-a6b1f3e38225$8b7e1031-9864-439c-86eb-11aa08f53b90$05e2fff5-4871-4468-a00e-9c1b7ba0ffc6$57a6510f-bd42-4d1d-a550-d1442f79569f$b0761704-5447-4e64-8270-708d9dccef60$54b92594-04b8-4a8a-82c2-773b4a24680d$278a26ac-c48f-4e18-93bb-706a4634c8c0$5f8b0254-88f4-4d19-ade1-8e7c40941b43$c5c839f7-1806-463d-b63a-bd7e1384f203$f11787a1-57f8-4077-8d60-bc760ece7cc6$1478745a-634d-4f31-8a70-b74f0e536201$c697e0b6-d3e4-4f5f-96e9-b9486c9d7efc$dc2cffeb-9adf-4956-afa3-ac82af377c59$56b0d69b-b7c3-4365-9b02-e0d5e8a85f94$8d096d0d-8fea-421a-aa33-82269d3fe7e2$f58cd0a2-8c82-46b2-bb8f-00f6aa1d867f$c678846c-aaff-4266-8b2c-07a3a92445ef$39b0f100-a7e7-4633-b296-ccc87a5a35ab$00e7783f-7f17-4944-a085-ea87509cd75a$a22e5d34-4b8d-479c-985c-d6abd41a6c80$b990ba67-42c8-4ab9-943d-085392204fdd$cafb20b4-a2bd-46a9-9660-b0ace84d6e4c$d577b393-4b40-4c90-9993-4ffbcbd9df6d$b07460f1-0461-4f63-b145-c4e1818a497e$df07524f-b3fe-4a66-98ac-8f80df66bcff$28e0d632-0df3-4a5b-85c4-571c845ff827$8befede5-378a-447a-96bd-edcd9d2ce98b$ac80958a-73ec-4342-b553-b33df6612a50$f9abf433-8ce3-4520-9b47-f17f8f07b4cb$1e9c537a-a731-4b81-8f6a-cb658b52c5be$5b2ffd90-ead0-42ce-999a-584ed8995910$f6e08689-040f-4565-9dfb-e9a65d1c1f18$528533f7-68f1-4d19-9a37-6d4d0d7c38e2$afee7bc9-aff0-4c71-a227-9845cb23d4e9$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93$ca970333-fa08-412c-b89d-491e70f0ac79$e86bc86f-9909-458d-b86d-0a4ac4b9d43d$b5273dfa-2262-487a-856b-441f007bd163$dae59fd9-0397-4307-afd8-bafb6f0bfa52$d291541d-ddba-4b71-a4eb-37fef758b71b$12f5065b-5bed-4d03-a0f0-72a942492394$39c63495-36c3-4e62-b8fb-36865f2c6243$33ea5f09-3a1f-476d-875a-1f3635a40295$1d417a66-205f-4883-b49c-a6fc900af4ce$7e8c89aa-8a5e-4ff4-afd2-df8f5c77b5b2$9d65285f-d49e-40ce-acea-1f565bcd4108$1b15efa9-c331-46bf-93db-f96dee026fe2$e338be2b-05f1-43f4-a194-45ffd710777e$e48af9f4-0b47-4a45-b0ad-8f53b094e712$72f575ee-d656-4af6-bf78-aab42bf1debd$57ea3538-33be-4673-b914-8191d35426a9$57659c52-de1b-46e6-a863-8eeec0cee601$be77b538-d106-4ca0-a974-289415588c47$3c300a2b-4139-4df0-906b-4cae3592cc2b$e2cd69c5-eda7-4897-9e64-0adf940d4d96$5bc2eda5-5f4c-4165-9afb-16920f30b0c5$8a5d9e3d-e8ef-4cea-8cd8-6975f797d7bd$d8d5db17-d89c-47db-b258-6ad1635478b7$1054cfa3-9f58-4a93-a318-c2d21cf23220$d42bb733-07e2-4932-aab4-09229ff67492$864450b9-1319-4426-961f-ee6df93463d8$99e3ec39-24f0-43d6-b6fd-9910b738ce2c$a97e3b12-b7a5-4f88-bdb9-c3158203e0ff$cbf1e5ed-8308-486e-a9b7-6cf7fb441fe3$66d6a4b0-ddf8-4781-b3b4-20f02b25199a$78087a57-33a0-4581-81de-926476090931$1a5acfb0-3b35-41b1-98f8-ffce941c587f$742100ba-c38e-4840-8988-40990039b527$af97f222-08d1-4200-a10b-8da178182175$224b4bec-9ec5-434d-a950-f5974cd786d0$b0cc6ff8-7296-461c-9db7-e52fa518e2e2$d0cf3806-05c6-4a50-94c8-55c9042d51b7$7d21c4cd-ab79-4f40-9b8b-f637b3efcab0$31fb07d2-1c34-44ec-b932-a598e78ec8dc$c12070a9-df63-4b25-99e6-26ff876af1b4$0f958535-6b18-46de-a1ba-81f64c217ee0$ee59176e-24b6-4213-8f8e-759a70bc1d5e$1e224a46-91ef-4a5f-ae35-ef4062147f2d$00399548-b21c-43b5-90e2-30656ab1541e$5db29488-a150-42ee-aedb-380a3a4fd548$c799ffe4-f4af-487d-b557-8b50d13632b7$58a0b622-1b51-4b42-a416-24109ae41a90$2f0d0a71-c65b-4aa0-a493-e7cdccd901eb$bd1f42e5-94cc-4aef-b82a-9bffd1c951d8$b3658e4d-ee8e-45cd-906a-06dd512a6921$7a47a518-dfc7-4310-a0b5-6f0d151c8263$c11aa069-93c2-435a-8f0e-353ced9633b6$5fdbce61-ca25-45e0-b07d-94adf7138446$b9125c5b-01d6-451e-84b5-a419e38425b5$fc3e0577-45aa-4bba-a275-fa7a352fc5cc$5cbaeb8e-bc02-47c9-87b4-57df554cea9d$59ec5223-f23f-4f32-9e5f-8a08e450da85$49249ac1-8964-4afc-89f2-3cd4d4322cc2$e1abf8c7-06b8-4cd5-b557-1d187004bdf1$98a5d65e-4253-4523-a74e-99d03be03b89$8ed6f8fd-8574-4d5a-9964-ce8a32629c6f$1410db13-4b73-4a87-af34-30a5232af4ba$7812e801-70fd-4331-ad0a-fad02c1a399f$5be866c3-0fb2-4d1f-9c31-b85aba332905$f7410fe7-e3d8-4047-8fa7-f076476e9d3a$d6ad1ff1-8fbf-4799-8b1b-ae1e3ce88c5b$b8c031ca-7995-4501-a1e3-df3f34e5f0da$69a06405-57cd-42e5-96b1-5cc77d74aa03$a9fdb1fd-3f62-4e1c-9157-c4eee6215261$565c53ee-7ad5-44e2-bce5-4ff1f5f162c0$c9759bd9-ec9b-47a1-9080-a7fc332be565$b5d2776f-4b93-4eaa-8873-c1c4e610e6b0$1a7ba296-52ca-4069-85fa-792d08d77b0e$eb28458f-b222-4f8e-9a5b-8203d3997f7b$e5ad765a-341f-4f11-9ae8-37d81cb349d2$bc1d7cce-c0f4-47a8-b674-8acb82491c7f$d3ba78fa-f032-4bb9-9359-ef3bcff2252d$ae5c5377-8b44-4c82-a63c-d2cb8a0d6667$b094bf9f-bb97-4f23-acdc-f39411a07fb9$425fe768-c7bb-4d3e-87e6-47fa052ba612$b191d3f9-cf25-4fb4-8f5a-8da86e96e125$c44dd6c6-8213-49fb-8d33-ba8f2c766b2e$9df1a18d-137c-4ea5-8d15-05697f7bbf07$0c7f5742-6c51-4c6a-b67f-217163935ba5$a6c5ec28-b2d5-4893-a118-95c1318d1f7f$44d43dbf-fe32-438e-b89d-c677bbc35893$f1edb500-fbd1-4c03-b033-53860dfa452d$2d7679ad-a9b3-448b-a4bc-7e5b9bce6adb$a9b74949-9392-4048-bcb6-5fd48c1d9b98$fbf1c64f-1979-4384-a8c6-dc7875174d1f$e7372e2b-a2db-4a93-9efc-f75aa74c197b$014339eb-5b23-4ac5-a551-8eeb2238366f$96548352-cd4d-4448-8312-ed10057f4359$b9ebd6bb-90a1-4945-85ed-023206e2420a$2c620fe4-2f62-40f8-a666-8dced1e0b84a$7c5fb569-81f0-4b70-ae95-1fce0c51b6f4$30ab21ba-3f5b-46a8-8b8c-753f2755d419$4afbb723-340b-4d85-9115-027a0ff8dfad$f2201afe-8952-4dde-9e39-02beeb920f6f$c1388562-0708-4a6a-acfe-927413dab5d2$1a82ae95-3c3e-4281-bc1d-9eb19bf50286$ddcb50be-5287-47f8-89f9-58c026a6b151$cbac1927-b087-4c4c-98ae-6aa5f0b824ad$b5409b69-a254-4355-b2b9-99394eceb2f7$f9ee13e8-7406-4fba-9a30-1e2714bd7cfc$065b2626-01f1-443f-8be4-3036003a2772$49e43d51-05d6-415b-a685-76e50904c5bc$db189316-e880-4cc8-9070-ccfe2b4fc545$7bc49107-9de5-4985-8750-979f36b3aa81$ab4cb3db-3a2d-4145-826b-b1001114eeff$0e3e506d-1959-47fd-8da9-b3dfd294be67$4775126e-4374-49be-b25f-4597401f3642$4271151d-d5a6-4a29-96c3-f2102b142b95$5534526a-d790-4379-98b0-8e4ee981fd9f$f68952bd-4c0b-4331-a09c-5b118c8fa5a9$62839b2a-398a-4445-87d1-b15ff2acc1d1$b4af8d87-a6e5-4e09-92b4-b07757f58f7f$546a775e-d3c9-4693-9f64-d4c47a84fb9f$41c626c7-908d-4ff6-9730-4ad0b8c3cc25$662759be-282c-460b-adc3-8595475b53c2$0e66a941-1ec1-4d3b-b064-e5f25cc93baf$c316c5d3-f484-4e8e-bd56-be1e236d96bc$bc220d14-97fd-486d-9880-6908135fe036$39eada35-8c3e-4ddc-8df9-7cf9f120928d$8752c98d-fac1-4b3b-b20b-70acc0677fcb$50f6ff51-d81b-4e97-9f8a-0daf03af7192$953907cd-9926-4478-99b3-da7068118c22$13e477f0-dc15-46cb-9691-c04a1b4c83c8$06834750-cc3a-468a-b0c2-81349c288a33$c85033e1-3ee6-42ad-9ef0-144ce6238ce4$5c920177-8e46-49c9-9b95-1a657fdcae4e$4ccb8a52-c6af-445d-a39e-d4d9b10c0d6a$09088eee-4cb3-40ac-b127-658ce1332fba$17d11fea-883b-4ddb-bec2-c4ad491b39dd$0714a1cf-9288-4f1e-ba72-d82608704d69$b76551e0-c027-4682-b5ae-bba7ea2b987a$954848db-6dcc-4666-90f8-b5a900203242$b55d50a4-b039-4240-b434-42f7b724d24d$c75dc51c-cbff-48b1-b0fd-108828929b51$6cea9e69-bf8c-4079-9884-663a728d7b08$f5e32900-6eb6-4b61-916d-893c0bcaf214$ed1bd92c-8cc7-457f-9692-a10a9487c953$dd472c0f-7b43-4abe-ada9-9dc8004a18cblast_hot_reload_time shortpath2Chapter_10_On_policy_Control_with_Approximation.jlprocess_statusreadypathm/home/runner/work/RL-Deploy-Test/RL-Deploy-Test/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jlpluto_versionv0.19.47last_save_timeA6*X֪cell_order $35d59eae-77fd-11ef-2790-35dd5a834060$b0265b93-ae5f-48f2-a9fd-44fd6115164b$47710ddd-79d9-464d-b5dd-27180f2d6b31$4d392303-4681-4ea1-8dcc-e002a78ea0a1$a3cf270b-b309-44f0-9972-bd84228bcf17$2f685ee2-6ad8-4bb1-b326-e5de7c15eb18$14fe2253-cf2c-4159-a360-1e65f1c82b09$6351304f-50ac-4755-86e1-cd4680f2d803$e7bf61d7-c362-433d-9b83-6537d308c255$fc0b88f3-fbf9-450d-b770-b34357ffad49$991492f4-7dfc-43aa-ab6c-a6b1f3e38225$8b7e1031-9864-439c-86eb-11aa08f53b90$05e2fff5-4871-4468-a00e-9c1b7ba0ffc6$57a6510f-bd42-4d1d-a550-d1442f79569f$b0761704-5447-4e64-8270-708d9dccef60$54b92594-04b8-4a8a-82c2-773b4a24680d$278a26ac-c48f-4e18-93bb-706a4634c8c0$5f8b0254-88f4-4d19-ade1-8e7c40941b43$c5c839f7-1806-463d-b63a-bd7e1384f203$f11787a1-57f8-4077-8d60-bc760ece7cc6$1478745a-634d-4f31-8a70-b74f0e536201$c697e0b6-d3e4-4f5f-96e9-b9486c9d7efc$dc2cffeb-9adf-4956-afa3-ac82af377c59$b9ebd6bb-90a1-4945-85ed-023206e2420a$2c620fe4-2f62-40f8-a666-8dced1e0b84a$56b0d69b-b7c3-4365-9b02-e0d5e8a85f94$8d096d0d-8fea-421a-aa33-82269d3fe7e2$f58cd0a2-8c82-46b2-bb8f-00f6aa1d867f$c678846c-aaff-4266-8b2c-07a3a92445ef$39b0f100-a7e7-4633-b296-ccc87a5a35ab$00e7783f-7f17-4944-a085-ea87509cd75a$a22e5d34-4b8d-479c-985c-d6abd41a6c80$b990ba67-42c8-4ab9-943d-085392204fdd$cafb20b4-a2bd-46a9-9660-b0ace84d6e4c$b07460f1-0461-4f63-b145-c4e1818a497e$df07524f-b3fe-4a66-98ac-8f80df66bcff$d577b393-4b40-4c90-9993-4ffbcbd9df6d$28e0d632-0df3-4a5b-85c4-571c845ff827$8befede5-378a-447a-96bd-edcd9d2ce98b$ac80958a-73ec-4342-b553-b33df6612a50$f9abf433-8ce3-4520-9b47-f17f8f07b4cb$1e9c537a-a731-4b81-8f6a-cb658b52c5be$5b2ffd90-ead0-42ce-999a-584ed8995910$f6e08689-040f-4565-9dfb-e9a65d1c1f18$528533f7-68f1-4d19-9a37-6d4d0d7c38e2$d42bb733-07e2-4932-aab4-09229ff67492$afee7bc9-aff0-4c71-a227-9845cb23d4e9$864450b9-1319-4426-961f-ee6df93463d8$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93$ca970333-fa08-412c-b89d-491e70f0ac79$e86bc86f-9909-458d-b86d-0a4ac4b9d43d$b5273dfa-2262-487a-856b-441f007bd163$dae59fd9-0397-4307-afd8-bafb6f0bfa52$d291541d-ddba-4b71-a4eb-37fef758b71b$12f5065b-5bed-4d03-a0f0-72a942492394$1d417a66-205f-4883-b49c-a6fc900af4ce$7e8c89aa-8a5e-4ff4-afd2-df8f5c77b5b2$9d65285f-d49e-40ce-acea-1f565bcd4108$1b15efa9-c331-46bf-93db-f96dee026fe2$e338be2b-05f1-43f4-a194-45ffd710777e$e48af9f4-0b47-4a45-b0ad-8f53b094e712$39c63495-36c3-4e62-b8fb-36865f2c6243$33ea5f09-3a1f-476d-875a-1f3635a40295$99e3ec39-24f0-43d6-b6fd-9910b738ce2c$72f575ee-d656-4af6-bf78-aab42bf1debd$57ea3538-33be-4673-b914-8191d35426a9$57659c52-de1b-46e6-a863-8eeec0cee601$a97e3b12-b7a5-4f88-bdb9-c3158203e0ff$cbf1e5ed-8308-486e-a9b7-6cf7fb441fe3$c799ffe4-f4af-487d-b557-8b50d13632b7$be77b538-d106-4ca0-a974-289415588c47$3c300a2b-4139-4df0-906b-4cae3592cc2b$e2cd69c5-eda7-4897-9e64-0adf940d4d96$66d6a4b0-ddf8-4781-b3b4-20f02b25199a$78087a57-33a0-4581-81de-926476090931$58a0b622-1b51-4b42-a416-24109ae41a90$5bc2eda5-5f4c-4165-9afb-16920f30b0c5$8a5d9e3d-e8ef-4cea-8cd8-6975f797d7bd$d8d5db17-d89c-47db-b258-6ad1635478b7$1054cfa3-9f58-4a93-a318-c2d21cf23220$1a5acfb0-3b35-41b1-98f8-ffce941c587f$742100ba-c38e-4840-8988-40990039b527$7c5fb569-81f0-4b70-ae95-1fce0c51b6f4$30ab21ba-3f5b-46a8-8b8c-753f2755d419$4afbb723-340b-4d85-9115-027a0ff8dfad$f2201afe-8952-4dde-9e39-02beeb920f6f$c1388562-0708-4a6a-acfe-927413dab5d2$ddcb50be-5287-47f8-89f9-58c026a6b151$af97f222-08d1-4200-a10b-8da178182175$224b4bec-9ec5-434d-a950-f5974cd786d0$b0cc6ff8-7296-461c-9db7-e52fa518e2e2$d0cf3806-05c6-4a50-94c8-55c9042d51b7$bd1f42e5-94cc-4aef-b82a-9bffd1c951d8$7d21c4cd-ab79-4f40-9b8b-f637b3efcab0$5c920177-8e46-49c9-9b95-1a657fdcae4e$31fb07d2-1c34-44ec-b932-a598e78ec8dc$c12070a9-df63-4b25-99e6-26ff876af1b4$0f958535-6b18-46de-a1ba-81f64c217ee0$ee59176e-24b6-4213-8f8e-759a70bc1d5e$b3658e4d-ee8e-45cd-906a-06dd512a6921$1e224a46-91ef-4a5f-ae35-ef4062147f2d$00399548-b21c-43b5-90e2-30656ab1541e$1a82ae95-3c3e-4281-bc1d-9eb19bf50286$5db29488-a150-42ee-aedb-380a3a4fd548$2f0d0a71-c65b-4aa0-a493-e7cdccd901eb$7a47a518-dfc7-4310-a0b5-6f0d151c8263$c11aa069-93c2-435a-8f0e-353ced9633b6$5fdbce61-ca25-45e0-b07d-94adf7138446$b9125c5b-01d6-451e-84b5-a419e38425b5$4ccb8a52-c6af-445d-a39e-d4d9b10c0d6a$fc3e0577-45aa-4bba-a275-fa7a352fc5cc$5cbaeb8e-bc02-47c9-87b4-57df554cea9d$59ec5223-f23f-4f32-9e5f-8a08e450da85$49249ac1-8964-4afc-89f2-3cd4d4322cc2$e1abf8c7-06b8-4cd5-b557-1d187004bdf1$98a5d65e-4253-4523-a74e-99d03be03b89$8ed6f8fd-8574-4d5a-9964-ce8a32629c6f$1410db13-4b73-4a87-af34-30a5232af4ba$7812e801-70fd-4331-ad0a-fad02c1a399f$5be866c3-0fb2-4d1f-9c31-b85aba332905$f7410fe7-e3d8-4047-8fa7-f076476e9d3a$cbac1927-b087-4c4c-98ae-6aa5f0b824ad$b5409b69-a254-4355-b2b9-99394eceb2f7$f9ee13e8-7406-4fba-9a30-1e2714bd7cfc$09088eee-4cb3-40ac-b127-658ce1332fba$d6ad1ff1-8fbf-4799-8b1b-ae1e3ce88c5b$b8c031ca-7995-4501-a1e3-df3f34e5f0da$69a06405-57cd-42e5-96b1-5cc77d74aa03$a9fdb1fd-3f62-4e1c-9157-c4eee6215261$565c53ee-7ad5-44e2-bce5-4ff1f5f162c0$c9759bd9-ec9b-47a1-9080-a7fc332be565$065b2626-01f1-443f-8be4-3036003a2772$b5d2776f-4b93-4eaa-8873-c1c4e610e6b0$1a7ba296-52ca-4069-85fa-792d08d77b0e$eb28458f-b222-4f8e-9a5b-8203d3997f7b$e5ad765a-341f-4f11-9ae8-37d81cb349d2$bc1d7cce-c0f4-47a8-b674-8acb82491c7f$49e43d51-05d6-415b-a685-76e50904c5bc$db189316-e880-4cc8-9070-ccfe2b4fc545$7bc49107-9de5-4985-8750-979f36b3aa81$ab4cb3db-3a2d-4145-826b-b1001114eeff$0e3e506d-1959-47fd-8da9-b3dfd294be67$4775126e-4374-49be-b25f-4597401f3642$b094bf9f-bb97-4f23-acdc-f39411a07fb9$d3ba78fa-f032-4bb9-9359-ef3bcff2252d$ae5c5377-8b44-4c82-a63c-d2cb8a0d6667$425fe768-c7bb-4d3e-87e6-47fa052ba612$b191d3f9-cf25-4fb4-8f5a-8da86e96e125$c44dd6c6-8213-49fb-8d33-ba8f2c766b2e$9df1a18d-137c-4ea5-8d15-05697f7bbf07$0c7f5742-6c51-4c6a-b67f-217163935ba5$a6c5ec28-b2d5-4893-a118-95c1318d1f7f$44d43dbf-fe32-438e-b89d-c677bbc35893$f1edb500-fbd1-4c03-b033-53860dfa452d$2d7679ad-a9b3-448b-a4bc-7e5b9bce6adb$a9b74949-9392-4048-bcb6-5fd48c1d9b98$fbf1c64f-1979-4384-a8c6-dc7875174d1f$e7372e2b-a2db-4a93-9efc-f75aa74c197b$014339eb-5b23-4ac5-a551-8eeb2238366f$62839b2a-398a-4445-87d1-b15ff2acc1d1$96548352-cd4d-4448-8312-ed10057f4359$4271151d-d5a6-4a29-96c3-f2102b142b95$5534526a-d790-4379-98b0-8e4ee981fd9f$f68952bd-4c0b-4331-a09c-5b118c8fa5a9$b4af8d87-a6e5-4e09-92b4-b07757f58f7f$41c626c7-908d-4ff6-9730-4ad0b8c3cc25$546a775e-d3c9-4693-9f64-d4c47a84fb9f$662759be-282c-460b-adc3-8595475b53c2$0e66a941-1ec1-4d3b-b064-e5f25cc93baf$c316c5d3-f484-4e8e-bd56-be1e236d96bc$bc220d14-97fd-486d-9880-6908135fe036$39eada35-8c3e-4ddc-8df9-7cf9f120928d$8752c98d-fac1-4b3b-b20b-70acc0677fcb$50f6ff51-d81b-4e97-9f8a-0daf03af7192$953907cd-9926-4478-99b3-da7068118c22$13e477f0-dc15-46cb-9691-c04a1b4c83c8$06834750-cc3a-468a-b0c2-81349c288a33$0714a1cf-9288-4f1e-ba72-d82608704d69$c85033e1-3ee6-42ad-9ef0-144ce6238ce4$b76551e0-c027-4682-b5ae-bba7ea2b987a$954848db-6dcc-4666-90f8-b5a900203242$b55d50a4-b039-4240-b434-42f7b724d24d$17d11fea-883b-4ddb-bec2-c4ad491b39dd$c75dc51c-cbff-48b1-b0fd-108828929b51$6cea9e69-bf8c-4079-9884-663a728d7b08$69fb26ed-763e-44ad-9b70-193e5a1a09b9$3f7484b3-272d-410d-92b1-ca13e5d7a8b7$318b398a-d8f2-4f39-a45d-fd9023961bf8$9fb5dace-a799-4424-bcb3-8542e508dd4b$f5e32900-6eb6-4b61-916d-893c0bcaf214$ed1bd92c-8cc7-457f-9692-a10a9487c953$dd472c0f-7b43-4abe-ada9-9dc8004a18cbpublished_objectsnbpkginstall_time_ns ^instantiatedòinstalled_versionsStatistics1.11.1Transducers0.4.84PlutoUI0.7.60RandomstdlibBenchmarkTools1.5.0LinearAlgebrastdlibPlutoDevMacros0.9.0PlutoProfile0.4.0HypertextLiteral0.9.5LaTeXStrings1.3.1PlutoPlotly0.5.0terminal_outputsStatistics@
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mResolving...[22m
[90m===[39m
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Project.toml`
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Manifest.toml`
[0m[1mPrecompiling...[22m
[90m===[39m
[32m[1m Activating[22m[39m project at `/tmp/jl_PWP9T2`Transducers@
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mResolving...[22m
[90m===[39m
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Project.toml`
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Manifest.toml`
[0m[1mPrecompiling...[22m
[90m===[39m
[32m[1m Activating[22m[39m project at `/tmp/jl_PWP9T2`PlutoUI@
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mResolving...[22m
[90m===[39m
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Project.toml`
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Manifest.toml`
[0m[1mPrecompiling...[22m
[90m===[39m
[32m[1m Activating[22m[39m project at `/tmp/jl_PWP9T2`Random@
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mResolving...[22m
[90m===[39m
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Project.toml`
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Manifest.toml`
[0m[1mPrecompiling...[22m
[90m===[39m
[32m[1m Activating[22m[39m project at `/tmp/jl_PWP9T2`BenchmarkTools@
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mResolving...[22m
[90m===[39m
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Project.toml`
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Manifest.toml`
[0m[1mPrecompiling...[22m
[90m===[39m
[32m[1m Activating[22m[39m project at `/tmp/jl_PWP9T2`LinearAlgebra@
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mResolving...[22m
[90m===[39m
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Project.toml`
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Manifest.toml`
[0m[1mPrecompiling...[22m
[90m===[39m
[32m[1m Activating[22m[39m project at `/tmp/jl_PWP9T2`PlutoProfile@
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mResolving...[22m
[90m===[39m
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Project.toml`
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Manifest.toml`
[0m[1mPrecompiling...[22m
[90m===[39m
[32m[1m Activating[22m[39m project at `/tmp/jl_PWP9T2`LaTeXStrings@
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mResolving...[22m
[90m===[39m
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Project.toml`
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Manifest.toml`
[0m[1mPrecompiling...[22m
[90m===[39m
[32m[1m Activating[22m[39m project at `/tmp/jl_PWP9T2`ApproximationUtils@
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mResolving...[22m
[90m===[39m
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Project.toml`
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Manifest.toml`
[0m[1mPrecompiling...[22m
[90m===[39m
[32m[1m Activating[22m[39m project at `/tmp/jl_PWP9T2`nbpkg_sync@
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mResolving...[22m
[90m===[39m
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Project.toml`
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Manifest.toml`
[0m[1mPrecompiling...[22m
[90m===[39m
[32m[1m Activating[22m[39m project at `/tmp/jl_PWP9T2`PlutoDevMacros@
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mResolving...[22m
[90m===[39m
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Project.toml`
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Manifest.toml`
[0m[1mPrecompiling...[22m
[90m===[39m
[32m[1m Activating[22m[39m project at `/tmp/jl_PWP9T2`HypertextLiteral@
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mResolving...[22m
[90m===[39m
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Project.toml`
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Manifest.toml`
[0m[1mPrecompiling...[22m
[90m===[39m
[32m[1m Activating[22m[39m project at `/tmp/jl_PWP9T2`PlutoPlotly@
[0m[1mInstantiating...[22m
[90m===[39m
[0m[1mResolving...[22m
[90m===[39m
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Project.toml`
[32m[1m No Changes[22m[39m to `/tmp/jl_PWP9T2/Manifest.toml`
[0m[1mPrecompiling...[22m
[90m===[39m
[32m[1m Activating[22m[39m project at `/tmp/jl_PWP9T2`enabled÷restart_recommended_msgrestart_required_msgbusy_packageswaiting_for_permission,waiting_for_permission_but_probably_disabled«cell_inputs $f68952bd-4c0b-4331-a09c-5b118c8fa5a9cell_id$f68952bd-4c0b-4331-a09c-5b118c8fa5a9code4function state_aggregation_action_gradient_setup(assign_state_group::Function)
function update_params!(parameters, s, i_a, g::T, α::T) where {T<:Real}
i_s = assign_state_group(s)
update_parameters!(parameters, i_s, i_a, g, α)
end
q̂(s, i_a, parameters) = get_action_value(assign_state_group(s), i_a, parameters)
q̂(action_values::Vector{T}, s, parameters) where T<:Real = update_action_values!(action_values, assign_state_group(s), parameters)
return (value_function = q̂, value_args = (), parameter_update = update_params!, update_args = ())
endmetadatashow_logsèdisabled®skip_as_script«code_folded$9df1a18d-137c-4ea5-8d15-05697f7bbf07cell_id$9df1a18d-137c-4ea5-8d15-05697f7bbf07codemd"""
> ### *Exercise 10.4*
> Give pseudocode for a differential version of semi-gradient Q-learning.
Given the pseudocode for semi-gradient Sarsa, make the following changes:
$\vdots$
Initialize S
Loop for each step of episode:
Choose A from S using ϵ-greedy policy
Take action A, observe R, S'
$\delta \leftarrow R - \bar R + \max_a \hat q(S^\prime, a, \mathbf{w}) - \hat q(S, A, \mathbf{w})$
$\vdots$
$S \leftarrow S^\prime$
See implementation above
"""metadatashow_logsèdisabled®skip_as_script«code_folded$c11aa069-93c2-435a-8f0e-353ced9633b6cell_id$c11aa069-93c2-435a-8f0e-353ced9633b6codefunction mountaincar_fcann_test(max_steps::Integer, α::Float32, ϵ::Float32; num_layers = 3, layer_size = 2, kwargs...)
feature_vector = zeros(Float32, 2)
function update_feature_vector!(v::Vector{Float32}, s::NTuple{2, Float32})
x1 = 3.45f0*(((s[1] - 1.2f0) / 1.7f0) - 0.5f0)
x2 = 1.725f0*s[2] / 0.07f0
v[1] = x1
v[2] = x2
end
layers = fill(layer_size, num_layers)
run_fcann_semi_gradient_sarsa(mountain_car_mdp, 1f0, 100, max_steps, feature_vector, update_feature_vector!, layers; α = α, ϵ = ϵ, kwargs...)
endmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$7812e801-70fd-4331-ad0a-fad02c1a399fcell_id$7812e801-70fd-4331-ad0a-fad02c1a399fcodeوsemi_gradient_expected_sarsa!(args...; kwargs...) = semi_gradient_sarsa!(args...; kwargs..., compute_value=compute_expected_sarsa_value)metadatashow_logsèdisabled®skip_as_script«code_folded$2f685ee2-6ad8-4bb1-b326-e5de7c15eb18cell_id$2f685ee2-6ad8-4bb1-b326-e5de7c15eb18codemd"""
#### Sampling Tabular Case
##### Problem conditions
- All states and actions can be enumerated: $\mathcal{S} = \{s_1, s_2, \cdots, s_n\}$ and $\mathcal{A} = \{a_1, a_2, \cdots, a_m\}$
- $p(s^\prime, r \vert s, a)$ is not available
- Observations from the environment can be collected: $S_t, A_t \implies R_{t+1}, S_{t+1}$
##### Solution Techniques
In the absence of $p$, we cannot use value iteration which is the only technique that circumvents the need for a policy. So we must use some form of policy iteration. It turns out that as long as we continue to update both the policy and the value function, neither need to converge to the correct values at any intermediate step. The idea behind *Generalized Policy Iteration* is to maintain a value estimate for a given policy and update the policy periodically prior to knowing whether or not the value function has converged. This interval could be as short as a single time step or as it takes to converge. For episodic tasks, using a single episode of samples to update the value function followed by the policy is a natural choice. For continuing tasks, one or more steps can be used in place of an episode. All of the techniques will have the following in common:
- A list of state-action value estimates: $q = [q_{1, 1}, q_{1, 2}, \cdots, q_{1, m}, \cdots q_{n, m}]$, one for each state-action pair initialized to some value
- An initial random policy $\pi$ (probability distribution over actions for each state, could be a matrix)
- State-action values will be updated by averaging together samples which are unbiased estimates of $q_\pi(s, a)$
The primary difference between the techniques will be which equation is used to calculate the sample values.
- Monte Carlo Control: uses samples of the expected value in the definition of $q_\pi(s, a) = \mathbb{E}_\pi [G_t \vert S_t = s, A_t = a]$
- repeat the following for a set number of episodes
- Collect a trajectory under the policy $\pi$: $S_0 \overset{\pi}{\rightarrow} A_0 \rightarrow R_1, S_1 \overset{\pi}{\rightarrow} A_1 \rightarrow R_2, S_2 \overset{\pi}{\rightarrow} A_2 \rightarrow \cdots\rightarrow R_T, S_T$
- Use the reward sequence to compute an unbiased estimate of $\mathbb{E}_\pi[G_t] = \mathbb{E}[q_\pi(S_t, A_t)]$
- Update the existing value for each state-action pair $S_t, A_t$ observed in the episode using the estimate (can use any number of averaging techniques)
- Update $\pi$ to select greedy actions with respect to the state-action value estimates and random actions occassionally (this is required to ensure visits to all state-action pairs and convergence of the expected values)
- Sarsa/Expected Sarsa: uses samples of the expected value in the Bellman equation for $q_\pi(s, a) = \mathbb{E} [R_{t+1} + \gamma\sum_{a^\prime} \pi(a^\prime \vert s^\prime) q_\pi(s^\prime, a^\prime) \mid S_t = s, A_t = a]$
- initialize a state $S_0$
- repeat the following for a set number of steps
- Use $\pi$ to select an action $A_t$
- Sample from the environment $R_{t+1}, S_{t+1}$
- Calculate an unbiased estimate for $q_\pi(S_t, A_t)$ using $R_{t+1} + \gamma\sum_{a^\prime} \pi(a^\prime \vert s^\prime) q(S_{t+1}, a^\prime)$ OR use $\pi$ to select the next action $A_{t+1}$ and use $R_{t+1} + \gamma q(S_{t+1}, A_{t+1})$
- Use some averaging method to update the estimated state-action value for $S_t, A_t$
- Update $\pi$ to select greedy actions with respect to the state-action value estimates and random actions occassionally (this is required to ensure visits to all state-action pairs and convergence of the expected values)
- Q-learning: uses samples of the expected value in the Bellman optimality equation for $q_*(s, a) = \mathbb{E} \left [ R_t + γ \max_{a^\prime} q_*(s^\prime, a^\prime) \mid S_t = s, A_t = a \right ]$
- initialize a state $S_0$
- repeat the following for a set number of steps
- Use $\pi$ to select an action $A_t$
- Sample from the environment $R_{t+1}, S_{t+1}$
- Calculate an unbiased estimate for $q_*(S_t, A_t)$ using $R_{t+1} + \gamma \max_{a^\prime} q(S_{t+1}, a^\prime)$
- Use some averaging method ot update the state-action value for $S_t, A_t$
- Update $\pi$ to select greedy actions with respect to the state-action value estimates and random actions occassionally (this is required to ensure visits to all state-action pairs and convergence of the expected values)
Note that technically, Monte Carlo Control and Sarsa find the optimal $\epsilon$-greedy policy and value function; however in practice $\epsilon$ can be reduced over time to arbitrarily approach the true optimal policy. Q-learning, on the other hand can work even if the policy is never updated since the value update does not depend at all on the policy.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$dae59fd9-0397-4307-afd8-bafb6f0bfa52cell_id$dae59fd9-0397-4307-afd8-bafb6f0bfa52codef(1:nsamples |> Map(i -> runepisode(mountain_car_mdp; max_steps = 100_000)[5]) |> foldxt(+)) / nsamplesmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$c678846c-aaff-4266-8b2c-07a3a92445efcell_id$c678846c-aaff-4266-8b2c-07a3a92445efcodefunction fcann_action_gradient_setup(mdp::StateMDP, layers::Vector{Int64}, feature_vector::Vector{Float32}, update_feature_vector!::Function; kwargs...)
s0 = mdp.initialize_state()
num_actions = length(mdp.actions)
input_layer_size = length(feature_vector)
update_feature_vector!(feature_vector, s0)
θ, β = FCANN.initializeparams_saxe(input_layer_size, layers, num_actions, 1; use_μP = true)
∇θ = deepcopy(θ)
∇β = deepcopy(β)
∇tanh_z = FCANN.form_tanh_grads(layers, 1)
function setup_training(batch_size::Integer)
activations = [zeros(Float32, batch_size, l) for l in [layers; num_actions]]
δs = deepcopy(activations)
onesvec = zeros(Float32, batch_size)
return (activations, δs, onesvec)
end
(activations, δs, onesvec) = setup_training(1)
input = zeros(Float32, 1, input_layer_size)
output = zeros(Float32, 1, num_actions)
scales = ones(Float32, length(layers)+1)
for i in 2:length(scales)
scales[i] /= size(θ[i], 2)
end
mT = deepcopy(θ)
vT = deepcopy(θ)
# θ_est = deepcopy(θ)
# θ_avg = deepcopy(θ)
mB = deepcopy(β)
vB = deepcopy(β)
# β_est = deepcopy(β)
# β_avg = deepcopy(β)
FCANN.zeroParams!(mT, vT)
FCANN.zeroParams!(vT, vB)
# function update_parameters!(parameters, s, i_a::Integer, g::Float32, α::Float32, gradients, state_representation::Vector{Float32}, input, output, ∇tanh_z, activations, δs, onesvec, scales)
# update_feature_vector!(state_representation, s)
# NonTabularRL.update_input!(input, state_representation, 1)
# FCANN.predict!(parameters[1], parameters[2], input, activations, 1)
# for i in 1:num_actions
# output[1, i] = activations[end][1, i]
# end
# output[1, i_a] = g
# NonTabularRL.update_nn_parameters!(parameters[1], parameters[2], layers, gradients[1], gradients[2], input, output, ∇tanh_z, activations, δs, onesvec, α, scales; kwargs...)
# end
function update_parameters!(parameters, s, i_a::Integer, g::Float32, α::Float32, gradients, state_representation::Vector{Float32}, input, output, ∇tanh_z, activations, δs, onesvec, scales, mT, mB, vT, vB)
update_feature_vector!(state_representation, s)
update_input!(input, state_representation, 1)
for i in 1:num_actions
output[1, i] = activations[end][1, i]
end
output[1, i_a] = g
update_nn_parameters!(parameters[1], parameters[2], layers, gradients[1], gradients[2], input, output, ∇tanh_z, activations, δs, onesvec, α, scales, mT, mB, vT, vB, 10000)
end
function q̂(s, i_a::Integer, parameters, state_representation, input, activations)
update_feature_vector!(state_representation, s)
update_input!(input, state_representation, 1)
FCANN.predict!(parameters[1], parameters[2], input, activations, 1)
return activations[end][1, i_a]
end
function q̂(action_values::Vector{Float32}, s, parameters, state_representation, input, activations)
update_feature_vector!(state_representation, s)
update_input!(input, state_representation, 1)
FCANN.predict!(parameters[1], parameters[2], input, activations, 1)
best_action = 1
best_value = typemin(Float32)
for i_a in eachindex(action_values)
q = activations[end][1, i_a]
newmax = q > best_value
best_action = !newmax*best_action + newmax*i_a
best_value = !newmax*best_value + newmax*q
action_values[i_a] = q
end
return (best_value, best_action)
end
# update_args = ((∇θ, ∇β), feature_vector, input, output, ∇tanh_z, activations, δs, onesvec, scales)
update_args = ((∇θ, ∇β), feature_vector, input, output, ∇tanh_z, activations, δs, onesvec, scales, mT, mB, vT, vB)
return (value_function = q̂, value_args = (feature_vector, input, activations), parameter_update = update_parameters!, update_args = update_args, parameters = (θ, β))
endmetadatashow_logsèdisabled®skip_as_script«code_folded$528533f7-68f1-4d19-9a37-6d4d0d7c38e2cell_id$528533f7-68f1-4d19-9a37-6d4d0d7c38e2code @bind constant_params PlutoUI.combine() do Child
md"""
Number of Steps: $(Child(:nsteps, Slider(1:1000, default = 200, show_value=true)))
Select Constant Action: $(Child(:action, Select([1 => "Decelerate", 2 => "Nothing", 3 => "Accelerate"])))
"""
end |> confirmmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$cafb20b4-a2bd-46a9-9660-b0ace84d6e4ccell_id$cafb20b4-a2bd-46a9-9660-b0ace84d6e4ccodebfunction initialize_car_state()
a = rand(Float32) * 0.2f0
x = a - 0.6f0
ẋ = 0f0
(x, ẋ)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$66d6a4b0-ddf8-4781-b3b4-20f02b25199acell_id$66d6a4b0-ddf8-4781-b3b4-20f02b25199acodeٍshow_mountaincar_trajectory(tabular_mountaincar_mdp, mountaincar_policy_iteration[1][policy_num], 500, "Policy Iteration Number $policy_num")metadatashow_logsèdisabled®skip_as_script«code_folded$b0265b93-ae5f-48f2-a9fd-44fd6115164bcell_id$b0265b93-ae5f-48f2-a9fd-44fd6115164bcodemd"""
## Solving the Control Problem
### Goal: Maximizing $G_t$
For a given MDP problem with a state space $\mathcal{S}$ and action space $\mathcal{A}$, there exists some optimal policy $\pi_*$ for which taking actions under that policy will result in a higher expected discounted reward sum than any other policy. In short:
$\mathbb{E}_{\pi_*}[G_t \vert S_t = s] \ge \mathbb{E}_{\pi}[G_t \vert S_t = s] \quad \forall s,\pi$ where $G_t \doteq \sum_{k=0}^\infty \gamma^k R_{t+k+1} \text{ or } \sum_{k = t+1} ^ T \gamma^{k-t-1}R_k$
"""metadatashow_logsèdisabled®skip_as_script«code_folded$57659c52-de1b-46e6-a863-8eeec0cee601cell_id$57659c52-de1b-46e6-a863-8eeec0cee601codeٍπ_optimal_value_iteration(s) = sample_action(view(mountaincar_value_iteration.optimal_policy, :, assign_state_index_tabular_mountaincar(s)))metadatashow_logsèdisabled®skip_as_script«code_folded$a9fdb1fd-3f62-4e1c-9157-c4eee6215261cell_id$a9fdb1fd-3f62-4e1c-9157-c4eee6215261codeCfunction differential_semi_gradient_sarsa!(parameters, mdp::StateMDP{T, S, A, P, F1, F2, F3}, max_episodes::Integer, max_steps::Integer, estimate_value::Function, estimate_args::Tuple, update_parameters!::Function, update_args::Tuple; α = one(T)/10, β = one(T)/100, ϵ = one(T) / 10, compute_value = compute_sarsa_value, kwargs...) where {T<:Real, S, A, P, F1, F2, F3}
s = mdp.initialize_state()
i_a = rand(eachindex(mdp.actions))
ep = 1
step = 1
R̄ = zero(T)
ō = zero(T)
epreward = zero(T)
episode_rewards = zeros(T, max_episodes)
episode_steps = zeros(Int64, max_episodes)
action_values = zeros(T, length(mdp.actions))
average_step_reward = Vector{T}()
policy = zeros(T, length(mdp.actions))
while (ep <= max_episodes) && (step <= max_steps)
(r, s′) = mdp.ptf(s, i_a)
estimate_value(action_values, s, parameters, estimate_args...)
q̂ = action_values[i_a]
U_t = r - R̄
epreward += r
if mdp.isterm(s′)
s′ = mdp.initialize_state()
episode_rewards[ep] = epreward
episode_steps[ep] = step
epreward = zero(T)
ep += 1
end
estimate_value(action_values, s′, parameters, estimate_args...)
policy .= action_values
make_ϵ_greedy_policy!(policy; ϵ = ϵ)
i_a′ = sample_action(policy)
q̂′ = compute_value(action_values, policy, i_a′)
U_t += q̂′
δ = U_t - q̂
ō += β * (one(T) - ō)
R̄ += (β/ō)*δ
# R̄ += β*δ
push!(average_step_reward, R̄)
update_parameters!(parameters, s, i_a, U_t, α, update_args...)
s = s′
i_a = i_a′
step += 1
end
return episode_rewards, episode_steps, average_step_reward
endmetadatashow_logsèdisabled®skip_as_script«code_folded$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93cell_id$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93codeNfunction show_mountaincar_trajectory(π::Function, max_steps::Integer, name)
states, actions, rewards, sterm, nsteps = runepisode(mountain_car_mdp; π = π, max_steps = max_steps)
positions = [s[1] for s in states]
velocities = [s[2] for s in states]
tr1 = scatter(x = positions, y = velocities, mode = "markers", showlegend = false)
tr2 = scatter(y = positions, showlegend = false)
tr3 = scatter(y = [mountain_car_actions[i] for i in actions], showlegend = false)
p1 = plot(tr1, Layout(xaxis_title = "position", yaxis_title = "velocity", xaxis_range = [-1.2, 0.5], yaxis_range = [-0.07, 0.07]))
p2 = plot(tr2, Layout(xaxis_title = "time", yaxis_title = "position"))
p3 = plot(tr3, Layout(xaxis_title = "time", yaxis_title = "action"))
mdname = Markdown.parse(name)
md"""
$mdname
Total Reward: $(sum(rewards))
$([p1 p2 p3])
"""
endmetadatashow_logsèdisabled®skip_as_script«code_folded$e86bc86f-9909-458d-b86d-0a4ac4b9d43dcell_id$e86bc86f-9909-458d-b86d-0a4ac4b9d43dcode@@bind nsamples NumberField(1:100_000, default = 1000) |> confirmmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$bc1d7cce-c0f4-47a8-b674-8acb82491c7fcell_id$bc1d7cce-c0f4-47a8-b674-8acb82491c7fcodeٔconst mountain_car_differential_mdp = StateMDP(mountain_car_actions, mountain_car_differential_transition, initialize_car_state, s -> s[1] == 0.5f0)metadatashow_logsèdisabled®skip_as_scriptëcode_folded$7e8c89aa-8a5e-4ff4-afd2-df8f5c77b5b2cell_id$7e8c89aa-8a5e-4ff4-afd2-df8f5c77b5b2codebconst mountaincar_velocities = LinRange(-0.07f0, 0.07f0, tabular_mountaincar_args.num_velocities) metadatashow_logsèdisabled®skip_as_script«code_folded$c12070a9-df63-4b25-99e6-26ff876af1b4cell_id$c12070a9-df63-4b25-99e6-26ff876af1b4codeټfunction update_mountaincar_feature_vector!(v::Vector{Float32}, s::NTuple{2, Float32})
x1 = 3.45f0*(((s[1] - 1.2f0) / 1.7f0) - 0.5f0)
x2 = 1.725f0*s[2] / 0.07f0
v[1] = x1
v[2] = x2
endmetadatashow_logsèdisabled®skip_as_script«code_folded$991492f4-7dfc-43aa-ab6c-a6b1f3e38225cell_id$991492f4-7dfc-43aa-ab6c-a6b1f3e38225codefunction semi_gradient_sarsa!(parameters::P, mdp::StateMDP, γ::T, max_episodes::Integer, max_steps::Integer, estimate_value::Function, estimate_args::Tuple, update_parameters!::Function, update_args::Tuple; α = one(T)/10, ϵ = one(T) / 10, compute_value = compute_sarsa_value, nn_momentum = false, α_decay = one(T), decay_step = typemax(Int64), kwargs...) where {P, T<:Real}
s = mdp.initialize_state()
i_a = rand(eachindex(mdp.actions))
ep = 1
step = 1
epreward = zero(T)
episode_rewards = Vector{T}()
episode_steps = Vector{Int64}()
action_values = zeros(T, length(mdp.actions))
policy = zeros(T, length(mdp.actions))
decay = one(T)
while (ep <= max_episodes) && (step <= max_steps)
(r, s′) = mdp.ptf(s, i_a)
epreward += r
if mdp.isterm(s′)
U_t = r
s′ = mdp.initialize_state()
i_a′ = rand(eachindex(mdp.actions))
push!(episode_rewards, epreward)
push!(episode_steps, step)
epreward = zero(T)
ep += 1
else
estimate_value(action_values, s′, parameters, estimate_args...)
policy .= action_values
make_ϵ_greedy_policy!(policy; ϵ = ϵ)
i_a′ = sample_action(policy)
q̂ = compute_value(action_values, policy, i_a′)
U_t = r + γ*q̂
end
learning_rate = nn_momentum ? T(1 - 0.999^step) : one(T)
if step > decay_step
decay *= α_decay
end
update_parameters!(parameters, s, i_a, U_t, α * learning_rate * decay, update_args...)
s = s′
i_a = i_a′
step += 1
end
return episode_rewards, episode_steps
endmetadatashow_logsèdisabled®skip_as_script«code_folded$28e0d632-0df3-4a5b-85c4-571c845ff827cell_id$28e0d632-0df3-4a5b-85c4-571c845ff827codeIconst mountain_car_action_names = ["Decelerate", "Nothing", "Accelerate"]metadatashow_logsèdisabled®skip_as_script«code_folded$b191d3f9-cf25-4fb4-8f5a-8da86e96e125cell_id$b191d3f9-cf25-4fb4-8f5a-8da86e96e125codedshow_mountaincar_trajectory(π_mountain_car2_fcann, 1_000, "Differential Q-learning Learned Policy")metadatashow_logsèdisabled®skip_as_script«code_folded$e338be2b-05f1-43f4-a194-45ffd710777ecell_id$e338be2b-05f1-43f4-a194-45ffd710777ecodeكconst accelerate_mountaincar_π = begin
out = zeros(Float32, 3, length(tabular_mountaincar_mdp.states))
out[3, :] .= 1f0
out
endmetadatashow_logsèdisabled®skip_as_script«code_folded$224b4bec-9ec5-434d-a950-f5974cd786d0cell_id$224b4bec-9ec5-434d-a950-f5974cd786d0codemd"""
##### Linear Tile Coding
Since we are only learning the value function, the same tiling setup will have fewer parameters than the action value techniques. Empirically, more tilings are necessary to learn a state value function that can approach the optimal policy.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$8752c98d-fac1-4b3b-b20b-70acc0677fcbcell_id$8752c98d-fac1-4b3b-b20b-70acc0677fcbcodemd"""
> ### *Exercise 10.9*
> In the differential semi-gradient n-step Sarsa algorithm, the step-size parameter on the average reward, $\beta$, needs to be quite small so that $\bar R$ becomes a good long-term estimate of the average reward. Unfortunately, $\bar R$ will then be biased by its initial value for many steps, which may make learning inefficient. Alternatively, one could use a sample average of the observed rewards for $\bar R$. That would initially adapt rapidly but in the long run would also adapt slowly. As the policy slowly changed, $\bar R$ would also change; the potential for such long-term nonstationarity makes sample-average methods ill-suited. In fact, the step-size parameter on the average reward is a perfect place to use the unbiased constant-step-size trick from Exercise 2.7. Describe the specific changes needed to the boxed algorithm for differential semi-gradient n-step Sarsa to use this trick.
At the start initialize $\bar o = 0$ and select $\lambda > 0$ small instead of $\beta$.
Within the loop under the $\tau \geq 0$ line, add two lines; one to update $\bar o$ and one to calculate the update rate for the average reward:
Line 1: $\bar o \leftarrow \bar o + \lambda (1 - \bar o)$
Line 2: $\beta = \lambda / \bar o$
As steps progress $\beta$ will approach $\lambda$ but early on will take on much larger values as $\bar o$ starts close to 0 and approaches 1.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$dd472c0f-7b43-4abe-ada9-9dc8004a18cbcell_id$dd472c0f-7b43-4abe-ada9-9dc8004a18cbcodebegin
function add_elements(a, b)
@htl("""
$a
$b
""")
end
add_elements(a::HTML, b::HTML) = add_elements(a.content, b.content)
add_elements(a::HTML, b::AbstractString) = add_elements(a.content, b)
add_elements(a::AbstractString, b::HTML) = add_elements(a, b.content)
endmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$ab4cb3db-3a2d-4145-826b-b1001114eeffcell_id$ab4cb3db-3a2d-4145-826b-b1001114eeffcode^show_mountaincar_trajectory(π_mountain_car2, 1_000, "Differential Q-learning Learned Policy")metadatashow_logsèdisabled®skip_as_script«code_folded$1410db13-4b73-4a87-af34-30a5232af4bacell_id$1410db13-4b73-4a87-af34-30a5232af4bacodezcompute_q_learning_value(action_values::Vector{T}, policy::Vector{T}, i_a::Integer) where T<:Real = maximum(action_values)metadatashow_logsèdisabled®skip_as_script«code_folded$eb28458f-b222-4f8e-9a5b-8203d3997f7bcell_id$eb28458f-b222-4f8e-9a5b-8203d3997f7bcodeZfunction mountain_car_differential_step(s::Tuple{Float32, Float32}, i_a::Int64)
a = mountain_car_actions[i_a]
ẋ′ = clamp(s[2] + 0.001f0*a - 0.0025f0*cos(3*s[1]), -0.07f0, 0.07f0)
x′ = clamp(s[1] + ẋ′, -1.2f0, 0.5f0)
x′ == -1.2f0 && return (0f0, (x′, 0f0))
s′ = (x′, ẋ′)
r = Float32(x′ == 0.5f0)
return (r, s′)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$a97e3b12-b7a5-4f88-bdb9-c3158203e0ffcell_id$a97e3b12-b7a5-4f88-bdb9-c3158203e0ffcodeٕshow_mountaincar_trajectory(tabular_mountaincar_mdp, mountaincar_value_iteration.optimal_policy, 1000, "Tabular Mountain Car Value Iteration Policy")metadatashow_logsèdisabled®skip_as_script«code_folded$4ccb8a52-c6af-445d-a39e-d4d9b10c0d6acell_id$4ccb8a52-c6af-445d-a39e-d4d9b10c0d6acodebplot(scatter(y = -smooth_error(mountain_car_fcann.reward_history, 1)), Layout(yaxis_type = "log"))metadatashow_logsèdisabled®skip_as_scriptëcode_folded$1e224a46-91ef-4a5f-ae35-ef4062147f2dcell_id$1e224a46-91ef-4a5f-ae35-ef4062147f2dcode_show_mountaincar_trajectory(mountaincar_fcann_dp_results.π_greedy, 1_000, "DP Learned Policy")metadatashow_logsèdisabled®skip_as_scriptëcode_folded$5b2ffd90-ead0-42ce-999a-584ed8995910cell_id$5b2ffd90-ead0-42ce-999a-584ed8995910codeٌconst mountain_car_dist_mdp = StateMDP(mountain_car_actions, mountain_car_transition_distribution, initialize_car_state, s -> s[1] == 0.5f0)metadatashow_logsèdisabled®skip_as_scriptëcode_folded$62839b2a-398a-4445-87d1-b15ff2acc1d1cell_id$62839b2a-398a-4445-87d1-b15ff2acc1d1codefunction create_access_control_task(num_servers::Integer, priority_payments::Vector{Float32})
actions = [Accept(), Reject()]
initialize_state() = AccessControlState(num_servers, rand(priority_payments))
transition = StateMDPTransitionSampler((s, i_a) -> access_control_step(s, actions[i_a], num_servers, priority_payments), initialize_state())
mdp = StateMDP(actions, transition, initialize_state, s -> false)
states = [AccessControlState(n, p) for n in 0:num_servers for p in priority_payments]
assign_group(s::AccessControlState) = s.num_free_servers + 1 + (num_servers+1)*Int64(log2(s.top_priority))
(mdp = mdp, gradient_setup = state_aggregation_action_gradient_setup(assign_group), num_groups = (num_servers+1) * length(priority_payments))
endmetadatashow_logsèdisabled®skip_as_script«code_folded$8d096d0d-8fea-421a-aa33-82269d3fe7e2cell_id$8d096d0d-8fea-421a-aa33-82269d3fe7e2codeGmd"""
### *Action-Value Implementation of Non-Linear Approximation*
"""metadatashow_logsèdisabled®skip_as_script«code_folded$39b0f100-a7e7-4633-b296-ccc87a5a35abcell_id$39b0f100-a7e7-4633-b296-ccc87a5a35abcode!function run_fcann_semi_gradient_sarsa(mdp::StateMDP, γ::Float32, max_episodes::Integer, max_steps::Integer, state_representation::Vector{Float32}, update_state_representation!::Function, layers::Vector{T}; λ = 0f0, c = Inf, dropout = 0f0, kwargs...) where T<:Integer
setup = fcann_action_gradient_setup(mdp, layers, state_representation, update_state_representation!; λ = λ, c = c, dropout = dropout)
num_actions = length(mdp.actions)
episode_rewards, episode_steps = semi_gradient_sarsa!(setup.parameters, mdp, γ, max_episodes, max_steps, setup.value_function, setup.value_args, setup.parameter_update, setup.update_args; nn_momentum = true, kwargs...)
q̂(s, i_a) = setup.value_function(s, i_a, setup.parameters, setup.value_args...)
action_values = zeros(Float32, num_actions)
q̂(s) = setup.value_function(action_values, s, setup.parameters, setup.value_args...)
π_greedy(s) = q̂(s)[2]
return (value_function = q̂, π_greedy = π_greedy, reward_history = episode_rewards, step_history = episode_steps, parameters = setup.parameters)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$1a82ae95-3c3e-4281-bc1d-9eb19bf50286cell_id$1a82ae95-3c3e-4281-bc1d-9eb19bf50286codefunction figure_10_2(;α_list = [0.1f0, 0.2f0, 0.5f0], num_episodes = 50, ϵ = 0.05f0)
traces = map(α_list) do α
scatter(y = 1:100 |> Map(_ -> mountaincar_test(num_episodes, α/8, ϵ; num_tiles = 12, num_tilings = 8).reward_history) |> foldxt((a, b) -> a .+ b) |> v -> -v ./ 100, name = "α = $α/8")
end
plot(traces, Layout(xaxis_title = "Episode", yaxis_title = "Steps per episode
averaged over 100 runs", yaxis_type = "log"))
endmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$99e3ec39-24f0-43d6-b6fd-9910b738ce2ccell_id$99e3ec39-24f0-43d6-b6fd-9910b738ce2ccodeِshow_mountaincar_trajectory(tabular_mountaincar_mdp, tabular_policies[tabular_mountaincar_args.policy], 1000, "Tabular Mountain Car Trajectory")metadatashow_logsèdisabled®skip_as_script«code_folded$f11787a1-57f8-4077-8d60-bc760ece7cc6cell_id$f11787a1-57f8-4077-8d60-bc760ece7cc6codebegin
calculate_action_value(state_representation::AbstractVector{T}, i_a::Integer, parameters::Vector{Vector{T}}) where T<:Real = dot(state_representation, parameters[i_a])
function calculate_action_value(state_representation::AbstractVector{T}, i_a::Integer, parameters::Matrix{T}) where T<:Real
q = zero(T)
@inbounds @simd for i in eachindex(state_representation)
q += state_representation[i]*parameters[i, i_a]
end
return q
end
function calculate_action_value(state_representation::SparseVector{T, Int64}, i_a::Integer, parameters::Matrix{T}) where T<:Real
q = zero(T)
@inbounds @simd for i in state_representation.nzind
q += state_representation[i]*parameters[i, i_a]
end
return q
end
end metadatashow_logsèdisabled®skip_as_script«code_folded$fc3e0577-45aa-4bba-a275-fa7a352fc5cccell_id$fc3e0577-45aa-4bba-a275-fa7a352fc5cccodeKplot_mountaincar_action_values(mountain_car_fcann.value_function, 200, 200)metadatashow_logsèdisabled®skip_as_scriptëcode_folded$98a5d65e-4253-4523-a74e-99d03be03b89cell_id$98a5d65e-4253-4523-a74e-99d03be03b89codeYmd"""
### *Semi-gradient Expected Sarsa Implementation*
Since we already update the policy and action values in the sarsa algorithm, the only difference in expected sarsa is to compute the action-value using the entire policy distribution instead of just the sampled action. Similarly for Q-learning we would only select the maximum value.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$4271151d-d5a6-4a29-96c3-f2102b142b95cell_id$4271151d-d5a6-4a29-96c3-f2102b142b95codebegin
get_action_value(i_s::Integer, i_a::Integer, parameters::Vector{Vector{T}}) where T<:Real = parameters[i_a][i_s]
get_action_value(i_s::Integer, i_a::Integer, parameters::Matrix{T}) where T<:Real = parameters[i_s, i_a]
endmetadatashow_logsèdisabled®skip_as_script«code_folded$56b0d69b-b7c3-4365-9b02-e0d5e8a85f94cell_id$56b0d69b-b7c3-4365-9b02-e0d5e8a85f94codefunction run_linear_semi_gradient_dp(mdp::StateMDP, γ::T, max_episodes::Integer, max_steps::Integer, state_representation::AbstractVector{T}, update_state_representation!::Function; setup_kwargs = NamedTuple(), kwargs...) where T<:Real
setup = linear_features_gradient_setup(mdp, state_representation, update_state_representation!; setup_kwargs...)
l = length(state_representation)
num_actions = length(mdp.actions)
parameters = zeros(T, l)
episode_rewards, episode_steps = semi_gradient_dp!(parameters, mdp, γ, max_episodes, max_steps, setup.value_function, setup.value_args, setup.parameter_update, setup.update_args; kwargs...)
v̂(s) = setup.value_function(s, parameters, setup.value_args...)
function π_greedy(s)
action_values = zeros(T, num_actions)
for i_a in eachindex(action_values)
(rewards, states, probabilities) = mdp.ptf.step(s, i_a)
q = zero(T)
for i in eachindex(probabilities)
v̂′ = !mdp.isterm(states[i])*v̂(states[i])
q += probabilities[i]*(rewards[i] + γ*v̂′)
end
action_values[i_a] = q
end
make_greedy_policy!(action_values)
i_a = sample_action(action_values)
end
return (value_function = v̂, π_greedy = π_greedy, reward_history = episode_rewards, step_history = episode_steps)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$3f7484b3-272d-410d-92b1-ca13e5d7a8b7cell_id$3f7484b3-272d-410d-92b1-ca13e5d7a8b7codepPlutoDevMacros.@frompackage @raw_str(joinpath(@__DIR__, "..", "ApproximationUtils.jl")) using ApproximationUtilsmetadatashow_logs¨disabled®skip_as_script«code_folded$1a7ba296-52ca-4069-85fa-792d08d77b0ecell_id$1a7ba296-52ca-4069-85fa-792d08d77b0ecodemd"""
### Example: Differential Sarsa and Q-learning with Mountain Car Task
In order to apply differential learning to the mountain car task, we need to change the rewards per step. Previously, the rewards were assigned in a manner appropriate for learning with a discount rate of 1. The reward of -1 per episode step ensures that policies that finish the task faster have a higher reward. In the average reward setting, every policy would have an average reward per step of -1 making the task ill posed. Instead, we can assign a reward of 1 for finishing to the right and 0 at all other steps. These rewards would produce an ill posed task for $\gamma = 1$ but are perfectly fine for the average reward setting. Now our learning procedure should find a policy that produces the highest average reward $\frac{1}{\text{num steps}}$ which is maximized when the number of steps to finish an episode is minimized.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$39eada35-8c3e-4ddc-8df9-7cf9f120928dcell_id$39eada35-8c3e-4ddc-8df9-7cf9f120928dcode;md"""
## 10.5 Differential Semi-gradient *n*-step Sarsa
"""metadatashow_logsèdisabled®skip_as_script«code_folded$b55d50a4-b039-4240-b434-42f7b724d24dcell_id$b55d50a4-b039-4240-b434-42f7b724d24dcode@plot_mountaincar_action_values(mc_test.value_function, 100, 100)metadatashow_logsèdisabled®skip_as_scriptëcode_folded$41c626c7-908d-4ff6-9730-4ad0b8c3cc25cell_id$41c626c7-908d-4ff6-9730-4ad0b8c3cc25codefigure_10_5()metadatashow_logsèdisabled®skip_as_script«code_folded$1e9c537a-a731-4b81-8f6a-cb658b52c5becell_id$1e9c537a-a731-4b81-8f6a-cb658b52c5becodezconst mountain_car_mdp = StateMDP(mountain_car_actions, mountain_car_transition, initialize_car_state, s -> s[1] == 0.5f0)metadatashow_logsèdisabled®skip_as_scriptëcode_folded$13e477f0-dc15-46cb-9691-c04a1b4c83c8cell_id$13e477f0-dc15-46cb-9691-c04a1b4c83c8codeGfunction gradient_monte_carlo_action_policy_estimation!(parameters, mdp::StateMDP, π::Function, γ::T, num_episodes::Integer, update_parameters!::Function, update_args::Tuple; α = one(T)/10, epkwargs...) where {T<:Real}
(states, actions, rewards, sterm, nsteps) = runepisode(mdp; π = π, epkwargs...)
gradient_monte_carlo_action_episode_update!(parameters, update_parameters!, states, actions, rewards, γ, α, update_args...)
step_history = [nsteps]
for ep in 2:num_episodes
(states, actions, rewards, sterm, nsteps) = runepisode!((states, actions, rewards), mdp; π = π, epkwargs...)
gradient_monte_carlo_episode_update!(parameters, update_parameters!, view(states, 1:nsteps), view(actions:1:nsteps), view(rewards, 1:nsteps), γ, α, update_args...)
push!(step_history, nsteps)
end
return step_history, reward_history
endmetadatashow_logsèdisabled®skip_as_script«code_folded$47710ddd-79d9-464d-b5dd-27180f2d6b31cell_id$47710ddd-79d9-464d-b5dd-27180f2d6b31code md"""
### Defining the Value Function
Since we are interested in maximizing the expected value of $G_t$, it is useful to define functions which calculate this expected value given a state or state action pair
Below is the definition of the two types of value functions as well as derived expressions that are used in solution or approximation techniques. The Bellman equation as well as other definitions are used to derive all of the useful expressions for the value function.
#### State Value Function
$\begin{flalign}
v_\pi(s) &\doteq \mathbb{E}_\pi [G_t \mid S_t = s] \tag{Used in Monte Carlo Estimation}\\
&= \sum_a \pi(a \vert s) \mathbb{E}_\pi [G_{t} \mid S_t = s, A_t = a] \tag{exp value def} \\
&= \sum_a \pi(a \vert s) q_\pi(s, a) \tag{by definition of q} \\
&= \sum_a \pi(a \vert s) \sum_{s^\prime, r} p(s^\prime, r \vert s, a) [r + \gamma v_\pi(s^\prime)] \tag{Used in Dynamic Programming when p is available} \\
&= \mathbb{E}_\pi [R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s] \tag{Used in TD(0) when p is not available}\\
\end{flalign}$
#### State-Action Value Function
$\begin{flalign}
q_\pi(s, a) &\doteq \mathbb{E}_\pi[G_t \mid S_t=s,A_t=a] \tag{Used in Monte Carlo Estimation} \\
& = \mathbb{E}_\pi \left [ R_{t+1} + \gamma G_{t+1} \mid S_t = s, A_t = a \right ] \tag{by (3.9)} \\
& = \sum_{s^\prime, r} p(s^\prime, r \vert s, a) \mathbb{E}_\pi \left [ r + \gamma G_{t+1} \mid S_{t+1} = s^\prime \right ] \tag{exp value def}\\
& = \sum_{s^\prime, r} p(s^\prime, r \vert s, a) [r + \gamma v_\pi(s^\prime)] \tag{by definition of v (4.6)} \\
& = \sum_{s^\prime, r} p(s^\prime, r \vert s, a) [r + \gamma\sum_{a^\prime} \pi(a^\prime \vert s^\prime) q_\pi(s^\prime, a^\prime)] \tag{Used in Dynamic Programming when p is available} \\
& = \mathbb{E} [R_{t+1} + \gamma\sum_{a^\prime} \pi(a^\prime \vert s^\prime) q_\pi(s^\prime, a^\prime) \mid S_t = s, A_t = a] \tag{Used in Expected Sarsa when p is not available} \\
\end{flalign}$
The optimal policy $\pi_*$ will have a value function $v_{\pi_*}(s)$ $q_{\pi_*}(s, a)$ whose values are greather than or equal to any other value function at every state or state action pair. In short
$v_{\pi_*}(s) \geq v_\pi(s) \forall s \in \mathcal{S} \quad \text{and} \quad q_{\pi_*}(s, a) \geq q_\pi(s, a) \forall s \in \mathcal{S}, \forall a \in \mathcal{A}$
"""metadatashow_logsèdisabled®skip_as_script«code_folded$14fe2253-cf2c-4159-a360-1e65f1c82b09cell_id$14fe2253-cf2c-4159-a360-1e65f1c82b09codemd"""
#### Distributional Non-Tabular Case
##### Problem conditions
- All actions can be enumerated: $\mathcal{A} = \{a_1, a_2, \cdots, a_m\}$ but the state space is either infinite or too large to practically count
- $p(s^\prime, r \vert s, a)$ is available
Previously we considered value estimates in the form of a list. Since that list is now uncountably large, a different approach, that of approximation, is needed to estimate the value function. The approximation function must rely on a countable, limited set of information such as a list of parameters $\mathbf{w}$ or a memory of past observations. Either way, that limited set of information must be used to generalize value estimates accross any state that is encountered. By construction, this function cannot guarantee that a change to one state value does not affect another, thus the previous goal of optimizing all of the state values is no longer possible. In order to even define success in this case, a new objective is needed. Consider the caes of a parameterized function $\hat v(s, \mathbf{w})$ whose goal is to estimate the true value function of a policy $v_\pi(s)$. One natural objective is to find the parameters that minimize the squared error this function has with the true value function under the distribution of states visited under that policy. This objective is called the *value error*:
$\overline{\text{VE}}(\mathbf{w}) \doteq \sum_{s \in S} \mu(s)[v_\pi(s) - \hat v(s, \mathbf{w})]^2$
In Chapter 9, we used stochastic gradient descent to derive an update rule for the parameters in the case of knowning the true value function:
$$\begin{flalign}
\mathbf{w}_{t+1} & \doteq \mathbf{w}_t - \frac{1}{2} \alpha \nabla [v_\pi(S_t) - \hat v(S_t, \mathbf{w}_t)]^2 \\
& = \mathbf{w}_t + \alpha[v_\pi(S_t) - \hat v(S_t, \mathbf{w}_t)]\nabla\hat v(S_t, \mathbf{w}_t)
\end{flalign}$$
Since we do not know the true value function, we can sample unbiased estimates of it using the methods already described above. Then the solution techniques would mirror those in the tabular case with the value updates simply replaced with parameter updates using the same sample estimate.
##### Solution Techniques
Since $p$ is available, we can use state value estimates to compute state-action value estimates. Consider the estimate Bellman optimality equation for state values:
$v_* = \max_{a \in \mathcal{A}(s)} \sum_{s^\prime, r} p(s^\prime, r \vert s, a) \left [ r + γ v_* (s^\prime) \right ] \: \forall s \in \mathcal{S}$
This target value can be used in the gradient update as follows:
$\mathbf{w}_{t+1} = \mathbf{w}_t + \alpha \left [ \max_{a \in \mathcal{A}(s)} \left [ \sum_{s^\prime, r} p(s^\prime, r \vert S_t, a) \left [ r + γ \hat v(s^\prime, \mathbf{w}_t) \right ] \right ]- \hat v(S_t, \mathbf{w}_t) \right ]\nabla\hat v(S_t, \mathbf{w}_t)$
while the optimal policy can be derived as:
$\pi(s) = \mathrm{argmax}_a\sum_{s^\prime, r} p(s^\prime, r \vert s, a)( r + \gamma \hat v(s^\prime, \mathbf{w}))$
The derivation of the parameter update rule assumed that the sample estimate for $v_\pi$ did not depend on the parameters. This assumption is violated here as it was in the semi-gradient TD methods from Chapter 9. Nevertheless, in the linear case, this technique can converge to some bounded region around the true minimum value error. Updating the parameters in this way is similar to value iteration which used the same target value and swept across the entire state space. Using this method here highlights the problem with approximation and its connection to the minimum value error objective. That objective is only defined in terms of the on policy distribution, so in order for this to converge, the states sampled must match the on-policy distribution which would be the greedy policy in this case. So while the update rule does not explicitely reference the policy (seemingly implying like in Q-learning that we could perform these updates with any policy), the samples do need to be drawn from the on policy distribution for this to work properly.
#### Sample Non-Tabular Case
##### Problem conditions
- All actions can be enumerated: $\mathcal{A} = \{a_1, a_2, \cdots, a_m\}$ but the state space is either infinite or too large to practically count
- $p(s^\prime, r \vert s, a)$ is not available
##### Solution Techniques
Finally, we arrive at the case considered at the beginning of Chapter 10 where we must rely on sampling from the environment in the non-tabular case. Since $p$ is not available, we must instead estimate $\hat q_\pi(s, a)$ for a given policy and proceed with generalized policy iteration as before either with episodic or per step updates to the parameters. The value error objective can easily be modified to consider all actions as well as states. Since the actions are enumerable in this case, there is no need to consider the on policy distribution as the error can be minimized across all actions:
$\overline{\text{VE}}(\mathbf{w}) \doteq \sum_a \sum_{s \in S} \mu(s)[q_\pi(s, a) - \hat q(s, a, \mathbf{w})]^2$
The parameter update will look identical to that for state values with the update target replaced by the true state-action value. The control algorithms will mirror the tabular case with the gradient update replacing the averaging update. The techniques are defined by which target value is used:
- Semi-gradient Sarsa: $q_\pi(s, a) = \mathbb{E} [R_{t+1} + \gamma\sum_{a^\prime} \pi(a^\prime \vert s^\prime) q_\pi(s^\prime, a^\prime) \mid S_t = s, A_t = a]$
- Gradient Monte Carlo Control: $q_\pi(s, a) = \mathbb{E}_\pi[G_t \vert S_t = s, A_t = a]$
- Semi-gradient Q-learning: $q_*(s, a) = \mathbb{E} \left [ R_t + γ \max_{a^\prime} q_*(s^\prime, a^\prime) \mid S_t = s, A_t = a \right ]$
Note that genearlized policy iteration only works if the policy improvement theorem applies. In the case of approximation, that is not the case since a policy change cannot be said to only apply to one state. While many of these techniques can work emphirically, there is no theoretical guarantee that iterating in this manner will produce the optimal policy, even if the approximation is linear. The only guarantee we can make in that case is that the value function will converge to one that minimizes the value error for the policy at the time.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$5c920177-8e46-49c9-9b95-1a657fdcae4ecell_id$5c920177-8e46-49c9-9b95-1a657fdcae4ecodeSplot(scatter(y = -smooth_error(episode_rewards_dp, 1)), Layout(yaxis_type = "log"))metadatashow_logsèdisabled®skip_as_scriptëcode_folded$b5d2776f-4b93-4eaa-8873-c1c4e610e6b0cell_id$b5d2776f-4b93-4eaa-8873-c1c4e610e6b0codefunction run_fcann_differential_semi_gradient_sarsa(mdp::StateMDP, max_episodes::Integer, max_steps::Integer, state_representation::Vector{Float32}, update_state_representation!::Function, layers::Vector{T}; kwargs...) where T<:Integer
setup = fcann_action_gradient_setup(mdp, layers, state_representation, update_state_representation!)
num_actions = length(mdp.actions)
episode_rewards, episode_steps, average_step_reward = differential_semi_gradient_sarsa!(setup.parameters, mdp, max_episodes, max_steps, setup.value_function, setup.value_args, setup.parameter_update, setup.update_args; kwargs...)
q̂(s, i_a) = setup.value_function(s, i_a, setup.parameters, setup.value_args...)
action_values = zeros(Float32, num_actions)
q̂(s) = setup.value_function(action_values, s, setup.parameters, setup.value_args...)
return (value_function = q̂, reward_history = episode_rewards, step_history = episode_steps, average_step_reward = average_step_reward, parameters = setup.parameters)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$3c300a2b-4139-4df0-906b-4cae3592cc2bcell_id$3c300a2b-4139-4df0-906b-4cae3592cc2bcodewconst mountaincar_policy_iteration = policy_iteration_v(tabular_mountaincar_mdp, 1f0; θ = 0.001f0, max_iterations = 2)metadatashow_logsèdisabled®skip_as_scriptëcode_folded$8a5d9e3d-e8ef-4cea-8cd8-6975f797d7bdcell_id$8a5d9e3d-e8ef-4cea-8cd8-6975f797d7bdcodefunction plot_mountaincar_action_values(tabular_mountaincar_mdp, value_function::Matrix{Float32}, π::Matrix{Float32}, mountaincar_positions, mountaincar_velocities)
n = 100
num_positions = length(mountaincar_positions)
num_velocities = length(mountaincar_velocities)
values = [zeros(Float32, num_positions, num_velocities) for _ in 1:size(π, 1)]
actions = zeros(Float32, num_positions, num_velocities)
for (i_x, x) in enumerate(mountaincar_positions)
for (i_v, v) in enumerate(mountaincar_velocities)
value_index = tabular_mountaincar_mdp.state_index[(x, v)]
(pmax, i_amax) = findmax(value_function[i, value_index] for i in 1:3)
actions[i_v, i_x] = i_amax
# pmax ≈ 1f0/3 ? actions[i_x, i_v] = 2 : actions[i_x, i_v] = i_amax
for i_a in 1:size(value_function, 1)
values[i_a][i_v, i_x] = value_function[i_a, value_index]
end
end
end
p1 = [plot(heatmap(x = mountaincar_positions, y = mountaincar_velocities, z = values[i]) , Layout(xaxis_title = "position", yaxis_title = "velocity", title = "Learned Value Function")) for i in eachindex(values)]
p2 = plot(heatmap(x = mountaincar_positions, y = mountaincar_velocities, z = actions, colorscale = "rb", showscale = false), Layout(xaxis_title = "position", yaxis_title = "velocity", title = "Greedy Policy (blue = accelerate left,
red = accelerate right, gray = no acceleration)"))
# [p1; p2]
# $(HTML(reduce(add_elements, p1)))
@htl("""
$(reduce(hcat, p1))
$p2
""")
endmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$fbf1c64f-1979-4384-a8c6-dc7875174d1fcell_id$fbf1c64f-1979-4384-a8c6-dc7875174d1fcodeلbegin
abstract type AccessControlAction end
struct Accept <: AccessControlAction end
struct Reject <: AccessControlAction end
endmetadatashow_logsèdisabled®skip_as_script«code_folded$0714a1cf-9288-4f1e-ba72-d82608704d69cell_id$0714a1cf-9288-4f1e-ba72-d82608704d69codeٳmc_test = run_linear_gradient_monte_carlo_control(mountain_car_mdp, 1f0, 5_000, setup_mountain_car_tiles((1/12f0, 1/12f0), 9).args...; α = 1f-7, ϵ = 0.25f0, max_steps = 100_000)metadatashow_logsèdisabled®skip_as_scriptëcode_folded$f7410fe7-e3d8-4047-8fa7-f076476e9d3acell_id$f7410fe7-e3d8-4047-8fa7-f076476e9d3acodeDmd"""
### Example: Semi-gradient Q-learning on Mountain Car Task
"""metadatashow_logsèdisabled®skip_as_script«code_folded$864450b9-1319-4426-961f-ee6df93463d8cell_id$864450b9-1319-4426-961f-ee6df93463d8codeeshow_mountaincar_trajectory(s -> rand(1:3), rand_nsteps, "Mountain Car Trajectory for Random Policy")metadatashow_logsèdisabled®skip_as_script«code_folded$662759be-282c-460b-adc3-8595475b53c2cell_id$662759be-282c-460b-adc3-8595475b53c2codeAmd"""
## 10.4 Deprecating the Discounted Setting
In a special case of indistinguishable states, we can only use the actions and reward sequences to analyze a continuing task. For a policy $\pi$, the average of the discounted returns with discount factor $\gamma$ is always $\frac{r(\pi)}{1-\gamma}$. Therefore the *ordering* of all policies is independent of the discount rate and would match the ordering we get in the average reward setting. This derivation however depends on states being indistinguishable allowing us to match up the weights on reward sequences from different policies.
We can use discounting in approximate solution methods regardless but then $\gamma$ changes from a problem parameter to a solution method parameter. Unfortunately, discounting algorithms with function approximation do not optimize discounted value over the on-policy distribution, and thus are not guaranteed to optimze average reward.
The root cause of the problem applying discounting with function approximation is that we have lost the policy improvement theorem which states that a policy $\pi^\prime$ is better than policy $\pi$ if $v_{\pi^\prime}(s) \geq v_\pi(s) \forall s\in \mathcal{S}$. Under this theorem we could take a deterministic policy, choose a specific state, and find a new action at that state with a higher expected reward than the current policy. If the policy is an approximation function that uses states represented by feature vectors, then adjusting the parameters can in general affect the actions at many states including ones that have not been encountered yet. In fact, with approximate solution methods we cannot guarantee policy improvement in any setting. Later we will introduce a theoretical guarantee called the "policy-gradient theorem" but for an alternative class of algorithms based on parametrized policies.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$f5e32900-6eb6-4b61-916d-893c0bcaf214cell_id$f5e32900-6eb6-4b61-916d-893c0bcaf214codeTableOfContents()metadatashow_logsèdisabled®skip_as_scriptëcode_folded$e1abf8c7-06b8-4cd5-b557-1d187004bdf1cell_id$e1abf8c7-06b8-4cd5-b557-1d187004bdf1code,md"""
> ### *Exercise 10.2*
> Give pseudocode for semi-gradient one-step *Expected* Sarsa for control.
Use the same pseudocode given for semi-gradient one-step Sarsa but with the following change to the weight update step in the non-terminal case:
$\mathbf{w} \leftarrow \mathbf{w} + \alpha[R + \gamma \sum_a \pi(a|S^\prime)\hat q(S^\prime, a, \mathbf{w}) - \hat q(S, A, \mathbf{w}) ] \nabla \hat q(S, A, \mathbf{w})$
where $\pi$ is the currently used policy which is $\epsilon$ greedy with respect to $\hat q$. See complete implementation below.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$b76551e0-c027-4682-b5ae-bba7ea2b987acell_id$b76551e0-c027-4682-b5ae-bba7ea2b987acodeHplot(smooth_error(mc_test.step_history, 10), Layout(yaxis_type = "log"))metadatashow_logsèdisabled®skip_as_scriptëcode_folded$d8d5db17-d89c-47db-b258-6ad1635478b7cell_id$d8d5db17-d89c-47db-b258-6ad1635478b7codefunction plot_mountaincar_action_values(tabular_mountaincar_mdp, value_function::Vector{Float32}, π::Matrix{Float32}, mountaincar_positions, mountaincar_velocities)
n = 100
num_positions = length(mountaincar_positions)
num_velocities = length(mountaincar_velocities)
values = zeros(Float32, num_positions, num_velocities)
actions = zeros(Float32, num_positions, num_velocities)
for (i_x, x) in enumerate(mountaincar_positions)
for (i_v, v) in enumerate(mountaincar_velocities)
value_index = tabular_mountaincar_mdp.state_index[(x, v)]
values[i_v, i_x] = value_function[value_index]
(pmax, i_amax) = findmax(π[i, value_index] for i in 1:3)
pmax ≈ 1f0/3 ? actions[i_v, i_x] = 2 : actions[i_v, i_x] = i_amax
end
end
p1 = plot(heatmap(x = mountaincar_positions, y = mountaincar_velocities, z = values), Layout(xaxis_title = "position", yaxis_title = "velocity", title = "Learned Value Function"))
p2 = plot(heatmap(x = mountaincar_positions, y = mountaincar_velocities, z = actions, colorscale = "rb", showscale = false), Layout(xaxis_title = "position", yaxis_title = "velocity", title = "Policy (blue = accelerate left,
red = accelerate right, gray = no acceleration)"))
[p1 p2]
endmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$78087a57-33a0-4581-81de-926476090931cell_id$78087a57-33a0-4581-81de-926476090931codeshow_mountaincar_trajectory(s -> sample_action(view(mountaincar_policy_iteration[1][policy_num], :, assign_state_index_tabular_mountaincar(s))), 500, "Policy Iteration Number $policy_num on True MDP")metadatashow_logsèdisabled®skip_as_script«code_folded$69fb26ed-763e-44ad-9b70-193e5a1a09b9cell_id$69fb26ed-763e-44ad-9b70-193e5a1a09b9codeDusing PlutoDevMacros, Random, Statistics, LinearAlgebra, Transducersmetadatashow_logsèdisabled®skip_as_script«code_folded$35d59eae-77fd-11ef-2790-35dd5a834060cell_id$35d59eae-77fd-11ef-2790-35dd5a834060code 0
policy_output[priority, num_free_servers] = actions[i_a]
end
end
end
policy_trace = heatmap(x = 1:10, y = 1:4, z = Float32.(policy_output), colorscale="Greys", showscale = false)
value_traces = [scatter(x = 0:10, y = value_function_outputs[i], name = "priority $(priorities[i])") for i in 1:4]
p1 = plot(policy_trace, Layout(yaxis_tickvals = 1:4, yaxis_ticktext = priorities, xaxis_ticktext = 1:10, xaxis_tickvals = 1:10, xaxis_title = "Number of free servers", yaxis_title = "Priority", title = "Policy (black=reject, white=accept)"))
p2 = plot(value_traces, Layout(xaxis_title = "Number of free servers", yaxis_title = "Differential value of best action", title = "Value Function"))
md"""
Figure 10.5
The policy and value function found by differential semi-gradient one-step Sarsa on the access-control queuing task after 2 million steps. The value learned for $\bar R$ was about $(access_control_output.steprewards[end-10000:end] |> mean |> Float64 |> x -> round(x, sigdigits = 3))
$([p1 p2])
"""
endmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$6351304f-50ac-4755-86e1-cd4680f2d803cell_id$6351304f-50ac-4755-86e1-cd4680f2d803codemd"""
## 10.1 Episodic Semi-gradient Control
It is straightforward to extend the semi-gradient prediction methods in Chapter 9 to action values. We simply consider examples of the form $S_t, A_t \rightarrow U_t$ where $U_t$ is any of the previously described update targets such as the Monte Carlo Return ($G_t$). The new gradient-decent update for action-value prediction is:
$\mathbf{w}_{t+1} \doteq \alpha \left [ U_t - \hat q(S_t, A_t, \mathbf{w}_t) \right ] \nabla \hat q(S_t, A_t, \mathbf{w}_t)$
For example, the one-step Sarsa update is:
$\mathbf{w}_{t+1} \doteq \alpha \left [ R_{t+1} + \gamma \hat q(S_{t+1}, A_{t+1}, \mathbf{w}_t) - \hat q(S_t, A_t, \mathbf{w}_t) \right ] \nabla \hat q(S_t, A_t, \mathbf{w}_t)$
If the action set is discrete, then at the next state $S_{t+1}$ we can compute $\hat q(S_{t+1}, a, \mathbf{w}_t)$ for every action and then find the greedy action $A^*_{t+1} = \text{argmax}_a\hat q(S_{t+1}, a, \mathbf{w}_t)$. Policy improvement is then done by changing the estimation policy to a soft approximation of the greedy policy such as the $\epsilon$-greedy policy. Actions are selected according to this same policy.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$05e2fff5-4871-4468-a00e-9c1b7ba0ffc6cell_id$05e2fff5-4871-4468-a00e-9c1b7ba0ffc6codemd"""
### Semi-gradient Dynamic Programming
Typically, to solve the control problem we require action-value estimates. Even in the non-tabular case; however, we may have access to the transition distribution of an MDP. A simple example of this is a deterministic problem in which there may be an uncountable number of states, but the transition dynamics are known exactly. In this case, one can reconstruct the action values from the state values as follows:
$\hat q(s, a) = \sum_{s^\prime, r}p(s^\prime, r \vert s, a)\left (r + \gamma \hat v(s^\prime) \right ) = \sum_{s^\prime}p(s^\prime \vert s, a) \left[ r(s^\prime, s, a) + \gamma \hat v(s^\prime) \right ]$
In the case of a deterministic problem there is only one transition state $s^\prime = t(s, a)$ where $t$ is the deterministic mapping function. Then the formula simplifies to $\hat q(s, a) = r(s, a) + \hat v(t(s, a))$. We can update the parameters $\mathbf{w}$ for some value function $\hat v(s, \mathbf{w})$ using the techniques in Chapter 9. Then, to derive the greedy policy, we can use
$\pi(s) = \text{argmax}_a \left [ r(s, a) + \gamma \sum_{s^\prime}p(s^\prime \vert s, a) \hat v(s^\prime) \right ]$
From tabular dynamic programming, we have the following update rule for the optimal state value function:
$v_*(s) = \max_a \sum_{s^\prime}p(s^\prime \vert s, a) \left[ r(s^\prime, s, a) + \gamma v_*(s^\prime) \right ]$
If the right side expression uses the approximate value function, then it is available to use as an update target instead of the usual Sarsa one.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$bc220d14-97fd-486d-9880-6908135fe036cell_id$bc220d14-97fd-486d-9880-6908135fe036codemd"""
The reason why the left policy can be better if $\gamma < 0.5$ in the original example is because it has a higher value in each state considered. Consider $\gamma = 0.25$. The left policy has the following approximate discounted value estimates for top, left, right:
1.0667, 0.2667, 2.2667.
Meanwhile the right policy has the corresponding values of:
0.533, 0.133, 2.133.
Each value is smaller for the right policy. However when we calculate the average value calculated over the long term distribution of states, the left policy averages the first two values while the right policy averages the first and third values because in the long run we expect the left policy to only exist in the top and left state while the right policy will exist in the top and right state. Because the right state has such a high value for both policies but only the right policy includes it in the average it makes its entire objective estimate higher. However, we can see that in the event of being in the right state, it is still a higher value expectation following the left policy in this case. The decision to average based on the final distribution results in a policy ordering that doesn't match with what we know to be the optimal policy from the policy improvement theorem over finite states.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$e48af9f4-0b47-4a45-b0ad-8f53b094e712cell_id$e48af9f4-0b47-4a45-b0ad-8f53b094e712codePconst tabular_policies = [tabular_mountaincar_πrand, accelerate_mountaincar_π]metadatashow_logsèdisabled®skip_as_script«code_folded$5534526a-d790-4379-98b0-8e4ee981fd9fcell_id$5534526a-d790-4379-98b0-8e4ee981fd9fcode=begin
function update_action_values!(action_values::Vector{T}, i_s::Integer, parameters::Vector{Vector{T}}) where T<:Real
maxvalue = typemin(T)
maxindex = 1
@inbounds @simd for i_a in eachindex(action_values)
q = parameters[i_a][i_s]
action_values[i_a] = q
newmax = q > maxvalue
maxvalue = newmax*q + !newmax*maxvalue
maxindex = newmax*i_a + !newmax*maxindex
end
return maxvalue, maxindex
end
function update_action_values!(action_values::Vector{T}, i_s::Integer, parameters::Matrix{T}) where T<:Real
maxvalue = typemin(T)
maxindex = 1
@inbounds @simd for i_a in eachindex(action_values)
q = parameters[i_s, i_a]
action_values[i_a] = q
newmax = q > maxvalue
maxvalue = newmax*q + !newmax*maxvalue
maxindex = newmax*i_a + !newmax*maxindex
end
return maxvalue, maxindex
end
endmetadatashow_logsèdisabled®skip_as_script«code_folded$ca970333-fa08-412c-b89d-491e70f0ac79cell_id$ca970333-fa08-412c-b89d-491e70f0ac79code9md"""
#### Typical Episode Length under Random Policy
"""metadatashow_logsèdisabled®skip_as_script«code_folded$db189316-e880-4cc8-9070-ccfe2b4fc545cell_id$db189316-e880-4cc8-9070-ccfe2b4fc545codeٸ(q̂_mountain_car2, episode_rewards2, episode_steps2, average_step_reward) = mountaincar_differential_test(100, 0.0008f0/8, 0.00001f0, 0.33f0; compute_value = compute_q_learning_value)metadatashow_logsèdisabled®skip_as_scriptëcode_folded$ddcb50be-5287-47f8-89f9-58c026a6b151cell_id$ddcb50be-5287-47f8-89f9-58c026a6b151codefigure_10_2()metadatashow_logsèdisabled®skip_as_scriptëcode_folded$e7bf61d7-c362-433d-9b83-6537d308c255cell_id$e7bf61d7-c362-433d-9b83-6537d308c255codemd"""
### *Semi-gradient Sarsa Implementation*
Below is an implementation of Semi-gradient Sarsa in a similar style to the algorithms in Chapter 9. This function updates the provided parameters using the `update_parameters!` function and also requires an `estimate_value` function. The linear function approximation version of this simplifies the required arguments greatly, needing only a state representation update function.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$69a06405-57cd-42e5-96b1-5cc77d74aa03cell_id$69a06405-57cd-42e5-96b1-5cc77d74aa03code?md"""
### *Differential Semi-gradient Sarsa Implementation*
"""metadatashow_logsèdisabled®skip_as_script«code_folded$c44dd6c6-8213-49fb-8d33-ba8f2c766b2ecell_id$c44dd6c6-8213-49fb-8d33-ba8f2c766b2ecodeAplot_mountaincar_action_values(q̂_mountain_car2_fcann, 500, 500)metadatashow_logsèdisabled®skip_as_script«code_folded$ac80958a-73ec-4342-b553-b33df6612a50cell_id$ac80958a-73ec-4342-b553-b33df6612a50codedconst mountain_car_transition = StateMDPTransitionSampler(mountain_car_step, initialize_car_state())metadatashow_logsèdisabled®skip_as_script«code_folded$09088eee-4cb3-40ac-b127-658ce1332fbacell_id$09088eee-4cb3-40ac-b127-658ce1332fbacodeٍplot(scatter(y = -smooth_error(episode_rewards_q, 10)), Layout(yaxis_type = "log", xaxis_title = "Episode", yaxis_title = "Number of Steps"))metadatashow_logsèdisabled®skip_as_script«code_folded$33ea5f09-3a1f-476d-875a-1f3635a40295cell_id$33ea5f09-3a1f-476d-875a-1f3635a40295codeY@bind tabular_mountaincar_args PlutoUI.combine() do Child
md"""
Policy View Selection: $(Child(:policy, Select([1 => "Random", 2 => "Accelerate Only"])))
Number of Positions: $(Child(:num_positions, NumberField(1:10000, default = 500)))
Number of Velocities: $(Child(:num_velocities, NumberField(1:10000, default = 500)))
"""
end |> confirmmetadatashow_logsèdisabled®skip_as_script«code_folded$318b398a-d8f2-4f39-a45d-fd9023961bf8cell_id$318b398a-d8f2-4f39-a45d-fd9023961bf8codefinclude(joinpath(@__DIR__, "..", "Chapter-9", "Chapter_9_On-policy_Prediction_with_Approximation.jl"))metadatashow_logsèdisabled®skip_as_scriptëcode_folded$be77b538-d106-4ca0-a974-289415588c47cell_id$be77b538-d106-4ca0-a974-289415588c47codeJmd"""
##### Solving Mountain Car Tabular Problem with Policy Iteration
"""metadatashow_logsèdisabled®skip_as_script«code_folded$5bc2eda5-5f4c-4165-9afb-16920f30b0c5cell_id$5bc2eda5-5f4c-4165-9afb-16920f30b0c5codeوπ_optimal_policy_iteration(s) = sample_action(view(mountaincar_policy_iteration[1][end], :, assign_state_index_tabular_mountaincar(s)))metadatashow_logsèdisabled®skip_as_script«code_folded$f9ee13e8-7406-4fba-9a30-1e2714bd7cfccell_id$f9ee13e8-7406-4fba-9a30-1e2714bd7cfccode 0.5$ the right policy is better.
Similarly, we can consider the value of the left state for both left and right policies:
$v_{\pi_{left}} (left) = 0 + \gamma + 0 + \gamma^3 + \cdots = \gamma + \gamma^3 + \cdots$
$v_{\pi_{right}} (left) = 0 + 0 + 2\gamma^2 + 0 + 2\gamma^4 + \cdots = 2 \times (\gamma^2 + \gamma^4 + \cdots) = 2\gamma(v_{\pi_{left}}(left))$
Again, for $\gamma > 0.5$ the right policy is better.
And finally for the right state:
$v_{\pi_{left}} (right) = 2 + \gamma + 0 + \gamma^3 + 0 + \gamma^5 \cdots = 2+\gamma(1 + \gamma^2 + \gamma^4 + \cdots)=2 + \frac{\gamma}{1-\gamma^2}$
$= \frac{2(1-\gamma^2) + \gamma}{1-\gamma^2} = \frac{2 - 2\gamma^2 + \gamma}{1-\gamma^2}$
$v_{\pi_{right}} (right) = 2 + 0 + 2\gamma^2 + 0 + 2\gamma^4 + \cdots = 2 \times (1+\gamma^2 + \gamma^4 + \cdots) = \frac{2}{1-\gamma^2}$
$\frac{v_{\pi_{left}} (right)}{v_{\pi_{right}} (right)}=\frac{2 - 2\gamma^2 + \gamma}{2}$
For $\gamma=0$ this quantity is 1 meaning the policies are equal and for $\gamma=1$ this quantity is 0.5 meaning that the right policy is better. At $\gamma=0.5$ the quantity is $\frac{2 - 0.5 + 0.5}{2}=\frac{2}{2}=1$ meaning they are equal. The maximum value occurs at $2\gamma = 0.5 \implies \gamma = 0.25$ with a ratio value of $\frac{2 - 0.125 + 0.25}{2}=\frac{2.125}{2}=1.0625$ meaning that the left policy is slightly better or equal from $0 \leq \gamma \leq 0.5$ and worse at $\gamma > 0.5$ which matches the earlier states.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$f2201afe-8952-4dde-9e39-02beeb920f6fcell_id$f2201afe-8952-4dde-9e39-02beeb920f6fcodeKshow_mountaincar_trajectory(π_mountain_car, 1_000, "Sarsa Learned Policy")metadatashow_logsèdisabled®skip_as_scriptëcode_folded$31fb07d2-1c34-44ec-b932-a598e78ec8dccell_id$31fb07d2-1c34-44ec-b932-a598e78ec8dccodemd"""
#### Non-linear Neural Network
Compared to tile coding, the feature vector for non-linear learning will simply be two values: one for the position and another for the velocity. Both values will be scaled so the mean value is 0 and the variance is approximately 1.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$5db29488-a150-42ee-aedb-380a3a4fd548cell_id$5db29488-a150-42ee-aedb-380a3a4fd548code!function plot_mountaincar_action_values(q̂_mountain_car, n1, n2)
xvals = LinRange(-1.2f0, 0.5f0, n1)
vvals = LinRange(-0.07f0, 0.07f0, n2)
values = zeros(Float32, n1, n2)
actions = zeros(Float32, n1, n2)
for (i, x) in enumerate(xvals)
for (j, v) in enumerate(vvals)
(q̂, i_a) = q̂_mountain_car((x, v))
values[j, i] = q̂
actions[j, i] = mountain_car_actions[i_a]
end
end
p1 = plot(heatmap(x = xvals, y = vvals, z = values), Layout(xaxis_title = "position", yaxis_title = "velocity", title = "Learned Value Function"))
p2 = plot(heatmap(x = xvals, y = vvals, z = actions, colorscale = "rb", showscale = false), Layout(xaxis_title = "position", yaxis_title = "velocity", title = "Policy (blue = accelerate left,
red = accelerate right, gray = no acceleration)"))
[p1 p2]
endmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$39c63495-36c3-4e62-b8fb-36865f2c6243cell_id$39c63495-36c3-4e62-b8fb-36865f2c6243code constant_params.action, constant_params.nsteps, "Mountain Car Trajectory for $(mountain_car_action_names[constant_params.action]) only Policy")metadatashow_logsèdisabled®skip_as_script«code_folded$58a0b622-1b51-4b42-a416-24109ae41a90cell_id$58a0b622-1b51-4b42-a416-24109ae41a90codeplot_mountaincar_action_values(tabular_mountaincar_mdp, mountaincar_policy_iteration[2][policy_num], mountaincar_policy_iteration[1][policy_num], mountaincar_positions, mountaincar_velocities)metadatashow_logsèdisabled®skip_as_scriptëcode_folded$954848db-6dcc-4666-90f8-b5a900203242cell_id$954848db-6dcc-4666-90f8-b5a900203242code]show_mountaincar_trajectory(s -> mc_test.π_ϵ_greedy(s, 0.25f0), 10000, "MC Learned Policy")metadatashow_logsèdisabled®skip_as_script«code_folded$df07524f-b3fe-4a66-98ac-8f80df66bcffcell_id$df07524f-b3fe-4a66-98ac-8f80df66bcffcodeوfunction mountain_car_dist_step(s::Tuple{Float32, Float32}, i_a::Int64)
(r, s′) = mountain_car_step(s, i_a)
([r], [s′], [1f0])
endmetadatashow_logsèdisabled®skip_as_script«code_folded$c85033e1-3ee6-42ad-9ef0-144ce6238ce4cell_id$c85033e1-3ee6-42ad-9ef0-144ce6238ce4codesfunction smooth_error(error_history, n)
l = length(error_history)
[mean(error_history[i-n:i]) for i in n+1:l]
endmetadatashow_logsèdisabled®skip_as_script«code_folded$f6e08689-040f-4565-9dfb-e9a65d1c1f18cell_id$f6e08689-040f-4565-9dfb-e9a65d1c1f18code'md"""
#### Visualizing Trajectories
"""metadatashow_logsèdisabled®skip_as_script«code_folded$e7372e2b-a2db-4a93-9efc-f75aa74c197bcell_id$e7372e2b-a2db-4a93-9efc-f75aa74c197bcodeMstruct AccessControlState
num_free_servers::Int64
top_priority::Float32
endmetadatashow_logsèdisabled®skip_as_script«code_folded$dc2cffeb-9adf-4956-afa3-ac82af377c59cell_id$dc2cffeb-9adf-4956-afa3-ac82af377c59codemd"""
Finally we can create the action-value function and parameter update for the generic linear case. If a vector of action values is provided as the first argument to the value function, that vector will be updated with all of the action values for a given state.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$fc0b88f3-fbf9-450d-b770-b34357ffad49cell_id$fc0b88f3-fbf9-450d-b770-b34357ffad49codeqcompute_sarsa_value(action_values::Vector{T}, policy::Vector{T}, i_a::Integer) where T<:Real = action_values[i_a]metadatashow_logsèdisabled®skip_as_script«code_folded$50f6ff51-d81b-4e97-9f8a-0daf03af7192cell_id$50f6ff51-d81b-4e97-9f8a-0daf03af7192code)md"""
## Monte Carlo Gradient Control
"""metadatashow_logsèdisabled®skip_as_script«code_folded$5cbaeb8e-bc02-47c9-87b4-57df554cea9dcell_id$5cbaeb8e-bc02-47c9-87b4-57df554cea9dcodeQshow_mountaincar_trajectory(π_mountain_car_fcann, 1_000, "Sarsa Learned Policy")metadatashow_logsèdisabled®skip_as_scriptëcode_folded$b094bf9f-bb97-4f23-acdc-f39411a07fb9cell_id$b094bf9f-bb97-4f23-acdc-f39411a07fb9codeهπ_mountain_car2_fcann(s) = rand() < 0.05 ? rand(1:3) : argmax(i_a -> q̂_mountain_car2_fcann(s, i_a), eachindex(mountain_car_actions))metadatashow_logsèdisabled®skip_as_script«code_folded$1d417a66-205f-4883-b49c-a6fc900af4cecell_id$1d417a66-205f-4883-b49c-a6fc900af4cecode^const mountaincar_positions = LinRange(-1.2f0, 0.5f0, tabular_mountaincar_args.num_positions) metadatashow_logsèdisabled®skip_as_script«code_folded$17d11fea-883b-4ddb-bec2-c4ad491b39ddcell_id$17d11fea-883b-4ddb-bec2-c4ad491b39ddcodefunction run_linear_gradient_monte_carlo_control(mdp::StateMDP, γ::T, num_episodes::Integer, state_representation::AbstractVector{T}, update_state_representation!::Function; kwargs...) where T<:Real
setup = linear_features_action_gradient_setup(mdp, state_representation, update_state_representation!)
parameters = [zeros(T, length(state_representation)) for _ in 1:length(mdp.actions)]
step_history, reward_history = gradient_monte_carlo_control!(parameters, mdp, γ, num_episodes, setup...; kwargs...)
q̂(s) = setup.value_function(action_values, s, parameters, setup.value_args...)
action_values = zeros(T, length(mdp.actions))
π_greedy(s) = setup.value_function(action_values, s, parameters, setup.value_args...)[2]
π_ϵ_greedy(s, ϵ) = rand() < ϵ ? rand(eachindex(mdp.actions)) : setup.value_function(action_values, s, parameters, setup.value_args...)[2]
return (value_function = q̂, π_greedy = π_greedy, π_ϵ_greedy = π_ϵ_greedy, step_history = step_history, reward_history = reward_history)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$b4af8d87-a6e5-4e09-92b4-b07757f58f7fcell_id$b4af8d87-a6e5-4e09-92b4-b07757f58f7fcodefunction run_access_control_differential_sarsa(max_steps::Int64; num_servers = 10, priority_payments = [1f0, 2f0, 4f0, 8f0], kwargs...)
(mdp, gradient_setup, num_groups) = create_access_control_task(num_servers, priority_payments)
parameters = [zeros(Float32, num_groups) for _ in eachindex(mdp.actions)]
state_representation = zeros(Float32, num_groups)
(_, _, steprewards) = differential_semi_gradient_sarsa!(parameters, mdp, 1, max_steps, gradient_setup...; kwargs...)
action_values = zeros(Float32, length(mdp.actions))
v̂(num_free_servers::Int64, priority::Real) = gradient_setup.value_function(action_values, AccessControlState(num_free_servers, Float32(priority)), parameters)
(value_function = v̂, mdp = mdp, parameters = parameters, steprewards = steprewards)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$d6ad1ff1-8fbf-4799-8b1b-ae1e3ce88c5bcell_id$d6ad1ff1-8fbf-4799-8b1b-ae1e3ce88c5bcodecmd"""
> ### *Exercise 10.3*
> Why do the results shown in Figure 10.4 have higher standard errors at large *n* than at small *n*?
At large n more of the reward function comes from the actual trajectory observed during a run. Since random actions are taken initially there will be more spread in the observed reward estimates than with 1 step bootstrapping which is more dependent on the initialization of the action value function. If ties are broken randomly then you would select random actions for the first n-steps of bootstrapping thus experience more spread in the early trajectories for higher n.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$c799ffe4-f4af-487d-b557-8b50d13632b7cell_id$c799ffe4-f4af-487d-b557-8b50d13632b7codeٻplot_mountaincar_action_values(tabular_mountaincar_mdp, mountaincar_value_iteration.final_value, mountaincar_value_iteration.optimal_policy, mountaincar_positions, mountaincar_velocities)metadatashow_logsèdisabled®skip_as_script«code_folded$0e66a941-1ec1-4d3b-b064-e5f25cc93bafcell_id$0e66a941-1ec1-4d3b-b064-e5f25cc93bafcode%md"""
### Connection to Chapter 3
"""metadatashow_logsèdisabled®skip_as_script«code_folded$c5c839f7-1806-463d-b63a-bd7e1384f203cell_id$c5c839f7-1806-463d-b63a-bd7e1384f203codemd"""
The action value calculation also depends on how parameters are represented. Either a dot product is used by extracting the appropriate parameter vector, or the parameter matrix needs to be iterated over the appropriate column
"""metadatashow_logsèdisabled®skip_as_script«code_folded$1b15efa9-c331-46bf-93db-f96dee026fe2cell_id$1b15efa9-c331-46bf-93db-f96dee026fe2codeNconst tabular_mountaincar_πrand = make_random_policy(tabular_mountaincar_mdp)metadatashow_logsèdisabled®skip_as_script«code_folded$72f575ee-d656-4af6-bf78-aab42bf1debdcell_id$72f575ee-d656-4af6-bf78-aab42bf1debdcodeImd"""
##### Solving Mountain Car Tabular Problem with Value Iteration
"""metadatashow_logsèdisabled®skip_as_script«code_folded$2c620fe4-2f62-40f8-a666-8dced1e0b84acell_id$2c620fe4-2f62-40f8-a666-8dced1e0b84acodeQfunction run_linear_semi_gradient_sarsa(mdp::StateMDP, γ::T, max_episodes::Integer, max_steps::Integer, state_representation::AbstractVector{T}, update_state_representation!::Function; setup_kwargs = NamedTuple(), kwargs...) where T<:Real
setup = linear_features_action_gradient_setup(mdp, state_representation, update_state_representation!; setup_kwargs...)
l = length(state_representation)
num_actions = length(mdp.actions)
# parameters = zeros(T, l, num_actions)
parameters = [zeros(T, l) for _ in 1:num_actions]
episode_rewards, episode_steps = semi_gradient_sarsa!(parameters, mdp, γ, max_episodes, max_steps, setup.value_function, setup.value_args, setup.parameter_update, setup.update_args; kwargs...)
q̂(s, i_a) = setup.value_function(s, i_a, parameters, setup.value_args...)
function q̂(s)
action_values = zeros(T, num_actions)
setup.value_function(action_values, s, parameters, setup.value_args...)
findmax(action_values)
end
π_greedy(s) = q̂(s)[2]
return (value_function = q̂, π_greedy = π_greedy, reward_history = episode_rewards, step_history = episode_steps)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$bd1f42e5-94cc-4aef-b82a-9bffd1c951d8cell_id$bd1f42e5-94cc-4aef-b82a-9bffd1c951d8code7plot_mountaincar_values(v̂_mountain_car, π_greedy_dp)metadatashow_logsèdisabled®skip_as_scriptëcode_folded$b8c031ca-7995-4501-a1e3-df3f34e5f0dacell_id$b8c031ca-7995-4501-a1e3-df3f34e5f0dacodemd"""
## 10.3 Average Reward: A New Problem Setting for Continuing Tasks
We now introduce an alternative to the discount setting for solving continuing problems (MDPs without a terminal state). The average-reward setting is more commonly used in the classical theory of dynamic programming. The purpose of introducing the average-reward is because discounting is problematic with function approximation in a way it was not problematic for tabular problems.
In the average-reward setting the quality of a policy $\pi$ is defined as the average rate of reward, or simply *average reward*, while following that policy, which we denote as $r(\pi)$:
$\begin{flalign}
r(\pi) &\doteq \lim_{h \rightarrow \infty} \frac{1}{h}\sum_{t=1}^h \mathbb{E}[R_t \mid S_0,A_{0:t-1} \sim \pi] \tag{10.6}\\
&= \lim_{h \rightarrow \infty} \mathbb{E} [R_t \mid S_0,A_{0:t-1} \sim \pi] \tag{10.7}\\
&= \sum_s \mu_\pi(s)\sum_a\pi(a \vert s) \sum_{s^\prime,r} p(s^\prime,r \vert s, a)r
\end{flalign}$
where the expectations are conditioned on the initial state, $S_0$, and on the subsequent actions, $A_0, A_1, \dots,A_{t-1}$, being taken according to $\pi$. The second and third equations hold if the state-state distribution $\mu_\pi(s) \doteq \lim_{t\rightarrow \infty} \Pr \{S_t = s \mid A_{0:t-1} \sim \pi \}$, exists and is independent of $S_0$, in other words, if the MDP is *ergodic*. In an ergodic MDP, the starting state and any early decision made by the agent can only have a temporary effect; in the long run the expectation of being in a state depends on the policy and the MDP transition probabilities. Ergodicity is sufficient but not necessary to guarantee the existence of the limit in (10.6).
In this setting, we consider all policies that obtain the maximum value of $r(\pi)$ or the *reward rate* to be optimal. Note that the steady state distribution $\mu_\pi$ is the special distribution under which, if you select actions according to $\pi$, you remain in the same distribution. That is, for which
$\sum_s \mu_\pi(s) \sum_a \pi(a\vert s)p(s^\prime \vert s, a) = \mu_\pi(s^\prime) \tag{10.8}$
In the average-reward setting, returns are defined in terms of differences between rewards and the average reward:
$G_t \doteq R_{t+1} - r(\pi) + R_{t+2} - r(\pi) + R_{t+3} - r(\pi) + \cdots \tag{10.9}$
This is known as the *differential* return, and th corresponding value functions are known as *differential* value functions. Differential value functions are defined in terms of the new return just as conventional value functions were defined in terms of the discounted return; thus we will use the same notation, $v_\pi (s) \doteq \mathbb{E}_\pi[G_t \vert S_t = s]$ and $q_\pi (s, a) \doteq \mathbb{E}_\pi[G_t \vert S_t = s, A_t = a]$ (similarly for $v_*$ and $q_*$), for differential value functions. Differential value functions also have Bellman equations, just slightly different from those we have seen earlier. We simply remove all $\gamma$s and replace all rewards by the difference between the reward and the true average reward:
$\begin{flalign}
&v_\pi(s) = \sum_a \pi(a\vert s) \sum_{r, s^\prime}p(s^\prime, r \vert s, a) \left [ r - r(\pi) + v_\pi(s^\prime) \right ] \\
&q_\pi(s, a) = \sum_{r, s^\prime}p(s^\prime, r \vert s, a) \left [ r - r(\pi) + \sum_{a^\prime} \pi(a^\prime \vert s^\prime) q_\pi(s^\prime, a^\prime) \right ] \\
&v_* = \max_a \sum_{r, s^\prime}p(s^\prime, r \vert s, a) \left [ r - r(\pi) + v_*(s^\prime) \right ] \\
&q_* = \sum_{r, s^\prime}p(s^\prime, r \vert s, a) \left [ r - \max_{\pi}r(\pi) + \max_a q_\pi(s^\prime, a^\prime) \right ] \\
\end{flalign}$
There is also a differential form of the two TD errors:
$\delta_t \doteq R_{t+1} - \bar{R}_t+ \hat v (S_{t+1}, \mathbf{w}_t) - \hat v(S_t, \mathbf{w}_t) \tag{10.10}$
and
$\delta_t \doteq R_{t+1} - \bar{R}_t+ \hat q (S_{t+1}, A_{t+1}, \mathbf{w}_t) - \hat q(S_t, A_t, \mathbf{w}_t) \tag{10.11}$
where $\bar{R}_t$ is an estimate at time $t$ of the average reward $r(\pi)$. With these alternate definitions, most of our algorithms and many theoretical results carry through to the average_reward setting without any change.
For example, an average reward version of semi-gradient Sarsa could be defined just as in (10.2) except with the differential version of the TD error. That is by
$\mathbf{w}_{t+1} \doteq \mathbf{w}_t + \alpha \delta_t \nabla \hat q(S_t, A_t, \mathbf{w}_t)$
with $\delta_t$ given by (10.11). See a full implementation below. One limitation of this algorithm is that it does not converge to the differential values but to the differential values plut an arbitrary offset. Notice that the Bellman equations and TD errors given above are unaffected if all the values are shifted by the same amount. Thus, the offset may not matter in practice.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$014339eb-5b23-4ac5-a551-8eeb2238366fcell_id$014339eb-5b23-4ac5-a551-8eeb2238366fcode}begin
function access_control_step(s::AccessControlState, ::Reject, num_servers::Integer, priority_payments::Vector{Float32})
occupied_servers = num_servers - s.num_free_servers
freed_servers = sum(_ -> Float32(rand() < 0.06), 1:occupied_servers; init = 0f0)
new_occupied_servers = occupied_servers - freed_servers
new_free_servers = num_servers - new_occupied_servers
new_priority = rand(priority_payments)
(0f0, AccessControlState(new_free_servers, new_priority))
end
function access_control_step(s::AccessControlState, ::Accept, num_servers::Integer, priority_payments::Vector{Float32})
occupied_servers = num_servers - s.num_free_servers
(r_reject, s′) = access_control_step(s, Reject(), num_servers, priority_payments)
s.num_free_servers == 0 && return (r_reject, s′)
(s.top_priority, AccessControlState(s′.num_free_servers - 1, s′.top_priority))
end
endmetadatashow_logsèdisabled®skip_as_script«code_folded$49249ac1-8964-4afc-89f2-3cd4d4322cc2cell_id$49249ac1-8964-4afc-89f2-3cd4d4322cc2codemd"""
> ### *Exercise 10.1*
> We have not explicitely considered or given pseudocode for any Monte Carlo methods in this chapter. What would they be like? Why is it reasonable not to give pseudocode for them? How would they perform on the Mountain Car task?
Monte Carlo methods require an episode to terminate prior to updating any action value estimates. After the final reward is retrieved then all the action value pairs visited along the trajectory can be updated and the policy can be updated prior to starting the next episode. For tasks such as the Mountain Car task where a random policy will likely never terminate, such a method will never be able to complete a single episode worth of updates. We saw in earlier chapters with the racetrack and gridworld examples that for some environments a bootstrap method is the only suitable one given this possibility of an episode never terminating.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$1a5acfb0-3b35-41b1-98f8-ffce941c587fcell_id$1a5acfb0-3b35-41b1-98f8-ffce941c587fcodeAmd"""
#### Mountain Car Linear Approximation with Tile Coding
"""metadatashow_logsèdisabled®skip_as_script«code_folded$7bc49107-9de5-4985-8750-979f36b3aa81cell_id$7bc49107-9de5-4985-8750-979f36b3aa81code_π_mountain_car2(s) = argmax(i_a -> q̂_mountain_car2(s, i_a), eachindex(mountain_car_actions))metadatashow_logsèdisabled®skip_as_script«code_folded$4d392303-4681-4ea1-8dcc-e002a78ea0a1cell_id$4d392303-4681-4ea1-8dcc-e002a78ea0a1code
emd"""
### Policy Improvement
The purpose of the value function lies in the *Policy Improvement Theorem* which provides a way to iteratively improve a given policy towards the optimal policy. Consider a policy $\pi(s)$ and its associated value functions $v_\pi(s)$ and $q_\pi(s, a)$. Now consider a new policy $\pi^\prime(s)$ that would select a different action $a^\prime$ at state $s$ than the original policy $\pi$ such that $q_\pi(s, a^\prime) \geq v_\pi(s)$. The theorem proves that if the former is true, then $v_{\pi^\prime}(s) \geq v_\pi(s) \forall s \in \mathcal{S}$. In other words, the new policy is superior to the old one since it has a higher value value at every state. There is also an easy way to construct a policy which meets the necessary criteria of the policy improvement theorem:
$\begin{flalign}
\pi^\prime(s) &\doteq \mathrm{argmax}_a q_\pi(s, a) \\
& = \mathrm{argmax}_a \mathbb{E} [R_{t+1} + \gamma v_\pi(S_{t+1}) \mid S_t = s, A_t = a] \\
& = \mathrm{argmax}_a \sum_{s^\prime, r} p(s^\prime, r \vert s, a) [r + \gamma v_\pi(s^\prime)] \\
\end{flalign}$
If we have the state-action value function $q_\pi(s, a)$, then the construction is trivial. If we only have $v_\pi(s)$, then we must also have the probability transition function for the environment in order to reconstruct the state-action values. In the absence of $p$ we must rely on $q_\pi$. Consider some future policy such that $\pi(s) = \mathrm{argmax}_a q_\pi(s, a) \: \forall s$. In this case, the updated policy will be identical to the original policy and the process will have converged. The policy at convergence will also be the optimal policy $\pi_*$ whose value functions fulfill the following properties:
$\begin{flalign}
v_*(s) &\doteq \max_\pi v_\pi(s) \: \forall \: s \in \mathcal{S} \tag{3.15} \\
&= \max_{a \in \mathcal{A}(s)} q_{*}(s, a) \: \forall \: s \in \mathcal{S} \tag{meaning of optimal}\\
&= \max_{a \in \mathcal{A}(s)} \sum_{s^\prime, r} p(s^\prime, r \vert s, a) \left [ r + γ v_* (s^\prime) \right ] \quad \forall s \in \mathcal{S} \tag{Used by Value Iteration when p is available}\\
q_*(s, a) &\doteq \max_\pi q_\pi(s, a) \: \forall \: s \in \mathcal{S} \text{ and } a \in \mathcal{A}(s) \tag{3.16} \\
&=\mathbb{E} \left [ R_{t+1} + \gamma v_* (S_{t+1}) \mid S_t = s, A_t = a \right ] \tag{3.17} \\
&= \sum_{s^\prime, r} p(s^\prime, r \vert s, a) \left [ r + γ v_* (s^\prime) \right ] \tag{exp value def (3.21)} \\
&= \sum_{s^\prime, r} p(s^\prime, r \vert s, a) \left [ r + γ \max_{a^\prime} q_*(s^\prime, a^\prime) \right ] \tag{Used by Q Value Iteration when p is available} \\
&= \mathbb{E} \left [ R_t + γ \max_{a^\prime} q_*(s^\prime, a^\prime) \mid S_t = s, A_t = a \right ] \tag{Used by Q Learning when p is not available} \\
\end{flalign}$
The policy improvement theorem suggests an approach where we initialize a random policy, find its value function, and then derive an improved policy until the process has converged. If we have the probability transition function, we can use dynamic programming to calculate the value function for a policy as well as the improved policy. Repeating this process until convergence is called *Policy Iteration*. Alternatively, we can use the properties of the optimal value function without explicitely considering a sequence of policies. That is only possible when the probability transition function is known and is called *Value Iteration*.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$d3ba78fa-f032-4bb9-9359-ef3bcff2252dcell_id$d3ba78fa-f032-4bb9-9359-ef3bcff2252dcodeJfunction mountaincar_fcann_differential_test(max_steps::Integer, α::Float32, β::Float32, ϵ::Float32; num_layers = 3, layer_size = 2, kwargs...)
feature_vector = zeros(Float32, 2)
function update_feature_vector!(v::Vector{Float32}, s::NTuple{2, Float32})
x1 = 3.45f0*(((s[1] - 1.2f0) / 1.7f0) - 0.5f0)
x2 = 1.725f0*s[2] / 0.07f0
v[1] = x1
v[2] = x2
end
layers = fill(layer_size, num_layers)
run_fcann_differential_semi_gradient_sarsa(mountain_car_differential_mdp, 1000, max_steps, feature_vector, update_feature_vector!, layers; α = α, β = β, ϵ = ϵ, kwargs...)
endmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$742100ba-c38e-4840-8988-40990039b527cell_id$742100ba-c38e-4840-8988-40990039b527codeٷsetup_mountain_car_tiles(tile_size::NTuple{2, Float32}, num_tilings::Integer) = tile_coding_setup(mountain_car_mdp, (-1.2f0, 0.5f0), (-0.07f0, 0.07f0), tile_size, num_tilings, (1, 3))metadatashow_logsèdisabled®skip_as_scriptëcode_folded$2f0d0a71-c65b-4aa0-a493-e7cdccd901ebcell_id$2f0d0a71-c65b-4aa0-a493-e7cdccd901ebcodefunction plot_mountaincar_values(v̂_mountain_car, π; n1 = 100, n2 = 100)
xvals = LinRange(-1.2f0, 0.5f0, n1)
vvals = LinRange(-0.07f0, 0.07f0, n2)
values = zeros(Float32, n1, n2)
actions = zeros(Float32, n1, n2)
for (i, x) in enumerate(xvals)
for (j, v) in enumerate(vvals)
v̂ = v̂_mountain_car((x, v))
values[j, i] = v̂
actions[j, i] = π((x, v))
end
end
p1 = plot(heatmap(x = xvals, y = vvals, z = values), Layout(xaxis_title = "position", yaxis_title = "velocity", title = "Learned Value Function"))
p2 = plot(heatmap(x = xvals, y = vvals, z = actions, colorscale = "rb", showscale = false), Layout(xaxis_title = "position", yaxis_title = "velocity", title = "Policy (blue = accelerate left,
red = accelerate right, gray = no acceleration)"))
[p1 p2]
endmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$a3cf270b-b309-44f0-9972-bd84228bcf17cell_id$a3cf270b-b309-44f0-9972-bd84228bcf17codemd"""
### Finding the Optimal Policy
Depending on the nature of the problem and the available information, different techniques are available. Below is a summary of the conditions and available techniques for different scenarios starting with the ideal case where all information is available.
#### Idealized Tabular Case
##### Problem conditions
- All states and actions can be enumerated: $\mathcal{S} = \{s_1, s_2, \cdots, s_n\}$ and $\mathcal{A} = \{a_1, a_2, \cdots, a_m\}$
- $p(s^\prime, r \vert s, a)$ is available for all states and actions
In order to verify that we have the correct value function or the optimal one, we need to confirm the conditions for every state or state-action pair. In short we require $p(s^\prime, r \vert s, a) \: \forall s, a$ which also implies the ability to check all the state action pairs. If this is possible, then the problem is *tabular* since we can tabulate all of the necessary values. It is only in this best case scenario that we can definitively verify the correct solution.
##### Solution Techniques
- Value Iteration
- initialize a list of state values: $[v_1, v_2, \cdots, v_n]$, one for each state
- perform the following update accross all states until the values converge: $v_i = \max_{a \in \mathcal{A}} \sum_{s_j, r} p(s_j, r \vert s_i, a) \left [ r + γ v_j \right ]$
- Policy Iteration
- initialize a random policy $\pi$ (probability distribution over actions for each state, could be a matrix)
- initialize a list of state values: $[v_1, v_2, \cdots, v_n]$, one for each state
- repeat the following until the values converge
- use dynamic programming policy evaulation to update the state values
- update the policy to be greedy with respect to the value function
"""metadatashow_logsèdisabled®skip_as_script«code_folded$b9125c5b-01d6-451e-84b5-a419e38425b5cell_id$b9125c5b-01d6-451e-84b5-a419e38425b5codetπ_mountain_car_fcann(s) = argmax(i_a -> mountain_car_fcann.value_function(s, i_a), eachindex(mountain_car_actions))metadatashow_logsèdisabled®skip_as_scriptëcode_folded$9d65285f-d49e-40ce-acea-1f565bcd4108cell_id$9d65285f-d49e-40ce-acea-1f565bcd4108codeٳconst (tabular_mountaincar_mdp, assign_state_index_tabular_mountaincar) = make_tabular_mountaincar(tabular_mountaincar_args.num_positions, tabular_mountaincar_args.num_velocities)metadatashow_logsèdisabled®skip_as_script«code_folded$57a6510f-bd42-4d1d-a550-d1442f79569fcell_id$57a6510f-bd42-4d1d-a550-d1442f79569fcode@md"""
### *Semi-gradient Dynamic Programming Implementation*
"""metadatashow_logsèdisabled®skip_as_script«code_folded$b0761704-5447-4e64-8270-708d9dccef60cell_id$b0761704-5447-4e64-8270-708d9dccef60coderfunction semi_gradient_dp!(parameters, mdp::StateMDP{T, S, A, P, F1, F2, F3}, γ::T, max_episodes::Integer, max_steps::Integer, estimate_value::Function, estimate_args::Tuple, update_parameters!::Function, update_args::Tuple; α = one(T)/10, ϵ = one(T) / 10, nn_momentum = false, α_decay = one(T), decay_step = typemax(Int64), kwargs...) where {T<:Real, S, A, P<:StateMDPTransitionDistribution, F1<:Function, F2<:Function, F3<:Function}
s = mdp.initialize_state()
i_a = rand(eachindex(mdp.actions))
ep = 1
step = 1
epreward = zero(T)
episode_rewards = Vector{T}()
episode_steps = Vector{Int64}()
action_values = zeros(T, length(mdp.actions))
policy = zeros(T, length(mdp.actions))
decay = one(T)
while (ep <= max_episodes) && (step <= max_steps)
maxq = typemin(T)
#computes q and finds maximizing action value, this is effectively trajectory sampling in the case of approximation where we stay close to the optimal policy
for i_a in eachindex(action_values)
(rewards, states, probabilities) = mdp.ptf.step(s, i_a)
v′ = zero(T)
r_avg = zero(T)
for i in eachindex(probabilities)
v′ += probabilities[i]*(!mdp.isterm(states[i])*estimate_value(states[i], parameters, estimate_args...))
r_avg += probabilities[i]*rewards[i]
end
q = r_avg + γ*v′
action_values[i_a] = q
if q > maxq
maxq = q
end
end
learning_rate = nn_momentum ? T(1 - 0.999^step) : one(T)
update_parameters!(parameters, s, maxq, α * learning_rate * decay, update_args...)
make_ϵ_greedy_policy!(action_values; ϵ = ϵ)
i_a = sample_action(action_values)
(r, s) = mdp.ptf(s, i_a)
epreward += r
if mdp.isterm(s)
s = mdp.initialize_state()
push!(episode_rewards, epreward)
push!(episode_steps, step)
epreward = zero(T)
ep += 1
end
if step > decay_step
decay *= α_decay
end
step += 1
end
return episode_rewards, episode_steps
endmetadatashow_logsèdisabled®skip_as_script«code_folded$a6c5ec28-b2d5-4893-a118-95c1318d1f7fcell_id$a6c5ec28-b2d5-4893-a118-95c1318d1f7fcodeGmd"""
> ### *Exercise 10.6*
> Suppose there is an MDP that under any policy produces the deterministic sequence of rewards +1, 0, +1, 0, +1, 0, . . . going on forever. Technically, this violates ergodicity; there is no stationary limiting distribution $μ_\pi$ and the limit (10.7) does not exist. Nevertheless, the average reward (10.6) is well defined. What is it? Now consider two states in this MDP. From A, the reward sequence is exactly as described above, starting with a +1, whereas, from B, the reward sequence starts with a 0 and then continues with +1, 0, +1, 0, . . .. We would like to compute the differential values of A and B. Unfortunately, the differential return (10.9) is not well defined when starting from these states as the implicit limit does not exist. To repair this, one could alternatively define the differential value of a state as $v_\pi (s) \doteq \lim_{\gamma \rightarrow 1} \lim_{h \rightarrow \infty} \sum_{t=0}^h \gamma^t \left ( \mathbb{E_\pi} [R_{t+1}|S_0=s]-r(\pi) \right )$. Under this definition what are the differential values of states A and B?
"""metadatashow_logsèdisabled®skip_as_script«code_folded$f1edb500-fbd1-4c03-b033-53860dfa452dcell_id$f1edb500-fbd1-4c03-b033-53860dfa452dcode md"""
> ### *Exercise 10.7*
> Consider a Markov reward process consisting of a ring of three states A, B, and C, with state transitions going deterministically around the ring. A reward of +1 is received upon arrival in A and otherwise the reward is 0. What are the differential values of the three states, using (10.13)
From 10.13 we have
$v_\pi (s) \doteq \lim_{\gamma \rightarrow 1} \lim_{h \rightarrow \infty} \sum_{t=0}^h \gamma^t \left ( \mathbb{E_\pi} [R_{t+1}|S_0=s]-r(\pi) \right )$
The average reward per step is $\frac{1}{3}$ so we can apply the same method used in exercise 10.6 where the elements inside the parentheses of the sum are: $\frac{2}{3}$ for $C \rightarrow A$ and $-\frac{1}{3}$ for the other two. Starting in state A we transition twice and then on the third arrive in state A leading to the following mean corrected values of $-\frac{1}{3}$, $-\frac{1}{3}$, and $\frac{2}{3}$. The other states will have these values cyclically permuted leading to the following infinite sums:
For state A:
$-\frac{1}{3} - \frac{1}{3}\gamma + \frac{2}{3}\gamma^2 - \frac{1}{3}\gamma^3 - \frac{1}{3}\gamma^4 + \cdots$
For state B:
$-\frac{1}{3} + \frac{2}{3}\gamma - \frac{1}{3}\gamma^2 - \frac{1}{3}\gamma^3 + \frac{2}{3}\gamma^4 + \cdots$
For state C:
$\frac{2}{3} - \frac{1}{3}\gamma - \frac{1}{3} \gamma^2 + \frac{2}{3}\gamma^3 + \cdots = 3 \times (2 - \gamma - \gamma^2 + 2\gamma^3 + \cdots)$
Comparing these sequences we have:
$\gamma \times v(A) = v(C) - \frac{2}{3} \implies v(A) = \frac{v(C) - \frac{2}{3}}{\gamma}$
$\gamma \times v(B) = v(A) + \frac{1}{3} \implies v(A) = \gamma \times v(B) - \frac{1}{3}$
so
$\frac{v(C) - \frac{2}{3}}{\gamma} = \gamma \times v(B) - \frac{1}{3} \implies v(C) = \gamma \left ( \gamma \times v(B) - \frac{1}{3} \right ) + \frac{2}{3}$
also
$\gamma \times v(C) = v(B) + \frac{1}{3} \implies v(C) = \frac{v(B) + \frac{1}{3}}{\gamma}$
Equation the two sides for $v(C)$ that only contain $v(B)$ terms we have:
$\frac{v(B) + \frac{1}{3}}{\gamma} = \gamma \left ( \gamma \times v(B) - \frac{1}{3} \right ) + \frac{2}{3}$
$v(B) = \gamma \left ( \gamma \left ( \gamma \times v(B) - \frac{1}{3} \right ) + \frac{2}{3} \right ) - \frac{1}{3} = \gamma^3 v(B) - \gamma^2 \frac{1}{3} + \gamma\frac{2}{3} - \frac{1}{3}$
$v(B) \left ( 1 - \gamma^3 \right ) = - \gamma^2 \frac{1}{3} + \gamma\frac{2}{3} - \frac{1}{3} \implies v(B) = \frac{- \gamma^2 \frac{1}{3} + \gamma\frac{2}{3} - \frac{1}{3}}{1 - \gamma^3}$
$v(B) = -\frac{1}{3} \frac{\gamma^2 - 2\gamma + 1}{1 - \gamma^3} = -\frac{1}{3} \frac{(\gamma - 1)^2}{-(\gamma - 1)(\gamma^2 + \gamma + 1)} = \frac{1}{3} \frac{\gamma - 1}{\gamma^2 + \gamma + 1}$
Therefore,
$\begin{flalign}
\lim_{\gamma \rightarrow 1} v(B) &= \frac{1}{3} \frac{1 - 1}{3} = 0 \\
\lim_{\gamma \rightarrow 1} v(A) &= \gamma \times 0 - \frac{1}{3} = -\frac{1}{3} \\
$\lim_{\gamma \rightarrow 1} v(C) &= \frac{0 + \frac{1}{3}}{\gamma} = \frac{1}{3}
\end{flalign}$
"""metadatashow_logsèdisabled®skip_as_script«code_folded$96548352-cd4d-4448-8312-ed10057f4359cell_id$96548352-cd4d-4448-8312-ed10057f4359codebegin
function update_parameters!(parameters::Vector{Vector{T}}, i_s::Integer, i_a::Integer, g::T, α::T) where {T<:Real}
q̂ = parameters[i_a][i_s]
δ = (g - q̂)
parameters[i_a][i_s] += α*δ
return nothing
end
function update_parameters!(parameters::Matrix{T}, i_s::Integer, i_a::Integer, g::T, α::T) where {T<:Real}
q̂ = parameters[i_s, i_a]
δ = (g - q̂)
parameters[i_s, i_a] += α*δ
return nothing
end
endmetadatashow_logsèdisabled®skip_as_script«code_folded$ed1bd92c-8cc7-457f-9692-a10a9487c953cell_id$ed1bd92c-8cc7-457f-9692-a10a9487c953codeٿhtml"""
"""metadatashow_logsèdisabled®skip_as_scriptëcode_folded$c9759bd9-ec9b-47a1-9080-a7fc332be565cell_id$c9759bd9-ec9b-47a1-9080-a7fc332be565codeٚdifferential_semi_gradient_q_learning!(args...; kwargs...) = differential_semi_gradient_sarsa!(args...; kwargs..., compute_value=compute_q_learning_value)metadatashow_logsèdisabled®skip_as_script«code_folded$953907cd-9926-4478-99b3-da7068118c22cell_id$953907cd-9926-4478-99b3-da7068118c22codefunction gradient_monte_carlo_action_episode_update!(parameters, update_parameters!::Function, states::AbstractVector{S}, actions::AbstractVector{A}, rewards::AbstractVector{T}, γ::T, α::T, update_args...) where {T<:Real, S, A}
g = zero(T)
l = length(states)
for i in l:-1:1
s = states[i]
i_a = actions[i]
g = γ * g + rewards[i]
update_parameters!(parameters, s, i_a, g, α, update_args...)
end
endmetadatashow_logsèdisabled®skip_as_script«code_folded$278a26ac-c48f-4e18-93bb-706a4634c8c0cell_id$278a26ac-c48f-4e18-93bb-706a4634c8c0codemd"""
Two options to represent parameters for use with action-values is to simply have a unique set of parameters for each action each of which matches the size of the state representation vector. Using this technique means we do not need to encode the action space into the representation. The parameters could be represented by a vector of vectors or a matrix in which each column is assigned to an action. Below are the update rules for both of these cases.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$8b7e1031-9864-439c-86eb-11aa08f53b90cell_id$8b7e1031-9864-439c-86eb-11aa08f53b90codefunction semi_gradient_double_sarsa!(parameters1::P, parameters2::P, mdp::StateMDP, γ::T, max_episodes::Integer, max_steps::Integer, estimate_value::Function, estimate_args::Tuple, update_parameters!::Function, update_args::Tuple; α = one(T)/10, ϵ = one(T) / 10, compute_value = compute_sarsa_value, nn_decay = false, kwargs...) where {P, T<:Real}
s = mdp.initialize_state()
i_a = rand(eachindex(mdp.actions))
ep = 1
step = 1
epreward = zero(T)
episode_rewards = Vector{T}()
episode_steps = Vector{Int64}()
action_values = zeros(T, length(mdp.actions))
policy = zeros(T, length(mdp.actions))
while (ep <= max_episodes) && (step <= max_steps)
(r, s′) = mdp.ptf(s, i_a)
epreward += r
if rand() < 0.5
update_params = parameters1
select_params = parameters2
end
if mdp.isterm(s′)
U_t = r
s′ = mdp.initialize_state()
i_a′ = rand(eachindex(mdp.actions))
push!(episode_rewards, epreward)
push!(episode_steps, step)
epreward = zero(T)
ep += 1
else
estimate_value(action_values, s′, select_params, estimate_args...)
policy .= action_values
make_ϵ_greedy_policy!(policy; ϵ = ϵ)
i_a′ = sample_action(policy)
estimate_value(action_values, s′, update_params, estimate_args...)
q̂ = compute_value(action_values, policy, i_a′)
U_t = r + γ*q̂
end
learning_rate = nn_decay ? T(1 - 0.999^step) : one(T)
update_parameters!(update_params, s, i_a, U_t, α * learning_rate, update_args...)
s = s′
i_a = i_a′
step += 1
end
return episode_rewards, episode_steps
endmetadatashow_logsèdisabled®skip_as_script«code_folded$d577b393-4b40-4c90-9993-4ffbcbd9df6dcell_id$d577b393-4b40-4c90-9993-4ffbcbd9df6dcode-const mountain_car_actions = [-1f0, 0f0, 1f0]metadatashow_logsèdisabled®skip_as_script«code_folded$5fdbce61-ca25-45e0-b07d-94adf7138446cell_id$5fdbce61-ca25-45e0-b07d-94adf7138446codeٰmountain_car_fcann = mountaincar_fcann_test(1_000_000, 8f-7, 0.05f0; num_layers = 3, layer_size = 16, compute_value = compute_sarsa_value, λ = 0f-4, c = 10f0, dropout = 0.0f0)metadatashow_logsèdisabled®skip_as_scriptëcode_folded$49e43d51-05d6-415b-a685-76e50904c5bccell_id$49e43d51-05d6-415b-a685-76e50904c5bccodefunction mountaincar_differential_test(max_episodes::Integer, α::Float32, β::Float32, ϵ::Float32; num_tiles = 12, num_tilings = 8, kwargs...)
setup = setup_mountain_car_tiles((1f0/num_tiles, 1f0/num_tiles), num_tilings)
v = setup.args.feature_vector
run_linear_differential_semi_gradient_sarsa(mountain_car_differential_mdp, max_episodes, typemax(Int64), zeros(Float32, length(v)), setup.args.feature_vector_update; α = α, β = β, ϵ = ϵ, kwargs...)
endmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$0f958535-6b18-46de-a1ba-81f64c217ee0cell_id$0f958535-6b18-46de-a1ba-81f64c217ee0code7function mountaincar_fcann_dp(max_episodes::Integer, α::Float32, ϵ::Float32; layers = [4, 4], max_steps = typemax(Int64), kwargs...)
run_fcann_semi_gradient_dp(mountain_car_dist_mdp, 1f0, max_episodes, max_steps, zeros(Float32, 2), update_mountaincar_feature_vector!, layers; α = α, ϵ = ϵ, kwargs...)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$44d43dbf-fe32-438e-b89d-c677bbc35893cell_id$44d43dbf-fe32-438e-b89d-c677bbc35893codemd"""
In order to use (10.6): $r(\pi) \doteq \lim_{h \rightarrow \infty} \frac{1}{h} \sum_{t = 1}^h \mathbb{E} [R_t \mid S_0, A_{0:t-1} \sim \pi]$ we need to compute $\mathbb{E} [R_t \mid S_0, A_{0:t-1} \sim \pi]$. In this case, we are told that regardless of the policy, the reward sequence will be +1, 0, +1, 0, .... We can therefore replace the expected values in the equation with this sequence since the rewards at each time step are known with 100% probability.
the average reward can be computed as $r(\pi) = \lim_{h \rightarrow \infty} \frac{1}{2h}\sum_{t=1}^h (-1)^{t+1} + 1 = \lim_{h \rightarrow \infty} \frac{h}{2h} + \frac{1}{2h} \sum_{t=1}^h (-1)^{t+1}$
The sum left in the expression is $1 - 1 + 1 - 1 \cdots$ which is 1 for even h and 0 for odd h. Either way, when divided by $2h$ that term goes to 0 leaving only the term $\frac{h}{2h} = \frac{1}{2}$ so $r(\pi) = \frac{1}{2}$
To compute the differential value function for state A and B, consider the alternative definition above using the fact that $r(\pi) = 0.5$.
For state A, each parenthetical term in the sum will be: $1 - 0.5, 0 - 0.5, 1 - 0.5, 0 - 0.5, \dots = 0.5, -0.5, 0.5, -0.5, \dots$
For state B, each parenthetical term in the sum will be: $0 - 0.5, 1 - 0.5, 0 - 0.5, 1 - 0.5, \dots = -0.5, 0.5, -0.5, 0.5, \dots$
$\begin{flalign}
v_\pi (A) &= \lim_{\gamma \rightarrow 1} \lim_{h \rightarrow \infty} 0.5 - 0.5\gamma + 0.5 \gamma^2 - 0.5\gamma^3 + \cdots \\
&=0.5\lim_{\gamma \rightarrow 1} \lim_{h \rightarrow \infty}\sum_{t=0}^h (-\gamma)^t \\
&=0.5\lim_{\gamma \rightarrow 1}\frac{1}{\gamma +1 } = 0.25
\end{flalign}$
$\begin{flalign}
v_\pi (B) &= \lim_{\gamma \rightarrow 1} \lim_{h \rightarrow \infty} -0.5 + 0.5\gamma - 0.5 \gamma^2 + 0.5\gamma^3 + \cdots \\
&=-0.5\lim_{\gamma \rightarrow 1} \lim_{h \rightarrow \infty}\sum_{t=0}^h (-\gamma)^t \\
&=-0.5\lim_{\gamma \rightarrow 1}\frac{1}{\gamma +1 } = -0.25
\end{flalign}$
"""metadatashow_logsèdisabled®skip_as_script«code_folded$b3658e4d-ee8e-45cd-906a-06dd512a6921cell_id$b3658e4d-ee8e-45cd-906a-06dd512a6921codeـplot_mountaincar_values(mountaincar_fcann_dp_results.value_function, mountaincar_fcann_dp_results.π_greedy; n1 = 100, n2 = 100)metadatashow_logsèdisabled®skip_as_scriptëcode_folded$00e7783f-7f17-4944-a085-ea87509cd75acell_id$00e7783f-7f17-4944-a085-ea87509cd75acodefunction run_fcann_semi_gradient_dp(mdp::StateMDP, γ::T, max_episodes::Integer, max_steps::Integer, state_representation::AbstractVector{T}, update_state_representation!::Function, layers::Vector{Int64}; λ = 0f0, c = Inf, dropout = 0f0, kwargs...) where T<:Real
setup = fcann_gradient_setup(mdp, layers, state_representation, update_state_representation!; λ = λ, c = c, dropout = dropout)
l = length(state_representation)
num_actions = length(mdp.actions)
episode_rewards, episode_steps = semi_gradient_dp!(setup.parameters, mdp, γ, max_episodes, max_steps, setup.value_function, setup.value_args, setup.parameter_update, setup.update_args; kwargs...)
v̂(s) = setup.value_function(s, setup.parameters, setup.value_args...)
function π_greedy(s)
action_values = zeros(T, num_actions)
for i_a in eachindex(action_values)
(rewards, states, probabilities) = mdp.ptf.step(s, i_a)
q = zero(T)
for i in eachindex(probabilities)
v̂′ = !mdp.isterm(states[i])*v̂(states[i])
q += probabilities[i]*(rewards[i] + γ*v̂′)
end
action_values[i_a] = q
end
make_greedy_policy!(action_values)
i_a = sample_action(action_values)
end
return (value_function = v̂, π_greedy = π_greedy, reward_history = episode_rewards, step_history = episode_steps)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$5be866c3-0fb2-4d1f-9c31-b85aba332905cell_id$5be866c3-0fb2-4d1f-9c31-b85aba332905codeـsemi_gradient_q_learning!(args...; kwargs...) = semi_gradient_sarsa!(args...; kwargs..., compute_value=compute_q_learning_value)metadatashow_logsèdisabled®skip_as_script«code_folded$e5ad765a-341f-4f11-9ae8-37d81cb349d2cell_id$e5ad765a-341f-4f11-9ae8-37d81cb349d2code~const mountain_car_differential_transition = StateMDPTransitionSampler(mountain_car_differential_step, initialize_car_state())metadatashow_logsèdisabled®skip_as_scriptëcode_folded$8befede5-378a-447a-96bd-edcd9d2ce98bcell_id$8befede5-378a-447a-96bd-edcd9d2ce98bcodemd"""
We can use these to create a sampling transition function, although it will be deterministic. The positions and velocities are still defined by two real numbers so the state space is unbounded and we cannot use a tabular method.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$ae5c5377-8b44-4c82-a63c-d2cb8a0d6667cell_id$ae5c5377-8b44-4c82-a63c-d2cb8a0d6667code(q̂_mountain_car2_fcann, episode_rewards2_fcann, episode_steps2_fcann, average_step_reward_fcann) = mountaincar_fcann_differential_test(1_000_000, 1f-4, 0.001f0, 0.5f0; num_layers = 3, layer_size = 8, compute_value = compute_q_learning_value)metadatashow_logsèdisabled®skip_as_script«code_folded$f58cd0a2-8c82-46b2-bb8f-00f6aa1d867fcell_id$f58cd0a2-8c82-46b2-bb8f-00f6aa1d867fcode5function update_input!(input::Matrix{Float32}, feature_vector::Vector{Float32}, i_a::Integer, num::Integer)
l1 = length(feature_vector)
l2 = size(input, 2)
for i in eachindex(feature_vector)
input[num, i] = feature_vector[i]
end
for i in l1+1:l2
input[num, i] = 0f0
end
input[num, l1+i_a] = 1f0
endmetadatashow_logsèdisabled®skip_as_script«code_folded$065b2626-01f1-443f-8be4-3036003a2772cell_id$065b2626-01f1-443f-8be4-3036003a2772codeDfunction run_linear_differential_semi_gradient_sarsa(mdp::StateMDP, max_episodes::Integer, max_steps::Integer, state_representation::AbstractVector{T}, update_state_representation!::Function; setup_kwargs = NamedTuple(), kwargs...) where T<:Real
setup = linear_features_action_gradient_setup(mdp, state_representation, update_state_representation!; setup_kwargs...)
l = length(state_representation)
num_actions = length(mdp.actions)
# parameters = zeros(T, l, num_actions)
parameters = [zeros(T, l) for _ in 1:num_actions]
episode_rewards, episode_steps, average_step_reward = differential_semi_gradient_sarsa!(parameters, mdp, max_episodes, max_steps, setup.value_function, setup.value_args, setup.parameter_update, setup.update_args; kwargs...)
q̂(s, i_a) = setup.value_function(s, i_a, parameters, setup.value_args...)
action_values = zeros(T, num_actions)
q̂(s) = setup.value_function(action_values, s, parameters, setup.value_args...)
return (value_function = q̂, reward_history = episode_rewards, step_history = episode_steps, average_step_reward = average_step_reward)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$57ea3538-33be-4673-b914-8191d35426a9cell_id$57ea3538-33be-4673-b914-8191d35426a9codeiconst mountaincar_value_iteration = value_iteration_v(tabular_mountaincar_mdp, 1f0; save_history = false)metadatashow_logsèdisabled®skip_as_script«code_folded$2d7679ad-a9b3-448b-a4bc-7e5b9bce6adbcell_id$2d7679ad-a9b3-448b-a4bc-7e5b9bce6adbcodemd"""
> ### *Exercise 10.8*
> The pseudocode in the box on page 251 updates $\bar R_t$ using $\delta_t$ as an error rather than simply $R_{t+1} - \bar R_t$. Both errors work, but using $\delta_t$ is better. To see why, consider the ring MRP of three states from Exercise 10.7. The estimate of the average reward should tend towards its true value of $\frac{1}{3}$. Suppose it was already there and was held stuck there. What would the sequence of $R_{t+1} - \bar R_t$ errors be? What would the sequence of $\delta_t$ errors be (using Equation 10.10)? Which error sequence would produce a more stable estimate of the average reward if the estimate were allowed to change in response to the errors? Why?
The sequence of $R_{t+1} - \bar R_t$ would be given by the cyclical sequence of rewards. Let's assume we start the sequence at state A. Then our reward sequence will be 0, 0, 1, 0, 0, 1... so the error sequence will be $-\frac{1}{3}$, $-\frac{1}{3}$, $\frac{2}{3}$,... If we update the average error estimate using these corrections it would remain centered at the correct value but fluctuate up and down with each correction.
In order to calculate $\delta_t$ we must use the definition given by 10.10:
$\delta_t = R_{t+1} - \bar R_t + \hat v(S_{t+1}, \mathbf{w}_t) - \hat v(S_t, \mathbf{w}_t)$
This equation requires us to have value estimates for each state which we can assume have converged to the true values as we have for the average reward estimate: $\hat v(A) = -\frac{1}{3}$, $\hat v(B) = 0$, and $\hat v(C) = \frac{1}{3}$. Starting at state A, $\delta_t = 0 - \frac{1}{3} + 0 - -\frac{1}{3} = 0$. For the following state we have $0 - \frac{1}{3} + \frac{1}{3} = 0$. Finally we have $1 - \frac{1}{3} + -\frac{1}{3} - \frac{1}{3} = 0$. So if we use the TD error to update our average reward estimate, at equilibrium all the values will remain unchanged. Using $\delta$ provides a lower variance estimator than simply using the reward.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$425fe768-c7bb-4d3e-87e6-47fa052ba612cell_id$425fe768-c7bb-4d3e-87e6-47fa052ba612codeٷplot(scatter(y = (episode_steps2_fcann[2:findlast(!iszero, episode_steps2_fcann)] .- episode_steps2_fcann[1:findlast(!iszero, episode_steps2_fcann) - 1])), Layout(yaxis_type = "log"))metadatashow_logsèdisabled®skip_as_script«code_folded$06834750-cc3a-468a-b0c2-81349c288a33cell_id$06834750-cc3a-468a-b0c2-81349c288a33codefunction gradient_monte_carlo_control!(parameters, mdp::StateMDP, γ::T, num_episodes::Integer, value_function::Function, value_args::Tuple, update_parameters!::Function, update_args::Tuple; α = one(T)/10, ϵ = one(T)/10, suppress_warning = false, epkwargs...) where {T<:Real}
action_values = zeros(T, length(mdp.actions))
function π_ϵ_greedy(s)
rand() < ϵ && return rand(eachindex(mdp.actions))
value_function(action_values, s, parameters, value_args...)[2]
end
(states, actions, rewards, sterm, nsteps) = runepisode(mdp; epkwargs...)
gradient_monte_carlo_action_episode_update!(parameters, update_parameters!, states, actions, rewards, γ, α, update_args...)
if !suppress_warning && !mdp.isterm(sterm)
@info "Warning: Episode 1 did not conclude in $nsteps steps"
end
step_history = [nsteps]
reward_history = [sum(rewards)]
for ep in 2:num_episodes
(states, actions, rewards, sterm, nsteps) = runepisode!((states, actions, rewards), mdp; π = π_ϵ_greedy, epkwargs...)
gradient_monte_carlo_action_episode_update!(parameters, update_parameters!, view(states, 1:nsteps), view(actions, 1:nsteps), view(rewards, 1:nsteps), γ, α, update_args...)
if !suppress_warning && !mdp.isterm(sterm)
@info "Warning: Episode $ep did not conclude in $nsteps steps"
end
push!(step_history, nsteps)
push!(reward_history, sum(rewards[i] for i in 1:nsteps))
end
return step_history, reward_history
endmetadatashow_logsèdisabled®skip_as_script«code_folded$1054cfa3-9f58-4a93-a318-c2d21cf23220cell_id$1054cfa3-9f58-4a93-a318-c2d21cf23220codefunction show_mountaincar_trajectory(tabular_mountaincar_mdp, π::Matrix{T}, max_steps::Integer, name) where T<:Real
state_indices, actions, rewards, sterm, nsteps = runepisode(tabular_mountaincar_mdp; π = π, max_steps = max_steps)
states = [tabular_mountaincar_mdp.states[i_s] for i_s in state_indices]
positions = [s[1] for s in states]
velocities = [s[2] for s in states]
tr1 = scatter(x = positions, y = velocities, mode = "markers", showlegend = false)
tr2 = scatter(y = positions, showlegend = false)
tr3 = scatter(y = [mountain_car_actions[i] for i in actions], showlegend = false)
p1 = plot(tr1, Layout(xaxis_title = "position", yaxis_title = "velocity", xaxis_range = [-1.2, 0.5], yaxis_range = [-0.07, 0.07]))
p2 = plot(tr2, Layout(xaxis_title = "time", yaxis_title = "position"))
p3 = plot(tr3, Layout(xaxis_title = "time", yaxis_title = "action"))
mdname = Markdown.parse(name)
md"""
$mdname
Total Reward: $(sum(rewards))
$([p1 p2 p3])
"""
endmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$8ed6f8fd-8574-4d5a-9964-ce8a32629c6fcell_id$8ed6f8fd-8574-4d5a-9964-ce8a32629c6fcodeقcompute_expected_sarsa_value(action_values::Vector{T}, policy::Vector{T}, i_a::Integer) where T<:Real = dot(action_values, policy)metadatashow_logsèdisabled®skip_as_script«code_folded$f9abf433-8ce3-4520-9b47-f17f8f07b4cbcell_id$f9abf433-8ce3-4520-9b47-f17f8f07b4cbcode{const mountain_car_transition_distribution = StateMDPTransitionDistribution(mountain_car_dist_step, initialize_car_state())metadatashow_logsèdisabled®skip_as_script«code_folded$59ec5223-f23f-4f32-9e5f-8a08e450da85cell_id$59ec5223-f23f-4f32-9e5f-8a08e450da85codeTmd"""
## 10.2 Semi-gradient *n*-step Sarsa
We can obtain an $n$-step version of semi-gradient Sarsa by using an $n$-step return as the update target for the semi-gradient Sarsa update equation (10.1). The $n$-step return immediately generalizes from its tabular form (7.4) to a function approximation form:
$G_{t:t+n} \doteq R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{n-1}R_{t+n} + \gamma^n \hat q(S_{t+n}, A_{t+n}, \mathbf{w}_{t+n-1}), \quad t+n \lt T \tag{10.4}$
with $G_{t:t+n} \doteq G_t$ if $t+n \geq T$, as usual. The $n$-step update equation is
$\mathbf{w}_{t+n} \doteq \mathbf{w}_{t+n-1} + \alpha \left [ G_{t:t+n} - \hat q(S_t, A_t, \mathbf{w}_{t+n-1}) \right ] \nabla \hat q(S_t, A_t, \mathbf{w}_{t+n-1}), \quad 0 \leq t \lt T \tag{10.5}$
As we have seen before, performance is often best with an $n$ that is some intermediate value between the 1-step sarsa method and Monte Carlo; however, we will not create a full implementation of this algorithm here as it will be replaced by semi-gradient Sarsa($\lambda$) in Chapter 12 which is a much more efficient version of the same concept.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$0c7f5742-6c51-4c6a-b67f-217163935ba5cell_id$0c7f5742-6c51-4c6a-b67f-217163935ba5codemd"""
> ### *Exercise 10.5*
> What equations are needed (beyond 10.10) to specify the differential version of TD(0)?
10.10 includes a reward estimate at time t, $\bar R_t$, which also needs to be updated. The TD error represents the newly observed reward the was experienced in excess of the estimated average so the update equation should move $\bar R$ in the direction of the TD error. After each step, the following updates should occur.
$\begin{flalign}
\delta &\leftarrow R - \bar R + \hat v(S^\prime, \mathbf{w}) - \hat v(S, \mathbf{w}) \\
\bar R &\leftarrow \bar R + \beta \delta \\
\mathbf{w} &\leftarrow \mathbf{w} + \alpha \delta \nabla \hat v(S, \mathbf{w}) \\
S & \leftarrow S^\prime \\
\end{flalign}$
"""metadatashow_logsèdisabled®skip_as_script«code_folded$c697e0b6-d3e4-4f5f-96e9-b9486c9d7efccell_id$c697e0b6-d3e4-4f5f-96e9-b9486c9d7efccodebegin
fill_action_values!(action_values::Vector{T}, state_representation::AbstractVector{T}, parameters::Matrix{T}) where T<:Real = mul!(action_values, parameters', state_representation)
function fill_action_values!(action_values::Vector{T}, state_representation::AbstractVector{T}, parameters::Vector{Vector{T}}) where T<:Real
@inbounds for i in eachindex(action_values)
action_values[i] = dot(state_representation, parameters[i])
end
end
endmetadatashow_logsèdisabled®skip_as_script«code_folded$9fb5dace-a799-4424-bcb3-8542e508dd4bcell_id$9fb5dace-a799-4424-bcb3-8542e508dd4bcodeWusing PlutoUI,PlutoPlotly, PlutoProfile, BenchmarkTools, LaTeXStrings, HypertextLiteralmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$c1388562-0708-4a6a-acfe-927413dab5d2cell_id$c1388562-0708-4a6a-acfe-927413dab5d2code?plot(scatter(y = -episode_rewards), Layout(yaxis_type = "log"))metadatashow_logsèdisabled®skip_as_scriptëcode_folded$cbf1e5ed-8308-486e-a9b7-6cf7fb441fe3cell_id$cbf1e5ed-8308-486e-a9b7-6cf7fb441fe3codexshow_mountaincar_trajectory(π_optimal_value_iteration, 1000, "Tabular Mountain Car Value Iteration Policy on True MDP")metadatashow_logsèdisabled®skip_as_script«code_folded$6cea9e69-bf8c-4079-9884-663a728d7b08cell_id$6cea9e69-bf8c-4079-9884-663a728d7b08codemd"""
# Dependencies
"""metadatashow_logsèdisabled®skip_as_script«code_folded$b0cc6ff8-7296-461c-9db7-e52fa518e2e2cell_id$b0cc6ff8-7296-461c-9db7-e52fa518e2e2codefunction mountaincar_dist_test(max_episodes::Integer, α::Float32, ϵ::Float32; num_tiles = 24, num_tilings = 32, max_steps = typemax(Int64), kwargs...)
setup = setup_mountain_car_tiles((1f0/num_tiles, 1f0/num_tiles), num_tilings)
v = setup.args.feature_vector
run_linear_semi_gradient_dp(mountain_car_dist_mdp, 1f0, max_episodes, max_steps, zeros(Float32, length(v)), setup.args.feature_vector_update; α = α, ϵ = ϵ, kwargs...)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$30ab21ba-3f5b-46a8-8b8c-753f2755d419cell_id$30ab21ba-3f5b-46a8-8b8c-753f2755d419codep(q̂_mountain_car, π_mountain_car, episode_rewards, episode_steps) = mountaincar_test(5000, 0.0001f0/8, 0.01f0)metadatashow_logsèdisabled®skip_as_scriptëcode_folded$1478745a-634d-4f31-8a70-b74f0e536201cell_id$1478745a-634d-4f31-8a70-b74f0e536201codemd"""
Part of the Sarsa algorithm requires us to identify the maximizing action. These functions update a vector of action-values using the parameters and state representation. By computing all of the action values at once, the maximum can be identified, and these functions compute all the action values more efficiently than using the above function for each action individually.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$b07460f1-0461-4f63-b145-c4e1818a497ecell_id$b07460f1-0461-4f63-b145-c4e1818a497ecode(function mountain_car_step(s::Tuple{Float32, Float32}, i_a::Int64)
a = mountain_car_actions[i_a]
ẋ′ = clamp(s[2] + 0.001f0*a - 0.0025f0*cos(3*s[1]), -0.07f0, 0.07f0)
x′ = clamp(s[1] + ẋ′, -1.2f0, 0.5f0)
x′ == -1.2f0 && return (-1f0, (x′, 0f0))
return (-1f0, (x′, ẋ′))
endmetadatashow_logsèdisabled®skip_as_script«code_folded$a9b74949-9392-4048-bcb6-5fd48c1d9b98cell_id$a9b74949-9392-4048-bcb6-5fd48c1d9b98code:md"""
### Example 10.2: An Access-Control Queuing Task
"""metadatashow_logsèdisabled®skip_as_script«code_folded$565c53ee-7ad5-44e2-bce5-4ff1f5f162c0cell_id$565c53ee-7ad5-44e2-bce5-4ff1f5f162c0code٢differential_semi_gradient_expected_sarsa!(args...; kwargs...) = differential_semi_gradient_sarsa!(args...; kwargs..., compute_value=compute_expected_sarsa_value)metadatashow_logsèdisabled®skip_as_script«code_folded$12f5065b-5bed-4d03-a0f0-72a942492394cell_id$12f5065b-5bed-4d03-a0f0-72a942492394codefunction make_tabular_mountaincar(N, M)
x_range = (-1.2f0, 0.5f0)
v_range = (-0.07f0, 0.07f0)
x_vals = LinRange(x_range..., N)
v_vals = LinRange(v_range..., M)
states = [(x, v) for x in x_vals for v in v_vals]
state_transition_map = zeros(Int64, length(mountain_car_actions), length(states))
reward_transition_map = zeros(Float32, length(mountain_car_actions), length(states))
#assign a state to the closest state in the list by euclidean distance
d(x1, x2) = (x1 - x2)^2
function bucket_state(s1)
i_x = searchsortedfirst(x_vals, s1[1])
i_v = searchsortedfirst(v_vals, s1[2])
M*(i_x-1) + i_v
end
for (i_s, s) in enumerate(states)
if s[1] == 0.5f0
state_transition_map[:, i_s] .= i_s
reward_transition_map[:, i_s] .= 0f0
else
for (i_a, a) in enumerate(mountain_car_actions)
(r, s′) = mountain_car_step(s, i_a)
i_s′ = bucket_state(s′)
state_transition_map[i_a, i_s] = i_s′
reward_transition_map[i_a, i_s] = r
end
end
end
init_state_index() = bucket_state(initialize_car_state())
ptf = TabularDeterministicTransition(state_transition_map, reward_transition_map)
(mdp = TabularMDP(states, mountain_car_actions, ptf, init_state_index), assign_state_index = bucket_state)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$4afbb723-340b-4d85-9115-027a0ff8dfadcell_id$4afbb723-340b-4d85-9115-027a0ff8dfadcode:plot_mountaincar_action_values(q̂_mountain_car, 500, 500)metadatashow_logsèdisabled®skip_as_scriptëcode_folded$00399548-b21c-43b5-90e2-30656ab1541ecell_id$00399548-b21c-43b5-90e2-30656ab1541ecode[plot(scatter(y = -mountaincar_fcann_dp_results.reward_history), Layout(yaxis_type = "log"))metadatashow_logsèdisabled®skip_as_scriptëcode_folded$c75dc51c-cbff-48b1-b0fd-108828929b51cell_id$c75dc51c-cbff-48b1-b0fd-108828929b51codeHfunction run_fcann_gradient_monte_carlo_control(mdp::StateMDP, γ::T, num_episodes::Integer, state_representation::AbstractVector{T}, update_state_representation!::Function, layers::Vector{Int64}; λ = 0f0, c = Inf, dropout = 0f0, kwargs...) where T<:Real
setup = fcann_action_gradient_setup(mdp, layers, state_representation, update_state_representation!; λ = λ, c = c, dropout = dropout)
num_actions = length(mdp.actions)
step_history, reward_history = gradient_monte_carlo_control!(setup.parameters, mdp, γ, num_episodes, setup.value_function, setup.value_args, setup.parameter_update, setup.update_args; kwargs...)
q̂(s, i_a) = setup.value_function(s, i_a, setup.parameters, setup.value_args...)
action_values = zeros(Float32, num_actions)
q̂(s) = setup.value_function(action_values, s, setup.parameters, setup.value_args...)
π_greedy(s) = q̂(s)[2]
π_ϵ_greedy(s, ϵ) = rand() < ϵ ? rand(eachindex(mdp.actions)) : π_greedy(s)
return (value_function = q̂, π_greedy = π_greedy, π_ϵ_greedy = π_ϵ_greedy, step_history = step_history, reward_history = reward_history)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$7a47a518-dfc7-4310-a0b5-6f0d151c8263cell_id$7a47a518-dfc7-4310-a0b5-6f0d151c8263code=md"""
### Neural Network Mountain Car Semi-gradient Sarsa
"""metadatashow_logsèdisabled®skip_as_script«code_folded$a22e5d34-4b8d-479c-985c-d6abd41a6c80cell_id$a22e5d34-4b8d-479c-985c-d6abd41a6c80code-md"""
### Example 10.1: Mountain Car Task
"""metadatashow_logsèdisabled®skip_as_script«code_folded$b990ba67-42c8-4ab9-943d-085392204fddcell_id$b990ba67-42c8-4ab9-943d-085392204fddcode.md"""
#### Defining Car State and Dynamics
"""metadatashow_logsèdisabled®skip_as_script«code_folded$7c5fb569-81f0-4b70-ae95-1fce0c51b6f4cell_id$7c5fb569-81f0-4b70-ae95-1fce0c51b6f4codefunction mountaincar_test(max_episodes::Integer, α::Float32, ϵ::Float32; num_tiles = 12, num_tilings = 8, kwargs...)
setup = setup_mountain_car_tiles((1f0/num_tiles, 1f0/num_tiles), num_tilings)
v = setup.args.feature_vector
run_linear_semi_gradient_sarsa(mountain_car_mdp, 1f0, max_episodes, typemax(Int64), zeros(Float32, length(v)), setup.args.feature_vector_update; α = α, ϵ = ϵ, kwargs...)
endmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$0e3e506d-1959-47fd-8da9-b3dfd294be67cell_id$0e3e506d-1959-47fd-8da9-b3dfd294be67code;plot_mountaincar_action_values(q̂_mountain_car2, 500, 500)metadatashow_logsèdisabled®skip_as_script«code_folded$af97f222-08d1-4200-a10b-8da178182175cell_id$af97f222-08d1-4200-a10b-8da178182175code"md"""
#### Dynamic Programming
"""metadatashow_logsèdisabled®skip_as_script«code_folded$b5273dfa-2262-487a-856b-441f007bd163cell_id$b5273dfa-2262-487a-856b-441f007bd163codeq(1:nsamples |> Map(i -> runepisode(mountain_car_mdp; max_steps = 100_000)[5] == 100_000) |> foldxt(+)) / nsamplesmetadatashow_logsèdisabled®skip_as_scriptëcode_folded$b5409b69-a254-4355-b2b9-99394eceb2f7cell_id$b5409b69-a254-4355-b2b9-99394eceb2f7codeRshow_mountaincar_trajectory(π_mountain_car_q, 1_000, "Q-Learning Learned Policy")metadatashow_logsèdisabled®skip_as_scriptëcode_folded$b9ebd6bb-90a1-4945-85ed-023206e2420acell_id$b9ebd6bb-90a1-4945-85ed-023206e2420acodefunction linear_features_action_gradient_setup(problem::Union{StateMDP{T, S, A, P, F1, F2, F3}, StateMRP{T, S, P, F1, F2}}, state_representation::AbstractVector{T}, update_feature_vector!::Function) where {T<:Real, S, A, P, F1<:Function, F2<:Function, F3<:Function}
s0 = problem.initialize_state()
update_feature_vector!(state_representation, s0) #verify that feature vector update is compatible with provided state representation
function update_params!(parameters::AbstractArray, s::S, i_a::Integer, g::T, α::T, state_representation::AbstractVector{T}) where T<:Real
update_feature_vector!(state_representation, s)
q̂ = calculate_action_value(state_representation, i_a, parameters)
δ = (g - q̂)
iszero(δ) && return nothing
update_parameters!(parameters, state_representation, i_a, α, δ)
return nothing
end
function q̂(s::S, i_a::Integer, parameters::AbstractArray, state_representation::AbstractVector{T}) where {T<:Real}
update_feature_vector!(state_representation, s)
calculate_action_value(state_representation, i_a, parameters)
end
function q̂(action_values::Vector{T}, s::S, parameters::AbstractArray, state_representation::AbstractVector{T}) where {T<:Real}
update_feature_vector!(state_representation, s)
fill_action_values!(action_values, state_representation, parameters)
findmax(action_values)
end
return (value_function = q̂, value_args = (state_representation,), parameter_update = update_params!, update_args = (copy(state_representation),))
endmetadatashow_logsèdisabled®skip_as_script«code_folded$d0cf3806-05c6-4a50-94c8-55c9042d51b7cell_id$d0cf3806-05c6-4a50-94c8-55c9042d51b7codew(v̂_mountain_car, π_greedy_dp, episode_rewards_dp, episode_steps_dp) = mountaincar_dist_test(100, 0.001f0/32, 0.01f0)metadatashow_logsèdisabled®skip_as_scriptëcode_folded«notebook_id$68039796-8c6b-11ef-1217-bf750534f606in_temp_dir¨metadata