bondscell_results $f68952bd-4c0b-4331-a09c-5b118c8fa5a9queued¤logsrunning¦outputbodyHstate_aggregation_action_gradient_setup (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA
`persist_js_state·has_pluto_hook_features§cell_id$f68952bd-4c0b-4331-a09c-5b118c8fa5a9depends_on_disabled_cells§runtime )published_object_keysdepends_on_skipped_cells§errored$9df1a18d-137c-4ea5-8d15-05697f7bbf07queued¤logsrunning¦outputbody
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
mimetext/htmlrootassigneelast_run_timestampA |xհpersist_js_state·has_pluto_hook_features§cell_id$9df1a18d-137c-4ea5-8d15-05697f7bbf07depends_on_disabled_cells§runtime W published_object_keysdepends_on_skipped_cells§errored$c11aa069-93c2-435a-8f0e-353ced9633b6queued¤logsrunning¦outputbody7mountaincar_fcann_test (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA aI^persist_js_state·has_pluto_hook_features§cell_id$c11aa069-93c2-435a-8f0e-353ced9633b6depends_on_disabled_cells§runtime ,opublished_object_keysdepends_on_skipped_cellsçerrored$7812e801-70fd-4331-ad0a-fad02c1a399fqueued¤logsrunning¦outputbody>semi_gradient_expected_sarsa! (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA "^persist_js_state·has_pluto_hook_features§cell_id$7812e801-70fd-4331-ad0a-fad02c1a399fdepends_on_disabled_cells§runtime (published_object_keysdepends_on_skipped_cells§errored$2f685ee2-6ad8-4bb1-b326-e5de7c15eb18queued¤logsrunning¦outputbody
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.
In the discounted setting, we can think about optimizing $D(\pi) = \sum_s v_\pi(s)$ where $v_*$ has the highest possible value of $D$ since we know the state values are highest everywhere. Since all states are weighted equally, the result is different from optimizing $J$ and in general will depend on the discount rate. But what if $\gamma \rightarrow 1$, can we say anything about $D(\pi)$?
Returning to the definition of $v_\pi(s) = \mathbb{E}_\pi \left [ \sum_{k=1}^\infty R_k \gamma^{k-1} \mid S_0 = s \right ]$
Let's say that $\lim_{t \rightarrow \infty} \mathbb{E}_\pi [R_t]$ exists and is independent of $S_0$ (those are the criteria for the average reward setting). Then we can split this into a finite sum and an infinite sum where
and that in the limit as $N \rightarrow \infty$ this becomes exact. Now there is some $r_{max} \geq R_t \forall t < N$, so the first part of the sum can be bounded by $\sum_{k = 1}^N r_{max} \gamma^{k-1} = r_{max}\frac{\gamma^N - 1}{\gamma - 1}$ and in the limit of $\gamma \rightarrow 1$ this approaches $r_{max}N$.
Let $\gamma = 1 - \epsilon$ where $\epsilon \ll 1$ Then $\gamma^N = (1 - \epsilon)^N = 1 - N \epsilon + O(\epsilon^2)$ so we can rewrite the expression above as
The second sum is equal to $\frac{r(\pi) \gamma^N}{1-\gamma}$ which approaches infinite value as the discount rate approaches 1. So for any finite N, there exists a $\gamma \lt 1$ for which the second sum is arbitrarily larger than the first which means that in the limit $v_\pi(s) \approx \frac{r(\pi) \gamma^N}{1-\gamma}$ which is also approximately equal to $J(\pi)$ in the limit of $\gamma \rightarrow 1$. Thus optimizing the discounted value is equivalent to optimizing $r(\pi)$ in this limit.
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:
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$
mimetext/htmlrootassigneelast_run_timestampA upersist_js_state·has_pluto_hook_features§cell_id$b0265b93-ae5f-48f2-a9fd-44fd6115164bdepends_on_disabled_cells§runtime
published_object_keysdepends_on_skipped_cells§errored$57659c52-de1b-46e6-a863-8eeec0cee601queued¤logsrunning¦outputbody;π_optimal_value_iteration (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA @persist_js_state·has_pluto_hook_features§cell_id$57659c52-de1b-46e6-a863-8eeec0cee601depends_on_disabled_cells§runtime Gpublished_object_keysdepends_on_skipped_cellsçerrored$a9fdb1fd-3f62-4e1c-9157-c4eee6215261queued¤logsrunning¦outputbodyBdifferential_semi_gradient_sarsa! (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA &persist_js_state·has_pluto_hook_features§cell_id$a9fdb1fd-3f62-4e1c-9157-c4eee6215261depends_on_disabled_cells§runtime \Republished_object_keysdepends_on_skipped_cells§errored$cc9197e0-f5bd-4742-bea3-b54e0b8e3b93queued¤logsrunning¦outputbodymimetext/htmlrootassigneelast_run_timestampA kpersist_js_state·has_pluto_hook_features§cell_id$e86bc86f-9909-458d-b86d-0a4ac4b9d43ddepends_on_disabled_cells§runtimetgpublished_object_keysdepends_on_skipped_cellsçerrored$bc1d7cce-c0f4-47a8-b674-8acb82491c7fqueued¤logsrunning¦outputbodyprefix'StateMDP{Float32, Tuple{Float32, Float32}, Float32, StateMDPTransitionSampler{Float32, Tuple{Float32, Float32}, typeof(mountain_car_differential_step)}, typeof(Main.var"workspace#5".MountainCarTask.initialize_state), typeof(Main.var"workspace#5".MountainCarTask.isterm), TabularRL.var"#164#169"}elementsactionsprefixFloat32elements-1.0text/plain0.0text/plain1.0text/plaintypeArrayprefix_shortobjectid8ba0218b55bb916d!application/vnd.pluto.tree+objectptfprefixcStateMDPTransitionSampler{Float32, Tuple{Float32, Float32}, typeof(mountain_car_differential_step)}elementsstep?mountain_car_differential_step (generic function with 1 method)text/plaintypestructprefix_shortStateMDPTransitionSamplerobjectidffffffffaef964b1!application/vnd.pluto.tree+objectinitialize_state1initialize_state (generic function with 1 method)text/plainisterm'isterm (generic function with 1 method)text/plainis_valid_action%#164 (generic function with 1 method)text/plainaction_indexprefixDict{Float32, Int64}elements0.0text/plain2text/plain-1.0text/plain1text/plain1.0text/plain3text/plaintypeDictprefix_shortDictobjectidd8f4e71f8e062f0b!application/vnd.pluto.tree+objecttypestructprefix_shortStateMDPobjectidf022e99cb4e98f2bmime!application/vnd.pluto.tree+objectrootassignee#const mountain_car_differential_mdplast_run_timestampA persist_js_state·has_pluto_hook_features§cell_id$bc1d7cce-c0f4-47a8-b674-8acb82491c7fdepends_on_disabled_cells§runtimeߒpublished_object_keysdepends_on_skipped_cellsçerrored$7e8c89aa-8a5e-4ff4-afd2-df8f5c77b5b2queued¤logsrunning¦outputbody|500-element LinRange{Float32, Int64}:
-0.07, -0.0697194, -0.0694389, -0.0691583, …, 0.0691583, 0.0694389, 0.0697194, 0.07mimetext/plainrootassigneeconst mountaincar_velocitieslast_run_timestampA persist_js_state·has_pluto_hook_features§cell_id$7e8c89aa-8a5e-4ff4-afd2-df8f5c77b5b2depends_on_disabled_cells§runtime ȵpublished_object_keysdepends_on_skipped_cellsçerrored$c914fc12-d650-400b-8aff-e2a55bb2d5cfqueued¤logsrunning¦outputbody.sample_vector (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA +persist_js_state·has_pluto_hook_features§cell_id$c914fc12-d650-400b-8aff-e2a55bb2d5cfdepends_on_disabled_cells§runtime ֵpublished_object_keysdepends_on_skipped_cells§errored$c12070a9-df63-4b25-99e6-26ff876af1b4queued¤logsrunning¦outputbodyCupdate_mountaincar_feature_vector! (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA vpersist_js_state·has_pluto_hook_features§cell_id$c12070a9-df63-4b25-99e6-26ff876af1b4depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$991492f4-7dfc-43aa-ab6c-a6b1f3e38225queued¤logsrunning¦outputbody5semi_gradient_sarsa! (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA Xpersist_js_state·has_pluto_hook_features§cell_id$991492f4-7dfc-43aa-ab6c-a6b1f3e38225depends_on_disabled_cells§runtime W#published_object_keysdepends_on_skipped_cells§errored$b191d3f9-cf25-4fb4-8f5a-8da86e96e125queued¤logsrunning¦outputbodyj
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.
mimetext/htmlrootassigneelast_run_timestampA yopersist_js_state·has_pluto_hook_features§cell_id$224b4bec-9ec5-434d-a950-f5974cd786d0depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$f1f6f750-8c49-4435-82a1-e13a280b3738queued¤logsrunning¦outputbodyCfigure_10_5_tabular_average_reward (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA Y3
persist_js_state·has_pluto_hook_features§cell_id$f1f6f750-8c49-4435-82a1-e13a280b3738depends_on_disabled_cells§runtimeb'published_object_keysdepends_on_skipped_cellsçerrored$f009970f-bf6c-46dd-a534-a960582ce51bqueued¤logsrunning¦outputbodyq
Average Reward Solution to Access Control Task Solved with Policy Iteration
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.
mimetext/htmlrootassigneelast_run_timestampA persist_js_state·has_pluto_hook_features§cell_id$8752c98d-fac1-4b3b-b20b-70acc0677fcbdepends_on_disabled_cells§runtime x~published_object_keysdepends_on_skipped_cells§errored$dd472c0f-7b43-4abe-ada9-9dc8004a18cbqueued¤logsrunning¦outputbody.add_elements (generic function with 4 methods)mimetext/plainrootassigneelast_run_timestampA MVpersist_js_state·has_pluto_hook_features§cell_id$dd472c0f-7b43-4abe-ada9-9dc8004a18cbdepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cellsçerrored$ab4cb3db-3a2d-4145-826b-b1001114eeffqueued¤logsrunning¦outputbodyj
Differential Q-learning Learned Policy
Total Reward: -1000.0f0
mimetext/htmlrootassigneelast_run_timestampA *xpersist_js_state·has_pluto_hook_features§cell_id$ab4cb3db-3a2d-4145-826b-b1001114eeffdepends_on_disabled_cells§runtimewpublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/529ac09f15182c01depends_on_skipped_cellsçerrored$36a53700-9e9a-4131-89c8-dbd520d5c407queued¤logsrunning¦outputbodyHrun_linear_semi_gradient_expected_sarsa (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA persist_js_state·has_pluto_hook_features§cell_id$36a53700-9e9a-4131-89c8-dbd520d5c407depends_on_disabled_cells§runtime dpublished_object_keysdepends_on_skipped_cells§errored$f221fb13-4ef2-4ebe-b71b-fe6adbddb1e4queued¤logsrunning¦outputbody%Main.var"workspace#5".MountainCarTaskmimetext/plainrootassigneelast_run_timestampA zrpersist_js_state·has_pluto_hook_features§cell_id$f221fb13-4ef2-4ebe-b71b-fe6adbddb1e4depends_on_disabled_cells§runtimebpublished_object_keysdepends_on_skipped_cells§errored$1410db13-4b73-4a87-af34-30a5232af4baqueued¤logsrunning¦outputbody9compute_q_learning_value (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA |persist_js_state·has_pluto_hook_features§cell_id$1410db13-4b73-4a87-af34-30a5232af4badepends_on_disabled_cells§runtime Q:published_object_keysdepends_on_skipped_cells§errored$1a56e4dd-15dd-47b3-afd8-1dd7f5b690acqueued¤logsrunning¦outputbodyj
mimetext/htmlrootassigneelast_run_timestampA Dpersist_js_state·has_pluto_hook_features§cell_id$7cb7ca66-3130-4f06-a0dc-a3335ef85fdbdepends_on_disabled_cells§runtime\published_object_keysdepends_on_skipped_cellsçerrored$eb28458f-b222-4f8e-9a5b-8203d3997f7bqueued¤logsrunning¦outputbody?mountain_car_differential_step (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA ְpersist_js_state·has_pluto_hook_features§cell_id$eb28458f-b222-4f8e-9a5b-8203d3997f7bdepends_on_disabled_cells§runtime Upublished_object_keysdepends_on_skipped_cells§errored$a97e3b12-b7a5-4f88-bdb9-c3158203e0ffqueued¤logsrunning¦outputbodyj
Tabular Mountain Car Value Iteration Policy
Total Reward: -88.0f0
mimetext/htmlrootassigneelast_run_timestampA 5epersist_js_state·has_pluto_hook_features§cell_id$a97e3b12-b7a5-4f88-bdb9-c3158203e0ffdepends_on_disabled_cells§runtime KYpublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/66b159d94cb9116cdepends_on_skipped_cellsçerrored$25159f84-a120-4a20-aab8-010c110571a4queued¤logsrunning¦outputbody.uniform_value (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA Opersist_js_state·has_pluto_hook_features§cell_id$25159f84-a120-4a20-aab8-010c110571a4depends_on_disabled_cells§runtime 6published_object_keysdepends_on_skipped_cellsçerrored$a28f57c1-e48c-4f4f-8795-bdd195b26135queued¤logsrunning¦outputbody
With the value for state A known, the others will follow from (1), (2), and (3).
mimetext/htmlrootassigneelast_run_timestampA ~persist_js_state·has_pluto_hook_features§cell_id$a28f57c1-e48c-4f4f-8795-bdd195b26135depends_on_disabled_cells§runtime 1published_object_keysdepends_on_skipped_cells§errored$4ccb8a52-c6af-445d-a39e-d4d9b10c0d6aqueued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA RҰpersist_js_state·has_pluto_hook_features§cell_id$4ccb8a52-c6af-445d-a39e-d4d9b10c0d6adepends_on_disabled_cells§runtime qpublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/a22ee352190b1f11depends_on_skipped_cellsçerrored$5e500019-d129-4c3c-91dd-cae93e7ab44fqueued¤logsrunning¦outputbodyLrun_nonlinear_differential_semi_gradient_dp (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA Tpersist_js_state·has_pluto_hook_features§cell_id$5e500019-d129-4c3c-91dd-cae93e7ab44fdepends_on_disabled_cells§runtime _published_object_keysdepends_on_skipped_cells§errored$1e224a46-91ef-4a5f-ae35-ef4062147f2dqueued¤logsrunning¦outputbodyj
DP Learned Policy
Total Reward: -466.0f0
mimetext/htmlrootassigneelast_run_timestampA qpersist_js_state·has_pluto_hook_features§cell_id$1e224a46-91ef-4a5f-ae35-ef4062147f2ddepends_on_disabled_cells§runtime,published_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/ce69617ca62366f4depends_on_skipped_cellsçerrored$39a07c8a-0253-42b8-ba8d-f00b02ca82a5queued¤logsrunning¦outputbodyDrun_linear_semi_gradient_q_learning (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA apersist_js_state·has_pluto_hook_features§cell_id$39a07c8a-0253-42b8-ba8d-f00b02ca82a5depends_on_disabled_cells§runtime Ipublished_object_keysdepends_on_skipped_cells§errored$4ecb2297-9113-464c-a1b2-10b7bf0ac691queued¤logsrunning¦outputbodyIrun_linear_differential_semi_gradient_dp (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA
(persist_js_state·has_pluto_hook_features§cell_id$4ecb2297-9113-464c-a1b2-10b7bf0ac691depends_on_disabled_cells§runtime dnpublished_object_keysdepends_on_skipped_cells§errored$5b2ffd90-ead0-42ce-999a-584ed8995910queued¤logsrunning¦outputbodyprefix=StateMDP{Float32, Tuple{Float32, Float32}, Float32, StateMDPTransitionDistribution{Float32, Tuple{Float32, Float32}, typeof(Main.var"workspace#5".MountainCarTask.dist_step)}, typeof(Main.var"workspace#5".MountainCarTask.initialize_state), typeof(Main.var"workspace#5".MountainCarTask.isterm), TabularRL.var"#164#169"}elementsactionsprefixFloat32elements-1.0text/plain0.0text/plain1.0text/plaintypeArrayprefix_shortobjectid750051bc982d51cc!application/vnd.pluto.tree+objectptfprefixyStateMDPTransitionDistribution{Float32, Tuple{Float32, Float32}, typeof(Main.var"workspace#5".MountainCarTask.dist_step)}elementsstep*dist_step (generic function with 1 method)text/plaintypestructprefix_shortStateMDPTransitionDistributionobjectidffffffffbb026142!application/vnd.pluto.tree+objectinitialize_state1initialize_state (generic function with 1 method)text/plainisterm'isterm (generic function with 1 method)text/plainis_valid_action%#164 (generic function with 1 method)text/plainaction_indexprefixDict{Float32, Int64}elements0.0text/plain2text/plain-1.0text/plain1text/plain1.0text/plain3text/plaintypeDictprefix_shortDictobjectid1dcfe9b0eb4134ae!application/vnd.pluto.tree+objecttypestructprefix_shortStateMDPobjectidd643e702f1b29f0fmime!application/vnd.pluto.tree+objectrootassigneeconst mountain_car_dist_mdplast_run_timestampA +persist_js_state·has_pluto_hook_features§cell_id$5b2ffd90-ead0-42ce-999a-584ed8995910depends_on_disabled_cells§runtime S~published_object_keysdepends_on_skipped_cellsçerrored$62839b2a-398a-4445-87d1-b15ff2acc1d1queued¤logsrunning¦outputbody;create_access_control_task (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA UTpersist_js_state·has_pluto_hook_features§cell_id$62839b2a-398a-4445-87d1-b15ff2acc1d1depends_on_disabled_cells§runtime SDpublished_object_keysdepends_on_skipped_cells§errored$8d096d0d-8fea-421a-aa33-82269d3fe7e2queued¤logsrunning¦outputbodyf
Action-Value Implementation of Non-Linear Approximation
mimetext/htmlrootassigneelast_run_timestampA xpersist_js_state·has_pluto_hook_features§cell_id$8d096d0d-8fea-421a-aa33-82269d3fe7e2depends_on_disabled_cells§runtime jpublished_object_keysdepends_on_skipped_cells§errored$6f4f8b64-0c17-446e-bfb6-0540871ad9e0queued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA =mpersist_js_state·has_pluto_hook_features§cell_id$6f4f8b64-0c17-446e-bfb6-0540871ad9e0depends_on_disabled_cells§runtime Qpublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/5e207fb8f78fff1bdepends_on_skipped_cellsçerrored$39b0f100-a7e7-4633-b296-ccc87a5a35abqueued¤logsrunning¦outputbody>run_fcann_semi_gradient_sarsa (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA Vpersist_js_state·has_pluto_hook_features§cell_id$39b0f100-a7e7-4633-b296-ccc87a5a35abdepends_on_disabled_cells§runtime WH!published_object_keysdepends_on_skipped_cells§errored$1a82ae95-3c3e-4281-bc1d-9eb19bf50286queued¤logsrunning¦outputbody,figure_10_2 (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA ߰persist_js_state·has_pluto_hook_features§cell_id$1a82ae95-3c3e-4281-bc1d-9eb19bf50286depends_on_disabled_cells§runtime Spublished_object_keysdepends_on_skipped_cellsçerrored$99e3ec39-24f0-43d6-b6fd-9910b738ce2cqueued¤logsrunning¦outputbodyj
Tabular Mountain Car Trajectory
Total Reward: -1000.0f0
mimetext/htmlrootassigneelast_run_timestampA persist_js_state·has_pluto_hook_features§cell_id$99e3ec39-24f0-43d6-b6fd-9910b738ce2cdepends_on_disabled_cells§runtime;published_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/5acbba890cbba784depends_on_skipped_cellsçerrored$501b7284-6e04-4a15-b8e4-2601156b0345queued¤logsrunning¦outputbodyAmountaincar_differential_dp_test (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA 8ɰpersist_js_state·has_pluto_hook_features§cell_id$501b7284-6e04-4a15-b8e4-2601156b0345depends_on_disabled_cells§runtime !dpublished_object_keysdepends_on_skipped_cellsçerrored$f11787a1-57f8-4077-8d60-bc760ece7cc6queued¤logsrunning¦outputbody8calculate_action_value (generic function with 3 methods)mimetext/plainrootassigneelast_run_timestampA 8&persist_js_state·has_pluto_hook_features§cell_id$f11787a1-57f8-4077-8d60-bc760ece7cc6depends_on_disabled_cells§runtime rCpublished_object_keysdepends_on_skipped_cells§errored$fc3e0577-45aa-4bba-a275-fa7a352fc5ccqueued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA ypersist_js_state·has_pluto_hook_features§cell_id$fc3e0577-45aa-4bba-a275-fa7a352fc5ccdepends_on_disabled_cells§runtimepublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/265ffd812e3f0d89depends_on_skipped_cellsçerrored$54700e88-2c70-4b3e-bc93-6960dc70efcbqueued¤logsrunning¦outputbodyCcreate_access_control_tabular_task (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA .persist_js_state·has_pluto_hook_features§cell_id$54700e88-2c70-4b3e-bc93-6960dc70efcbdepends_on_disabled_cells§runtime b@published_object_keysdepends_on_skipped_cells§errored$4271151d-d5a6-4a29-96c3-f2102b142b95queued¤logsrunning¦outputbody2get_action_value (generic function with 2 methods)mimetext/plainrootassigneelast_run_timestampA tpersist_js_state·has_pluto_hook_features§cell_id$4271151d-d5a6-4a29-96c3-f2102b142b95depends_on_disabled_cells§runtime 0published_object_keysdepends_on_skipped_cells§errored$98a5d65e-4253-4523-a74e-99d03be03b89queued¤logsrunning¦outputbody~
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.
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.
mimetext/htmlrootassigneelast_run_timestampA persist_js_state·has_pluto_hook_features§cell_id$39eada35-8c3e-4ddc-8df9-7cf9f120928ddepends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$b55d50a4-b039-4240-b434-42f7b724d24dqueued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA ?Zpersist_js_state·has_pluto_hook_features§cell_id$b55d50a4-b039-4240-b434-42f7b724d24ddepends_on_disabled_cells§runtime Pԁpublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/4bba33d984a46ee6depends_on_skipped_cellsçerrored$9b3035f6-fe59-4748-a1cd-3c2ce61c6608queued¤logsrunning¦outputbodyHrun_fcann_gradient_monte_carlo_control (generic function with 2 methods)mimetext/plainrootassigneelast_run_timestampA Guqpersist_js_state·has_pluto_hook_features§cell_id$9b3035f6-fe59-4748-a1cd-3c2ce61c6608depends_on_disabled_cells§runtime AT]published_object_keysdepends_on_skipped_cells§errored$41c626c7-908d-4ff6-9730-4ad0b8c3cc25queued¤logsrunning¦outputbodyd
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 2.53
mimetext/htmlrootassigneelast_run_timestampA persist_js_state·has_pluto_hook_features§cell_id$41c626c7-908d-4ff6-9730-4ad0b8c3cc25depends_on_disabled_cells§runtime/kOpublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/593ac67d938f76664b9565ce0-38f6-11f0-350f-a762f362895d/2a65b0a6de4c79ddepends_on_skipped_cellsçerrored$1e9c537a-a731-4b81-8f6a-cb658b52c5bequeued¤logsrunning¦outputbodyprefix3StateMDP{Float32, Tuple{Float32, Float32}, Float32, StateMDPTransitionSampler{Float32, Tuple{Float32, Float32}, typeof(Main.var"workspace#5".MountainCarTask.step)}, typeof(Main.var"workspace#5".MountainCarTask.initialize_state), typeof(Main.var"workspace#5".MountainCarTask.isterm), TabularRL.var"#164#169"}elementsactionsprefixFloat32elements-1.0text/plain0.0text/plain1.0text/plaintypeArrayprefix_shortobjectid735f491d15a40ff1!application/vnd.pluto.tree+objectptfprefixoStateMDPTransitionSampler{Float32, Tuple{Float32, Float32}, typeof(Main.var"workspace#5".MountainCarTask.step)}elementsstep&step (generic function with 2 methods)text/plaintypestructprefix_shortStateMDPTransitionSamplerobjectidffffffffaba603fb!application/vnd.pluto.tree+objectinitialize_state1initialize_state (generic function with 1 method)text/plainisterm'isterm (generic function with 1 method)text/plainis_valid_action%#164 (generic function with 1 method)text/plainaction_indexprefixDict{Float32, Int64}elements0.0text/plain2text/plain-1.0text/plain1text/plain1.0text/plain3text/plaintypeDictprefix_shortDictobjectide45de565a359f0e4!application/vnd.pluto.tree+objecttypestructprefix_shortStateMDPobjectidb6f5ce304a1095admime!application/vnd.pluto.tree+objectrootassigneeconst mountain_car_mdplast_run_timestampA "persist_js_state·has_pluto_hook_features§cell_id$1e9c537a-a731-4b81-8f6a-cb658b52c5bedepends_on_disabled_cells§runtime i}published_object_keysdepends_on_skipped_cellsçerrored$13e477f0-dc15-46cb-9691-c04a1b4c83c8queued¤logsrunning¦outputbodyOgradient_monte_carlo_action_policy_estimation! (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA bpersist_js_state·has_pluto_hook_features§cell_id$13e477f0-dc15-46cb-9691-c04a1b4c83c8depends_on_disabled_cells§runtime =ߩpublished_object_keysdepends_on_skipped_cells§errored$47710ddd-79d9-464d-b5dd-27180f2d6b31queued¤logsrunning¦outputbody
f
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}$$
mimetext/htmlrootassigneelast_run_timestampA upersist_js_state·has_pluto_hook_features§cell_id$47710ddd-79d9-464d-b5dd-27180f2d6b31depends_on_disabled_cells§runtime Kipublished_object_keysdepends_on_skipped_cells§errored$14fe2253-cf2c-4159-a360-1e65f1c82b09queued¤logsrunning¦outputbody C
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:
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:
$$\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:
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.
mimetext/htmlrootassigneelast_run_timestampA w~persist_js_state·has_pluto_hook_features§cell_id$14fe2253-cf2c-4159-a360-1e65f1c82b09depends_on_disabled_cells§runtime ^published_object_keysdepends_on_skipped_cells§errored$164c68ef-01b8-43be-bc75-919dd99a6e03queued¤logsrunning¦outputbody?gradient_monte_carlo_control! (generic function with 2 methods)mimetext/plainrootassigneelast_run_timestampA Qpersist_js_state·has_pluto_hook_features§cell_id$164c68ef-01b8-43be-bc75-919dd99a6e03depends_on_disabled_cells§runtime &published_object_keysdepends_on_skipped_cells§errored$5c920177-8e46-49c9-9b95-1a657fdcae4equeued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA
// We start by putting all the variable interpolation here at the beginning
// We have to convert all typedarrays in the layout to normal arrays. See Issue #25
// We use lodash for this for compactness
function removeTypedArray(o) {
return _.isTypedArray(o) ? Array.from(o) :
_.isPlainObject(o) ? _.mapValues(o, removeTypedArray) :
o
}
// Publish the plot object to JS
let plot_obj = _.update(/* See the documentation for AbstractPlutoDingetjes.Display.published_to_js */ getPublishedObject("b9565ce0-38f6-11f0-350f-a762f362895d/d9e1c7748ec01469"), "layout", removeTypedArray)
// Get the plotly listeners
const plotly_listeners = {}
// Get the JS listeners
const js_listeners = {}
// Deal with eventual custom classes
let custom_classlist = []
// Load the plotly library
const Plotly = window.plutoplotly_imports?.['2.34.0'] ??(await import("https://esm.sh/plotly.js-dist-min@2.34.0")).default
// Check if we have to force local mathjax font cache
if (false && window?.MathJax?.config?.svg?.fontCache === 'global') {
window.MathJax.config.svg.fontCache = 'local'
}
// Flag to check if this cell was manually ran or reactively ran
const firstRun = this ? false : true
const CONTAINER = this ?? html`
`)
const parent = CONTAINER.parentElement
// We use a controller to remove event listeners upon invalidation
const controller = new AbortController()
// We have to add this to keep supporting @bind with the old API using PLOT
PLOT.addEventListener('input', (e) => {
CONTAINER.value = PLOT.value
if (e.bubbles) {
return
}
CONTAINER.dispatchEvent(new CustomEvent('input'))
}, { signal: controller.signal })
// This create the style subdiv on first run
firstRun && CONTAINER.appendChild(html`
`)
let original_height = plot_obj.layout.height
let original_width = plot_obj.layout.width
// For the height we have to also put a fixed value in case the plot is put on a non-fixed-size container (like the default wrapper)
// We define a variable to check whether we still have to remove the fixed height
let remove_container_size = firstRun
let container_height = original_height ?? PLOT.container_height ?? 400
CONTAINER.style.height = container_height + 'px'
// We create a Promise version of setTimeout
function delay(ms) {
return new Promise((resolve) => setTimeout(resolve, ms));
}
// We import interact for dragging/resizing
const { default: interact } = await import('https://esm.sh/interactjs@1.10.19')
function getImageOptions() {
const o = plot_obj.config.toImageButtonOptions ?? {};
return {
format: o.format ?? "png",
width: o.width ?? original_width,
height: o.height ?? original_height,
scale: o.scale ?? 1,
filename: o.filename ?? "newplot",
};
}
const CLIPBOARD_HEADER =
CONTAINER.querySelector(".plutoplotly-clipboard-header") ??
CONTAINER.insertAdjacentElement(
"afterbegin",
html`
Format:Width:pxHeight:pxScale:Filename:
`
);
function checkConfigSync(container) {
const valid_classes = [
"missing-config",
"matching-config",
"different-config",
];
function setClass(cl) {
for (const name of valid_classes) {
container.classList.toggle(name, name == cl);
}
}
// We use the custom getters we'll set up in the container
const { ui_value, config_value, config_span, key } = container;
if (config_value === undefined) {
setClass("missing-config");
config_span.innerHTML = `The key ${key} is not present in the config.`;
} else if (ui_value == config_value) {
setClass("matching-config");
config_span.innerHTML = `The key ${key} has the same value in the config and in the header.`;
} else {
setClass("different-config");
config_span.innerHTML = `The key ${key} has a different value (${config_value}) in the config.`;
}
// Add info about setting and unsetting
config_span.insertAdjacentHTML(
"beforeend",
` Click on the label once to set the current UI value in the config.`
);
config_span.insertAdjacentHTML(
"beforeend",
` Click twice to remove this key from the config.`
);
}
const valid_formats = ["png", "svg", "webp", "jpeg", "full-json"];
function initializeUIValueSpan(span, key, value) {
const container = span.closest(".clipboard-span");
span.contentEditable = key === "format" ? "false" : "true";
let parse = (x) => x;
let update = (x) => (span.textContent = x);
if (key === "width" || key === "height") {
parse = (x) => Math.round(parseFloat(x));
} else if (key === "scale") {
parse = parseFloat;
} else if (key === "format") {
// We remove contentEditable
span.contentEditable = "false";
// Here we first add the subspans for each option
const opts_div = span.appendChild(html``);
for (const fmt of valid_formats) {
const opt = opts_div.appendChild(
html`${fmt}`
);
opt.onclick = (e) => {
span.value = opt.textContent;
};
}
parse = (x) => {
return valid_formats.includes(x) ? x : localValue;
};
update = (x) => {
for (const opt of opts_div.children) {
opt.classList.toggle("selected", opt.textContent === x);
}
};
} else {
// We only have filename here
}
let localValue;
Object.defineProperty(span, "value", {
get: () => {
return localValue;
},
set: (val) => {
if (val !== "") {
localValue = parse(val);
}
update(localValue);
checkConfigSync(container);
},
});
// We also assign a listener so that the editable is blurred when enter is pressed
span.onkeydown = (e) => {
if (e.keyCode === 13) {
e.preventDefault();
span.blur();
}
};
span.value = value;
}
function initializeConfigValueSpan(span, key) {
// Here we mostly want to define the setter and getter
const container = span.closest(".clipboard-span");
Object.defineProperty(span, "value", {
get: () => {
return plot_obj.config.toImageButtonOptions[key];
},
set: (val) => {
// if undefined is passed, we remove the entry from the options
if (val === undefined) {
delete plot_obj.config.toImageButtonOptions[key];
} else {
plot_obj.config.toImageButtonOptions[key] = val;
}
checkConfigSync(container);
},
});
}
const config_spans = {};
for (const [key, value] of Object.entries(getImageOptions())) {
const container = CLIPBOARD_HEADER.querySelector(`.clipboard-span.${key}`);
const label = container.querySelector(".label");
// We give the label a function that on single click will set the current value and with double click will unset it
label.onclick = DualClick(
() => {
container.config_value = container.ui_value;
},
(e) => {
console.log("e", e);
e.preventDefault();
container.config_value = undefined;
}
);
const ui_value_span = container.querySelector(".clipboard-value");
const config_value_span =
container.querySelector(".config-value") ??
label.insertAdjacentElement(
"afterbegin",
html``
);
// Assing the two spans as properties of the containing span
container.ui_span = ui_value_span;
container.config_span = config_value_span;
container.key = key;
config_spans[key] = container;
if (firstRun) {
plot_obj.config.toImageButtonOptions =
plot_obj.config.toImageButtonOptions ?? {};
// We do the initialization of the value span
initializeUIValueSpan(ui_value_span, key, value);
// Then we initialize the config value
initializeConfigValueSpan(config_value_span, key);
// We put some convenience getters/setters
// ui_value forward
Object.defineProperty(container, "ui_value", {
get: () => ui_value_span.value,
set: (val) => {
ui_value_span.value = val;
},
});
// config_value forward
Object.defineProperty(container, "config_value", {
get: () => config_value_span.value,
set: (val) => {
config_value_span.value = val;
},
});
}
}
// These objects will contain the default value
// This code updates the image options in the PLOT config with the provided ones
function setImageOptions(o) {
for (const [key, container] of Object.entries(config_spans)) {
container.config_value = o[key];
}
}
function unsetImageOptions() {
setImageOptions({});
}
const set_button = CLIPBOARD_HEADER.querySelector(".clipboard-span.set");
const unset_button = CLIPBOARD_HEADER.querySelector(".clipboard-span.unset");
if (firstRun) {
set_button.onclick = (e) => {
for (const container of Object.values(config_spans)) {
container.config_value = container.ui_value;
}
};
unset_button.onclick = unsetImageOptions;
}
// We add a function to check if the clipboard is popped out
CONTAINER.isPoppedOut = () => {
return CONTAINER.classList.contains("popped-out");
};
CLIPBOARD_HEADER.onmousedown = function (event) {
if (event.target.matches("span.clipboard-value")) {
console.log("We don't move!");
return;
}
const start = {
left: parseFloat(CONTAINER.style.left),
top: parseFloat(CONTAINER.style.top),
X: event.pageX,
Y: event.pageY,
};
function moveAt(event, start) {
const top = event.pageY - start.Y + start.top + "px";
const left = event.pageX - start.X + start.left + "px";
CLIPBOARD_HEADER.style.left = left;
CONTAINER.style.left = left;
CONTAINER.style.top = top;
}
// move our absolutely positioned ball under the pointer
moveAt(event, start);
function onMouseMove(event) {
moveAt(event, start);
}
// We use this to remove the mousemove when clicking outside of the container
const controller = new AbortController();
// move the container on mousemove
document.addEventListener("mousemove", onMouseMove, {
signal: controller.signal,
});
document.addEventListener(
"mousedown",
(e) => {
if (e.target.closest(".plutoplotly-container") !== CONTAINER) {
cleanUp();
controller.abort();
return;
}
},
{ signal: controller.signal }
);
function cleanUp() {
console.log("cleaning up the plot move listener");
controller.abort();
CLIPBOARD_HEADER.onmouseup = null;
}
// (3) drop the ball, remove unneeded handlers
CLIPBOARD_HEADER.onmouseup = cleanUp;
};
function sendToClipboard(blob) {
if (!navigator.clipboard) {
alert(
"The Clipboard API does not seem to be available, make sure the Pluto notebook is being used from either localhost or an https source."
);
}
navigator.clipboard
.write([
new ClipboardItem({
// The key is determined dynamically based on the blob's type.
[blob.type]: blob,
}),
])
.then(
function () {
console.log("Async: Copying to clipboard was successful!");
},
function (err) {
console.error("Async: Could not copy text: ", err);
}
);
}
function copyImageToClipboard() {
// We extract the image options from the provided parameters (if they exist)
const config = {};
for (const [key, container] of Object.entries(config_spans)) {
let val =
container.config_value ??
(CONTAINER.isPoppedOut() ? container.ui_value : undefined);
// If we have undefined we don't create the key. We also ignore format because the clipboard only supports png.
if (val === undefined || key === "format") {
continue;
}
config[key] = val;
}
Plotly.toImage(PLOT, config).then(function (dataUrl) {
fetch(dataUrl)
.then((res) => res.blob())
.then((blob) => {
const paste_receiver = document.querySelector('paste-receiver.plutoplotly')
if (paste_receiver) {
paste_receiver.attachImage(dataUrl, CONTAINER)
}
sendToClipboard(blob)
});
});
}
function saveImageToFile() {
const config = {};
for (const [key, container] of Object.entries(config_spans)) {
let val =
container.config_value ??
(CONTAINER.isPoppedOut() ? container.ui_value : undefined);
// If we have undefined we don't create the key.
if (val === undefined) {
continue;
}
config[key] = val;
}
Plotly.downloadImage(PLOT, config);
}
let container_rect = { width: 0, height: 0, top: 0, left: 0 };
function unpop_container(cl) {
CONTAINER.classList.toggle("popped-out", false);
CONTAINER.classList.toggle(cl, false);
// We fix the height back to the value it had before popout, also setting the flag to signal that upon first resize we remove the fixed inline-style
CONTAINER.style.height = container_rect.height + "px";
remove_container_size = true;
// We set the other fixed inline-styles to null
CONTAINER.style.width = "";
CONTAINER.style.top = "";
CONTAINER.style.left = "";
// We also remove the CLIPBOARD_HEADER
CLIPBOARD_HEADER.style.width = "";
CLIPBOARD_HEADER.style.left = "";
// Finally we remove the hidden class to the header
CLIPBOARD_HEADER.classList.toggle("hidden", true);
return;
}
function popout_container(opts) {
const cl = opts?.cl;
const target_container_size = opts?.target_container_size ?? {};
const target_plot_size = opts?.target_plot_size ?? {};
if (CONTAINER.isPoppedOut()) {
return unpop_container(cl);
}
CONTAINER.classList.toggle(cl, cl === undefined ? false : true);
// We extract the current size of the container, save them and fix them
const { width, height, top, left } = CONTAINER.getBoundingClientRect();
container_rect = { width, height, top, left };
// We save the current plot size before we pop as it will fill the screen
const current_plot_size = {
width: PLOT._fullLayout.width,
height: PLOT._fullLayout.height,
};
// We have to save the pad data before popping so we can resize precisely
const pad = {};
pad.unpopped = getSizeData().container_pad;
CONTAINER.classList.toggle("popped-out", true);
pad.popped = getSizeData().container_pad;
// We do top and left based on the current rect
for (const key of ["top", "left"]) {
const start_val = target_container_size[key] ?? container_rect[key];
let offset = 0;
for (const kind of ["padding", "border"]) {
offset += pad.popped[kind][key] - pad.unpopped[kind][key];
}
CONTAINER.style[key] = start_val - offset + "px";
if (key === "left") {
CLIPBOARD_HEADER.style[key] = CONTAINER.style[key];
}
}
// We compute the width and height depending on eventual config data
const csz = computeContainerSize({
width:
target_plot_size.width ??
config_spans.width.config_value ??
current_plot_size.width,
height:
target_plot_size.height ??
config_spans.height.config_value ??
current_plot_size.height,
});
for (const key of ["width", "height"]) {
const val = target_container_size[key] ?? csz[key];
CONTAINER.style[key] = val + "px";
if (key === "width") {
CLIPBOARD_HEADER.style[key] = CONTAINER.style[key];
}
}
CLIPBOARD_HEADER.classList.toggle("hidden", false);
const controller = new AbortController();
document.addEventListener(
"mousedown",
(e) => {
if (e.target.closest(".plutoplotly-container") !== CONTAINER) {
unpop_container();
controller.abort();
return;
}
},
{ signal: controller.signal }
);
}
CONTAINER.popOut = popout_container;
function DualClick(single_func, dbl_func) {
let nclicks = 0;
return function (...args) {
nclicks += 1;
if (nclicks > 1) {
dbl_func(...args);
nclicks = 0;
} else {
delay(300).then(() => {
if (nclicks == 1) {
single_func(...args);
}
nclicks = 0;
});
}
};
}
// We remove the default download image button
plot_obj.config.modeBarButtonsToRemove = _.union(
plot_obj.config.modeBarButtonsToRemove,
["toImage"]
);
// We add the custom button to the modebar
plot_obj.config.modeBarButtonsToAdd = _.union(
plot_obj.config.modeBarButtonsToAdd,
[
{
name: "Copy PNG to Clipboard",
icon: {
height: 520,
width: 520,
path: "M280 64h40c35.3 0 64 28.7 64 64V448c0 35.3-28.7 64-64 64H64c-35.3 0-64-28.7-64-64V128C0 92.7 28.7 64 64 64h40 9.6C121 27.5 153.3 0 192 0s71 27.5 78.4 64H280zM64 112c-8.8 0-16 7.2-16 16V448c0 8.8 7.2 16 16 16H320c8.8 0 16-7.2 16-16V128c0-8.8-7.2-16-16-16H304v24c0 13.3-10.7 24-24 24H192 104c-13.3 0-24-10.7-24-24V112H64zm128-8a24 24 0 1 0 0-48 24 24 0 1 0 0 48z",
},
direction: "up",
click: DualClick(copyImageToClipboard, () => {
popout_container();
}),
},
{
name: "Download Image",
icon: Plotly.Icons.camera,
direction: "up",
click: DualClick(saveImageToFile, () => {
popout_container({ cl: "filesave" });
}),
},
]
);
function getOffsetData(el) {
let cs = window.getComputedStyle(el, null);
const odata = {
padding: {
left: parseFloat(cs.paddingLeft),
right: parseFloat(cs.paddingRight),
top: parseFloat(cs.paddingTop),
bottom: parseFloat(cs.paddingBottom),
width: parseFloat(cs.paddingLeft) + parseFloat(cs.paddingRight),
height: parseFloat(cs.paddingTop) + parseFloat(cs.paddingBottom),
},
border: {
left: parseFloat(cs.borderLeftWidth),
right: parseFloat(cs.borderRightWidth),
top: parseFloat(cs.borderTopWidth),
bottom: parseFloat(cs.borderBottomWidth),
width: parseFloat(cs.borderLeftWidth) + parseFloat(cs.borderRightWidth),
height: parseFloat(cs.borderTopWidth) + parseFloat(cs.borderBottomWidth),
}
};
if (el === PLOT) {
// For the PLOT we also want to take into account the offset
odata.offset = {
top: PLOT.offsetParent == CONTAINER ? PLOT.offsetTop : 0,
left: PLOT.offsetParent == CONTAINER ? PLOT.offsetLeft : 0,
}
}
return odata;
}
function getSizeData() {
const data = {
plot_pad: getOffsetData(PLOT),
plot_rect: PLOT.getBoundingClientRect(),
container_pad: getOffsetData(CONTAINER),
container_rect: CONTAINER.getBoundingClientRect(),
};
return data;
}
function computeContainerSize({ width, height }, sizeData = getSizeData()) {
const computed_size = computePlotSize(sizeData);
const offsets = computed_size.offsets;
const plot_data = {
width: width ?? computed_size.width,
height: height ?? computed_size.height,
};
return {
width: (width ?? computed_size.width) + offsets.width,
height: (height ?? computed_size.height) + offsets.height,
noChange: width == computed_size.width && height == computed_size.height,
}
}
// This function will change the container size so that the resulting plot will be matching the provided specs
function changeContainerSize({ width, height }, sizeData = getSizeData()) {
if (!CONTAINER.isPoppedOut()) {
console.log("Tried to change container size when not popped, ignoring");
return;
}
const csz = computeContainerSize({ width, height }, sizeData);
if (csz.noChange) {
console.log("Size is the same as current, ignoring");
return
}
// We are now going to set he width and height of the container
for (const key of ["width", "height"]) {
CONTAINER.style[key] = csz[key] + "px";
}
}
// We now create the function that will update the plot based on the values specified
function updateFromHeader() {
const header_data = {
height: config_spans.height.ui_value,
width: config_spans.width.ui_value,
};
changeContainerSize(header_data);
}
// We assign this function to the onblur event of width and height
if (firstRun) {
for (const container of Object.values(config_spans)) {
container.ui_span.onblur = (e) => {
container.ui_value = container.ui_span.textContent;
updateFromHeader();
};
}
}
// This function computes the plot size to use for relayout as a function of the container size
function computePlotSize(data = getSizeData()) {
// Remove Padding
const { container_pad, plot_pad, container_rect } = data;
const offsets = {
width:
plot_pad.padding.width +
plot_pad.border.width +
plot_pad.offset.left +
container_pad.padding.width +
container_pad.border.width,
height:
plot_pad.padding.height +
plot_pad.border.height +
plot_pad.offset.top +
container_pad.padding.height +
container_pad.border.height,
};
const sz = {
width: Math.round(container_rect.width - offsets.width),
height: Math.round(container_rect.height - offsets.height),
offsets,
};
return sz;
}
// Create the resizeObserver to make the plot even more responsive! :magic:
const resizeObserver = new ResizeObserver((entries) => {
const sizeData = getSizeData();
const {container_rect, container_pad} = sizeData;
let plot_size = computePlotSize(sizeData);
// We save the height in the PLOT object
PLOT.container_height = container_rect.height;
// We deal with some stuff if the container is poppped
CLIPBOARD_HEADER.style.width = container_rect.width + "px";
CLIPBOARD_HEADER.style.left = container_rect.left + "px";
config_spans.height.ui_value = plot_size.height;
config_spans.width.ui_value = plot_size.width;
/*
The addition of the invalid argument `plutoresize` seems to fix the problem with calling `relayout` simply with `{autosize: true}` as update breaking mouse relayout events tracking.
See https://github.com/plotly/plotly.js/issues/6156 for details
*/
let config = {
// If this is popped out, we ignore the original width/height
width: (CONTAINER.isPoppedOut() ? undefined : original_width) ?? plot_size.width,
height: (CONTAINER.isPoppedOut() ? undefined : original_height) ?? plot_size.height,
plutoresize: true,
};
Plotly.relayout(PLOT, config).then(() => {
if (remove_container_size && !CONTAINER.isPoppedOut()) {
// This is needed to avoid the first resize upon plot creation to already be without a fixed height
CONTAINER.style.height = "";
CONTAINER.style.width = "";
remove_container_size = false;
}
});
});
resizeObserver.observe(CONTAINER);
Plotly.react(PLOT, plot_obj).then(() => {
// Assign the Plotly event listeners
for (const [key, listener_vec] of Object.entries(plotly_listeners)) {
for (const listener of listener_vec) {
PLOT.on(key, listener)
}
}
// Assign the JS event listeners
for (const [key, listener_vec] of Object.entries(js_listeners)) {
for (const listener of listener_vec) {
PLOT.addEventListener(key, listener, {
signal: controller.signal
})
}
}
}
)
invalidation.then(() => {
// Remove all plotly listeners
PLOT.removeAllListeners()
// Remove all JS listeners
controller.abort()
// Remove the resizeObserver
resizeObserver.disconnect()
})
return CONTAINER
mimetext/htmlrootassigneelast_run_timestampA Mupersist_js_state·has_pluto_hook_features§cell_id$c94da551-06b2-4e2b-bf39-ceb5cb5c390cdepends_on_disabled_cells§runtime@published_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/d9e1c7748ec01469depends_on_skipped_cellsçerrored$3c300a2b-4139-4df0-906b-4cae3592cc2bqueued¤logsrunning¦outputbodyelementsprefixMatrix{Float32}elements3×250000 Matrix{Float32}:
0.333333 0.333333 0.333333 0.333333 … 0.333333 0.333333 0.333333 0.333333
0.333333 0.333333 0.333333 0.333333 0.333333 0.333333 0.333333 0.333333
0.333333 0.333333 0.333333 0.333333 0.333333 0.333333 0.333333 0.333333text/plain3×250000 Matrix{Float32}:
0.333333 0.333333 0.333333 0.333333 … 0.333333 0.333333 0.333333 0.333333
0.333333 0.333333 0.333333 0.333333 0.333333 0.333333 0.333333 0.333333
0.333333 0.333333 0.333333 0.333333 0.333333 0.333333 0.333333 0.333333text/plain3×250000 Matrix{Float32}:
0.333333 0.333333 0.333333 0.333333 … 0.333333 0.333333 0.333333 0.333333
0.333333 0.333333 0.333333 0.333333 0.333333 0.333333 0.333333 0.333333
0.333333 0.333333 0.333333 0.333333 0.333333 0.333333 0.333333 0.333333text/plaintypeArrayprefix_shortobjectide832ac3c028db2d1!application/vnd.pluto.tree+objectprefixVector{Float32}elementsprefixFloat32elements-1063.58text/plain-1063.58text/plain-1063.58text/plain-1063.58text/plain-1063.58text/plainmore А0.0text/plaintypeArrayprefix_shortobjectid32fdd2619824105f!application/vnd.pluto.tree+objectprefixFloat32elements-38.0text/plain-38.0text/plain-38.0text/plain-38.0text/plain-38.0text/plainmore А0.0text/plaintypeArrayprefix_shortobjectidc3b819616d78f80c!application/vnd.pluto.tree+objectprefixFloat32elements-38.0text/plain-38.0text/plain-38.0text/plain-38.0text/plain-38.0text/plainmore А0.0text/plaintypeArrayprefix_shortobjectid3ad592cda98ba027!application/vnd.pluto.tree+objecttypeArrayprefix_shortobjectid2fa1eb5b81caa68!application/vnd.pluto.tree+objecttypeTupleobjectid861dfd67228ab799mime!application/vnd.pluto.tree+objectrootassignee"const mountaincar_policy_iterationlast_run_timestampA %persist_js_state·has_pluto_hook_features§cell_id$3c300a2b-4139-4df0-906b-4cae3592cc2bdepends_on_disabled_cells§runtime cȵpublished_object_keysdepends_on_skipped_cellsçerrored$8a5d9e3d-e8ef-4cea-8cd8-6975f797d7bdqueued¤logsrunning¦outputbody?plot_mountaincar_action_values (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA 9persist_js_state·has_pluto_hook_features§cell_id$8a5d9e3d-e8ef-4cea-8cd8-6975f797d7bddepends_on_disabled_cells§runtime*hpublished_object_keysdepends_on_skipped_cellsçerrored$fbf1c64f-1979-4384-a8c6-dc7875174d1fqueued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampA persist_js_state·has_pluto_hook_features§cell_id$fbf1c64f-1979-4384-a8c6-dc7875174d1fdepends_on_disabled_cells§runtime #published_object_keysdepends_on_skipped_cells§errored$dbde6c7c-a0ff-41bc-9a26-ffd38561a5efqueued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA .ܰpersist_js_state·has_pluto_hook_features§cell_id$dbde6c7c-a0ff-41bc-9a26-ffd38561a5efdepends_on_disabled_cells§runtime DYpublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/ebf54896bbfbe871depends_on_skipped_cellsçerrored$0714a1cf-9288-4f1e-ba72-d82608704d69queued¤logslinemsg3Warning: Episode 2 did not conclude in 100000 stepstext/plaincell_id$0714a1cf-9288-4f1e-ba72-d82608704d69kwargsidMain_workspace#2_e6615ae1file/home/runner/work/Reinforcement-Learning-Sutton-Barto-Exercise-Solutions/Reinforcement-Learning-Sutton-Barto-Exercise-Solutions/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#06834750-cc3a-468a-b0c2-81349c288a33group/Chapter_10_On_policy_Control_with_ApproximationlevelInfolinemsg3Warning: Episode 4 did not conclude in 100000 stepstext/plaincell_id$0714a1cf-9288-4f1e-ba72-d82608704d69kwargsidMain_workspace#2_e6615ae1file/home/runner/work/Reinforcement-Learning-Sutton-Barto-Exercise-Solutions/Reinforcement-Learning-Sutton-Barto-Exercise-Solutions/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#06834750-cc3a-468a-b0c2-81349c288a33group/Chapter_10_On_policy_Control_with_ApproximationlevelInfolinemsg3Warning: Episode 8 did not conclude in 100000 stepstext/plaincell_id$0714a1cf-9288-4f1e-ba72-d82608704d69kwargsidMain_workspace#2_e6615ae1file/home/runner/work/Reinforcement-Learning-Sutton-Barto-Exercise-Solutions/Reinforcement-Learning-Sutton-Barto-Exercise-Solutions/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#06834750-cc3a-468a-b0c2-81349c288a33group/Chapter_10_On_policy_Control_with_ApproximationlevelInfolinemsg6Warning: Episode 1835 did not conclude in 100000 stepstext/plaincell_id$0714a1cf-9288-4f1e-ba72-d82608704d69kwargsidMain_workspace#2_e6615ae1file/home/runner/work/Reinforcement-Learning-Sutton-Barto-Exercise-Solutions/Reinforcement-Learning-Sutton-Barto-Exercise-Solutions/Chapter-10/Chapter_10_On_policy_Control_with_Approximation.jl#==#06834750-cc3a-468a-b0c2-81349c288a33group/Chapter_10_On_policy_Control_with_ApproximationlevelInforunning¦outputbodyelementsvalue_functionq̂text/plainπ_greedyπ_greedytext/plainπ_ϵ_greedyπ_ϵ_greedytext/plainstep_historyprefixInt64elements9104text/plain100000text/plain10505text/plain100000text/plain1906text/plain2338text/plain11287text/plain100000text/plain 1012text/plainmore1777text/plaintypeArrayprefix_shortobjectid50d78950189388b9!application/vnd.pluto.tree+objectreward_historyprefixFloat32elements-9104.0text/plain-100000.0text/plain-10505.0text/plain-100000.0text/plain-1906.0text/plain-2338.0text/plain-11287.0text/plain-100000.0text/plain -1012.0text/plainmore-1777.0text/plaintypeArrayprefix_shortobjectid4c155a078f0ea674!application/vnd.pluto.tree+objecttypeNamedTupleobjectid7b1a6da5c15d218cmime!application/vnd.pluto.tree+objectrootassigneemc_testlast_run_timestampA +mҰpersist_js_state·has_pluto_hook_features§cell_id$0714a1cf-9288-4f1e-ba72-d82608704d69depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cellsçerrored$f7410fe7-e3d8-4047-8fa7-f076476e9d3aqueued¤logsrunning¦outputbody\
Example: Semi-gradient Q-learning on Mountain Car Task
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.
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.
mimetext/htmlrootassigneelast_run_timestampA zk{persist_js_state·has_pluto_hook_features§cell_id$e1abf8c7-06b8-4cd5-b557-1d187004bdf1depends_on_disabled_cells§runtime /published_object_keysdepends_on_skipped_cells§errored$d66cd124-7111-401a-a3e8-1059b31c6db7queued¤logsrunning¦outputbodyDcreate_differential_mountaincar_mdp (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA V2persist_js_state·has_pluto_hook_features§cell_id$d66cd124-7111-401a-a3e8-1059b31c6db7depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$b76551e0-c027-4682-b5ae-bba7ea2b987aqueued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA 3 persist_js_state·has_pluto_hook_features§cell_id$b76551e0-c027-4682-b5ae-bba7ea2b987adepends_on_disabled_cells§runtimevpublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/5784a7652a02b56cdepends_on_skipped_cellsçerrored$d8d5db17-d89c-47db-b258-6ad1635478b7queued¤logsrunning¦outputbody@plot_mountaincar_action_values (generic function with 2 methods)mimetext/plainrootassigneelast_run_timestampA :ekpersist_js_state·has_pluto_hook_features§cell_id$d8d5db17-d89c-47db-b258-6ad1635478b7depends_on_disabled_cells§runtime DEpublished_object_keysdepends_on_skipped_cellsçerrored$78087a57-33a0-4581-81de-926476090931queued¤logsrunning¦outputbodyj
mimetext/htmlrootassigneelast_run_timestampA utpersist_js_state·has_pluto_hook_features§cell_id$35d59eae-77fd-11ef-2790-35dd5a834060depends_on_disabled_cells§runtime 2published_object_keysdepends_on_skipped_cells§errored$5f8b0254-88f4-4d19-ade1-8e7c40941b43queued¤logsrunning¦outputbody4update_parameters! (generic function with 6 methods)mimetext/plainrootassigneelast_run_timestampA 2I
persist_js_state·has_pluto_hook_features§cell_id$5f8b0254-88f4-4d19-ade1-8e7c40941b43depends_on_disabled_cells§runtime M,published_object_keysdepends_on_skipped_cells§errored$3b66c97b-ebad-4d13-987c-ac0172b349d1queued¤logsrunning¦outputbodyKmountaincar_differential_dp_nonlinear_test (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA [@hpersist_js_state·has_pluto_hook_features§cell_id$3b66c97b-ebad-4d13-987c-ac0172b349d1depends_on_disabled_cells§runtime .j published_object_keysdepends_on_skipped_cellsçerrored$546a775e-d3c9-4693-9f64-d4c47a84fb9fqueued¤logsrunning¦outputbody,figure_10_5 (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA C?persist_js_state·has_pluto_hook_features§cell_id$546a775e-d3c9-4693-9f64-d4c47a84fb9fdepends_on_disabled_cells§runtime
pݵpublished_object_keysdepends_on_skipped_cellsçerrored$6351304f-50ac-4755-86e1-cd4680f2d803queued¤logsrunning¦outputbody
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:
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.
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 ) = r(s, a) + \gamma \sum_{s^\prime}p(s^\prime \vert s, a) \hat v(s^\prime)$$
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 \left [ r(s, a) + \gamma \sum_{s^\prime}p(s^\prime \vert s, a) 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.
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.
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.
The objective that uses discounting here is $J(\pi) = \sum_s \mu_\pi (s) v_\pi^\gamma(s)$ rather than the original goal of getting the maximum state values for every state. So this derivation is really only suited to the approximation setting and the altered objective. If we are in the tabular objective, then we have access to the policy improvmeent theorem and can guarantee a maximum value for every state, although none of those values may correspond to the average reward. We can see the example below that favoring this objective leads to a worse value function and policy which is not optimal given that discount rate. The only reason we consider it here is because in the case of approximation we are forced into using this objective. If we use an approximation method instead which does separate each state, then updates to one state will not affect the others and the optimal policy will be found anyway. The sampling according to the steady state distribution only affects the optimization result when multiple states are affected by a single update.
If we discretize the positions and velocities then we can transform this into a tabular problem. The number of states will be NxM where N and M are the number of distinct values for position and velocity respectively. As N and M approach infinity this problem will approach the original MDP, so we can study the limiting behavior of the optimal policy and value function using tabular methods that are guaranteed to converge.
mimetext/htmlrootassigneelast_run_timestampA y6epersist_js_state·has_pluto_hook_features§cell_id$d291541d-ddba-4b71-a4eb-37fef758b71bdepends_on_disabled_cells§runtime M!published_object_keysdepends_on_skipped_cells§errored$e2cd69c5-eda7-4897-9e64-0adf940d4d96queued¤logsrunning¦outputbodyپmimetext/htmlrootassigneelast_run_timestampA ,x persist_js_state·has_pluto_hook_features§cell_id$e2cd69c5-eda7-4897-9e64-0adf940d4d96depends_on_disabled_cells§runtime.published_object_keysdepends_on_skipped_cellsçerrored$cbac1927-b087-4c4c-98ae-6aa5f0b824adqueued¤logsrunning¦outputbodyelementsvalue_functionq̂text/plainπ_greedyπ_greedytext/plainreward_historyprefixFloat32elements-44453.0text/plain-18121.0text/plain-15046.0text/plain-11091.0text/plain-4345.0text/plain-7453.0text/plain-24648.0text/plain-8718.0text/plain -12602.0text/plainmore蒦-502.0text/plaintypeArrayprefix_shortobjectidc99722a5779f7378!application/vnd.pluto.tree+objectstep_historyprefixInt64elements44453text/plain62574text/plain77620text/plain88711text/plain93056text/plain100509text/plain125157text/plain133875text/plain 146477text/plainmore蒧1316688text/plaintypeArrayprefix_shortobjectidec6e43b33d4db63f!application/vnd.pluto.tree+objectparameter_historyprefixVector{Vector{Float32}}elementstypeArrayprefix_shortobjectide32f07312acf3497!application/vnd.pluto.tree+objecttypeNamedTupleobjectid300a9b2f53769a28mime!application/vnd.pluto.tree+objectrootassigneelast_run_timestampA w!persist_js_state·has_pluto_hook_features§cell_id$cbac1927-b087-4c4c-98ae-6aa5f0b824addepends_on_disabled_cells§runtimeYUpublished_object_keysdepends_on_skipped_cellsçerrored$f56743d1-d681-4bcf-b1bb-c4ef78a75180queued¤logsrunning¦outputbody i
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)
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:
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.
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.
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.
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.
mimetext/htmlrootassigneelast_run_timestampA yApersist_js_state·has_pluto_hook_features§cell_id$31fb07d2-1c34-44ec-b932-a598e78ec8dcdepends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$5db29488-a150-42ee-aedb-380a3a4fd548queued¤logsrunning¦outputbody@plot_mountaincar_action_values (generic function with 3 methods)mimetext/plainrootassigneelast_run_timestampA vpersist_js_state·has_pluto_hook_features§cell_id$5db29488-a150-42ee-aedb-380a3a4fd548depends_on_disabled_cells§runtime -published_object_keysdepends_on_skipped_cellsçerrored$39c63495-36c3-4e62-b8fb-36865f2c6243queued¤logsrunning¦outputbodyR
mimetext/htmlrootassigneelast_run_timestampA l@persist_js_state·has_pluto_hook_features§cell_id$cf00a316-38e3-4423-9909-d5ffbd7c0b06depends_on_disabled_cells§runtime35published_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/fa851210dd7f4501depends_on_skipped_cellsçerrored$c85033e1-3ee6-42ad-9ef0-144ce6238ce4queued¤logsrunning¦outputbody-smooth_error (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA Upersist_js_state·has_pluto_hook_features§cell_id$c85033e1-3ee6-42ad-9ef0-144ce6238ce4depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cellsçerrored$f6e08689-040f-4565-9dfb-e9a65d1c1f18queued¤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.
mimetext/htmlrootassigneelast_run_timestampA xpersist_js_state·has_pluto_hook_features§cell_id$dc2cffeb-9adf-4956-afa3-ac82af377c59depends_on_disabled_cells§runtime ȵpublished_object_keysdepends_on_skipped_cells§errored$4a5805f0-0cff-4e30-8305-304340734232queued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA bpersist_js_state·has_pluto_hook_features§cell_id$4a5805f0-0cff-4e30-8305-304340734232depends_on_disabled_cells§runtimeYVpublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/7a478c9aae405986depends_on_skipped_cellsçerrored$fc0b88f3-fbf9-450d-b770-b34357ffad49queued¤logsrunning¦outputbody4compute_sarsa_value (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA wypersist_js_state·has_pluto_hook_features§cell_id$fc0b88f3-fbf9-450d-b770-b34357ffad49depends_on_disabled_cells§runtime Kpublished_object_keysdepends_on_skipped_cells§errored$50f6ff51-d81b-4e97-9f8a-0daf03af7192queued¤logsrunning¦outputbodyB
Monte Carlo Gradient Control
mimetext/htmlrootassigneelast_run_timestampA 0persist_js_state·has_pluto_hook_features§cell_id$50f6ff51-d81b-4e97-9f8a-0daf03af7192depends_on_disabled_cells§runtime ֎published_object_keysdepends_on_skipped_cells§errored$12fa7b75-d13f-4a16-8562-1142002f3f3fqueued¤logsrunning¦outputbody?semi_gradient_differential_dp! (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA persist_js_state·has_pluto_hook_features§cell_id$12fa7b75-d13f-4a16-8562-1142002f3f3fdepends_on_disabled_cells§runtime n۵published_object_keysdepends_on_skipped_cells§errored$5cbaeb8e-bc02-47c9-87b4-57df554cea9dqueued¤logsrunning¦outputbodyj
Approximation is not really needed here since we have a small number of states, but we can always use state aggregation where each state is assigned a unique group. Here I use a matrix style indexing for the states where the number of free servers and the priority index are used and then converted into a linear index.
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.
mimetext/htmlrootassigneelast_run_timestampA zpersist_js_state·has_pluto_hook_features§cell_id$d6ad1ff1-8fbf-4799-8b1b-ae1e3ce88c5bdepends_on_disabled_cells§runtime *published_object_keysdepends_on_skipped_cells§errored$c799ffe4-f4af-487d-b557-8b50d13632b7queued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA Qpersist_js_state·has_pluto_hook_features§cell_id$c799ffe4-f4af-487d-b557-8b50d13632b7depends_on_disabled_cells§runtimeʵpublished_object_keys4b9565ce0-38f6-11f0-350f-a762f362895d/b7e07ca03327390depends_on_skipped_cellsçerrored$b4af8d87-a6e5-4e09-92b4-b07757f58f7fqueued¤logsrunning¦outputbodyFrun_access_control_differential_sarsa (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA %spersist_js_state·has_pluto_hook_features§cell_id$b4af8d87-a6e5-4e09-92b4-b07757f58f7fdepends_on_disabled_cells§runtime H
published_object_keysdepends_on_skipped_cellsçerrored$0e66a941-1ec1-4d3b-b064-e5f25cc93bafqueued¤logsrunning¦outputbody=
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
Keep in mind we only care about the case where $\gamma = 1$, so we can enforce that now and see if the values exist. Replacing terms to isolate $v_A$ yields:
As the discount rate approaches 1, this solution should converge to the average reward solution shown below. Numerically this is challenging because the values themselves diverge so there might not be enough precision to arrive at an answer. If the priority payments are considered money, this solution is more desireable if the value of γ actually reflects some real time value of the money like an interest rate.
Solving Mountain Car Tabular Problem with Value Iteration
mimetext/htmlrootassigneelast_run_timestampA yjMpersist_js_state·has_pluto_hook_features§cell_id$72f575ee-d656-4af6-bf78-aab42bf1debddepends_on_disabled_cells§runtime ppublished_object_keysdepends_on_skipped_cells§errored$2c620fe4-2f62-40f8-a666-8dced1e0b84aqueued¤logsrunning¦outputbody?run_linear_semi_gradient_sarsa (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA '_persist_js_state·has_pluto_hook_features§cell_id$2c620fe4-2f62-40f8-a666-8dced1e0b84adepends_on_disabled_cells§runtime nHpublished_object_keysdepends_on_skipped_cells§errored$708164fd-93ea-4720-ad6d-22e1c297c22aqueued¤logsrunning¦outputbody[
Distributional Transition for Access Control Task
Even though the problem is stochastic, we can calculate all of the probabilities for a step transition. The main challenge is using the 6% probability that an occupied server is freed on each step to compute the probabilities of transition states.
mimetext/htmlrootassigneelast_run_timestampA Ppersist_js_state·has_pluto_hook_features§cell_id$708164fd-93ea-4720-ad6d-22e1c297c22adepends_on_disabled_cells§runtime ,published_object_keysdepends_on_skipped_cells§errored$bd1f42e5-94cc-4aef-b82a-9bffd1c951d8queued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA 丰persist_js_state·has_pluto_hook_features§cell_id$bd1f42e5-94cc-4aef-b82a-9bffd1c951d8depends_on_disabled_cells§runtime gpublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/9a070c55bca67bffdepends_on_skipped_cellsçerrored$5a9bcf45-a04b-4a81-b825-9891021c8a15queued¤logsrunning¦outputbody6get_equivalent_values (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA V7persist_js_state·has_pluto_hook_features§cell_id$5a9bcf45-a04b-4a81-b825-9891021c8a15depends_on_disabled_cells§runtime &Mpublished_object_keysdepends_on_skipped_cellsçerrored$b8c031ca-7995-4501-a1e3-df3f34e5f0daqueued¤logsrunning¦outputbody
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)$:
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 steady-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
This is known as the differential return, and the 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 - \max_{\pi}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:
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
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.
mimetext/htmlrootassigneelast_run_timestampA I#persist_js_state·has_pluto_hook_features§cell_id$a92db2a7-3a6c-4328-a2a8-cb74d2e671e9depends_on_disabled_cells§runtimeoQpublished_object_keysdepends_on_skipped_cellsçerrored$014339eb-5b23-4ac5-a551-8eeb2238366fqueued¤logsrunning¦outputbody5access_control_step (generic function with 2 methods)mimetext/plainrootassigneelast_run_timestampA spersist_js_state·has_pluto_hook_features§cell_id$014339eb-5b23-4ac5-a551-8eeb2238366fdepends_on_disabled_cells§runtime (Zpublished_object_keysdepends_on_skipped_cells§errored$49249ac1-8964-4afc-89f2-3cd4d4322cc2queued¤logsrunning¦outputbody
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_timestampA yذpersist_js_state·has_pluto_hook_features§cell_id$1a5acfb0-3b35-41b1-98f8-ffce941c587fdepends_on_disabled_cells§runtime ϶published_object_keysdepends_on_skipped_cells§errored$7bc49107-9de5-4985-8750-979f36b3aa81queued¤logsrunning¦outputbody1π_mountain_car2 (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA Jpersist_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¦outputbody
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:
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.
mimetext/htmlrootassigneelast_run_timestampA -:persist_js_state·has_pluto_hook_features§cell_id$32b3c5b4-cdb8-43be-a398-6e158254c4a7depends_on_disabled_cells§runtime)5published_object_keysdepends_on_skipped_cellsçerrored$d3ba78fa-f032-4bb9-9359-ef3bcff2252dqueued¤logsrunning¦outputbodyDmountaincar_fcann_differential_test (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA vpersist_js_state·has_pluto_hook_features§cell_id$d3ba78fa-f032-4bb9-9359-ef3bcff2252ddepends_on_disabled_cells§runtime ,published_object_keysdepends_on_skipped_cellsçerrored$742100ba-c38e-4840-8988-40990039b527queued¤logsrunning¦outputbody9setup_mountain_car_tiles (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA persist_js_state·has_pluto_hook_features§cell_id$742100ba-c38e-4840-8988-40990039b527depends_on_disabled_cells§runtime !*published_object_keysdepends_on_skipped_cellsçerrored$2f0d0a71-c65b-4aa0-a493-e7cdccd901ebqueued¤logsrunning¦outputbody8plot_mountaincar_values (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA Zrpersist_js_state·has_pluto_hook_features§cell_id$2f0d0a71-c65b-4aa0-a493-e7cdccd901ebdepends_on_disabled_cells§runtime 98published_object_keysdepends_on_skipped_cellsçerrored$a3cf270b-b309-44f0-9972-bd84228bcf17queued¤logsrunning¦outputbody /
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
mimetext/htmlrootassigneelast_run_timestampA v\persist_js_state·has_pluto_hook_features§cell_id$a3cf270b-b309-44f0-9972-bd84228bcf17depends_on_disabled_cells§runtime Jpublished_object_keysdepends_on_skipped_cells§errored$b9125c5b-01d6-451e-84b5-a419e38425b5queued¤logsrunning¦outputbody6π_mountain_car_fcann (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA ްpersist_js_state·has_pluto_hook_features§cell_id$b9125c5b-01d6-451e-84b5-a419e38425b5depends_on_disabled_cells§runtime apublished_object_keysdepends_on_skipped_cellsçerrored$063e6f33-8b65-463c-a96f-5411f0ba0326queued¤logsrunning¦outputbodyl
mimetext/htmlrootassigneelast_run_timestampA x)persist_js_state·has_pluto_hook_features§cell_id$57a6510f-bd42-4d1d-a550-d1442f79569fdepends_on_disabled_cells§runtime |ŵpublished_object_keysdepends_on_skipped_cells§errored$b0761704-5447-4e64-8270-708d9dccef60queued¤logsrunning¦outputbody2semi_gradient_dp! (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA 9upersist_js_state·has_pluto_hook_features§cell_id$b0761704-5447-4e64-8270-708d9dccef60depends_on_disabled_cells§runtime hMepublished_object_keysdepends_on_skipped_cells§errored$350e057e-154f-4d0b-91fb-ffde9cc9059fqueued¤logsrunning¦outputbody?figure_10_5_tabular_discounted (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA 44persist_js_state·has_pluto_hook_features§cell_id$350e057e-154f-4d0b-91fb-ffde9cc9059fdepends_on_disabled_cells§runtime Rӌpublished_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?
mimetext/htmlrootassigneelast_run_timestampA }persist_js_state·has_pluto_hook_features§cell_id$a6c5ec28-b2d5-4893-a118-95c1318d1f7fdepends_on_disabled_cells§runtime Vipublished_object_keysdepends_on_skipped_cells§errored$c4ba34b5-e657-4b75-b853-0a2df081e34bqueued¤logsrunning¦outputbodyBaccess_control_step_distribution (generic function with 2 methods)mimetext/plainrootassigneelast_run_timestampA gӰpersist_js_state·has_pluto_hook_features§cell_id$c4ba34b5-e657-4b75-b853-0a2df081e34bdepends_on_disabled_cells§runtime F'published_object_keysdepends_on_skipped_cells§errored$89288ce6-11e8-41f3-b32d-e19edee7db33queued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA persist_js_state·has_pluto_hook_features§cell_id$89288ce6-11e8-41f3-b32d-e19edee7db33depends_on_disabled_cells§runtimekpublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/df1d5a1219704784depends_on_skipped_cellsçerrored$96548352-cd4d-4448-8312-ed10057f4359queued¤logsrunning¦outputbody4update_parameters! (generic function with 8 methods)mimetext/plainrootassigneelast_run_timestampA x$persist_js_state·has_pluto_hook_features§cell_id$96548352-cd4d-4448-8312-ed10057f4359depends_on_disabled_cells§runtime dpublished_object_keysdepends_on_skipped_cells§errored$ed1bd92c-8cc7-457f-9692-a10a9487c953queued¤logsrunning¦outputbodyٴ
mimetext/htmlrootassigneelast_run_timestampA ?1persist_js_state·has_pluto_hook_features§cell_id$ed1bd92c-8cc7-457f-9692-a10a9487c953depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cellsçerrored$53c5558b-e713-4c72-bdf8-e162c3892e6fqueued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA 1persist_js_state·has_pluto_hook_features§cell_id$53c5558b-e713-4c72-bdf8-e162c3892e6fdepends_on_disabled_cells§runtimeRpublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/ac0fecc71a5e2a8edepends_on_skipped_cellsçerrored$c9759bd9-ec9b-47a1-9080-a7fc332be565queued¤logsrunning¦outputbodyGdifferential_semi_gradient_q_learning! (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA Npersist_js_state·has_pluto_hook_features§cell_id$c9759bd9-ec9b-47a1-9080-a7fc332be565depends_on_disabled_cells§runtime Gpublished_object_keysdepends_on_skipped_cells§errored$953907cd-9926-4478-99b3-da7068118c22queued¤logsrunning¦outputbodyLgradient_monte_carlo_action_episode_update! (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA Spersist_js_state·has_pluto_hook_features§cell_id$953907cd-9926-4478-99b3-da7068118c22depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$278a26ac-c48f-4e18-93bb-706a4634c8c0queued¤logsrunning¦outputbody
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.
mimetext/htmlrootassigneelast_run_timestampA x@İpersist_js_state·has_pluto_hook_features§cell_id$278a26ac-c48f-4e18-93bb-706a4634c8c0depends_on_disabled_cells§runtime @bpublished_object_keysdepends_on_skipped_cells§errored$8b7e1031-9864-439c-86eb-11aa08f53b90queued¤logsrunning¦outputbodymountaincar_differential_test (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA persist_js_state·has_pluto_hook_features§cell_id$49e43d51-05d6-415b-a685-76e50904c5bcdepends_on_disabled_cells§runtime !published_object_keysdepends_on_skipped_cellsçerrored$0f958535-6b18-46de-a1ba-81f64c217ee0queued¤logsrunning¦outputbody5mountaincar_fcann_dp (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA fpersist_js_state·has_pluto_hook_features§cell_id$0f958535-6b18-46de-a1ba-81f64c217ee0depends_on_disabled_cells§runtime 9published_object_keysdepends_on_skipped_cellsçerrored$44d43dbf-fe32-438e-b89d-c677bbc35893queued¤logsrunning¦outputbody
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.
Since both bounds are 0, the limit must be 0, resulting in the following expression for the average reward:
$$r(\pi) = \frac{1}{2}[1 + 0] = \frac{1}{2}$$
The differetial value function is defined as: $v_\pi(s) \doteq \mathbb{E}_\pi[G_t \vert S_t = s]$ where $G_t \doteq R_{t+1} - r(\pi) + R_{t+2} - r(\pi) + R_{t+3} - r(\pi) + \cdots$ In this example, we know that $r(\pi) = 0.5$, but the reward sequence is periodic meaning the expected value of the differential return depends on $t$:
In particular, the sum does not converge since the values alternate and do not approach a single value. Thus the differential value function is not well defined. Therefore, we must consider the alternative definition:
This expression is identical to the original definition except for the presence of a discount rate in the sum which ensures the existence of a well defined value. By taking the limit as $\gamma \rightarrow 1$, the impact of the discount rate can be eliminated after the calculation is done.
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$
mimetext/htmlrootassigneelast_run_timestampA ~Fpersist_js_state·has_pluto_hook_features§cell_id$44d43dbf-fe32-438e-b89d-c677bbc35893depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$b3658e4d-ee8e-45cd-906a-06dd512a6921queued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA persist_js_state·has_pluto_hook_features§cell_id$b3658e4d-ee8e-45cd-906a-06dd512a6921depends_on_disabled_cells§runtimepublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/9ae29a8d0d0beaefdepends_on_skipped_cellsçerrored$00e7783f-7f17-4944-a085-ea87509cd75aqueued¤logsrunning¦outputbody;run_fcann_semi_gradient_dp (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA }$persist_js_state·has_pluto_hook_features§cell_id$00e7783f-7f17-4944-a085-ea87509cd75adepends_on_disabled_cells§runtime g
mpublished_object_keysdepends_on_skipped_cells§errored$5be866c3-0fb2-4d1f-9c31-b85aba332905queued¤logsrunning¦outputbody:semi_gradient_q_learning! (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA *
persist_js_state·has_pluto_hook_features§cell_id$5be866c3-0fb2-4d1f-9c31-b85aba332905depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$5f9a2231-8c4a-4519-adbe-a0dd92838ba4queued¤logsrunning¦outputbody`
Necessary Conditions for Average Reward Setting
Continuing task (i.e. no terminal state)
The average reward exists: $\lim_{h \rightarrow \infty} \frac{1}{h} \sum_{t=1}^h \mathbb{E}[R_t \mid S_0, A_{0:t-1} \sim \pi]$
To be useful, this limit should depend on the policy
If the reward is -1 per step for example, the average reward will always be -1 regardless of the policy
The long term limit of expected value of the reward exists: $\lim_{t \rightarrow \infty} \mathbb{E}[R_t \mid S_0, A_{0:t-1} \sim \pi]$
This limit only exists if the expected reward approaches a single value in the limit of infinite time away from some initial state $S_0$
If the limit exists, then in the limit, the sum above will be dominated by this value as more terms are added, wiping out any impact from the early rewards in the sequence
A repeating reward sequence would violate this assumption since the expected value of $R_t$ would be a specific value depending on the time step
The steady-state distribution exists and is independent of $S_0$: $\mu_\pi(s) \doteq \lim_{t \rightarrow \infty} \Pr \{ S_t = s \mid A_{0:t-1} \sim \pi \}$
In this case we can express $r(\pi)$ without reference to a starting state and simply use the policy, transition function, and steady-state distribution
The expected value of the reward must also not depend on $S_0$ as well
If either distribution or expected value exist, but depend on the starting state, then we cannot use the Bellman expressions with the average reward
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:
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.
mimetext/htmlrootassigneelast_run_timestampA 2persist_js_state·has_pluto_hook_features§cell_id$2d7679ad-a9b3-448b-a4bc-7e5b9bce6adbdepends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$a4c6a5c0-29c5-440c-bf86-20d0f881ee06queued¤logsrunning¦outputbody6update_action_values! (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA *?persist_js_state·has_pluto_hook_features§cell_id$a4c6a5c0-29c5-440c-bf86-20d0f881ee06depends_on_disabled_cells§runtime +?published_object_keysdepends_on_skipped_cells§errored$4154e827-6d0b-4b94-9f14-64baa85739afqueued¤logsrunning¦outputbody
Discounted Setting Connection to Average Reward
Consider an environment with a reset state and a goal state, like a gridworld. As a continuing problem, this can be formulated with a reward of 0 for every step and some positive reward r at the goal. If this problem is solved in the average reward setting, then the policy would minimize the expected number of steps to reach the goal from any state including the reset state.
What if instead it is treated as an episodic problem with a reward of -1 per step and a termination condition at the goal. In the discounted setting, we can define the value function of a state $s$ and a policy $\pi$ as $v_\pi(s) = -\mathbb{E}_\pi \left [ \sum_{k=0}^{N_s - 1} \gamma^k \right ]$ where $N_s$ is the number of steps until terminationfrom state $s$. For an arbitrarily policy and environment, there could be some distribution over $N_s$. In the undiscounted case where $\gamma = 1$, the value at each state is simply: $v_\pi(s) = -\mathbb{E}_\pi [N_s]$ which is also minus the average number of steps until termination. So regardless of the distribution, maximizing the value is equivalent to minimizing the expected number of steps until termination. This policy will be equivalent to that found in the average reward setting.
Now consider the discounted case with some $0 \le \gamma \lt 1$. $v_\pi(s) = -\mathbb{E}_\pi \left [ \sum_{k=0}^{N_s - 1} \gamma^k \right ] = - \mathbb{E}_\pi \left [ \frac{\gamma^{N_s} - 1}{\gamma - 1} \right ] = \frac{1 - \mathbb{E}_\pi [ \gamma ^{N_s}]}{\gamma - 1}$ where now the value depends on the average of $\gamma^{N_s}$ rather than $N_s$. One notable difference is that in the undiscounted case, larger values of $N_s$ contribute negatively to the value in an unbounded fashion. In the discounted case, $0 \le \gamma \lt 1, N_s \rightarrow \infty \implies \gamma^{N_s} \rightarrow 0 \implies v_\pi(s) \rightarrow \frac{1}{1-\gamma}$. In the plot below, we can see this limiting value come into play especially for smaller $\gamma$ so that the negative contribution from very large $N_s$ is capped. Therefore, it is always beneficial to symetrically add probabilities of finishing in a shorter time and the correspondingly longer time on the other side of it.
mimetext/htmlrootassigneelast_run_timestampA {persist_js_state·has_pluto_hook_features§cell_id$4154e827-6d0b-4b94-9f14-64baa85739afdepends_on_disabled_cells§runtime ,published_object_keysdepends_on_skipped_cells§errored$425fe768-c7bb-4d3e-87e6-47fa052ba612queued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA Dpersist_js_state·has_pluto_hook_features§cell_id$425fe768-c7bb-4d3e-87e6-47fa052ba612depends_on_disabled_cells§runtime {jpublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/ff448b2a8723c46fdepends_on_skipped_cellsçerrored$06834750-cc3a-468a-b0c2-81349c288a33queued¤logsrunning¦outputbody>gradient_monte_carlo_control! (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA "persist_js_state·has_pluto_hook_features§cell_id$06834750-cc3a-468a-b0c2-81349c288a33depends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$1054cfa3-9f58-4a93-a318-c2d21cf23220queued¤logsrunning¦outputbody=show_mountaincar_trajectory (generic function with 2 methods)mimetext/plainrootassigneelast_run_timestampA ;5߰persist_js_state·has_pluto_hook_features§cell_id$1054cfa3-9f58-4a93-a318-c2d21cf23220depends_on_disabled_cells§runtime f published_object_keysdepends_on_skipped_cellsçerrored$8ed6f8fd-8574-4d5a-9964-ce8a32629c6fqueued¤logsrunning¦outputbody=compute_expected_sarsa_value (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA }persist_js_state·has_pluto_hook_features§cell_id$8ed6f8fd-8574-4d5a-9964-ce8a32629c6fdepends_on_disabled_cells§runtime
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:
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.
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}$$
mimetext/htmlrootassigneelast_run_timestampA |dpersist_js_state·has_pluto_hook_features§cell_id$0c7f5742-6c51-4c6a-b67f-217163935ba5depends_on_disabled_cells§runtime אpublished_object_keysdepends_on_skipped_cells§errored$c697e0b6-d3e4-4f5f-96e9-b9486c9d7efcqueued¤logsrunning¦outputbody5fill_action_values! (generic function with 2 methods)mimetext/plainrootassigneelast_run_timestampA ?Lpersist_js_state·has_pluto_hook_features§cell_id$c697e0b6-d3e4-4f5f-96e9-b9486c9d7efcdepends_on_disabled_cells§runtime Wpublished_object_keysdepends_on_skipped_cells§errored$9fb5dace-a799-4424-bcb3-8542e508dd4bqueued¤logsrunning¦outputbodyM
mimetext/htmlrootassigneelast_run_timestampA Ypersist_js_state·has_pluto_hook_features§cell_id$9fb5dace-a799-4424-bcb3-8542e508dd4bdepends_on_disabled_cells§runtime'B]published_object_keysdepends_on_skipped_cellsçerrored$c1388562-0708-4a6a-acfe-927413dab5d2queued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA persist_js_state·has_pluto_hook_features§cell_id$c1388562-0708-4a6a-acfe-927413dab5d2depends_on_disabled_cells§runtime published_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/908057ef75b00408depends_on_skipped_cellsçerrored$cbf1e5ed-8308-486e-a9b7-6cf7fb441fe3queued¤logsrunning¦outputbodyj(
Tabular Mountain Car Value Iteration Policy on True MDP
In the plot below, the distribution $p(N_s) = \frac{1}{N_s+2d}; N_s - d \le N_s \le N_s + d$ and 0 otherwise. It is a uniform distribution around the mean value. Note that for a given discount rate and average number of steps, the discounted value will increase with $d$ while the expected value of $N_s$ is unchanged.
mimetext/htmlrootassigneelast_run_timestampA (persist_js_state·has_pluto_hook_features§cell_id$6cea9e69-bf8c-4079-9884-663a728d7b08depends_on_disabled_cells§runtime ڿpublished_object_keysdepends_on_skipped_cells§errored$30ab21ba-3f5b-46a8-8b8c-753f2755d419queued¤logsrunning¦outputbodyelementsvalue_functionq̂text/plainπ_greedyπ_greedytext/plainreward_historyprefixFloat32elements-15136.0text/plain-45698.0text/plain-60624.0text/plain-21078.0text/plain-25215.0text/plain-37137.0text/plain-35170.0text/plain-12175.0text/plain -15798.0text/plainmore-760.0text/plaintypeArrayprefix_shortobjectid749f6f4741482df0!application/vnd.pluto.tree+objectstep_historyprefixInt64elements15136text/plain60834text/plain121458text/plain142536text/plain167751text/plain204888text/plain240058text/plain252233text/plain 268031text/plainmore14481666text/plaintypeArrayprefix_shortobjectid79c64298cb95d41f!application/vnd.pluto.tree+objectparameter_historyprefixVector{Vector{Float32}}elementstypeArrayprefix_shortobjectid24892c10a11bafa8!application/vnd.pluto.tree+objecttypeNamedTupleobjectidaf3a50d5da87fb59mime!application/vnd.pluto.tree+objectrootassigneelast_run_timestampA
5persist_js_state·has_pluto_hook_features§cell_id$30ab21ba-3f5b-46a8-8b8c-753f2755d419depends_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_timestampA Gްpersist_js_state·has_pluto_hook_features§cell_id$b0cc6ff8-7296-461c-9db7-e52fa518e2e2depends_on_disabled_cells§runtime ,published_object_keysdepends_on_skipped_cellsçerrored$1478745a-634d-4f31-8a70-b74f0e536201queued¤logsrunning¦outputbody
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.
mimetext/htmlrootassigneelast_run_timestampA U&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$7146649a-1052-4ff6-8f44-eb448b849a6aqueued¤logsrunning¦outputbodyDmountain_car_differential_dist_step (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA fJApersist_js_state·has_pluto_hook_features§cell_id$7146649a-1052-4ff6-8f44-eb448b849a6adepends_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_timestampA ۰persist_js_state·has_pluto_hook_features§cell_id$565c53ee-7ad5-44e2-bce5-4ff1f5f162c0depends_on_disabled_cells§runtime npublished_object_keysdepends_on_skipped_cells§errored$12f5065b-5bed-4d03-a0f0-72a942492394queued¤logsrunning¦outputbody9make_tabular_mountaincar (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA rpersist_js_state·has_pluto_hook_features§cell_id$12f5065b-5bed-4d03-a0f0-72a942492394depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$38fe547e-6982-471a-ac11-02b07bdd0157queued¤logsrunning¦outputbodyIcreate_differential_mountaincar_dist_mdp (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA lpersist_js_state·has_pluto_hook_features§cell_id$38fe547e-6982-471a-ac11-02b07bdd0157depends_on_disabled_cells§runtime Ipublished_object_keysdepends_on_skipped_cells§errored$4afbb723-340b-4d85-9115-027a0ff8dfadqueued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA \persist_js_state·has_pluto_hook_features§cell_id$4afbb723-340b-4d85-9115-027a0ff8dfaddepends_on_disabled_cells§runtime T{3published_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/dcdfeb2579b32cf6depends_on_skipped_cellsçerrored$00399548-b21c-43b5-90e2-30656ab1541equeued¤logsrunning¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA >persist_js_state·has_pluto_hook_features§cell_id$00399548-b21c-43b5-90e2-30656ab1541edepends_on_disabled_cells§runtime lpublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/c1dc259f8cbaa64adepends_on_skipped_cellsçerrored$e6bf5b6e-75cd-49b3-bf36-7ed6dee11aafqueued¤logsrunning¦outputbody3show_distributions (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA =persist_js_state·has_pluto_hook_features§cell_id$e6bf5b6e-75cd-49b3-bf36-7ed6dee11aafdepends_on_disabled_cells§runtime 4published_object_keysdepends_on_skipped_cellsçerrored$86f7dcde-b27e-4096-bec8-c5d17fd553d2queued¤logsrunning¦outputbodyelementsvalue_functionv̂text/plainπ_greedyπ_greedytext/plainreward_historyprefixFloat32elements1.0text/plain1.0text/plain1.0text/plain1.0text/plain1.0text/plain1.0text/plain1.0text/plain1.0text/plaintypeArrayprefix_shortobjectid13ec73c68796485!application/vnd.pluto.tree+objectstep_historyprefixInt64elements5180text/plain38759text/plain42805text/plain53215text/plain57378text/plain68763text/plain81753text/plain98143text/plaintypeArrayprefix_shortobjectidd71da8cf14371e5b!application/vnd.pluto.tree+objectaverage_step_rewardprefixFloat32elements0.00023552text/plain0.00022985text/plain0.000223722text/plain0.000217189text/plain0.000217189text/plain0.000214608text/plain0.000210856text/plain0.00020628text/plain 0.000201065text/plainmore 9.78921f-5text/plaintypeArrayprefix_shortobjectid81a96e38e94eab20!application/vnd.pluto.tree+objecttypeNamedTupleobjectidc00d8547405c30c4mime!application/vnd.pluto.tree+objectrootassignee+const differential_nonlinear_dp_mountaincarlast_run_timestampA persist_js_state·has_pluto_hook_features§cell_id$86f7dcde-b27e-4096-bec8-c5d17fd553d2depends_on_disabled_cells§runtimeqpublished_object_keysdepends_on_skipped_cellsçerrored$c75dc51c-cbff-48b1-b0fd-108828929b51queued¤logsrunning¦outputbodyGrun_fcann_gradient_monte_carlo_control (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA FHpersist_js_state·has_pluto_hook_features§cell_id$c75dc51c-cbff-48b1-b0fd-108828929b51depends_on_disabled_cells§runtime g)published_object_keysdepends_on_skipped_cells§errored$7a47a518-dfc7-4310-a0b5-6f0d151c8263queued¤logsrunning¦outputbodyU
mimetext/htmlrootassigneelast_run_timestampA ;2persist_js_state·has_pluto_hook_features§cell_id$5c09f453-7b10-4a38-bb51-87bcc9f54247depends_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_timestampA persist_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¦outputbodyi
mimetext/htmlrootassigneelast_run_timestampA *Aݰpersist_js_state·has_pluto_hook_features§cell_id$0e3e506d-1959-47fd-8da9-b3dfd294be67depends_on_disabled_cells§runtime zwpublished_object_keys5b9565ce0-38f6-11f0-350f-a762f362895d/bb67a09923c17948depends_on_skipped_cellsçerrored$37db9d03-1978-4842-a016-f416c33ba1d7queued¤logsrunning¦outputbody
For the expected value calculation, each of these values is added with equal probability. That is why the discounted value favors higher variance because the longer episodes are not counted as much as in the undiscounted case where γ = 1. The expected discounted value does converge to the undiscounted one as γ approaches 1. One consequence of favoring higher variance is that a policy could be favored by producing episodes with a longer average number of steps, as long as the variance increases enough.
Consider the same distribution above where the distribution of $N_s$ is uniform from $N_s - d$ to $N_s + d$. Below is a derivation of the value function in this case and a graph that uses this value to find how much of an increase in $d$ is required to favor a higher $N$. Different lines are shown from different discount rates. In the limit of $\gamma = 1$, there is no value for $d$ that would result in higher values since the lowest average step is always favored.