The optimal policy and state-value function for blackjack found by Monte Carlo ES. The state value function shown was computed from the action-value function found by Monte Carlo ES
mimetext/htmlrootassigneelast_run_timestampA "'
аpersist_js_state·has_pluto_hook_features§cell_id$9fe42679-dce3-4ee3-b565-eed4ff7d8e4ddepends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$06960937-a87a-4015-bdeb-5d17aa41fe6bqueued¤logsrunning¦outputbody5plot_blackjack_value (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA %ۘpersist_js_state·has_pluto_hook_features§cell_id$06960937-a87a-4015-bdeb-5d17aa41fe6bdepends_on_disabled_cells§runtime dpublished_object_keysdepends_on_skipped_cells§errored$abdcbbad-747a-41ba-a95d-82404e735793queued¤logsrunning¦outputbody4make_ϵsoft_policy! (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA (persist_js_state·has_pluto_hook_features§cell_id$abdcbbad-747a-41ba-a95d-82404e735793depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$846ccb44-a18b-4d87-bbf8-fc59eaf87708queued¤logsrunning¦outputbody
Number of Episodes:
mimetext/htmlrootassigneelast_run_timestampA 0persist_js_state·has_pluto_hook_features§cell_id$846ccb44-a18b-4d87-bbf8-fc59eaf87708depends_on_disabled_cells§runtime/+published_object_keysdepends_on_skipped_cells§errored$154edd83-350d-4acf-adfb-6a2d20599b53queued¤logsrunning¦outputbody)showrace (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA /fpersist_js_state·has_pluto_hook_features§cell_id$154edd83-350d-4acf-adfb-6a2d20599b53depends_on_disabled_cells§runtime 6]published_object_keysdepends_on_skipped_cells§errored$ff9276eb-2151-4a6f-8257-8348047a9f4equeued¤logsrunning¦outputbodyelementsprefixI@NamedTuple{position::Tuple{Int64, Int64}, velocity::Tuple{Int64, Int64}}elementselementspositionelements6text/plain0text/plaintypeTupleobjectid9cbae2ac4ef69449!application/vnd.pluto.tree+objectvelocityelements0text/plain0text/plaintypeTupleobjectid9b52efd7a2a08bd5!application/vnd.pluto.tree+objecttypeNamedTupleobjectid38489c3038c1df3d!application/vnd.pluto.tree+objectelementspositionelements7text/plain0text/plaintypeTupleobjectid627f1c091b0a4b9c!application/vnd.pluto.tree+objectvelocityelements1text/plain0text/plaintypeTupleobjectid1539b04621ff8c7d!application/vnd.pluto.tree+objecttypeNamedTupleobjectid10ed139d1891153d!application/vnd.pluto.tree+objectelementspositionelements8text/plain1text/plaintypeTupleobjectid6d43cd1c8dd97fd1!application/vnd.pluto.tree+objectvelocityelements1text/plain1text/plaintypeTupleobjectid78e123e4f427692a!application/vnd.pluto.tree+objecttypeNamedTupleobjectidba6e6e87bab90698!application/vnd.pluto.tree+objectelementspositionelements10text/plain1text/plaintypeTupleobjectiddad6dff378d50b10!application/vnd.pluto.tree+objectvelocityelements2text/plain0text/plaintypeTupleobjectid83bf2aef4031930b!application/vnd.pluto.tree+objecttypeNamedTupleobjectid7f05885cf5a97609!application/vnd.pluto.tree+objectelementspositionelements12text/plain1text/plaintypeTupleobjectidba2d0d303a66d681!application/vnd.pluto.tree+objectvelocityelements2text/plain0text/plaintypeTupleobjectid83bf2aef4031930b!application/vnd.pluto.tree+objecttypeNamedTupleobjectid4fdd2575d8325500!application/vnd.pluto.tree+objectelementspositionelements13text/plain1text/plaintypeTupleobjectide6f480949e3f3c15!application/vnd.pluto.tree+objectvelocityelements1text/plain0text/plaintypeTupleobjectid1539b04621ff8c7d!application/vnd.pluto.tree+objecttypeNamedTupleobjectid1dfbc9164ac7630!application/vnd.pluto.tree+objectelementspositionelements14text/plain1text/plaintypeTupleobjectid7717f5f1045ca395!application/vnd.pluto.tree+objectvelocityelements1text/plain0text/plaintypeTupleobjectid1539b04621ff8c7d!application/vnd.pluto.tree+objecttypeNamedTupleobjectid4cab6926e0cac33!application/vnd.pluto.tree+objectelementspositionelements16text/plain1text/plaintypeTupleobjectid9466b49b27b0fbe4!application/vnd.pluto.tree+objectvelocityelements2text/plain0text/plaintypeTupleobjectid83bf2aef4031930b!application/vnd.pluto.tree+objecttypeNamedTupleobjectid7215dbdcb350d980!application/vnd.pluto.tree+object elementspositionelements17text/plain1text/plaintypeTupleobjectid5cabddc83be126e5!application/vnd.pluto.tree+objectvelocityelements1text/plain0text/plaintypeTupleobjectid1539b04621ff8c7d!application/vnd.pluto.tree+objecttypeNamedTupleobjectid80c7dd8e4d5c743a!application/vnd.pluto.tree+objectmoreFelementspositionelements29text/plain29text/plaintypeTupleobjectid7233ef8a34e83c81!application/vnd.pluto.tree+objectvelocityelements3text/plain3text/plaintypeTupleobjectid3ed622ab32dfec93!application/vnd.pluto.tree+objecttypeNamedTupleobjectid56645bf7a9faff88!application/vnd.pluto.tree+objecttypeArrayprefix_shortobjectid47e58d64316784d!application/vnd.pluto.tree+objectprefixTuple{Int64, Int64}elementselements0text/plain0text/plaintypeTupleobjectid9b52efd7a2a08bd5!application/vnd.pluto.tree+objectelements0text/plain1text/plaintypeTupleobjectid86128cc9b5ae8f4a!application/vnd.pluto.tree+objectelements1text/plain-1text/plaintypeTupleobjectid467534c86eaf64c9!application/vnd.pluto.tree+objectelements0text/plain0text/plaintypeTupleobjectid9b52efd7a2a08bd5!application/vnd.pluto.tree+objectelements-1text/plain-1text/plaintypeTupleobjectida5f5003e88013c47!application/vnd.pluto.tree+objectelements0text/plain0text/plaintypeTupleobjectid9b52efd7a2a08bd5!application/vnd.pluto.tree+objectelements1text/plain0text/plaintypeTupleobjectid1539b04621ff8c7d!application/vnd.pluto.tree+objectelements-1text/plain0text/plaintypeTupleobjectid29547c053cf46d53!application/vnd.pluto.tree+object elements1text/plain1text/plaintypeTupleobjectid78e123e4f427692a!application/vnd.pluto.tree+objectmoreFelements0text/plain0text/plaintypeTupleobjectid9b52efd7a2a08bd5!application/vnd.pluto.tree+objecttypeArrayprefix_shortobjectide60c88608632daae!application/vnd.pluto.tree+objectprefixFloat32elements-1.0text/plain-1.0text/plain-1.0text/plain-1.0text/plain-1.0text/plain-1.0text/plain-1.0text/plain-1.0text/plain -1.0text/plainmoreF-1.0text/plaintypeArrayprefix_shortobjectideac5b2068fa52d22!application/vnd.pluto.tree+objecttypeTupleobjectid19350ad34cc18b19mime!application/vnd.pluto.tree+objectrootassigneerace_episode2last_run_timestampA 0a-ܰpersist_js_state·has_pluto_hook_features§cell_id$ff9276eb-2151-4a6f-8257-8348047a9f4edepends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$6f914006-1d8d-41f5-ae8a-fbe0b336946cqueued¤logsrunning¦outputbody 1;
Race finished in 11 steps
Finish line
Starting line
Race finished in 22 steps
Finish line
Starting line
mimetext/htmlrootassigneelast_run_timestampA 4tpersist_js_state·has_pluto_hook_features§cell_id$6f914006-1d8d-41f5-ae8a-fbe0b336946cdepends_on_disabled_cells§runtime1]published_object_keysdepends_on_skipped_cells§errored$4197cc28-b24c-48cb-bd8d-ef998983ad77queued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampA )T\persist_js_state·has_pluto_hook_features§cell_id$4197cc28-b24c-48cb-bd8d-ef998983ad77depends_on_disabled_cells§runtime ?Opublished_object_keysdepends_on_skipped_cells§errored$e67d9deb-a074-48ba-84db-2e6938ea01f8queued¤logsrunning¦outputbody3monte_carlo_pred_Q (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA -U persist_js_state·has_pluto_hook_features§cell_id$e67d9deb-a074-48ba-84db-2e6938ea01f8depends_on_disabled_cells§runtime 2published_object_keysdepends_on_skipped_cells§errored$82a1f11e-b1b3-4c7d-ab9d-9f6136ae8195queued¤logsrunning¦outputbody2×1 Matrix{Float32}:
0.5
0.5mimetext/plainrootassigneeconst onestate_π_blast_run_timestampA ,epersist_js_state·has_pluto_hook_features§cell_id$82a1f11e-b1b3-4c7d-ab9d-9f6136ae8195depends_on_disabled_cells§runtime
&published_object_keysdepends_on_skipped_cells§errored$11f8290f-f589-49ff-9602-99ccc4192884queued¤logsrunning¦outputbodym
Statistics for Steps to Finish Race on Track 2
Statistic
Off policy MC Control
Random Policy
Mean
290
286
Median
218
194
Std
263
282
Minimum
10
10
Maximum
1848
1999
Cummulative Distribution Function of Steps to Finish Race
The pseudocode for Monte Carlo ES is inefficient because, for each state-action pair, it maintains a list of all returns and repeatedly calculates their mean. It would be more dfficient to use techniques similar to those explained in Section 2.4 to maintain just the mean and a count (for each state-action pair) and update them incrementally. Describe how the pseudocode would be altered to achieve this.
Returns(s,a) will not maintain a list but instead be a list of single values for each state-action pair. Additionally, another list Counts(s,a) should be initialized at 0 for each pair. When new G values are obtained for state-action pairs, the Count(s,a) value should be incremented by 1. Then Returns(s,a) can be updated with the following formula:
mimetext/htmlrootassigneelast_run_timestampA "')persist_js_state·has_pluto_hook_features§cell_id$c883748c-76b9-4086-8698-b40df51390dadepends_on_disabled_cells§runtime 'published_object_keysdepends_on_skipped_cells§errored$f071b7e2-3f78-4132-8b84-f810f178c89dqueued¤logsrunning¦outputbodyprefixNMDP_Opaque{OneState, OneStateAction, typeof(one_state_simulator), var"#48#49"}elementsstatesprefixMain.var"workspace#3".OneStateelementsprefixOneStateelementstypestructprefix_shortOneStateobjectidffffffff38bdf29f!application/vnd.pluto.tree+objecttypeArrayprefix_shortobjectidf894cef2b5e927e6!application/vnd.pluto.tree+objectstatelookupprefix+Dict{Main.var"workspace#3".OneState, Int64}elementsprefixOneStateelementstypestructprefix_shortOneStateobjectidffffffff38bdf29f!application/vnd.pluto.tree+object1text/plaintypeDictprefix_shortDictobjectid62a6db26cb4a56b2!application/vnd.pluto.tree+objectactionsprefix$Main.var"workspace#3".OneStateActionelementsprefixLeftelementstypestructprefix_shortLeftobjectidffffffff5e48f957!application/vnd.pluto.tree+objectprefixRightelementstypestructprefix_shortRightobjectidffffffff2428617a!application/vnd.pluto.tree+objecttypeArrayprefix_shortobjectid6ea419802207c1a3!application/vnd.pluto.tree+objectactionlookupprefix1Dict{Main.var"workspace#3".OneStateAction, Int64}elementsprefixLeftelementstypestructprefix_shortLeftobjectidffffffff5e48f957!application/vnd.pluto.tree+object1text/plainprefixRightelementstypestructprefix_shortRightobjectidffffffff2428617a!application/vnd.pluto.tree+object2text/plaintypeDictprefix_shortDictobjectid86f98bf29f7f50c5!application/vnd.pluto.tree+objectstate_init$#48 (generic function with 1 method)text/plainsimulator4one_state_simulator (generic function with 1 method)text/plaintypestructprefix_shortMDP_Opaqueobjectida8df05bb1d73c880mime!application/vnd.pluto.tree+objectrootassigneelast_run_timestampA ,:persist_js_state·has_pluto_hook_features§cell_id$f071b7e2-3f78-4132-8b84-f810f178c89ddepends_on_disabled_cells§runtimeVpublished_object_keysdepends_on_skipped_cells§errored$8d7b9826-b52c-4d5a-8c63-e83a1229a0bequeued¤logsrunning¦outputbodyk
Example trajectories after training for 1000 episodes with ϵ= 0.01
mimetext/htmlrootassigneelast_run_timestampA ")gpersist_js_state·has_pluto_hook_features§cell_id$67e535c7-437a-49ba-b5ab-9dfe63fe4aaadepends_on_disabled_cells§runtime ꣵpublished_object_keysdepends_on_skipped_cells§errored$c8f3f7e3-be7e-4615-a667-d9f789928883queued¤logsrunning¦outputbody,updatevalue (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA )`ðpersist_js_state·has_pluto_hook_features§cell_id$c8f3f7e3-be7e-4615-a667-d9f789928883depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$30809344-b4ab-468b-b4b7-5ef3dca5ffc7queued¤logsrunning¦outputbody
Exercise 5.2
Suppose every-visit MC was used instead of first-visit MC on the blackjack task. Would you expect the results to be very different? Why or why not?
As an episode proceeds in blackjack the states will not repeat since every time a card is dealt the player sum changes, or the usable Ace flag changes. Thus the check ensuring that only the first visit to a state is counted in the return average will have no effect on the MC evaluation.
To only way to ensure all state-action pairs are visited without exploring starts is to use a policy with a non-zero probability of visiting all such states. One policy that meets this criterion is an ϵ-soft policy meaning that $\pi(a \vert s) > 0 \: \forall \: s \in \mathcal{S}$. To achieve this with Monte Carlo Control, we simply update the policy to be $\epsilon$-greedy for every Q update, so the maximizing (greedy) action is given a probability $1 - \epsilon + \frac{\epsilon}{\vert \mathcal{A}(s) \vert}$ and all other actions are given the probability $\frac{\epsilon}{\vert \mathcal{A}(s) \vert}$.
Below is code implementing MC control for ϵ-soft policies. It is mostly identical to the every visit method except the policy is always used to select the initial action and the policy update uses an ϵ-greedy update rather than a greedy one.
Consider driving a race car around a turn like those shown in Figure 5.5. You want to go as fast as possible, but not so fast as to run off the track. In our simplified racetrack, the car is at one of a discrete set of grid positions, the cells in the diagram. The velocity is also discrete, a number of grid cells moved horizontally and vertically per time step. The actions are increments to the velocity components. Each may be changed by +1, -1, or 0 in each step, for a total of nine (3x3) actions. Both velocity components are restricted to be nonnegative and less than 5, and they cannot both be zero except at the starting line. Each episode begins in one of the randomly selected start states with both velocity components zero and ends when the car crosses the finish line. The rewards are -1 for each step until the car crosses the finish line. If the car hits the track boundry, it is moved back to a random position on the starting line, both velocity components are reduced to zero, and the episode continues. Before updating the car's location at each time step, check to see if the projected path of the car intersects the track boundary. If it intersects the finish line, the episode ends; if it intersects anywhere else, the car is considered to have hit the track boundary and is sent back to the starting line. To make the task more challenging, with probality 0.1 at each time step the velocity increments are both zero, independently of the intended increments. Apply a Monte Carlo control method to this task to compute the optimal policy from each starting state. Exhibit several trajectories following the optimal policy (but turn the noise off for these trajectories).
mimetext/htmlrootassigneelast_run_timestampA ")$persist_js_state·has_pluto_hook_features§cell_id$cebb79b7-c9d6-4b79-ba0e-b2f3c7587724depends_on_disabled_cells§runtime 2ߵpublished_object_keysdepends_on_skipped_cells§errored$54f73eb8-dcea-4da0-83af-35720e56ccbcqueued¤logsrunning¦outputbody4monte_carlo_ϵsoft (generic function with 2 methods)mimetext/plainrootassigneelast_run_timestampA )ڰpersist_js_state·has_pluto_hook_features§cell_id$54f73eb8-dcea-4da0-83af-35720e56ccbcdepends_on_disabled_cells§runtime ,published_object_keysdepends_on_skipped_cells§errored$418c045d-90c7-42d8-9126-90185f7e197bqueued¤logsrunning¦outputbody
In learning curves such as those shown in Figure 5.3 error generally decreases with training, as indeed happened for the ordinary importance-sampling method. But for the weighted importance-sampling method error first increased and then decreased. Why do you think this happened?
In figure 5.3, the true value is about -.277 and we initialized the value function at zero. For any given episode it is likely that the observed return will be -1.0 or 1.0 for a win or a loss. Weighted importance sampling won't update the state value for trajectories which cannot occur in the target policy, so for some of the runs at this early state the state value is unchanged at the 0 initial value. It is only after a certain number of episodes have occured that all of the values will be updated and produce an estimate which is worse than the initial value. Once many samples with non zero weight are collected for each run, then the estimate starts to approach the true value again. If instead we initialized the state value far away from the true value, then you would not see the initial increase in estimate error. See below for an example using an initial value of 1. In this case, no update from weighted importance sampling would produce an error larger than the initial value.
Blackjack State Estimate with Bad Initialization
Weighted importance sampling produces lower error estimates of the value of a single blackjack state from off-policy episodes
Consider an MDP with a single nonterminal state and a single action that transitions back to the nonterminal state with probability $p$ and transitions to the terminal state with probability $1-p$. Let the reward be +1 on all transitions, and let $\gamma=1$. Suppose you observe one episode that lasts 10 steps, with a return of 10. What are the first-visit and every-visit estimators of the value of the nonterminal state?
For the first-visit estimator, we only consider the single future reward from the starting state which would be 10. There is nothing to average since we just have the single value of 10 for the episode.
For the every-visit estimator, we need to average together all 10 visits to the non-terminal state. For the first visit, the future reward is 10. For the second visit it is 9, third 8, and so forth. The final visit has a reward of 1, so the value estimate is the average of 10, 9, ..., 1 which is $\frac{(1+10) \times 5}{10}=\frac{55}{10} = 5.5$
Off policy MC control training is slow because the random behavior policy takes a very long time to complete a race (~2500 or ~300 steps). Even after 1000 episodes performance is indistinguishable from the random policy.
mimetext/htmlrootassigneelast_run_timestampA (Npersist_js_state·has_pluto_hook_features§cell_id$f9bc84ff-c2f9-4ac2-b2ce-34dfcf837a73depends_on_disabled_cells§runtimeΜIpublished_object_keys5c6e0de0c-3901-11f0-234e-bd09c571f662/10b6971fa80c859d5c6e0de0c-3901-11f0-234e-bd09c571f662/1c437dfc407d89165c6e0de0c-3901-11f0-234e-bd09c571f662/7b3f5adc32cbaebf5c6e0de0c-3901-11f0-234e-bd09c571f662/acf9294267fab534depends_on_skipped_cells§errored$8f38a3e9-1872-4ea6-9a03-87112af4bf07queued¤logsrunning¦outputbody1sampleracepolicy (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA /persist_js_state·has_pluto_hook_features§cell_id$8f38a3e9-1872-4ea6-9a03-87112af4bf07depends_on_disabled_cells§runtime Kpublished_object_keysdepends_on_skipped_cells§errored$627d5aa3-974f-4949-8b65-9500eba1d7ccqueued¤logsrunning¦outputbody+figure_5_2 (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA &Fpersist_js_state·has_pluto_hook_features§cell_id$627d5aa3-974f-4949-8b65-9500eba1d7ccdepends_on_disabled_cells§runtimeMApublished_object_keysdepends_on_skipped_cells§errored$02dd1e77-2a7e-4123-94db-d17b31a8b15aqueued¤logsrunning¦outputbodyprefixBlackjackStateelementssum13text/plainupcard2text/plainuatruetext/plaintypestructprefix_shortBlackjackStateobjectida2f2eb542cb25fd2mime!application/vnd.pluto.tree+objectrootassigneeconst blackjack_state1last_run_timestampA )Npersist_js_state·has_pluto_hook_features§cell_id$02dd1e77-2a7e-4123-94db-d17b31a8b15adepends_on_disabled_cells§runtime 7 published_object_keysdepends_on_skipped_cells§errored$09b67730-39e7-4209-8117-6bc3adfb342aqueued¤logsrunning¦outputbody
Consider the term: $\left ( \sum_{i=1}^N 2^i \right ) ^2 = (2 + 2^2 + 2^3 + \cdots + 2^N)^2 \gt 2^{2N}$ since all the other terms in the parentheses are positive.
The question is then reduced to whether the following infinite sum diverges: $\sum_{N=1}^\infty \frac{1.8^{N}}{N^{2}}$. Consider the logarithm of each term in the series $\log {\frac{1.8^N}{N^2}} = \log{1.8^N} - \log{N^2} = N \log{1.8} - 2 \log{N}$. As N approaches infinity $N \gt \log{N}$ so the log of each term diverges as do the terms individually as does the series. Therefore the variance diverges with ever-visit MC as it does with first visit MC.
mimetext/htmlrootassigneelast_run_timestampA "&persist_js_state·has_pluto_hook_features§cell_id$47daf83b-8fe9-4491-b9ae-84bd269d5546depends_on_disabled_cells§runtime %published_object_keysdepends_on_skipped_cells§errored$ba8a5804-4be3-43fe-95d7-c957ce02a1d4queued¤logsrunning¦outputbody2make_action_style (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA 0 persist_js_state·has_pluto_hook_features§cell_id$ba8a5804-4be3-43fe-95d7-c957ce02a1d4depends_on_disabled_cells§runtime Y published_object_keysdepends_on_skipped_cells§errored$481ad435-cc80-4164-882d-8310b010ca91queued¤logsrunning¦outputbody=make_simple_blackjack_policy (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA %
Modify the algorithm for off-policy Monte Carlo control (page 111) to use the idea of the truncated weighted-average estimator (5.10). Note that you will first need to convert this equation to action values.
For the algorithm on page 111, need to add a variable in the loop to keep track of $\bar{G}$ both from the start of the episode forwards. The inner loop should also start from the beginning of each episode and go forwards rather than starting at the end going backwards. The term added to the numerator and denominator will be ready including $\bar{G}$ and $\rho$ once the end of the episode is reached. A $\gamma$ accumulator can be initiazed at 1 and kept track of in the inner loop by repeatedly multiplying by γ each iteration.
Ordinary importance sampling produces surprisingly unstable estimates on the one-state MDP shown in Example 5.5. The correct estimate here is 1 ($\gamma = 1$), and, even through this is the expected value of a sample return (after importance sampling), the variance of the samples is infinite, and the estimates do not converge to this value. In contrast weighted importance samping produces the correct value of 1 after the first episode that ends with the left action.
mimetext/htmlrootassigneelast_run_timestampA -9-4persist_js_state·has_pluto_hook_features§cell_id$830d6d61-7259-43e7-8d6d-09bc81818dd9depends_on_disabled_cells§runtime`published_object_keys4c6e0de0c-3901-11f0-234e-bd09c571f662/aebe9ff9bf4a3c7depends_on_skipped_cells§errored$e293e184-5938-40b5-a04b-5306760a06aequeued¤logsrunning¦outputbody9estimate_blackjack_state (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA )Qepersist_js_state·has_pluto_hook_features§cell_id$e293e184-5938-40b5-a04b-5306760a06aedepends_on_disabled_cells§runtime Zpublished_object_keysdepends_on_skipped_cells§errored$66645f1a-b591-43e7-b931-8ed0cc7d6898queued¤logsrunning¦outputbody A
Race finished in 58 steps
Finish line
Starting line
Race finished in 117 steps
Finish line
Starting line
mimetext/htmlrootassigneelast_run_timestampA 2}@persist_js_state·has_pluto_hook_features§cell_id$66645f1a-b591-43e7-b931-8ed0cc7d6898depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$658ceeaa-1b45-47bd-a364-eaa1759d17acqueued¤logsrunning¦outputbody3race_track_episode (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA /_persist_js_state·has_pluto_hook_features§cell_id$658ceeaa-1b45-47bd-a364-eaa1759d17acdepends_on_disabled_cells§runtime x published_object_keysdepends_on_skipped_cells§errored$04752549-ffca-4e31-869e-714f835d3e85queued¤logsrunning¦outputbody23mimetext/plainrootassigneeconst blackjack_stateindex1last_run_timestampA )persist_js_state·has_pluto_hook_features§cell_id$04752549-ffca-4e31-869e-714f835d3e85depends_on_disabled_cells§runtime M&published_object_keysdepends_on_skipped_cells§errored$e89706f1-0c6a-4da4-82a1-ccf153f2e186queued¤logsrunning¦outputbodyR
In the boxed algorithm for off-policy MC control, you may have been expecting the $W$ update to have involved the importance-sampling ratio $\frac{\pi(A_t|S_t)}{b(A_t|S_T)}$, but instead it involves $\frac{1}{b(A_t|S_t)}$. Why is this nevertheless correct?
The target policy $\pi(s)$ is always deterministic, only selecting a single action according to $\pi(s)=\text{argmax}_a Q(s,a)$. Therefore the numerator in importance-sampling ratio will either be 1 when the trajectory action matches the one given by $\pi(s)$ or it will be 0. The inner loop will exit if such as action is selected as it will result in zero values of W for the rest of the trajectory and thus no further updates to $Q(s,a)$ or $\pi(s)$. The only value of $\pi(s)$ that would be encountered in the equation is therefore 1 which is why the numerator is a constant.
Unlike the other techniques, Monte Carlo ϵ-Soft requires selecting the parameter ϵ and the performance of each algorithm varies a lot with this parameter and the number of training episodes. For a short training time of 1,000 episodes, small values of ϵ seem to perform better such as 0.01 or 0.02. Under those conditions, performance of the policies is far better than random with mean episode lengths of 32 and 24 respectively. Longer training improves the results but also requires changing ϵ and possibly introducing a decay rate so it can start high and approach 0 after a large number of episodes.
mimetext/htmlrootassigneelast_run_timestampA "+persist_js_state·has_pluto_hook_features§cell_id$1b02e593-d791-424c-b956-62cc480fcf40depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$72e9721f-ee17-4557-b090-71728e6c22cequeued¤logsrunning¦outputbody+makelookup (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA $ح persist_js_state·has_pluto_hook_features§cell_id$72e9721f-ee17-4557-b090-71728e6c22cedepends_on_disabled_cells§runtime Bpublished_object_keysdepends_on_skipped_cells§errored$11723075-d1db-4512-abf2-3fe494a71a3bqueued¤logsrunning¦outputbody-check_policy (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA $persist_js_state·has_pluto_hook_features§cell_id$11723075-d1db-4512-abf2-3fe494a71a3bdepends_on_disabled_cells§runtime uʵpublished_object_keysdepends_on_skipped_cells§errored$059b1c0f-eb21-4a4a-8aed-64e9ac07b541queued¤logsrunning¦outputbody
Number of Episodes:
mimetext/htmlrootassigneelast_run_timestampA 3" persist_js_state·has_pluto_hook_features§cell_id$059b1c0f-eb21-4a4a-8aed-64e9ac07b541depends_on_disabled_cells§runtime ypublished_object_keysdepends_on_skipped_cells§errored$b2115f33-f8e2-452e-9b0e-90610f0f09b1queued¤logsrunning¦outputbody3make_random_policy (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA $mpersist_js_state·has_pluto_hook_features§cell_id$b2115f33-f8e2-452e-9b0e-90610f0f09b1depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$82284c63-2306-4469-9b1a-a5ec87037e79queued¤logsrunning¦outputbody S
Usable ace
No usable ace
mimetext/htmlrootassigneelast_run_timestampA )N°persist_js_state·has_pluto_hook_features§cell_id$82284c63-2306-4469-9b1a-a5ec87037e79depends_on_disabled_cells§runtime &ipublished_object_keys5c6e0de0c-3901-11f0-234e-bd09c571f662/c2f9f46c95453d024c6e0de0c-3901-11f0-234e-bd09c571f662/d508a1aa913b68d5c6e0de0c-3901-11f0-234e-bd09c571f662/cc789608a7b2df165c6e0de0c-3901-11f0-234e-bd09c571f662/985b842d3ecfdc58depends_on_skipped_cells§errored$5b32bbc7-dc34-4fc3-bacc-92e55f26a98cqueued¤logsrunning¦outputbody7.860627f0mimetext/plainrootassigneelast_run_timestampA -JApersist_js_state·has_pluto_hook_features§cell_id$5b32bbc7-dc34-4fc3-bacc-92e55f26a98cdepends_on_disabled_cells§runtime &2.published_object_keysdepends_on_skipped_cells§errored$c8be6951-b6ec-4444-8c7f-ca5db6681571queued¤logsrunning¦outputbody0makegridsquare (generic function with 2 methods)mimetext/plainrootassigneelast_run_timestampA / persist_js_state·has_pluto_hook_features§cell_id$c8be6951-b6ec-4444-8c7f-ca5db6681571depends_on_disabled_cells§runtime gpublished_object_keysdepends_on_skipped_cells§errored$887de995-04e8-4d84-88d7-ad096a5747dfqueued¤logsrunning¦outputbodyY
Example trajectories after training for 1000 episodes
Each environment has 7300 and 12875 states respectively, so Monte Carlo Exploring starts would need to sample at least this many episodes to have a non zero probability of coverage. Surprisingly, even after just 1000 episodes of training the results are quite an improvement over the random policy with the mean finish time of about 30 steps for both. Although at the high end, some episodes still take over 100 steps to complete (still much better than the random policy). If we allow training for 10-100 million episodes, which is necessary to get a reasonable sample size for each state, then the results are much improved with episode step lengths from 11 to 18 for track 1 and 9 to 16 for track2.
mimetext/htmlrootassigneelast_run_timestampA "+=հpersist_js_state·has_pluto_hook_features§cell_id$ffd1e39d-e66b-40a3-8ad1-c9480d371fe8depends_on_disabled_cells§runtime
Vpublished_object_keysdepends_on_skipped_cells§errored$13cc524c-d983-44f4-8731-0595249fb888queued¤logsrunning¦outputbody/monte_carlo_ES (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA % persist_js_state·has_pluto_hook_features§cell_id$13cc524c-d983-44f4-8731-0595249fb888depends_on_disabled_cells§runtime D~published_object_keysdepends_on_skipped_cells§errored$8faca500-b80d-4b50-88b6-683d18a1286bqueued¤logsrunning¦outputbodyelements-0.254243text/plain0.91244text/plaintypeTupleobjectid8788401422089bb3mime!application/vnd.pluto.tree+objectrootassigneelast_run_timestampA *persist_js_state·has_pluto_hook_features§cell_id$8faca500-b80d-4b50-88b6-683d18a1286bdepends_on_disabled_cells§runtimeopublished_object_keysdepends_on_skipped_cells§errored$755be8f1-9d9e-4afd-8a70-07fab78e4333queued¤logsrunning¦outputbody-
Track 2
mimetext/htmlrootassigneelast_run_timestampA "+]persist_js_state·has_pluto_hook_features§cell_id$755be8f1-9d9e-4afd-8a70-07fab78e4333depends_on_disabled_cells§runtime Tpublished_object_keysdepends_on_skipped_cells§errored$01683e11-a368-45bc-abbc-bbd5c94d7b22queued¤logsrunning¦outputbody+plot_value (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA %ϰpersist_js_state·has_pluto_hook_features§cell_id$01683e11-a368-45bc-abbc-bbd5c94d7b22depends_on_disabled_cells§runtime /ȵpublished_object_keysdepends_on_skipped_cells§errored$5e2420fb-b2cc-49fc-91e3-3de80fba698bqueued¤logsrunning¦outputbody(runrace (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA /Ӓpersist_js_state·has_pluto_hook_features§cell_id$5e2420fb-b2cc-49fc-91e3-3de80fba698bdepends_on_disabled_cells§runtime
published_object_keysdepends_on_skipped_cells§errored$1e6f7e5e-c5ce-479c-abbb-6c388c254626queued¤logsrunning¦outputbody)updateV! (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA )g persist_js_state·has_pluto_hook_features§cell_id$1e6f7e5e-c5ce-479c-abbb-6c388c254626depends_on_disabled_cells§runtime 9 µpublished_object_keysdepends_on_skipped_cells§errored$5e012ead-b4f9-45a9-979d-88b0b1086263queued¤logsrunning¦outputbodyelementsprefixFloat32elements0.0text/plain0.0text/plain1.0text/plain1.0text/plain1.0text/plain1.0text/plain1.0text/plain1.0text/plain 1.0text/plainmored1.0text/plaintypeArrayprefix_shortobjectid19fc08302fa52c8b!application/vnd.pluto.tree+object2×1 Matrix{Float32}:
1.0
0.0text/plainprefixFloat32elements0.0text/plain0.0text/plain8.0text/plain0.0text/plain0.0text/plain0.0text/plain0.0text/plain0.0text/plain 0.0text/plainmored0.0text/plaintypeArrayprefix_shortobjectid28d9ec024d60f38f!application/vnd.pluto.tree+objecttypeTupleobjectid41645d3d17ae1bfmime!application/vnd.pluto.tree+objectrootassigneelast_run_timestampA .{apersist_js_state·has_pluto_hook_features§cell_id$5e012ead-b4f9-45a9-979d-88b0b1086263depends_on_disabled_cells§runtime#published_object_keysdepends_on_skipped_cells§errored$a0eb6939-11bb-458d-bee3-9ed763819f62queued¤logsrunning¦outputbodyB
Racetrack Visualization Code
mimetext/htmlrootassigneelast_run_timestampA "* persist_js_state·has_pluto_hook_features§cell_id$a0eb6939-11bb-458d-bee3-9ed763819f62depends_on_disabled_cells§runtime (published_object_keysdepends_on_skipped_cells§errored$21d248f5-edad-4614-8c1c-ae330f9e5a18queued¤logsrunning¦outputbodymimetext/plainrootassigneelast_run_timestampA $ܹpersist_js_state·has_pluto_hook_features§cell_id$21d248f5-edad-4614-8c1c-ae330f9e5a18depends_on_disabled_cells§runtime /=cpublished_object_keysdepends_on_skipped_cells§errored$a68b4965-c392-47e5-9b29-93e7ada9990aqueued¤logsrunning¦outputbody,plot_fig5_1 (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA )znpersist_js_state·has_pluto_hook_features§cell_id$a68b4965-c392-47e5-9b29-93e7ada9990adepends_on_disabled_cells§runtime+sǵpublished_object_keysdepends_on_skipped_cells§errored$d766d44e-3684-497c-814e-8f71740cb232queued¤logsrunning¦outputbody
Figure 5.1:
Approximate state-value functions for the blackjack policy that sticks only on 20 or 21, computed by Monte Carlo policy evaluation
mimetext/htmlrootassigneelast_run_timestampA "&I#persist_js_state·has_pluto_hook_features§cell_id$d766d44e-3684-497c-814e-8f71740cb232depends_on_disabled_cells§runtime D]published_object_keysdepends_on_skipped_cells§errored$0dfd7afb-127c-4afd-8374-3c9a20a9ee76queued¤logsrunning¦outputbody2π_racetrack_rand (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA 0EWpersist_js_state·has_pluto_hook_features§cell_id$0dfd7afb-127c-4afd-8374-3c9a20a9ee76depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$bf33230e-342b-4486-89ac-9667438de503queued¤logsrunning¦outputbody
Exercise 5.8
The results with Example 5.5 and shown in Figure 5.4 used a first-visit MC method. Suppose that instead an every-visit MC method was used on the same problem. Would the variance of the estimator still be infinite? Why or why not?
The state value estimate can be computed by summing terms for all of the episode lengths just like for the first visit method. Each episode has a reward of +1 from the terminal transition and we only need to consider episodes that take the left action. $\frac{\pi(A_t|S_t)}{b(A_t|S_t)} = 2$ for all cases, so the importance sampling ratio is just $2^T$ where T is the total length of that episode. The probabilities for each episode length is unchanged from Example 5.5 and is just 0.1 times 0.9 times the number of steps preceeding the terminal step. Compared to the calculation in Example 5.5, the expected value calculation must also have the importance sampling ratio terms for all of N visits in the length N episode instead of just the first one:
Length 1 episode
$$\frac{1}{2} \cdot 0.1 \cdot (2)^2$$
Length 2 episode, the term representing X is now an average of every visit along the trajectory. The probability of the trajectory is unchanged from before.
In this chapter we will use a sampling technique that does not require complete knowledge of the environment, only the ability to interact with it. We will focus on episodic tasks so that the sampled returns are always well defined. Unlike the dynamic programming methods from before, these techniques will estimate the value functions rather than computing them directly. With enough samples, these techniques will also converge to the correct solution.
5.1 Monte Carlo Prediction
First we consider using Monte Carlo methods to learn the state-value function for a given policy. The most obvious way to estimate this is to simply average the returns observed after vising a particular state. If we save the trajectories of an agent interacting with an MDP, we can keep track of how many times an agent visits a state. In the technique called first visit MC we look at the returns accumulated after the first visit to a state in that episode only making a single update. It is also possible to update the state value for every visit that occurs in an episode, but the theoretical properties for first visit MC are more widely studied. Both techniques, however, can be shown to converge as the number of visits goes to infinity. Below is code implementing Monte Carlo prediction using every visit MC and an in place update of the average
Example 5.4: Off-policy Estimation of a Blackjack State Value
mimetext/htmlrootassigneelast_run_timestampA "("persist_js_state·has_pluto_hook_features§cell_id$b39d1ea0-86a2-4215-ae73-e4492f3f2f00depends_on_disabled_cells§runtime ĵpublished_object_keysdepends_on_skipped_cells§errored$a307e780-996a-485f-af59-b44982dfceb4queued¤logsrunning¦outputbody,rendertrack (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA /Dpersist_js_state·has_pluto_hook_features§cell_id$a307e780-996a-485f-af59-b44982dfceb4depends_on_disabled_cells§runtime (published_object_keysdepends_on_skipped_cells§errored$b040f245-b2d6-4ec6-aa7f-511c54aabd0dqueued¤logsrunning¦outputbody
mimetext/htmlrootassigneelast_run_timestampA "*@Bpersist_js_state·has_pluto_hook_features§cell_id$1aaf3827-5851-4156-a7e6-14f5e4d00238depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$d6e7cc6d-f397-4bdf-974e-9a16922393ddqueued¤logsrunning¦outputbody7create_policy_function (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA /аpersist_js_state·has_pluto_hook_features§cell_id$d6e7cc6d-f397-4bdf-974e-9a16922393dddepends_on_disabled_cells§runtime +published_object_keysdepends_on_skipped_cells§errored$1951fc4c-acc4-49a6-a907-7447ff0f430aqueued¤logsrunning¦outputbodyY
Example trajectories after training for 1000 episodes
mimetext/htmlrootassigneelast_run_timestampA 3\ٰpersist_js_state·has_pluto_hook_features§cell_id$acb270a1-e2b9-46bc-9a52-9f66f1cca17cdepends_on_disabled_cells§runtimeINepublished_object_keysdepends_on_skipped_cells§errored$334b4d77-8784-46be-b9e8-80c0a2244694queued¤logsrunning¦outputbody3monte_carlo_ϵsoft (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA )Wpersist_js_state·has_pluto_hook_features§cell_id$334b4d77-8784-46be-b9e8-80c0a2244694depends_on_disabled_cells§runtime ?Npublished_object_keysdepends_on_skipped_cells§errored$e5384dd0-fad1-4a24-b011-73b062fcfb1bqueued¤logsrunning¦outputbody}
Exercise 5.1
Consider the diagroms on the right in Figure 5.1. Why does the estimated value function jump for the last two rows in the rear? Why does it drop off for the whole last row on the left? Why are the frontmost values higher in the upper diagrams than in the lower?
The last two rows in the rear are for a player sum equal to 20 or 21. For a sum of 19 and lower, this policy will hit which is suboptimal for these high sums. For the sums of 20 or 21 though, sticking is optimal so the value jumps compared to the suboptimal hit at 19.
The far left row represents cases where the dealer is showing an Ace. Since an Ace is a flexible card, the dealer policy will have more options that result in a win including the possibility of having another face card already (dealer natural). It is always worse for the player if the dealer is known to have an Ace.
The frontmost values represent cases where the player sum is 12. If there is a usable Ace this means that means that the player has two Aces which results in a sum of 12 when the first Ace is counted as 1 and the second is usable and counted as 11. If there is no usable Ace than a sum of 12 would have to result from some other combination of cards such as 10/2, 9/3, etc... Since the first case has two Aces, it means that potentially both could count as 1 if needed to avoid a bust. In the case without a usable Ace, the sum is the same, but there are more opportunities to bust if we draw a card worth 10, so having a sum of 12 with a usable Ace is strictly better.
For $Q(s,a)$, there is no need to calculate the sampling ratio for the first action selected. Here $\mathscr{T}(s, a)$ is the set of all time steps in which the state action pair $(s, a)$ is visited.
mimetext/htmlrootassigneelast_run_timestampA "([persist_js_state·has_pluto_hook_features§cell_id$881ba6c3-0e6a-4bb8-bc14-2e0face560f2depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$5c57e4b7-51d6-492d-9fc9-bcdab1dd46f4queued¤logsrunning¦outputbody6plot_blackjack_policy (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA %װpersist_js_state·has_pluto_hook_features§cell_id$5c57e4b7-51d6-492d-9fc9-bcdab1dd46f4depends_on_disabled_cells§runtime - published_object_keysdepends_on_skipped_cells§errored$e0d3d7d1-203f-42fa-8570-8d1d88bf17c2queued¤logsrunning¦outputbody-
Track 2
mimetext/htmlrootassigneelast_run_timestampA "*Wpersist_js_state·has_pluto_hook_features§cell_id$e0d3d7d1-203f-42fa-8570-8d1d88bf17c2depends_on_disabled_cells§runtime ҵpublished_object_keysdepends_on_skipped_cells§errored$760c5361-02d4-46b7-a05c-fc2d10d93de6queued¤logsrunning¦outputbody3monte_carlo_pred_V (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA %ppersist_js_state·has_pluto_hook_features§cell_id$760c5361-02d4-46b7-a05c-fc2d10d93de6depends_on_disabled_cells§runtime 8Epublished_object_keysdepends_on_skipped_cells§errored$d55860d1-e4c1-4a79-adbe-b40a6d6283a7queued¤logsrunning¦outputbody>initialize_state_action_value (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA $persist_js_state·has_pluto_hook_features§cell_id$d55860d1-e4c1-4a79-adbe-b40a6d6283a7depends_on_disabled_cells§runtime -published_object_keysdepends_on_skipped_cells§errored$06297d75-121a-4178-b45b-83e167efd90dqueued¤logsrunning¦outputbody*joinlines (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA 0
Apersist_js_state·has_pluto_hook_features§cell_id$06297d75-121a-4178-b45b-83e167efd90ddepends_on_disabled_cells§runtime kpublished_object_keysdepends_on_skipped_cells§errored$abe70666-39f8-4f1d-a285-a3a99f696d10queued¤logsrunning¦outputbody z
For (5.14) we need to turn this into an expected value
$$\mathbb{E}[\rho_{t:T-1}R_{t+1}]$$
Now we know that the reward at time step t+1 is only dependent on the action and state at time t. Moreover, the later parts of the trajectory are also independent of each other. So we can separate some of these terms into a product of expected values rather than an expected value of products:
We know from (5.13) that $\mathbb{E} \left [ \frac{\pi(A_k|S_k)}{b(A_k|S_k)} \right ] = 1$ so the above expression simplifies to: $\mathbb{E} \left [ \frac{\pi(A_t|S_t)}{b(A_t|S_t)}R_{t+1} \right ]$. Using the original shorthand with ρ:
Weighted importance sampling produces lower error estimates of the value of a single blackjack state from off-policy episodes
mimetext/htmlrootassigneelast_run_timestampA +̟opersist_js_state·has_pluto_hook_features§cell_id$9ca72278-fff6-4b0f-b72c-e0d3768aff73depends_on_disabled_cells§runtime.published_object_keys5c6e0de0c-3901-11f0-234e-bd09c571f662/58d51ac87604fe9cdepends_on_skipped_cells§errored$020131a1-c68b-403a-9c5e-944edb6220e9queued¤logsrunning¦outputbody-updatevalue (generic function with 2 methods)mimetext/plainrootassigneelast_run_timestampA )aspersist_js_state·has_pluto_hook_features§cell_id$020131a1-c68b-403a-9c5e-944edb6220e9depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$c23475f0-c5f0-49ce-a665-f93c8bda0474queued¤logsrunning¦outputbody3make_blackjack_mdp (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA %spersist_js_state·has_pluto_hook_features§cell_id$c23475f0-c5f0-49ce-a665-f93c8bda0474depends_on_disabled_cells§runtime 4|published_object_keysdepends_on_skipped_cells§errored$15925cc6-9605-4357-9c2a-cdfe54070989queued¤logsrunning¦outputbody
Consider an implementation or ordinary importance sampling that updates $V(s)$ incrementally every time a $G$ value is observed for that state. The equations should be similar to the incremental update rule previously derived for $V(s)$ without importance sampling.
Consider a sequence of returns $G_1, G_2, \dots , G_{n-1}$, all starting in the same state and each with a corresponding weight $W_i = \rho_{t_i:T(t_i)-1}$. We wish to form the estimate
$$V_n \dot= \frac{\sum_{k=1}^{n-1}W_k G_k}{n-1}, n \geq 2$$
and keep it up-to-date as we obtain a single additional return $G_n$. Observe that we can increment n by 1 to get an espression for V in terms of itself.
So, to calculate the value function, we can simply apply the following update rule after obtaining new values for W and G:
$$C \leftarrow C + 1$$
$$V \leftarrow V + \frac{WG-V}{C}$$
which looks very similar to the ordinary average update rule but with the weight multiplied by G. C just keeps a running total of the times the state was observed. Note that C needs to be updated even in the case where W is 0 which is not the case for weighted importance sampling. A similar inremental update rule is derived later for the weighted case as well as an algorithm for updating the action-value estimate using this method. Below are code examples for calculating the value estimates for both weighted and normal importance sampling using the incremental implementation.
What is the backup diagram for Monte Carlo estimation of $q_\pi$
Similar to the $v_\pi$ diagram except the root is the s,a pair under consideration followed by the new state and the action taken along the trajectory. The rewards are still accumulated to the end, just the start of the trajectory is a solid filled in circle that would contain the value for that s,a pair.
Given a starting state $S_t$, the probability of the subsequent state-action trajectory, $A_t, S_{t+1}, A_{t+1}, \ldots ,S_T$, occuring under any policy $\pi$ is:
where $p$ here is the state-transition probability function defined by (3.4). Thus, the relative probability of the trajectory under the target and behavior policies (the importance-sampling ratio) is
mimetext/htmlrootassigneelast_run_timestampA 31npersist_js_state·has_pluto_hook_features§cell_id$1117e6c3-2736-46a4-bac2-d3c99c1998b6depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$5948f670-1203-4b75-8517-f8470f5d01aaqueued¤logsrunning¦outputbody+figure_5_4 (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA , persist_js_state·has_pluto_hook_features§cell_id$5948f670-1203-4b75-8517-f8470f5d01aadepends_on_disabled_cells§runtime7
mimetext/htmlrootassigneelast_run_timestampA "+ޘpersist_js_state·has_pluto_hook_features§cell_id$88335fca-fd87-487b-9de2-ea7c779b54cfdepends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$fd91d00a-f94f-40ff-88a7-9d85f05acc96queued¤logsrunning¦outputbody-make_row_set (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA /Qkpersist_js_state·has_pluto_hook_features§cell_id$fd91d00a-f94f-40ff-88a7-9d85f05acc96depends_on_disabled_cells§runtime published_object_keysdepends_on_skipped_cells§errored$a59d9c84-d35f-4a9b-9fb6-13e30cdd7c3aqueued¤logsrunning¦outputbody2.01716f0mimetext/plainrootassigneelast_run_timestampA -tpersist_js_state·has_pluto_hook_features§cell_id$a59d9c84-d35f-4a9b-9fb6-13e30cdd7c3adepends_on_disabled_cells§runtimey̵published_object_keysdepends_on_skipped_cells§errored$df3c4a33-45f1-4cc2-8c06-d500a0eecc8fqueued¤logsrunning¦outputbodyelementsstartprefixSet{Tuple{Int64, Int64}}elementselements0text/plain0text/plaintypeTupleobjectid9b52efd7a2a08bd5!application/vnd.pluto.tree+objectelements4text/plain0text/plaintypeTupleobjectidc772df2bb869c6b4!application/vnd.pluto.tree+objectelements5text/plain0text/plaintypeTupleobjectid973ae957c0c386bd!application/vnd.pluto.tree+objectelements2text/plain0text/plaintypeTupleobjectid83bf2aef4031930b!application/vnd.pluto.tree+objectelements3text/plain0text/plaintypeTupleobjectidaa4c36dcad24fa29!application/vnd.pluto.tree+objectelements1text/plain0text/plaintypeTupleobjectid1539b04621ff8c7d!application/vnd.pluto.tree+objecttypeSetprefix_shortSetobjectid1d8241165bb36cd8!application/vnd.pluto.tree+objectfinishprefixSet{Tuple{Int64, Int64}}elementselements13text/plain27text/plaintypeTupleobjectid54596a77c929eebd!application/vnd.pluto.tree+objectelements13text/plain28text/plaintypeTupleobjectide62a3fcc16b8e2ed!application/vnd.pluto.tree+objectelements13text/plain30text/plaintypeTupleobjectid8412ec158a86a5dd!application/vnd.pluto.tree+objectelements13text/plain29text/plaintypeTupleobjectida412ad26df95fe95!application/vnd.pluto.tree+objectelements13text/plain26text/plaintypeTupleobjectidd220e80edae3ebdb!application/vnd.pluto.tree+objectelements13text/plain31text/plaintypeTupleobjectiddd11b696ef064776!application/vnd.pluto.tree+objecttypeSetprefix_shortSetobjectid445dadcb9dd2ee11!application/vnd.pluto.tree+objectbodyprefixSet{Tuple{Int64, Int64}}elementselements1text/plain28text/plaintypeTupleobjectid72e21e63940a8fea!application/vnd.pluto.tree+objectelements-2text/plain10text/plaintypeTupleobjectid9461b7cf1c0d4966!application/vnd.pluto.tree+objectelements-1text/plain4text/plaintypeTupleobjectid6ab5d2dd7af393ce!application/vnd.pluto.tree+objectelements2text/plain26text/plaintypeTupleobjectidd3f46239e4706803!application/vnd.pluto.tree+objectelements5text/plain28text/plaintypeTupleobjectideb92527562a71ccc!application/vnd.pluto.tree+objectelements-1text/plain22text/plaintypeTupleobjectid6f6a11db6a4c9b77!application/vnd.pluto.tree+objectelements0text/plain17text/plaintypeTupleobjectid7be014bd27506452!application/vnd.pluto.tree+objectelements6text/plain29text/plaintypeTupleobjectidbcd5c7e53eb2beaf!application/vnd.pluto.tree+object elements9text/plain26text/plaintypeTupleobjectid6f8558ee5165148d!application/vnd.pluto.tree+object
elements-2text/plain21text/plaintypeTupleobjectida97d298421d9eb40!application/vnd.pluto.tree+objectmoretypeSetprefix_shortSetobjectidc62bd8def750e86d!application/vnd.pluto.tree+objecttypeNamedTupleobjectid60c6d3bae0348446mime!application/vnd.pluto.tree+objectrootassigneeconst track1last_run_timestampA /GNpersist_js_state·has_pluto_hook_features§cell_id$df3c4a33-45f1-4cc2-8c06-d500a0eecc8fdepends_on_disabled_cells§runtimepublished_object_keysdepends_on_skipped_cells§errored$e2fc1d47-2ee9-4844-a6b1-16f76531da86queued¤logsrunning¦outputbodyamimetext/htmlrootassigneelast_run_timestampA 3ipersist_js_state·has_pluto_hook_features§cell_id$e2fc1d47-2ee9-4844-a6b1-16f76531da86depends_on_disabled_cells§runtime
npublished_object_keysdepends_on_skipped_cells§errored$2d36ebe3-1a86-4cad-a235-baec726da926queued¤logsrunning¦outputbody
Example Random Trajectories on Each Track
The black arrows represent the velocity of the car at that position, and the red arrows show the policy action to change the velocity. Note that only non-negative values are allowed for velocity to some of the actions have no impact. Also, the car is not allowed by be stopped so if an action were to reduce the velocity to 0, then a random velocity of +1 will be assigned to either the x or y direction.
Cummulative Distribution Function of Steps to Finish Race
mimetext/htmlrootassigneelast_run_timestampA 3_|persist_js_state·has_pluto_hook_features§cell_id$985f0537-2bbe-4dbb-a113-8ac98d2e0a5fdepends_on_disabled_cells§runtime_Gpublished_object_keys5c6e0de0c-3901-11f0-234e-bd09c571f662/6a054f00f0376f57depends_on_skipped_cells§errored$217ecc59-d6e3-48fa-9d6d-700a3947b805queued¤logsrunning¦outputbody1.936f0mimetext/plainrootassigneelast_run_timestampA -zpersist_js_state·has_pluto_hook_features§cell_id$217ecc59-d6e3-48fa-9d6d-700a3947b805depends_on_disabled_cells§runtimeBҵpublished_object_keysdepends_on_skipped_cells§errored$a35de859-4046-4f6d-9ea9-b523d21cee5dqueued¤logsrunning¦outputbody0make_value_grid (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA %cpersist_js_state·has_pluto_hook_features§cell_id$a35de859-4046-4f6d-9ea9-b523d21cee5ddepends_on_disabled_cells§runtime ѵpublished_object_keysdepends_on_skipped_cells§errored$12c0cd0b-eb4f-45a0-836b-53b3c5cdafd9queued¤logsrunning¦outputbodyW
5.5 Off-policy Prediction via Importance Sampling
mimetext/htmlrootassigneelast_run_timestampA "'+persist_js_state·has_pluto_hook_features§cell_id$12c0cd0b-eb4f-45a0-836b-53b3c5cdafd9depends_on_disabled_cells§runtime ŵpublished_object_keysdepends_on_skipped_cells§errored$aaa9647c-afb6-44d1-ae1e-a2e957064080queued¤logsrunning¦outputbody,updatecount (generic function with 1 method)mimetext/plainrootassigneelast_run_timestampA )Zpersist_js_state·has_pluto_hook_features§cell_id$aaa9647c-afb6-44d1-ae1e-a2e957064080depends_on_disabled_cells§runtime Z published_object_keysdepends_on_skipped_cells§errored$b57462b6-8f9c-4553-9c05-134ff043b00dqueued¤logsrunning¦outputbody&
Exercise 5.9
Modify the algorithm for first-visit MC policy evaluation (section 5.1) to use the incremental implementation for sample averages described in Section 2.4
Returns(s) will not maintain a list but instead be a list of single values for each state. Additionally, another list Counts(s) should be initialized at 0 for each state. When new G values are obtained for state, the Count(s) value should be incremented by 1. Then Returns(s) can be updated with the following formula:
""")
endmetadatashow_logsèdisabled®skip_as_script«code_folded$ff9276eb-2151-4a6f-8257-8348047a9f4ecell_id$ff9276eb-2151-4a6f-8257-8348047a9f4ecodeيrace_episode2 = race_track_episode((position = rand(track2.start), velocity = (0, 0)), rand(racetrack_actions), π_racetrack_rand, track2)metadatashow_logsèdisabled®skip_as_script«code_folded$6f914006-1d8d-41f5-ae8a-fbe0b336946ccell_id$6f914006-1d8d-41f5-ae8a-fbe0b336946ccode[begin
run3_2
showrace(track2, create_policy_function(πstar3_racetrack2, track2_mdp))
endmetadatashow_logsèdisabled®skip_as_script«code_folded$4197cc28-b24c-48cb-bd8d-ef998983ad77cell_id$4197cc28-b24c-48cb-bd8d-ef998983ad77code'struct Ordinary <: ImportanceMethod endmetadatashow_logsèdisabled®skip_as_script«code_folded$e67d9deb-a074-48ba-84db-2e6938ea01f8cell_id$e67d9deb-a074-48ba-84db-2e6938ea01f8codeMfunction monte_carlo_pred_Q(π_target::Matrix{T}, π_behavior::Matrix{T}, mdp::MDP_Opaque{S, A, F, G}, γ::T; num_episodes::Integer = 1000, qinit::T = zero(T), Q::Matrix{T} = ones(T, length(mdp.actions), length(mdp.states)) .* qinit, historystateindex::Integer = 1, samplemethod::ImportanceMethod = Ordinary(), override_state_init::Bool = false, use_target_initial_action::Bool = false, sampleinds = 1:num_episodes) where {T <: AbstractFloat, S, A, F, G}
check_policy(π_target, mdp)
check_policy(π_behavior, mdp)
@assert all(x -> x != 0, π_behavior) #behavior policy must have full coverage
#initialize
counts = zeros(T, length(mdp.actions), length(mdp.states))
valuehistory = zeros(T, length(sampleinds))
weighthistory = ones(T, length(sampleinds))
sampleind = 1
for i in 1:num_episodes
#if only interested in one state then always initialize there
s0 = override_state_init ? mdp.states[historystateindex] : mdp.state_init()
π_init = use_target_initial_action ? π_target : π_behavior
i_a0 = sample_action(π_init, mdp.statelookup[s0])
a0 = mdp.actions[i_a0]
# (s0, a0) = initialize_episode()
(states, actions, rewards) = mdp.simulator(s0, a0, π_behavior)
#update value function for each trajectory
w = updateQ!(mdp, Q, counts, π_target, π_behavior, states, actions, rewards, γ, samplemethod)
#for selected state check value
if i == sampleinds[sampleind]
valuehistory[sampleind] = sum(view(Q, :, historystateindex) .* view(π_target, :, historystateindex))
weighthistory[sampleind] = w
sampleind += 1
end
end
return valuehistory, Q, weighthistory
endmetadatashow_logsèdisabled®skip_as_script«code_folded$82a1f11e-b1b3-4c7d-ab9d-9f6136ae8195cell_id$82a1f11e-b1b3-4c7d-ab9d-9f6136ae8195code6const onestate_π_b = make_random_policy(onestate_mdp)metadatashow_logsèdisabled®skip_as_script«code_folded$11f8290f-f589-49ff-9602-99ccc4192884cell_id$11f8290f-f589-49ff-9602-99ccc4192884codeٕsampleracepolicy(create_policy_function(πstar1_racetrack2, track2_mdp); track = track2, trackname = "Track 2", policyname = "Off policy MC Control")metadatashow_logsèdisabled®skip_as_script«code_folded$7fb4244c-828a-49d6-a15b-178fa3a42e00cell_id$7fb4244c-828a-49d6-a15b-178fa3a42e00codev#policy defined in Example 5.1 which sticks on sums of 20 or 21
const π_blackjack1 = make_simple_blackjack_policy(20)metadatashow_logsèdisabled®skip_as_script«code_folded$0609ad22-0adc-4e4f-afed-b7a46d216576cell_id$0609ad22-0adc-4e4f-afed-b7a46d216576codeusampleracepolicy(create_policy_function(πstar2_racetrack1, track1_mdp); policyname = "Monte Carlo Exploring Starts")metadatashow_logsèdisabled®skip_as_script«code_folded$61eb74eb-88e0-42e6-a14b-3730a800694dcell_id$61eb74eb-88e0-42e6-a14b-3730a800694dcode8const onestate_π_target = reshape([1.0f0; 0.0f0], 2, 1)metadatashow_logsèdisabled®skip_as_script«code_folded$6a96304b-add3-4135-8ccf-46cc23859d53cell_id$6a96304b-add3-4135-8ccf-46cc23859d53code7md"""
#### Off-policy MC Control Racetrack Solution
"""metadatashow_logsèdisabled®skip_as_script«code_folded$c883748c-76b9-4086-8698-b40df51390dacell_id$c883748c-76b9-4086-8698-b40df51390dacodemd"""
> ### *Exercise 5.4*
> The pseudocode for Monte Carlo ES is inefficient because, for each state-action pair, it maintains a list of all returns and repeatedly calculates their mean. It would be more dfficient to use techniques similar to those explained in Section 2.4 to maintain just the mean and a count (for each state-action pair) and update them incrementally. Describe how the pseudocode would be altered to achieve this.
Returns(s,a) will not maintain a list but instead be a list of single values for each state-action pair. Additionally, another list Counts(s,a) should be initialized at 0 for each pair. When new G values are obtained for state-action pairs, the Count(s,a) value should be incremented by 1. Then Returns(s,a) can be updated with the following formula:
$\text{Returns}(s,a) = \frac{\text{Returns}(s,a) \times (\text{Count}(s,a) - 1) + G(s,a)}{\text{Count}(s,a)} = \text{Returns}(s,a) + \frac{G(s,a) - \text{Returns}(s,a)}{\text{Count}(s,a)}$
"""metadatashow_logsèdisabled®skip_as_script«code_folded$f071b7e2-3f78-4132-8b84-f810f178c89dcell_id$f071b7e2-3f78-4132-8b84-f810f178c89dcodebegin
abstract type OneStateAction end
struct Left <: OneStateAction end
struct Right <: OneStateAction end
struct OneState end
const one_state_actions = [Left(), Right()]
const one_state_action_lookup = Dict([Left() => 1, Right() => 2])
one_state_step(::Right) = (0.0f0, true)
one_state_step(::Left) = rand() <= 0.1 ? (1.0f0, true) : (0.0f0, false)
function one_state_simulator(s0, a0::OneStateAction, π)
state_history = [s0]
action_history = Vector{OneStateAction}([a0])
(r, term) = one_state_step(a0)
reward_history = [r]
while !term
i_a = sample_action(π, 1)
a = one_state_actions[i_a]
push!(state_history, OneState())
push!(action_history, a)
(r, term) = one_state_step(a)
push!(reward_history, r)
end
return (state_history, action_history, reward_history)
end
const onestate_mdp = MDP_Opaque([OneState()], [Left(), Right()], () -> OneState(), one_state_simulator)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$8d7b9826-b52c-4d5a-8c63-e83a1229a0becell_id$8d7b9826-b52c-4d5a-8c63-e83a1229a0becodecmd"""
Example trajectories after training for $(mcϵs2.episodes) episodes with ϵ= $(mcϵs2.ϵ)
"""metadatashow_logsèdisabled®skip_as_script«code_folded$67e535c7-437a-49ba-b5ab-9dfe63fe4aaacell_id$67e535c7-437a-49ba-b5ab-9dfe63fe4aaacode*md"""
#### Racetrack Environment Setup
"""metadatashow_logsèdisabled®skip_as_script«code_folded$c8f3f7e3-be7e-4615-a667-d9f789928883cell_id$c8f3f7e3-be7e-4615-a667-d9f789928883codeپ#updates the value estimates at a given state using the future discounted return and the importance-sampling ratio
updatevalue(::Ordinary, q::T, g::T, w::T, c::T) where T<:Real = (w*g - q)/cmetadatashow_logsèdisabled®skip_as_script«code_folded$30809344-b4ab-468b-b4b7-5ef3dca5ffc7cell_id$30809344-b4ab-468b-b4b7-5ef3dca5ffc7codemd"""
> ### *Exercise 5.2*
> Suppose every-visit MC was used instead of first-visit MC on the blackjack task. Would you expect the results to be very different? Why or why not?
As an episode proceeds in blackjack the states will not repeat since every time a card is dealt the player sum changes, or the usable Ace flag changes. Thus the check ensuring that only the first visit to a state is counted in the return average will have no effect on the MC evaluation.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$e2a720b0-a8c4-43a2-bf34-750ff3323004cell_id$e2a720b0-a8c4-43a2-bf34-750ff3323004codemd"""
## 5.4 Monte Carlo Control without Exploring Starts
To only way to ensure all state-action pairs are visited without exploring starts is to use a policy with a non-zero probability of visiting all such states. One policy that meets this criterion is an *ϵ-soft* policy meaning that $\pi(a \vert s) > 0 \: \forall \: s \in \mathcal{S}$. To achieve this with Monte Carlo Control, we simply update the policy to be $\epsilon$-greedy for every Q update, so the maximizing (greedy) action is given a probability $1 - \epsilon + \frac{\epsilon}{\vert \mathcal{A}(s) \vert}$ and all other actions are given the probability $\frac{\epsilon}{\vert \mathcal{A}(s) \vert}$.
Below is code implementing MC control for ϵ-soft policies. It is mostly identical to the every visit method except the policy is always used to select the initial action and the policy update uses an ϵ-greedy update rather than a greedy one.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$1067fcc4-cbc6-453c-a996-d420c498619acell_id$1067fcc4-cbc6-453c-a996-d420c498619acodensampleracepolicy(create_policy_function(πstar1_racetrack1, track1_mdp); policyname = "Off policy MC Control")metadatashow_logsèdisabled®skip_as_script«code_folded$6496c993-6d47-4a6e-a497-2a2de172fbc3cell_id$6496c993-6d47-4a6e-a497-2a2de172fbc3codeYmd"""
### Off-policy Monte-Carlo Prediction Algorithm for Estimating $Q \approx q_π$
"""metadatashow_logsèdisabled®skip_as_script«code_folded$aa647f3e-a4b2-4825-bb2a-1c2469d2c0ebcell_id$aa647f3e-a4b2-4825-bb2a-1c2469d2c0ebcodeٜsampleracepolicy(create_policy_function(πstar2_racetrack2, track2_mdp); track = track2, trackname = "Track 2", policyname = "Monte Carlo Exploring Starts")metadatashow_logsèdisabled®skip_as_script«code_folded$1d3d509c-b11b-4c57-b100-9bcf0489af2bcell_id$1d3d509c-b11b-4c57-b100-9bcf0489af2bcodefunction create_greedy_policy(Q::Matrix{T}; c = 1000, π = copy(Q)) where T<:Real
vhold = zeros(T, size(Q, 1))
for j in 1:size(Q, 2)
vhold .= Q[:, j]
make_greedy_policy!(vhold; c = c)
π[:, j] .= vhold
end
return π
endmetadatashow_logsèdisabled®skip_as_script«code_folded$989ccacd-b410-4967-bf6a-9244e3be785dcell_id$989ccacd-b410-4967-bf6a-9244e3be785dcode`md"""
Number of Episodes: $(@bind mces1 confirm(NumberField(1:10_000_000, default = 1_000)))
"""metadatashow_logsèdisabled®skip_as_script«code_folded$b352d98e-0854-45e3-ac73-8ef434525563cell_id$b352d98e-0854-45e3-ac73-8ef434525563codemd"""
##### Track 1
"""metadatashow_logsèdisabled®skip_as_script«code_folded$202eb066-877d-4537-85b2-31b41db8eca0cell_id$202eb066-877d-4537-85b2-31b41db8eca0codetinitialize_state_value(mdp::MDP_Opaque; vinit::T = 0.0f0) where T<:AbstractFloat = ones(length(mdp.states)) .* vinitmetadatashow_logsèdisabled®skip_as_script«code_folded$3955d71a-3105-445a-868d-66ba0b3dc515cell_id$3955d71a-3105-445a-868d-66ba0b3dc515codeيrace_episode1 = race_track_episode((position = rand(track1.start), velocity = (0, 0)), rand(racetrack_actions), π_racetrack_rand, track1)metadatashow_logsèdisabled®skip_as_script«code_folded$f406be9e-3e3f-4b55-99b0-4858c774ed96cell_id$f406be9e-3e3f-4b55-99b0-4858c774ed96code8md"""
## 5.2 Monte Carlo Estimation of Action Values
"""metadatashow_logsèdisabled®skip_as_script«code_folded$648bfc3f-0649-4401-a97f-89e21057f7b7cell_id$648bfc3f-0649-4401-a97f-89e21057f7b7codecmd"""
Example trajectories after training for $(mcϵs1.episodes) episodes with ϵ= $(mcϵs1.ϵ)
"""metadatashow_logsèdisabled®skip_as_script«code_folded$e10378eb-12b3-4468-9c22-1838107da450cell_id$e10378eb-12b3-4468-9c22-1838107da450code,md"""
### Example 5.5: Infinite Variance
"""metadatashow_logsèdisabled®skip_as_script«code_folded$2e57e4b5-d228-4ce3-b9d8-cf4375bb7c50cell_id$2e57e4b5-d228-4ce3-b9d8-cf4375bb7c50code%md"""
# Dependencies and Settings
"""metadatashow_logsèdisabled®skip_as_script«code_folded$edb4ad06-5e6e-48c4-9ee4-ae0b92927a91cell_id$edb4ad06-5e6e-48c4-9ee4-ae0b92927a91code@md"""
Example trajectories after $mces2 episodes of training
"""metadatashow_logsèdisabled®skip_as_script«code_folded$9df79a71-e58a-497b-bb02-debb69144925cell_id$9df79a71-e58a-497b-bb02-debb69144925code)const track1_mdp = make_track_mdp(track1)metadatashow_logsèdisabled®skip_as_script«code_folded$cebb79b7-c9d6-4b79-ba0e-b2f3c7587724cell_id$cebb79b7-c9d6-4b79-ba0e-b2f3c7587724codemd"""
> ### *Exercise 5.12: Racetrack (programming)*
> Consider driving a race car around a turn like those shown in Figure 5.5. You want to go as fast as possible, but not so fast as to run off the track. In our simplified racetrack, the car is at one of a discrete set of grid positions, the cells in the diagram. The velocity is also discrete, a number of grid cells moved horizontally and vertically per time step. The actions are increments to the velocity components. Each may be changed by +1, -1, or 0 in each step, for a total of nine (3x3) actions. Both velocity components are restricted to be nonnegative and less than 5, and they cannot both be zero except at the starting line. Each episode begins in one of the randomly selected start states with both velocity components zero and ends when the car crosses the finish line. The rewards are -1 for each step until the car crosses the finish line. If the car hits the track boundry, it is moved back to a random position on the starting line, both velocity components are reduced to zero, and the episode continues. Before updating the car's location at each time step, check to see if the projected path of the car intersects the track boundary. If it intersects the finish line, the episode ends; if it intersects anywhere else, the car is considered to have hit the track boundary and is sent back to the starting line. To make the task more challenging, with probality 0.1 at each time step the velocity increments are both zero, independently of the intended increments. Apply a Monte Carlo control method to this task to compute the optimal policy from each starting state. Exhibit several trajectories following the optimal policy (but turn the noise off for these trajectories).
"""metadatashow_logsèdisabled®skip_as_script«code_folded$54f73eb8-dcea-4da0-83af-35720e56ccbccell_id$54f73eb8-dcea-4da0-83af-35720e56ccbccodebmonte_carlo_ϵsoft(mdp::MDP_Opaque, ϵ::T, γ::T, num_episodes; Q_init::Matrix{T} = initialize_state_action_value(mdp; qinit = zero(T)), π_init::Matrix{T} = make_random_policy(mdp; init = one(T)), quench_episode = num_episodes, decay_ϵ = false) where T <: Real = monte_carlo_ϵsoft(mdp, ϵ, π_init, Q_init, γ, num_episodes, quench_episode, decay_ϵ) metadatashow_logsèdisabled®skip_as_script«code_folded$418c045d-90c7-42d8-9126-90185f7e197bcell_id$418c045d-90c7-42d8-9126-90185f7e197bcode/figure_5_2(πstar_blackjack3, Qstar_blackjack3)metadatashow_logsèdisabled®skip_as_script«code_folded$6979db32-670d-466a-9a6e-97c2d8527f3dcell_id$6979db32-670d-466a-9a6e-97c2d8527f3dcodemd"""
> ### *Exercise 5.7*
> In learning curves such as those shown in Figure 5.3 error generally decreases with training, as indeed happened for the ordinary importance-sampling method. But for the weighted importance-sampling method error first increased and then decreased. Why do you think this happened?
In figure 5.3, the true value is about -.277 and we initialized the value function at zero. For any given episode it is likely that the observed return will be -1.0 or 1.0 for a win or a loss. Weighted importance sampling won't update the state value for trajectories which cannot occur in the target policy, so for some of the runs at this early state the state value is unchanged at the 0 initial value. It is only after a certain number of episodes have occured that all of the values will be updated and produce an estimate which is worse than the initial value. Once many samples with non zero weight are collected for each run, then the estimate starts to approach the true value again. If instead we initialized the state value far away from the true value, then you would not see the initial increase in estimate error. See below for an example using an initial value of 1. In this case, no update from weighted importance sampling would produce an error larger than the initial value.
$(figure5_3(;n = 1000, vinit = 1.0f0, episodes = 100, title = "Initial Value = 1.0", caption = "Blackjack State Estimate with Bad Initialization"))
"""metadatashow_logsèdisabled®skip_as_script«code_folded$cd928f87-2832-4595-8ce5-79b69cc56bd9cell_id$cd928f87-2832-4595-8ce5-79b69cc56bd9codeImd"""
#### Figure 5.5
A couple of right turns for the racetrack task.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$ba044e4f-e2a6-4f96-8756-5b24b1bb5ca2cell_id$ba044e4f-e2a6-4f96-8756-5b24b1bb5ca2codey#trajectory of a random episode, arrows indicate the velocity at each step
@htl("""
""")
#using a random policy on track 1, the mean time to finish on track 1 is ~2800 steps. The best possible time when we get "lucky" with random decisions is ~12 steps with worst times ~15-30k steps
#using a random policy on track 2, the mean time to finish on track 1 is ~300 steps. The best possible time when we get "lucky" with random decisions is ~10 steps with worst times ~2k stepsmetadatashow_logsèdisabled®skip_as_script«code_folded$6d6e8916-9b36-4af1-b77d-86cb6a416f88cell_id$6d6e8916-9b36-4af1-b77d-86cb6a416f88codemd"""
##### Track 1
"""metadatashow_logsèdisabled®skip_as_script«code_folded$cede8090-5b1a-436b-a184-fca5c4d3de48cell_id$cede8090-5b1a-436b-a184-fca5c4d3de48codemd"""
> ### *Exercise 5.5*
> Consider an MDP with a single nonterminal state and a single action that transitions back to the nonterminal state with probability $p$ and transitions to the terminal state with probability $1-p$. Let the reward be +1 on all transitions, and let $\gamma=1$. Suppose you observe one episode that lasts 10 steps, with a return of 10. What are the first-visit and every-visit estimators of the value of the nonterminal state?
For the first-visit estimator, we only consider the single future reward from the starting state which would be 10. There is nothing to average since we just have the single value of 10 for the episode.
For the every-visit estimator, we need to average together all 10 visits to the non-terminal state. For the first visit, the future reward is 10. For the second visit it is 9, third 8, and so forth. The final visit has a reward of 1, so the value estimate is the average of 10, 9, ..., 1 which is $\frac{(1+10) \times 5}{10}=\frac{55}{10} = 5.5$
"""metadatashow_logsèdisabled®skip_as_script«code_folded$8668ffc3-6c8c-4c25-8d47-9977bef929d2cell_id$8668ffc3-6c8c-4c25-8d47-9977bef929d2code`md"""
Number of Episodes: $(@bind opmc2 confirm(NumberField(1:10_000_000, default = 1_000)))
"""metadatashow_logsèdisabled®skip_as_script«code_folded$5834c5e0-8a04-47ea-aab8-881c73d8fd4fcell_id$5834c5e0-8a04-47ea-aab8-881c73d8fd4fcodemd"""
##### Track 1
"""metadatashow_logsèdisabled®skip_as_script«code_folded$14536b70-35f0-46ba-93fc-3365a1e8c15ccell_id$14536b70-35f0-46ba-93fc-3365a1e8c15ccodemd"""
##### Results Summary
Off policy MC control training is slow because the random behavior policy takes a very long time to complete a race (~2500 or ~300 steps). Even after 1000 episodes performance is indistinguishable from the random policy.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$39da4cf9-5265-41bc-83d4-311e86675db7cell_id$39da4cf9-5265-41bc-83d4-311e86675db7codem(πstar_blackjack3, Qstar_blackjack3) = off_policy_MC_control(blackjack_mdp, 1.0f0; num_episodes = 3_000_000)metadatashow_logsèdisabled®skip_as_script«code_folded$d97f693d-27f2-49be-a549-07a290c95b53cell_id$d97f693d-27f2-49be-a549-07a290c95b53code}#types allow dispatch for each sampling method based on different incremental update rules
abstract type ImportanceMethod endmetadatashow_logsèdisabled®skip_as_script«code_folded$f9bc84ff-c2f9-4ac2-b2ce-34dfcf837a73cell_id$f9bc84ff-c2f9-4ac2-b2ce-34dfcf837a73code-figure_5_2(πstar_blackjack, Qstar_blackjack)metadatashow_logsèdisabled®skip_as_script«code_folded$8f38a3e9-1872-4ea6-9a03-87112af4bf07cell_id$8f38a3e9-1872-4ea6-9a03-87112af4bf07code(#run n episodes of a race and measure the statistics of the time required to finish
function sampleracepolicy(π; n = 1000, trackname = "Track 1", policyname = "", kwargs...)
trajs = [runrace(π; kwargs...)[1] for _ in 1:n]
randomtrajs = [runrace(s -> rand(racetrack_actions); kwargs...)[1] for _ in 1:n]
ls = filter(x -> x > 0, length.(trajs))
randomls = filter(x -> x > 0, length.(randomtrajs))
f1 = ecdf(ls)
f2 = ecdf(randomls)
t1 = scatter(x = f1.sorted_values, y = f1.(f1.sorted_values), name = "$policyname")
t2 = scatter(x = f2.sorted_values, y = f2.(f2.sorted_values), name = "Random Policy")
p = plot([t1, t2], Layout(xaxis_title = "Steps to Finish Race", yaxis_title = "Percent of Episodes", xaxis_type = "log"))
# p1 = plot(histogram(x = ls, showlegend=false), Layout(title = "$policyname", xaxis_title = "Steps to Finish Race", yaxis_title = "Number of Episodes", showlegend = false))
# p2 = plot(histogram(x = randomls, showlegend=false), Layout(title = "Random Policy", xaxis_title = "Steps to Finish Race", yaxis_title = "Number of Episodes", showlegend = false))
isempty(randomls) && return md"""Policy Unable to Complete race within 10,000 steps"""
parsestd(v) = isnan(std(v)) ? NaN : round(Int64, std(v))
md"""
$(Markdown.parse("Statistics for Steps to Finish Race on $trackname"))
| Statistic | $(Markdown.parse(policyname)) | Random Policy |
| --- | --- | --- |
|Mean | $(round(Int64, mean(ls))) | $(round(Int64, mean(randomls))) |
|Median | $(round(Int64, median(ls))) | $(round(Int64, median(randomls))) |
|Std| $(parsestd(ls)) | $(parsestd(randomls)) |
|Minimum| $(round(Int64, minimum(ls))) | $(round(Int64, minimum(randomls))) |
|Maximum| $(round(Int64, maximum(ls))) | $(round(Int64, maximum(randomls))) |
Cummulative Distribution Function of Steps to Finish Race
$p
"""
endmetadatashow_logsèdisabled®skip_as_script«code_folded$627d5aa3-974f-4949-8b65-9500eba1d7cccell_id$627d5aa3-974f-4949-8b65-9500eba1d7cccoded#recreation of figure 5.2
function figure_5_2(πstar_blackjack, Qstar_blackjack)
policyplot = plot_blackjack_policy(πstar_blackjack)
vstar = sum(Qstar_blackjack .* πstar_blackjack, dims = 1)[:]
# vhit = Qstar_blackjack[1, :][:]
# vstick = Qstar_blackjack[2, :][:]
# vdiff = (vhit .- vstick)
valueplot = plot_blackjack_value(vstar)
# policyplot = plot_blackjack_value(vdiff)
vtitle = md"""$v_*$"""
ptitle = md"""$π_*$"""
md"""
| |$\pi_*$ (Black = Stick, White = Hit)|$v_*$|
|---|:---:|:---:|
|Usable ace|$(policyplot[1])|$(valueplot[1])|
|No usable ace|$(policyplot[2])|$(valueplot[2])|
"""
endmetadatashow_logsèdisabled®skip_as_script«code_folded$02dd1e77-2a7e-4123-94db-d17b31a8b15acell_id$02dd1e77-2a7e-4123-94db-d17b31a8b15acode4const blackjack_state1 = BlackjackState(13, 2, true)metadatashow_logsèdisabled®skip_as_script«code_folded$09b67730-39e7-4209-8117-6bc3adfb342acell_id$09b67730-39e7-4209-8117-6bc3adfb342acodeKmd"""
$\begin{flalign}
&=0.1 \sum_{N=1}^\infty \left ( \frac{1}{2} \right ) ^N 0.9^{N-1} \left ( \frac{\sum_{i=1}^N 2^i}{N} \right ) ^2 \\
&=\frac{0.1}{0.9} \sum_{N=1}^\infty 0.45^{N} N^{-2} \left ( \sum_{i=1}^N 2^i \right ) ^2 \\
\end{flalign}$
Consider the term: $\left ( \sum_{i=1}^N 2^i \right ) ^2 = (2 + 2^2 + 2^3 + \cdots + 2^N)^2 \gt 2^{2N}$ since all the other terms in the parentheses are positive.
$\begin{flalign}
&\gt\frac{0.1}{0.9} \sum_{N=1}^\infty 0.45^{N} N^{-2} 2^{2N} \\
&= \frac{0.1}{0.9} \sum_{N=1}^\infty 0.45^{N} N^{-2} 4^{N} \\
&= \frac{0.1}{0.9} \sum_{N=1}^\infty \frac{1.8^{N}}{N^{2}} \\
\end{flalign}$
The question is then reduced to whether the following infinite sum diverges: $\sum_{N=1}^\infty \frac{1.8^{N}}{N^{2}}$. Consider the logarithm of each term in the series $\log {\frac{1.8^N}{N^2}} = \log{1.8^N} - \log{N^2} = N \log{1.8} - 2 \log{N}$. As N approaches infinity $N \gt \log{N}$ so the log of each term diverges as do the terms individually as does the series. Therefore the variance diverges with ever-visit MC as it does with first visit MC.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$b7dfc031-6bf6-44cd-b814-05f693a0a27dcell_id$b7dfc031-6bf6-44cd-b814-05f693a0a27dcode<#ϵ-soft training also produces a policy that can finish the race but results heavily depend on the value of ϵ. A small ϵ around 2% seems to produce the best results that exceed that of even the exploring starts algorithm
begin
run3_1
showrace(track1, create_policy_function(πstar3_racetrack1, track1_mdp))
endmetadatashow_logsèdisabled®skip_as_script«code_folded$2572e35c-e6a3-4562-aa0f-6a5ab32d39eacell_id$2572e35c-e6a3-4562-aa0f-6a5ab32d39eacode @htl("""
State Value Function
⋮
State Action Value Function
⋮
""")metadatashow_logsèdisabled®skip_as_script«code_folded$859354fe-7f40-4658-bf12-b5ee20a815a7cell_id$859354fe-7f40-4658-bf12-b5ee20a815a7code6md"""
## 5.8 Discounting-aware Importance Sampling
"""metadatashow_logsèdisabled®skip_as_script«code_folded$f9f6c182-62f8-4a5a-8b43-8716db468427cell_id$f9f6c182-62f8-4a5a-8b43-8716db468427code)const maxspeed = maximum(racetrackspeeds)metadatashow_logsèdisabled®skip_as_script«code_folded$47daf83b-8fe9-4491-b9ae-84bd269d5546cell_id$47daf83b-8fe9-4491-b9ae-84bd269d5546code$md"""
## 5.3 Monte Carlo Control
"""metadatashow_logsèdisabled®skip_as_script«code_folded$ba8a5804-4be3-43fe-95d7-c957ce02a1d4cell_id$ba8a5804-4be3-43fe-95d7-c957ce02a1d4codefunction make_action_style(dvx, dvy)
((dvx==0) && (dvy==0)) && return """"""
"""
[dvx='$dvx'][dvy='$dvy']::after {
content: '→';
color: red;
transform: rotate($(atand(dvy, dvx))deg);
}
"""
endmetadatashow_logsèdisabled®skip_as_script«code_folded$481ad435-cc80-4164-882d-8310b010ca91cell_id$481ad435-cc80-4164-882d-8310b010ca91codeٶfunction make_simple_blackjack_policy(stick_sum::Integer)
mapreduce(hcat, blackjackstates) do state
state.sum < stick_sum && return [1.0f0, 0.0f0]
return [0.0f0, 1.0f0]
end
endmetadatashow_logsèdisabled®skip_as_script«code_folded$8bcaa31b-8caf-43da-83a0-47e0c04c2a30cell_id$8bcaa31b-8caf-43da-83a0-47e0c04c2a30code@htl("""
Track 1
Track 2
$(rendertrack(track1))
$(rendertrack(track2))
""")metadatashow_logsèdisabled®skip_as_script«code_folded$7c9486cd-1916-4e13-b415-fb113bd9e04bcell_id$7c9486cd-1916-4e13-b415-fb113bd9e04bcode/md"""
## 5.7 Off-policy Monte Carlo Control
"""metadatashow_logsèdisabled®skip_as_script«code_folded$821ce23a-524b-4203-96d6-4d5b454fe1fdcell_id$821ce23a-524b-4203-96d6-4d5b454fe1fdcodeٓsampleracepolicy(create_policy_function(πstar3_racetrack2, track2_mdp); track = track2, trackname = "Track 2", policyname = "Monte Carlo ϵ-Soft")metadatashow_logsèdisabled®skip_as_script«code_folded$dc57a71f-e44c-4385-ad2a-e6c14d5e5201cell_id$dc57a71f-e44c-4385-ad2a-e6c14d5e5201codemd"""
> ### *Exercise 5.14*
> Modify the algorithm for off-policy Monte Carlo control (page 111) to use the idea of the truncated weighted-average estimator (5.10). Note that you will first need to convert this equation to action values.
Equation (5.10)
$V(s) = \frac{\sum_{t \in \mathscr{T}(s)}\left((1-\gamma)\sum_{h=t+1}^{T(t)-1}\gamma^{h-t-1} \rho_{t:h-1} \bar{G}_{t:h} + \gamma^{T(t)-t-1} \rho_{t:T(t)-1} \bar{G}_{t:T(t)} \right)}{\sum_{t \in \mathscr{T}(s)} \left( (1-\gamma) \sum_{h=t+1}^{T(t)-1} \gamma^{h-t-1} \rho_{t:h-1} + \gamma^{T(t)-t-1} \rho_{t:T(t)-1} \right)}$
Converting this to action-value estimates:
$Q(s,a) = \frac{\sum_{t \in \mathscr{T}(s,a)}\left( R_{t+1} + (1-\gamma)\sum_{h=t+2}^{T(t)-1}\gamma^{h-t-1} \rho_{t+1:h-1} \bar{G}_{t+1:h} + \gamma^{T(t)-t-1} \rho_{t+1:T(t)-1} \bar{G}_{t+1:T(t)} \right)}{\sum_{t \in \mathscr{T}(s,a)} \left( 1 + (1-\gamma) \sum_{h=t+2}^{T(t)-1} \gamma^{h-t-1} \rho_{t+1:h-1} + \gamma^{T(t)-t-1} \rho_{t+1:T(t)-1} \right)}$
For the algorithm on page 111, need to add a variable in the loop to keep track of $\bar{G}$ both from the start of the episode forwards. The inner loop should also start from the beginning of each episode and go forwards rather than starting at the end going backwards. The term added to the numerator and denominator will be ready including $\bar{G}$ and $\rho$ once the end of the episode is reached. A $\gamma$ accumulator can be initiazed at 1 and kept track of in the inner loop by repeatedly multiplying by γ each iteration.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$00cd2194-af13-415a-b725-bb34832e5d9acell_id$00cd2194-af13-415a-b725-bb34832e5d9acode function figure5_3(;n = 100, vinit = 0.0f0, targetstart = true, episodes = 10_000, title = "", caption = "Figure 5.3")
#note that with targetstart = true, the episode will always begin with the action selected by the target policy. Since we only care about the value estimate for this state, we only need the q value for actions taken by the target policy. This way, every episode will produce relevant sample updates
runsim(importancemethod) = monte_carlo_pred_V(π_blackjack1, π_rand_blackjack, blackjack_mdp, 1.0f0; num_episodes = episodes, historystateindex = blackjack_stateindex1, vinit = vinit, override_state_init = true, samplemethod=importancemethod)[1]
vhists = [[runsim(importancemethod) for _ in 1:n] for importancemethod in [Ordinary(), Weighted()]]
errors = [[(v .- blackjack_state_value1) .^2 for v in vhists] for vhists in vhists]
traces1 = [scatter(x = 1:episodes, y = mean(error), name = name) for (error, name) in zip(errors, ["Ordinary importance sampling", "Weighted importance sampling"])]
p1 = plot(traces1, Layout(xaxis_type = "log", yaxis_range = [-0.1,5], legend_orientation = "h", legend_y = -0.2, xaxis_title = "Episodes", yaxis_title = "Mean square error (average over $n runs)", title = title))
traces2 = [scatter(x = 1:episodes, y = mean(vhist), name = name) for (vhist, name) in zip(vhists, ["Ordinary importance sampling", "Weighted importance sampling"])]
p2 = plot(traces2, Layout(xaxis_type = "log", legend_orientation = "h", xaxis_title = "Episodes", yaxis_title = "State Value Estimate (average over $n runs)"))
traces3 = [scatter(x = 1:episodes, y = var(vhist), name = name) for (vhist, name) in zip(vhists, ["Ordinary importance sampling", "Weighted importance sampling"])]
p3 = plot(traces3, Layout(xaxis_type = "log", legend_orientation = "h", xaxis_title = "Episodes", yaxis_title = "State Value Estimate Variance Over $n runs"))
md"""
### $caption
Weighted importance sampling produces lower error estimates of the value of a single blackjack state from off-policy episodes
$p1
"""
endmetadatashow_logsèdisabled®skip_as_script«code_folded$da66b3be-1fe2-4edb-9560-71ce7c0bed12cell_id$da66b3be-1fe2-4edb-9560-71ce7c0bed12codeh(πstar1_racetrack2, Qstar1_racetrack2) = off_policy_MC_control(track2_mdp, 1.0f0; num_episodes = opmc2)metadatashow_logsèdisabled®skip_as_script«code_folded$d16ac2a8-1a5a-4ded-9285-d2c6cd550066cell_id$d16ac2a8-1a5a-4ded-9285-d2c6cd550066code#target policy state value estimate and variance, why is the mean squared error after 1 episode for weighted importance sampling less than the variance of the state values? The reason is after 1 episode of weighted importance sampling, there is a greater than 50% chance of a 0% decision being made resulting in the value estimate not updating from its initial value. Since that initial value is 0 and episodes are likely to terminate with rewards of -1 or 1, the variance is moved closer to 0 than for truly sampling the target policy rewards
const blackjack_state_value1 = estimate_blackjack_state(blackjack_state1, π_blackjack1, 5_000_000) |> meanmetadatashow_logsèdisabled®skip_as_script«code_folded$830d6d61-7259-43e7-8d6d-09bc81818dd9cell_id$830d6d61-7259-43e7-8d6d-09bc81818dd9codefigure_5_4(6, 10)metadatashow_logsèdisabled®skip_as_script«code_folded$e293e184-5938-40b5-a04b-5306760a06aecell_id$e293e184-5938-40b5-a04b-5306760a06aecodefunction estimate_blackjack_state(blackjackstate, π_blackjack, num_episodes)
stateindex = blackjack_mdp.statelookup[blackjackstate]
estimate_mdp_state(blackjack_mdp, π_blackjack, stateindex, num_episodes)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$66645f1a-b591-43e7-b931-8ed0cc7d6898cell_id$66645f1a-b591-43e7-b931-8ed0cc7d6898code]begin
race_1_2
showrace(track2, create_policy_function(πstar1_racetrack2, track2_mdp))
endmetadatashow_logsèdisabled®skip_as_script«code_folded$658ceeaa-1b45-47bd-a364-eaa1759d17accell_id$658ceeaa-1b45-47bd-a364-eaa1759d17accode#starting in state s0 and with policy π, complete a single episode on given track returning the trajectory and rewards
function race_track_episode(s0::S, a0::A, π, track; maxsteps = Inf, failchance = 0.1) where {S, A}
# @assert in(s0.position, track.start)
# @assert s0.velocity == (0, 0)
#take a forward step from current state returning new state and whether or not the episode is over
function step(s, a)
pnew, vnew, psquare = project_path(s.position, s.velocity, a)
# setdiff!(psquare, track.body, track.start)
# fsquares = intersect(psquare, track.finish)
finish = any(square -> in(square, track.finish), psquare)
# outsquares = setdiff!(psquare, track.body, track.start)
# if !isempty(fsquares) #car finished race
if finish # care finished race
((position = first(intersect!(psquare, track.finish)), velocity = (0, 0)), true)
elseif !isempty(setdiff!(psquare, track.body, track.start)) #car path went outside of track
((position = rand(track.start), velocity = (0, 0)), false)
else
((position = pnew, velocity = vnew), false)
end
end
states = [s0]
actions = [a0]
rewards = Vector{Float32}()
function get_traj(s, a, nstep = 1)
(snew, isdone) = step(s, a)
push!(rewards, -1.0f0)
while !isdone && (nstep < maxsteps)
anew = π(snew)
push!(states, snew)
push!(actions, anew)
(snew, isdone) = step(snew, rand() > failchance ? anew : (0, 0))
push!(rewards, -1.0f0)
nstep += 1
end
return isdone
end
isdone = get_traj(s0, a0)
!isdone && length(states) >= maxsteps && return Vector{S}(), Vector{A}(), Vector{Float32}()
return states, actions, rewards
endmetadatashow_logsèdisabled®skip_as_script«code_folded$04752549-ffca-4e31-869e-714f835d3e85cell_id$04752549-ffca-4e31-869e-714f835d3e85codeIconst blackjack_stateindex1 = blackjack_mdp.statelookup[blackjack_state1]metadatashow_logsèdisabled®skip_as_script«code_folded$e89706f1-0c6a-4da4-82a1-ccf153f2e186cell_id$e89706f1-0c6a-4da4-82a1-ccf153f2e186code;md"""
#### Monte Carlo Exploring Starts Solution Method
"""metadatashow_logsèdisabled®skip_as_script«code_folded$ab10ccd7-75ba-475c-af26-f8b36daaf880cell_id$ab10ccd7-75ba-475c-af26-f8b36daaf880codelmd"""
> ### *Exercise 5.11*
> In the boxed algorithm for off-policy MC control, you may have been expecting the $W$ update to have involved the importance-sampling ratio $\frac{\pi(A_t|S_t)}{b(A_t|S_T)}$, but instead it involves $\frac{1}{b(A_t|S_t)}$. Why is this nevertheless correct?
The target policy $\pi(s)$ is always deterministic, only selecting a single action according to $\pi(s)=\text{argmax}_a Q(s,a)$. Therefore the numerator in importance-sampling ratio will either be 1 when the trajectory action matches the one given by $\pi(s)$ or it will be 0. The inner loop will exit if such as action is selected as it will result in zero values of W for the rest of the trajectory and thus no further updates to $Q(s,a)$ or $\pi(s)$. The only value of $\pi(s)$ that would be encountered in the equation is therefore 1 which is why the numerator is a constant.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$4481fa33-1ff3-4778-8486-d4d8a15775cdcell_id$4481fa33-1ff3-4778-8486-d4d8a15775cdcode\begin
run2_2
showrace(track2, create_policy_function(πstar2_racetrack2, track2_mdp))
endmetadatashow_logsèdisabled®skip_as_script«code_folded$1b02e593-d791-424c-b956-62cc480fcf40cell_id$1b02e593-d791-424c-b956-62cc480fcf40codemd"""
##### Results Summary
Unlike the other techniques, Monte Carlo ϵ-Soft requires selecting the parameter ϵ and the performance of each algorithm varies a lot with this parameter and the number of training episodes. For a short training time of 1,000 episodes, small values of ϵ seem to perform better such as 0.01 or 0.02. Under those conditions, performance of the policies is far better than random with mean episode lengths of 32 and 24 respectively. Longer training improves the results but also requires changing ϵ and possibly introducing a decay rate so it can start high and approach 0 after a large number of episodes.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$72e9721f-ee17-4557-b090-71728e6c22cecell_id$72e9721f-ee17-4557-b090-71728e6c22cecode?makelookup(v::Vector) = Dict(x => i for (i, x) in enumerate(v))metadatashow_logsèdisabled®skip_as_script«code_folded$11723075-d1db-4512-abf2-3fe494a71a3bcell_id$11723075-d1db-4512-abf2-3fe494a71a3bcodefunction check_policy(π::Matrix{T}, mdp::MDP_Opaque{S, A, F}) where {T <: AbstractFloat, S, A, F}
#checks to make sure that a policy is defined over the same space as an MDP
(n, m) = size(π)
num_actions = length(mdp.actions)
num_states = length(mdp.states)
@assert n == num_actions "The policy distribution length $n does not match the number of actions in the mdp of $(num_actions)"
@assert m == num_states "The policy is defined over $m states which does not match the mdp state count of $num_states"
return nothing
endmetadatashow_logsèdisabled®skip_as_script«code_folded$059b1c0f-eb21-4a4a-8aed-64e9ac07b541cell_id$059b1c0f-eb21-4a4a-8aed-64e9ac07b541code`md"""
Number of Episodes: $(@bind mces2 confirm(NumberField(1:10_000_000, default = 1_000)))
"""metadatashow_logsèdisabled®skip_as_script«code_folded$b2115f33-f8e2-452e-9b0e-90610f0f09b1cell_id$b2115f33-f8e2-452e-9b0e-90610f0f09b1code٣function make_random_policy(mdp::MDP_Opaque; init::T = 1.0f0) where T <: AbstractFloat
ones(T, length(mdp.actions), length(mdp.states)) ./ length(mdp.actions)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$82284c63-2306-4469-9b1a-a5ec87037e79cell_id$82284c63-2306-4469-9b1a-a5ec87037e79codeplot_fig5_1()metadatashow_logsèdisabled®skip_as_script«code_folded$5b32bbc7-dc34-4fc3-bacc-92e55f26a98ccell_id$5b32bbc7-dc34-4fc3-bacc-92e55f26a98ccode4[monte_carlo_pred_Q(π_blackjack1, π_rand_blackjack, blackjack_mdp, 1.0f0; num_episodes = 1, historystateindex = blackjack_stateindex1, qinit = 0.0f0, override_state_init = true, samplemethod=Ordinary(), use_target_initial_action = true)[3][1:1] |> sum for i in 1:1000] |> v -> mean(filter(x -> x != 0, v))metadatashow_logsèdisabled®skip_as_script«code_folded$c8be6951-b6ec-4444-8c7f-ca5db6681571cell_id$c8be6951-b6ec-4444-8c7f-ca5db6681571code٠makegridsquare(x, y; class="", xmin=0, ymin=0) = """"""metadatashow_logsèdisabled®skip_as_script«code_folded$887de995-04e8-4d84-88d7-ad096a5747dfcell_id$887de995-04e8-4d84-88d7-ad096a5747dfcodeAmd"""
Example trajectories after training for $opmc1 episodes
"""metadatashow_logsèdisabled®skip_as_script«code_folded$3ee31af5-b19c-49dc-8fbf-f07e93d1f0c5cell_id$3ee31af5-b19c-49dc-8fbf-f07e93d1f0c5codegmd"""
### Figure 5.2b:
Recreation of Figure 5.2 using an ϵ-soft MC control with $$\epsilon = 0.1$$
"""metadatashow_logsèdisabled®skip_as_script«code_folded$ffd1e39d-e66b-40a3-8ad1-c9480d371fe8cell_id$ffd1e39d-e66b-40a3-8ad1-c9480d371fe8codemd"""
##### Results Summary
Each environment has 7300 and 12875 states respectively, so Monte Carlo Exploring starts would need to sample at least this many episodes to have a non zero probability of coverage. Surprisingly, even after just 1000 episodes of training the results are quite an improvement over the random policy with the mean finish time of about 30 steps for both. Although at the high end, some episodes still take over 100 steps to complete (still much better than the random policy). If we allow training for 10-100 million episodes, which is necessary to get a reasonable sample size for each state, then the results are much improved with episode step lengths from 11 to 18 for track 1 and 9 to 16 for track2.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$13cc524c-d983-44f4-8731-0595249fb888cell_id$13cc524c-d983-44f4-8731-0595249fb888codefunction monte_carlo_ES(mdp::MDP_Opaque, π_init::Matrix{T}, Q_init::Matrix{T}, γ, num_episodes; override_state_init = false) where T <: Real
#initialize
π = copy(π_init)
Q = copy(Q_init)
counts = zeros(Int64, length(mdp.actions), length(mdp.states))
vhold = zeros(T, length(mdp.actions))
for i in 1:num_episodes
s0 = override_state_init ? rand(mdp.states) : mdp.state_init()
a0 = rand(mdp.actions)
(states, actions, rewards) = mdp.simulator(s0, a0, π)
#there's no check here so this is equivalent to every-visit estimation
t = length(states)
g = zero(T)
for t in length(states):-1:1
#accumulate future discounted returns
g = γ*g + rewards[t]
i_s = mdp.statelookup[states[t]]
i_a = mdp.actionlookup[actions[t]]
#increment count by 1
counts[i_a, i_s] += 1
Q[i_a, i_s] += (g - Q[i_a, i_s])/counts[i_a, i_s] #update running average of Q
vhold .= Q[:, i_s]
make_greedy_policy!(vhold)
π[:, i_s] .= vhold
end
end
return π, Q
endmetadatashow_logsèdisabled®skip_as_script«code_folded$8faca500-b80d-4b50-88b6-683d18a1286bcell_id$8faca500-b80d-4b50-88b6-683d18a1286bcodeٕ#behavior policy state value estimate and variance
estimate_blackjack_state(blackjack_state1, π_rand_blackjack, 5_000_000) |> v -> (mean(v), var(v))metadatashow_logsèdisabled®skip_as_script«code_folded$755be8f1-9d9e-4afd-8a70-07fab78e4333cell_id$755be8f1-9d9e-4afd-8a70-07fab78e4333codemd"""
##### Track 2
"""metadatashow_logsèdisabled®skip_as_script«code_folded$01683e11-a368-45bc-abbc-bbd5c94d7b22cell_id$01683e11-a368-45bc-abbc-bbd5c94d7b22code&plot_value(grid; title = "", xtitle = "Dealer showing", ytitle = "Player sum", xticktext = ["A", "10"], yticktext = [12, 21], showscale = false, width = 350, height = 300) = plot(heatmap(x = 1:10, y = 12:21, z = grid, showscale=showscale, colorscale = "Bluered", zmin = -1.0, zmax = 1.0), Layout(title = title, yaxis_title = ytitle, yaxis_tickvals = [12, 21], xaxis_title = xtitle, yaxis_ticktext = yticktext, xaxis_tickvals = [1, 10], xaxis_ticktext = xticktext, width = width, height = height, autosize = false, margin = attr(l = 0, b = 0, r = 0)))metadatashow_logsèdisabled®skip_as_script«code_folded$5e2420fb-b2cc-49fc-91e3-3de80fba698bcell_id$5e2420fb-b2cc-49fc-91e3-3de80fba698bcode&#run a single race episode from a valid starting position with a given policy and track
function runrace(π; track = track1, maxsteps = 10_000)
s0 = (position = rand(track.start), velocity = (0, 0))
a0 = π(s0)
race_track_episode(s0, a0, π, track, maxsteps = maxsteps, failchance = 0.0)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$1e6f7e5e-c5ce-479c-abbb-6c388c254626cell_id$1e6f7e5e-c5ce-479c-abbb-6c388c254626code2#there's no check here so this is equivalent to every-visit estimation
function updateV!(mdp, V::Vector{T}, counts::Vector{T}, π_target::Matrix{T}, π_behavior::Matrix{T}, states, actions, rewards::Vector{T}, γ::T, samplemethod::ImportanceMethod; t = length(states), g_old = zero(T), w = one(T)) where T<:Real
#terminate at the end of a trajectory
(t == 0) && return w
i_s = mdp.statelookup[states[t]]
i_a = mdp.actionlookup[actions[t]]
#since this is the value estimate, every action must update the importance-sampling weight before the update to that state is calculated. In contrast, for the action-value estimate the weight is only the actions made after the current step are relevant to the weight
w = w * π_target[i_a, i_s] / π_behavior[i_a, i_s]
counts[i_s] += updatecount(samplemethod, w)
#terminate when w = 0 if the weighted sample method is being used. under ordinary sampling, the updates to the count and value will still occur because the denominator will still increment
if (w == zero(T)) && isa(samplemethod, Weighted)
return w
end
#accumulate future discounted returns
g = γ*g_old + rewards[t]
V[i_s] += updatevalue(samplemethod, V[i_s], g, w, counts[i_s])
updateV!(mdp, V, counts, π_target, π_behavior, states, actions, rewards, γ, samplemethod; t = t-1, g_old = g, w = w)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$5e012ead-b4f9-45a9-979d-88b0b1086263cell_id$5e012ead-b4f9-45a9-979d-88b0b1086263code#weighted importance sampling produces the correct value estimate even after 100 episodes
monte_carlo_pred_Q(onestate_π_target, onestate_π_b, onestate_mdp, 1.0f0; num_episodes = 100, samplemethod = Weighted())metadatashow_logsèdisabled®skip_as_script«code_folded$a0eb6939-11bb-458d-bee3-9ed763819f62cell_id$a0eb6939-11bb-458d-bee3-9ed763819f62code+md"""
#### Racetrack Visualization Code
"""metadatashow_logsèdisabled®skip_as_script«code_folded$21d248f5-edad-4614-8c1c-ae330f9e5a18cell_id$21d248f5-edad-4614-8c1c-ae330f9e5a18codestruct MDP_Opaque{S, A, F<:Function, G<:Function}
states::Vector{S}
statelookup::Dict{S, Int64}
actions::Vector{A}
actionlookup::Dict{A, Int64}
state_init::G #function that produces an initial state for an episode
simulator::F #function that takes as input an initial state action pair as well as the policy to be simulated. Should return a trajectory as a vector of states, actions and rewards all of equal length
function MDP_Opaque(states::Vector{S}, actions::Vector{A}, state_init::G, simulator::F) where {S, A, F<:Function, G<:Function}
statelookup = makelookup(states)
actionlookup = makelookup(actions)
new{S, A, F, G}(states, statelookup, actions, actionlookup, state_init, simulator)
end
endmetadatashow_logsèdisabled®skip_as_script«code_folded$a68b4965-c392-47e5-9b29-93e7ada9990acell_id$a68b4965-c392-47e5-9b29-93e7ada9990acodeofunction plot_fig5_1()
(uagrid10k, nuagrid10k) = eval_blackjack_policy(π_blackjack1, 10_000)
(uagrid500k, nuagrid500k) = eval_blackjack_policy(π_blackjack1, 500_000)
p1 = plot_value(uagrid10k; title = "After 10,000 episodes", width = 320, ytitle = "", xtitle = "")
p2 = plot_value(nuagrid10k, width = 320, ytitle = "")
# p2 = plot(heatmap(z = nuagrid10k, showscale = false, colorscale = "Bluered", zmin = -1.0, zmax = 1.0), Layout(width = 300, height = 300, margin = attr(b = 0, r = 0, t=0, l = 0), autosize = false, yaxis_title = "No usable ace"))
p3 = plot_value(uagrid500k, title = "After 500,000 episodes", showscale=true, width = 400, xtitle = "")
# p3 = plot(heatmap(z = uagrid500k, showscale = false, colorscale = "Bluered", zmin = -1.0, zmax = 1.0), Layout(margin = attr(b = 0, r = 0, t=0, l = 0), autosize = false, width = 350, height = 300, title = "After 500,000 episodes"))
p4 = plot_value(nuagrid500k; showscale = true, width = 400)
# p4 = plot(heatmap(z = nuagrid500k, colorscale = "Bluered", zmin = -1.0, zmax = 1.0), Layout(width = 300, height = 300, yaxis_ticks = (1:10, 12:21), xaxis_ticks = (1:10, ["A", "", "", "", "", "", "", "", "", "10"]), legend = false, xaxis_title = "Dealer Showing"))
# plot(p1, p3, p2, p4, layout = (2, 2))
@htl("""
Usable ace
$p1
$p3
No usable ace
$p2
$p4
""")
# [p1 p3; p2 p4]
endmetadatashow_logsèdisabled®skip_as_script«code_folded$d766d44e-3684-497c-814e-8f71740cb232cell_id$d766d44e-3684-497c-814e-8f71740cb232code٢md"""
### **Figure 5.1**:
Approximate state-value functions for the blackjack policy that sticks only on 20 or 21, computed by Monte Carlo policy evaluation
"""metadatashow_logsèdisabled®skip_as_script«code_folded$0dfd7afb-127c-4afd-8374-3c9a20a9ee76cell_id$0dfd7afb-127c-4afd-8374-3c9a20a9ee76code.π_racetrack_rand(s) = rand(racetrack_actions)metadatashow_logsèdisabled®skip_as_script«code_folded$bf33230e-342b-4486-89ac-9667438de503cell_id$bf33230e-342b-4486-89ac-9667438de503codemd"""
> ### *Exercise 5.8*
> The results with Example 5.5 and shown in Figure 5.4 used a first-visit MC method. Suppose that instead an every-visit MC method was used on the same problem. Would the variance of the estimator still be infinite? Why or why not?
The state value estimate can be computed by summing terms for all of the episode lengths just like for the first visit method. Each episode has a reward of +1 from the terminal transition and we only need to consider episodes that take the left action. $\frac{\pi(A_t|S_t)}{b(A_t|S_t)} = 2$ for all cases, so the importance sampling ratio is just $2^T$ where T is the total length of that episode. The probabilities for each episode length is unchanged from Example 5.5 and is just 0.1 times 0.9 times the number of steps preceeding the terminal step. Compared to the calculation in Example 5.5, the expected value calculation must also have the importance sampling ratio terms for all of N visits in the length N episode instead of just the first one:
Length 1 episode
$\frac{1}{2} \cdot 0.1 \cdot (2)^2$
Length 2 episode, the term representing X is now an average of every visit along the trajectory. The probability of the trajectory is unchanged from before.
$\frac{1}{2} \cdot 0.9 \cdot \frac{1}{2} \cdot 0.1 \left ( \frac{2^2 + 2}{2} \right)^2$
Length 3 episode
$\frac{1}{2} \cdot 0.9 \cdot \frac{1}{2} \cdot 0.9 \cdot \frac{1}{2} \cdot 0.1 \left ( \frac{2^3 + 2^2 + 2}{3} \right)^2$
Length N episode
$=0.1 \left ( \frac{1}{2} \right ) ^N 0.9^{N-1} \left ( \frac{\sum_{i=1}^N 2^i}{N} \right ) ^2$
So the expected value is the sum of these terms for every possible episode length:
"""metadatashow_logsèdisabled®skip_as_script«code_folded$826139cc-b52e-11ec-0d47-25ab689851fdcell_id$826139cc-b52e-11ec-0d47-25ab689851fdcodewmd"""
# Chapter 5: Monte Carlo Methods
In this chapter we will use a sampling technique that does not require complete knowledge of the environment, only the ability to interact with it. We will focus on episodic tasks so that the sampled returns are always well defined. Unlike the dynamic programming methods from before, these techniques will estimate the value functions rather than computing them directly. With enough samples, these techniques will also converge to the correct solution.
## 5.1 Monte Carlo Prediction
First we consider using Monte Carlo methods to learn the state-value function for a given policy. The most obvious way to estimate this is to simply average the returns observed after vising a particular state. If we save the trajectories of an agent interacting with an MDP, we can keep track of how many times an agent visits a state. In the technique called *first visit MC* we look at the returns accumulated after the first visit to a state in that episode only making a single update. It is also possible to update the state value for every visit that occurs in an episode, but the theoretical properties for *first visit MC* are more widely studied. Both techniques, however, can be shown to converge as the number of visits goes to infinity. Below is code implementing Monte Carlo prediction using *every visit MC* and an in place update of the average
"""metadatashow_logsèdisabled®skip_as_script«code_folded$0bd705cb-ad38-4cbb-b8fc-7e0617635282cell_id$0bd705cb-ad38-4cbb-b8fc-7e0617635282codecmd"""
### Optimal Blackjack Policy Found with Off-policy MC control (behavior policy is random)
"""metadatashow_logsèdisabled®skip_as_script«code_folded$43f9b824-fd56-4d56-84c3-23e2a3a37178cell_id$43f9b824-fd56-4d56-84c3-23e2a3a37178codemonte_carlo_pred_V(π_blackjack1, π_rand_blackjack, blackjack_mdp, 1.0f0; num_episodes = 100000, historystateindex = blackjack_stateindex1, vinit = 0.0f0, override_state_init = true, samplemethod=Ordinary())[3] |> mean #mean weight is 2 and it stays this way as the number of episodes increases so the returns that are seen by the behavior are roughtly doubled and counted with the 0 returnsmetadatashow_logsèdisabled®skip_as_script«code_folded$b39d1ea0-86a2-4215-ae73-e4492f3f2f00cell_id$b39d1ea0-86a2-4215-ae73-e4492f3f2f00codeKmd"""
### Example 5.4: Off-policy Estimation of a Blackjack State Value
"""metadatashow_logsèdisabled®skip_as_script«code_folded$a307e780-996a-485f-af59-b44982dfceb4cell_id$a307e780-996a-485f-af59-b44982dfceb4code/function rendertrack(track; episode = ())
trajectory = if isempty(episode)
Dict()
else
states, actions, rewards = episode
Dict(begin
position, velocity = states[i]
action = actions[i]
position => (velocity = velocity, action = action)
end
for i in eachindex(first(episode)))
end
function getvelocities(position)
!haskey(trajectory, position) && return ()
(vx, vy) = trajectory[position].velocity
(dvx, dvy) = trajectory[position].action
(vx = vx, vy = vy, dvx = dvx, dvy = dvy)
end
trackpoints = union(track...)
xmin, xmax = extrema(p -> p[1], trackpoints)
ymin, ymax = extrema(p -> p[2], trackpoints)
function makesquare(a; kwargs...)
velocities = getvelocities(a)
isempty(velocities) && return makegridsquare(first(a), last(a); xmin = xmin, ymin = ymin, kwargs...)
makegridsquare(first(a), last(a), velocities.vx, velocities.vy, velocities.dvx, velocities.dvy; xmin = xmin, ymin = ymin, kwargs...)
end
startsquares = [makesquare(a; class="start") for a in track.start]
tracksquares = [makesquare(a) for a in track.body]
finishsquares = [makesquare(a; class = "finish") for a in track.finish]
squares = reduce(*, vcat(startsquares, tracksquares, finishsquares)) |> HTML
racemessage = isempty(episode) ? "" : "Race finished in $(length(first(episode))) steps"
@htl("""
$racemessage
$squares
Finish line
Starting line
""")
endmetadatashow_logsèdisabled®skip_as_script«code_folded$b040f245-b2d6-4ec6-aa7f-511c54aabd0dcell_id$b040f245-b2d6-4ec6-aa7f-511c54aabd0dcode^#recreation of figure 5.2 using ϵ-soft method
figure_5_2(πstar_blackjack2, Qstar_blackjack2)metadatashow_logsèdisabled®skip_as_script«code_folded$7cdf4142-82fe-4aa6-9665-84a1eef5d038cell_id$7cdf4142-82fe-4aa6-9665-84a1eef5d038code!@bind race_1_2 Button("Run race")metadatashow_logsèdisabled®skip_as_script«code_folded$3d10f89f-876e-4d25-b8d6-34ce5c99eb8ccell_id$3d10f89f-876e-4d25-b8d6-34ce5c99eb8ccode#Given there are 7300 states to the problem with track1, exploring starts would need to sample at least this many times to even explore all of them. Using 100_000 episodes, it produces a policy that finishes the race between 16 and 100 steps usually, but the technique works with higher variance even as low as 1000 episodes.
begin
run2_1
showrace(track1, create_policy_function(πstar2_racetrack1, track1_mdp))
endmetadatashow_logsèdisabled®skip_as_script«code_folded$772b4dd6-870c-4a16-937c-701d5bb5da44cell_id$772b4dd6-870c-4a16-937c-701d5bb5da44code@bind run3_1 Button("Run Race")metadatashow_logsèdisabled®skip_as_script«code_folded$1aaf3827-5851-4156-a7e6-14f5e4d00238cell_id$1aaf3827-5851-4156-a7e6-14f5e4d00238code*md"""
#### Random Policy Visualization
"""metadatashow_logsèdisabled®skip_as_script«code_folded$d6e7cc6d-f397-4bdf-974e-9a16922393ddcell_id$d6e7cc6d-f397-4bdf-974e-9a16922393ddcodeٍfunction create_policy_function(π, mdp)
function f(s)
i_s = mdp.statelookup[s]
i_a = sample_action(π, i_s)
mdp.actions[i_a]
end
endmetadatashow_logsèdisabled®skip_as_script«code_folded$1951fc4c-acc4-49a6-a907-7447ff0f430acell_id$1951fc4c-acc4-49a6-a907-7447ff0f430acodeAmd"""
Example trajectories after training for $opmc2 episodes
"""metadatashow_logsèdisabled®skip_as_script«code_folded$660ef59c-205c-44c2-9c46-5a74e09497abcell_id$660ef59c-205c-44c2-9c46-5a74e09497abcode'struct Weighted <: ImportanceMethod endmetadatashow_logsèdisabled®skip_as_script«code_folded$a47474b0-f262-4453-a116-addc3a09119ecell_id$a47474b0-f262-4453-a116-addc3a09119ecodeoq_offpol = monte_carlo_pred_Q(π_blackjack1, π_rand_blackjack, blackjack_mdp, 1.0f0; num_episodes = 1_000_000)metadatashow_logsèdisabled®skip_as_script«code_folded$acb270a1-e2b9-46bc-9a52-9f66f1cca17ccell_id$acb270a1-e2b9-46bc-9a52-9f66f1cca17ccode @bind mcϵs1 confirm(PlutoUI.combine() do Child
md"""
| Number of Episodes | ϵ | Decay ϵ |
| :-: | :-: | :-: |
|$(Child(:episodes, NumberField(1:10_000_000, default = 1_000))) | $(Child(:ϵ, NumberField(0.001:0.001:1.0; default = 0.01))) | $(Child(:decay, CheckBox())) |
"""
end)metadatashow_logsèdisabled®skip_as_script«code_folded$334b4d77-8784-46be-b9e8-80c0a2244694cell_id$334b4d77-8784-46be-b9e8-80c0a2244694codefunction monte_carlo_ϵsoft(mdp::MDP_Opaque, ϵ::T, π_init::Matrix{T}, Q_init::Matrix{T}, γ, num_episodes::Integer, quench_episode::Integer, decay_ϵ::Bool) where T <: Real
#initialize
π = copy(π_init)
Q = copy(Q_init)
counts = zeros(Int64, length(mdp.actions), length(mdp.states))
vhold = zeros(T, length(mdp.actions))
decayrate = decay_ϵ ? ϵ / num_episodes : zero(T)
for i in 1:num_episodes
s0 = mdp.state_init()
i_a0 = sample_action(π, mdp.statelookup[s0])
a0 = mdp.actions[i_a0]
(states, actions, rewards) = mdp.simulator(s0, a0, π)
g = zero(T)
for t in length(states):-1:1
#accumulate future discounted returns
g = γ*g + rewards[t]
i_s = mdp.statelookup[states[t]]
i_a = mdp.actionlookup[actions[t]]
#increment count by 1
counts[i_a, i_s] += 1
Q[i_a, i_s] += (g - Q[i_a, i_s])/counts[i_a, i_s] #update running average of Q
vhold .= Q[:, i_s]
#if desired at some point prior to the final episode the training can revert to using the greedy policy
if i > quench_episode
make_greedy_policy!(vhold)
else
make_ϵsoft_policy!(vhold, ϵ)
end
π[:, i_s] .= vhold
ϵ -= decayrate
end
end
return π, Q
endmetadatashow_logsèdisabled®skip_as_script«code_folded$e5384dd0-fad1-4a24-b011-73b062fcfb1bcell_id$e5384dd0-fad1-4a24-b011-73b062fcfb1bcode md"""
> ### *Exercise 5.1*
> Consider the diagroms on the right in Figure 5.1. Why does the estimated value function jump for the last two rows in the rear? Why does it drop off for the whole last row on the left? Why are the frontmost values higher in the upper diagrams than in the lower?
The last two rows in the rear are for a player sum equal to 20 or 21. For a sum of 19 and lower, this policy will hit which is suboptimal for these high sums. For the sums of 20 or 21 though, sticking is optimal so the value jumps compared to the suboptimal hit at 19.
The far left row represents cases where the dealer is showing an Ace. Since an Ace is a flexible card, the dealer policy will have more options that result in a win including the possibility of having another face card already (dealer natural). It is always worse for the player if the dealer is known to have an Ace.
The frontmost values represent cases where the player sum is 12. If there is a usable Ace this means that means that the player has two Aces which results in a sum of 12 when the first Ace is counted as 1 and the second is *usable* and counted as 11. If there is no usable Ace than a sum of 12 would have to result from some other combination of cards such as 10/2, 9/3, etc... Since the first case has two Aces, it means that potentially both could count as 1 if needed to avoid a bust. In the case without a usable Ace, the sum is the same, but there are more opportunities to bust if we draw a card worth 10, so having a sum of 12 with a usable Ace is strictly better.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$35914757-6af1-4056-bba4-a9996f65f7f7cell_id$35914757-6af1-4056-bba4-a9996f65f7f7code#normal importance sampling for one state MDP produces state-action value estimates that fail to converge to [1, 0] even after 1M episodes
monte_carlo_pred_Q(onestate_π_target, onestate_π_b, onestate_mdp, 1.0f0; num_episodes = 1_000_000)metadatashow_logsèdisabled®skip_as_script«code_folded$cde7be85-9344-4526-bcb2-c2c8b3322435cell_id$cde7be85-9344-4526-bcb2-c2c8b3322435codeٍ(πstar3_racetrack2, Qstar3_racetrack2) = monte_carlo_ϵsoft(track2_mdp, Float32(mcϵs2.ϵ), 1.0f0, mcϵs2.episodes; decay_ϵ = mcϵs2.decay)metadatashow_logsèdisabled®skip_as_script«code_folded$881ba6c3-0e6a-4bb8-bc14-2e0face560f2cell_id$881ba6c3-0e6a-4bb8-bc14-2e0face560f2codenmd"""
> ### *Exercise 5.6*
> What is the equation analogous to (5.6) for *action* values $Q(s,a)$ instead of state values $V(s)$, again given returns generated using $b$?
Equation (5.6):
$V(s) = \frac{\sum_{t \in \mathscr{T}(s)}\rho_{t:T(t)-1}G_t}{\sum_{t \in \mathscr{T}(s)} \rho_{t:T(t)-1}}$
For $Q(s,a)$, there is no need to calculate the sampling ratio for the first action selected. Here $\mathscr{T}(s, a)$ is the set of all time steps in which the state action pair $(s, a)$ is visited.
$Q(s,a) = \frac{\sum_{t \in \mathscr{T}(s, a)}\rho_{t+1:T(t)-1}G_t}{\sum_{t \in \mathscr{T}(s, a)} \rho_{t+1:T(t)-1}}$
"""metadatashow_logsèdisabled®skip_as_script«code_folded$5c57e4b7-51d6-492d-9fc9-bcdab1dd46f4cell_id$5c57e4b7-51d6-492d-9fc9-bcdab1dd46f4codefunction plot_blackjack_policy(π)
πstargridua = zeros(Float64, 10, 10)
πstargridnua = zeros(Float64, 10, 10)
for state in blackjackstates
i_s = blackjack_mdp.statelookup[state]
v = π[1, i_s] - π[2, i_s]
if state.ua
πstargridua[state.sum-11, state.upcard] = v
else
πstargridnua[state.sum-11, state.upcard] = v
end
end
function plot_policy_grid(grid)
plot(heatmap(x = 1:10, y = 12:21, z = grid, showscale=false, colorscale = "Greys", zmin = -1, zmax = 1), Layout(xaxis_title = "Dealer showing", yaxis_title = "Player sum", margin = attr(t = 30, b = 0, l = 0, r = 10), width = 300, height = 300, xaxis_tickvals = 1:10, yaxis_tickvals = 12:21, yaxis_ticktext = 12:21, xaxis_ticktext = ["A"; 2:10]))
end
p1 = plot_policy_grid(πstargridua)
p2 = plot_policy_grid(πstargridnua)
# vstar = eval_blackjack_policy(Dict(s => π[s] == :hit ? [1.0, 0.0] : [0.0, 1.0] for s in blackjackstates), 500_000)
# p1 = heatmap(πstargridua, xticks = (1:10, ["A", 2, 3, 4, 5, 6, 7, 8, 9, 10]), yticks = (1:10, 12:21), legend = false, title = "Usable Ace Policy, Black=Stick, White = Hit")
# p2 = heatmap(πstargridnua, xticks = (1:10, ["A", 2, 3, 4, 5, 6, 7, 8, 9, 10]), yticks = (1:10, 12:21), legend = false, title = "No usable Ace Policy", xlabel = "Dealer Showing", ylabel = "Player sum")
# p3 = heatmap(vstar[1], legend = false, yticks = (1:10, 12:21), title = "V*")
# p4 = heatmap(vstar[2], yticks = (1:10, 12:21))
# plot(p1, p3, p2, p4, layout = (2,2))
(p1, p2)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$e0d3d7d1-203f-42fa-8570-8d1d88bf17c2cell_id$e0d3d7d1-203f-42fa-8570-8d1d88bf17c2codemd"""
##### Track 2
"""metadatashow_logsèdisabled®skip_as_script«code_folded$760c5361-02d4-46b7-a05c-fc2d10d93de6cell_id$760c5361-02d4-46b7-a05c-fc2d10d93de6code}function monte_carlo_pred_V(π::Matrix{T}, mdp::MDP_Opaque{S, A, F, G}, γ::T; num_episodes::Integer = 1000, vinit::T = zero(T), V::Vector{T} = ones(T, length(mdp.states)) .* vinit) where {T <: AbstractFloat, S, A, F, G}
check_policy(π, mdp)
#initialize
counts = zeros(Integer, length(mdp.states))
#there's no check here so this is equivalent to every-visit estimation
function updateV!(states, actions, rewards; t = length(states), g = zero(T))
#terminate at the end of a trajectory
t == 0 && return nothing
#accumulate future discounted returns
g = γ*g + rewards[t]
i_s = mdp.statelookup[states[t]]
i_a = mdp.actionlookup[actions[t]]
#increment count by 1
counts[i_s] += 1
V[i_s] += (g - V[i_s])/counts[i_s] #update running average of V
updateV!(states, actions, rewards; t = t-1, g = g)
end
for i in 1:num_episodes
s0 = mdp.state_init()
i_a0 = sample_action(π, mdp.statelookup[s0])
a0 = mdp.actions[i_a0]
# (s0, a0) = initialize_episode()
(states, actions, rewards) = mdp.simulator(s0, a0, π)
#update value function for each trajectory
updateV!(states, actions, rewards)
end
return V
endmetadatashow_logsèdisabled®skip_as_script«code_folded$d55860d1-e4c1-4a79-adbe-b40a6d6283a7cell_id$d55860d1-e4c1-4a79-adbe-b40a6d6283a7codeٓinitialize_state_action_value(mdp::MDP_Opaque; qinit::T = 0.0f0) where T<:AbstractFloat = ones(T, length(mdp.actions), length(mdp.states)) .* qinitmetadatashow_logsèdisabled®skip_as_script«code_folded$06297d75-121a-4178-b45b-83e167efd90dcell_id$06297d75-121a-4178-b45b-83e167efd90dcodejoinlines(x, y) = """
$x
$y
"""metadatashow_logsèdisabled®skip_as_script«code_folded$abe70666-39f8-4f1d-a285-a3a99f696d10cell_id$abe70666-39f8-4f1d-a285-a3a99f696d10codemd"""
> ### *Exercise 5.13*
> Show the steps to derive (5.14) from (5.12)
Starting at (5.12)
$\rho_{t:T-1}R_{t+1}=\frac{\pi(A_t|S_t)}{b(A_t|S_t)}\frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}\frac{\pi(A_{t+2}|S_{t+2})}{b(A_{t+2}|S_{t+2})}\cdots\frac{\pi(A_{T-1}|S_{T-1})}{b(A_{T-1}|S_{T-1})}R_{t+1}$
For (5.14) we need to turn this into an expected value
$\mathbb{E}[\rho_{t:T-1}R_{t+1}]$
Now we know that the reward at time step t+1 is only dependent on the action and state at time t. Moreover, the later parts of the trajectory are also independent of each other. So we can separate some of these terms into a product of expected values rather than an expected value of products:
$\mathbb{E}[\rho_{t:T-1}R_{t+1}]=\mathbb{E} \left [ \frac{\pi(A_t|S_t)}{b(A_t|S_t)}\frac{\pi(A_{t+1}|S_{t+1})}{b(A_{t+1}|S_{t+1})}\frac{\pi(A_{t+2}|S_{t+2})}{b(A_{t+2}|S_{t+2})}\cdots\frac{\pi(A_{T-1}|S_{T-1})}{b(A_{T-1}|S_{T-1})}R_{t+1} \right ]$
$=\mathbb{E} \left [ \frac{\pi(A_t|S_t)}{b(A_t|S_t)}R_{t+1} \right ] \prod_{k=t+1}^{T-1}\mathbb{E} \left [ \frac{\pi(A_k|S_k)}{b(A_k|S_k)} \right ]$
We know from (5.13) that $\mathbb{E} \left [ \frac{\pi(A_k|S_k)}{b(A_k|S_k)} \right ] = 1$ so the above expression simplifies to: $\mathbb{E} \left [ \frac{\pi(A_t|S_t)}{b(A_t|S_t)}R_{t+1} \right ]$. Using the original shorthand with ρ:
$\mathbb{E}[\rho_{t:T-1}R_{t+1}]=\mathbb{E} \left [ \frac{\pi(A_t|S_t)}{b(A_t|S_t)}R_{t+1} \right ]=\mathbb{E}[\rho_{t:t}R_{t+1}]$
"""metadatashow_logsèdisabled®skip_as_script«code_folded$7ce6e28e-acd7-46d1-87d6-a25f4656d79dcell_id$7ce6e28e-acd7-46d1-87d6-a25f4656d79dcode@bind run2_1 Button("Run race")metadatashow_logsèdisabled®skip_as_script«code_folded$a85e7dd3-ea5e-4c77-a18e-f1e190658ae3cell_id$a85e7dd3-ea5e-4c77-a18e-f1e190658ae3codeكfunction sample_action(π::Matrix{T}, i_s::Integer) where T<:AbstractFloat
(n, m) = size(π)
sample(1:n, weights(π[:, i_s]))
endmetadatashow_logsèdisabled®skip_as_script«code_folded$68f9e0d9-5c9d-4e89-b5ae-f24fd7544a09cell_id$68f9e0d9-5c9d-4e89-b5ae-f24fd7544a09coden(πstar2_racetrack1, Qstar2_racetrack1) = monte_carlo_ES(track1_mdp, 1.0f0, mces1; override_state_init = true)metadatashow_logsèdisabled®skip_as_script«code_folded$ec29865f-3ba3-4bb3-84df-c2b472e03ff2cell_id$ec29865f-3ba3-4bb3-84df-c2b472e03ff2coden(πstar_blackjack, Qstar_blackjack) = monte_carlo_ES(blackjack_mdp, 1.0f0, 5_000_000; π_init = π_blackjack1)metadatashow_logsèdisabled®skip_as_script«code_folded$1d6eccf0-2731-47fc-9a41-ea8649e290efcell_id$1d6eccf0-2731-47fc-9a41-ea8649e290efcodeٍ(πstar3_racetrack1, Qstar3_racetrack1) = monte_carlo_ϵsoft(track1_mdp, Float32(mcϵs1.ϵ), 1.0f0, mcϵs1.episodes; decay_ϵ = mcϵs1.decay)metadatashow_logsèdisabled®skip_as_script«code_folded$9ca72278-fff6-4b0f-b72c-e0d3768aff73cell_id$9ca72278-fff6-4b0f-b72c-e0d3768aff73code"figure5_3(;n = 100, vinit = 0.0f0)metadatashow_logsèdisabled®skip_as_script«code_folded$020131a1-c68b-403a-9c5e-944edb6220e9cell_id$020131a1-c68b-403a-9c5e-944edb6220e9codeKupdatevalue(::Weighted, q::T, g::T, w::T, c::T) where T<:Real = (g - q)*w/cmetadatashow_logsèdisabled®skip_as_script«code_folded$c23475f0-c5f0-49ce-a665-f93c8bda0474cell_id$c23475f0-c5f0-49ce-a665-f93c8bda0474code function make_blackjack_mdp()
state_init() = BlackjackState(rand(12:21), rand(unique_cards), rand() > 0.5)
#starting with an initial state, action, and policy, generate a trajectory for blackjack returning that and the reward
function blackjackepisode(s0::BlackjackState, a0::BlackjackAction, π::Matrix{Float32})
#given any valid state, the simulation results will be affected by whether or not the player has a natural. This can only be the case when the player sum is 21 and the player has a usable ace. However, even if this is the case, it is not necessarily a natural. A natural would occur with (A, 10), (A, J), (A, Q), (A, K). But the player could also have (A, A, 9), (A, A, 7, 2), (A, A, A, 8), (A, A, A, A, 7) and so forth. Also, if the starting state has a sum less than 21 and a usable ace, then after further dealing the player could arrive at the state with a sum of 21 and a usable ace. In that situation, the player would never have a natural, but state value will be updated nonetheless. So the probabilities must match for sampling purposes meaning the reward sampled from the (sum=21, ua=true) player state must reflect the true probabilities. This would be the case if the simulation is always started with zero cards and dealt, but how to do that when we pass the starting state into it? Since the game can go on past this point, this starting state should be handled for initial card draws where the sum is less than 12. All of the situations with a usuable ace, a sum of 21, and not having a player natural require the player having two or more aces without a face/10 card. If the first two cards dealt are the aces, then this would be a sum of 12 and the player would need to hit for a subsequent state. If the first two cards result in a sum of less than 12 such as 7,2 then the player would automatically receive an additional card with zero probability of a bust, so no policy is needed. Once the first ace is dealt, the policy would be required to hit to draw a second ace. So if we treat s0 as the initial deal, then the remainder of the simulation will cover all of the other cases where we arrive at a sum of 21 with a usable ace
playernatural = (s0.sum == 21) && s0.ua
splayer, statehistory, actionhistory = playersim(s0, a0, π)
rewardbase = zeros(Float32, length(statehistory) - 1)
finalr = if splayer > 21
#if the player goes bust, the game is lost regardless of the dealers actions
-1.0f0
else
#generate hidden dealer card and final state
(ds, dua) = addsum(0, false, deal())
(ds, dua) = addsum(ds, dua, s0.upcard)
dealernatural = ds == 21
if playernatural
Float32(!dealernatural)
elseif dealernatural #not stated in book but used by authors in their code and matches actual blackjack rules
-1.0f0
else
sdealer = dealer_sim(ds, dua)
scoregame(splayer, sdealer)
end
end
return (statehistory, actionhistory, push!(rewardbase, finalr))
end
MDP_Opaque(blackjackstates, blackjack_actions, state_init, blackjackepisode)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$15925cc6-9605-4357-9c2a-cdfe54070989cell_id$15925cc6-9605-4357-9c2a-cdfe54070989codemd"""
Consider an implementation or ordinary importance sampling that updates $V(s)$ incrementally every time a $G$ value is observed for that state. The equations should be similar to the incremental update rule previously derived for $V(s)$ without importance sampling.
Consider a sequence of returns $G_1, G_2, \dots , G_{n-1}$, all starting in the same state and each with a corresponding weight $W_i = \rho_{t_i:T(t_i)-1}$. We wish to form the estimate
$V_n \dot= \frac{\sum_{k=1}^{n-1}W_k G_k}{n-1}, n \geq 2$
and keep it up-to-date as we obtain a single additional return $G_n$. Observe that we can increment n by 1 to get an espression for V in terms of itself.
$V_{n+1} = \frac{\sum_{k=1}^n W_k G_k}{n} = \frac{W_n G_n + \sum_{k=1}^{n-1} W_k G_k}{n}$
Using the original formula for $V_n$, we can make the following substitution:
$\sum_{k=1}^{n-1} W_k G_k = (n-1)V_n$
which results in
$V_{n+1} = \frac{W_n G_n + V_n (n-1)}{n} = V_n + \frac{W_n G_n - V_n}{n}$
So, to calculate the value function, we can simply apply the following update rule after obtaining new values for W and G:
$C \leftarrow C + 1$
$V \leftarrow V + \frac{WG-V}{C}$
which looks very similar to the ordinary average update rule but with the weight multiplied by G. C just keeps a running total of the times the state was observed. Note that C needs to be updated even in the case where W is 0 which is not the case for weighted importance sampling. A similar inremental update rule is derived later for the weighted case as well as an algorithm for updating the action-value estimate using this method. Below are code examples for calculating the value estimates for both weighted and normal importance sampling using the incremental implementation.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$be7c096c-cc8c-407b-8287-8fb2ee7150a7cell_id$be7c096c-cc8c-407b-8287-8fb2ee7150a7codemd"""
> ### *Exercise 5.3*
> What is the backup diagram for Monte Carlo estimation of $q_\pi$
Similar to the $v_\pi$ diagram except the root is the s,a pair under consideration followed by the new state and the action taken along the trajectory. The rewards are still accumulated to the end, just the start of the trajectory is a solid filled in circle that would contain the value for that s,a pair.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$9618a093-cdb7-4589-a783-de8e9021b705cell_id$9618a093-cdb7-4589-a783-de8e9021b705code,md"""
### Example 5.3: Solving Blackjack
"""metadatashow_logsèdisabled®skip_as_script«code_folded$fa49c253-e016-46a7-ba94-0e7448a7e0aecell_id$fa49c253-e016-46a7-ba94-0e7448a7e0aecodeOmd"""
> ### *Exercise 5.10*
> Derive the weighted-average update rule (5.8) from (5.7). Follow the pattern of the derivation of the unweighted rule (2.3).
Equation (5.7)
$V_{n} = \frac{\sum_{k=1}^{n-1} W_k G_k}{\sum_{k=1}^{n-1}W_k} \implies \sum_{k=1}^{n-1} W_k G_k = V_n \sum_{k=1}^{n-1} W_k \tag{a}$
or
$V_{n+1} = \frac{\sum_{k=1}^{n} W_k G_k}{\sum_{k=1}^{n}W_k}$
now we can expand the expresion for $V_{n+1}$ to get an incremental rule
$\begin{flalign}
V_{n+1} &= \frac{W_n G_n + \sum_{k=1}^{n-1} W_k G_k}{\sum_{k=1}^{n}W_k} \\
&= \frac{W_n G_n + V_n \sum_{k=1}^{n-1}W_k}{\sum_{k=1}^{n}W_k} \tag{by (a)} \\
&= \frac{W_n G_n + V_n \sum_{k=1}^{n}W_k - V_n W_n}{\sum_{k=1}^{n}W_k} \\
&= V_n + W_n\frac{G_n - V_n}{\sum_{k=1}^{n}W_k}
\end{flalign}$
For a fully incremental rule we also have to replace the sum over $W_k$ which can simply be a running total.
$C_n = \sum_{k=1}^n W_k$
the following update rule will produce an equivalent $C_n$ assuming we take $C_0=0$
$C_n = C_{n-1} + W_n$
Now we can rewrite our last expression for $V_{n+1}$
$V_{n+1} = V_n + \frac{W_n}{C_n}(G_n - V_n)$
"""metadatashow_logsèdisabled®skip_as_script«code_folded$f41dd3e6-81bf-43e4-afc2-fc549b77f610cell_id$f41dd3e6-81bf-43e4-afc2-fc549b77f610coden(πstar2_racetrack2, Qstar2_racetrack2) = monte_carlo_ES(track2_mdp, 1.0f0, mces2; override_state_init = true)metadatashow_logsèdisabled®skip_as_script«code_folded$6d765229-2816-4abb-a868-6be919a96530cell_id$6d765229-2816-4abb-a868-6be919a96530code*const blackjack_mdp = make_blackjack_mdp()metadatashow_logsèdisabled®skip_as_script«code_folded$e7de31e8-ae95-4616-86a9-a115a5e24330cell_id$e7de31e8-ae95-4616-86a9-a115a5e24330code)const track2_mdp = make_track_mdp(track2)metadatashow_logsèdisabled®skip_as_script«code_folded$fff54c56-5afe-4d89-9dc5-502d08c89de9cell_id$fff54c56-5afe-4d89-9dc5-502d08c89de9code i:min(i, 1000):i*9, vcat, 10 .^(0:expmax-1))
vcat(plotinds, 10^(expmax))
end
plotinds = makeplotinds(expmax)
vhistnormal = Vector{Vector{Float32}}(undef, nsims)
@threads for i in 1:nsims
vhistnormal[i] = monte_carlo_pred_V(onestate_π_target, onestate_π_b, onestate_mdp, 1.0f0; num_episodes = nmax, sampleinds = plotinds)[1]
end
# vhistnormal = [monte_carlo_pred(onestate_π_target, onestate_π_b, onestate_mdp, 1.0f0; num_episodes = nmax)[1][plotinds] for _ in 1:nsims]
vhistweighted = monte_carlo_pred_V(onestate_π_target, onestate_π_b, onestate_mdp, 1.0f0; num_episodes = nmax, samplemethod = Weighted(), sampleinds = plotinds)[1]
traces1 = [scatter(x = plotinds, y = vhist, showlegend = false) for vhist in vhistnormal]
trace2 = scatter(x = plotinds, y = vhistweighted, name = "Weighted Importance Sampling", line_dash = "dash", line_width = 4)
p = plot([traces1; trace2], Layout(yaxis_range = [0, 3], xaxis_type = "log", legend_orientation = "h", xaxis_title = "Episodes (log scale)", yaxis_title = attr(text = "Monte-Carlo estimate of state value with ordinary importance sampling ($nsims runs)", rotation = 90)))
md"""
### Figure 5.4
Ordinary importance sampling produces surprisingly unstable estimates on the one-state MDP shown in Example 5.5. The correct estimate here is 1 ($\gamma = 1$), and, even through this is the expected value of a sample return (after importance sampling), the variance of the samples is infinite, and the estimates do not converge to this value. In contrast weighted importance samping produces the correct value of 1 after the first episode that ends with the left action.
$p
"""
# p2 = plot(histogram(x = [v[end] for v in vhistnormal], showlegend = false))
# [p p2]
# traces2 = [scatter(x = plotinds, y = vhist) for vhist in vhistweighted]
# p2 = plot(traces2, Layout(showlegend = false))
# md"""
# $p1
# $p2
# """
endmetadatashow_logsèdisabled®skip_as_script«code_folded$2ed88aa5-fc42-4a57-924d-e918805e2208cell_id$2ed88aa5-fc42-4a57-924d-e918805e2208codemd"""
##### Track 2
"""metadatashow_logsèdisabled®skip_as_script«code_folded$c9bd778c-217a-4664-8cde-841beca10307cell_id$c9bd778c-217a-4664-8cde-841beca10307code&@htl("""
Reward = +1 on All Transitions
1-p
""")metadatashow_logsèdisabled®skip_as_script«code_folded$605b045d-fe5c-426b-9f55-b7dd1d037c50cell_id$605b045d-fe5c-426b-9f55-b7dd1d037c50codeAmd"""
Example trajectories after training for $mces1 episodes
"""metadatashow_logsèdisabled®skip_as_script«code_folded$88335fca-fd87-487b-9de2-ea7c779b54cfcell_id$88335fca-fd87-487b-9de2-ea7c779b54cfcode1md"""
## 5.9 Per-decision Importance Sampling
"""metadatashow_logsèdisabled®skip_as_script«code_folded$fd91d00a-f94f-40ff-88a7-9d85f05acc96cell_id$fd91d00a-f94f-40ff-88a7-9d85f05acc96code mean #mean weight is 2 and it stays this way as the number of episodes increases so the returns that are seen by the behavior are roughtly doubled and counted with the 0 returnsmetadatashow_logsèdisabled®skip_as_script«code_folded$df3c4a33-45f1-4cc2-8c06-d500a0eecc8fcell_id$df3c4a33-45f1-4cc2-8c06-d500a0eecc8fcode #track is defined as a set of points for each of the start, body, and finish
const track1 = ( start = Set((x, 0) for x in 0:5),
finish = Set((13, y) for y in 26:31),
body = union( Set((x, y) for x in 0:5 for y in 1:2),
Set((x, y) for x in -1:5 for y in 3:9),
Set((x, y) for x in -2:5 for y in 10:17),
Set((x, y) for x in -3:5 for y in 18:24),
Set((x, 25) for x in -3:6),
Set((x, y) for x in -3:12 for y in 26:27),
Set((x, 28) for x in -2:12),
Set((x, y) for x in -1:12 for y in 29:30),
Set((x, 31) for x in 0:12)),
)metadatashow_logsèdisabled®skip_as_script«code_folded$e2fc1d47-2ee9-4844-a6b1-16f76531da86cell_id$e2fc1d47-2ee9-4844-a6b1-16f76531da86code@bind run3_2 Button("Run Race")metadatashow_logsèdisabled®skip_as_script«code_folded$2d36ebe3-1a86-4cad-a235-baec726da926cell_id$2d36ebe3-1a86-4cad-a235-baec726da926codemd"""
#### Example Random Trajectories on Each Track
The black arrows represent the velocity of the car at that position, and the red arrows show the policy action to change the velocity. Note that only non-negative values are allowed for velocity to some of the actions have no impact. Also, the car is not allowed by be stopped so if an action were to reduce the velocity to 0, then a random velocity of +1 will be assigned to either the x or y direction.
"""metadatashow_logsèdisabled®skip_as_script«code_folded$dfc2d648-ec08-49cd-a55f-72a766cad728cell_id$dfc2d648-ec08-49cd-a55f-72a766cad728codeh(πstar1_racetrack1, Qstar1_racetrack1) = off_policy_MC_control(track1_mdp, 1.0f0; num_episodes = opmc1)metadatashow_logsèdisabled®skip_as_script«code_folded$7ee4e17e-c1a9-4df0-a014-114bebcb4f52cell_id$7ee4e17e-c1a9-4df0-a014-114bebcb4f52codemakegridsquare(x, y, vx, vy, dvx, dvy; class = "", xmin=0, ymin=0) = """"""metadatashow_logsèdisabled®skip_as_script«code_folded$2d10281a-a4af-4ea8-b63b-e11f2d0893edcell_id$2d10281a-a4af-4ea8-b63b-e11f2d0893edcodefunction make_greedy_policy!(v::AbstractVector{T}; c = 1000) where T<:Real
(vmin, vmax) = extrema(v)
if vmin == vmax
v .= one(T) / length(v)
else
v .= (v .- vmax) ./ abs(vmin - vmax)
v .= exp.(c .* v)
v .= v ./ sum(v)
end
return v
endmetadatashow_logsèdisabled®skip_as_script«code_folded$e87932d9-fbc0-4ea5-a8ee-28eac5eed84fcell_id$e87932d9-fbc0-4ea5-a8ee-28eac5eed84fcode {begin
abstract type BlackjackAction end
struct Hit <: BlackjackAction end
struct Stick <: BlackjackAction end
struct BlackjackState
sum::Int64
upcard::Int64
ua::Bool
end
const cards = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 10, 10]
const unique_cards = collect(1:10)
const blackjack_actions = [Hit(), Stick()]
const blackjackstates = [BlackjackState(s, c, ua) for s in 12:21 for c in unique_cards for ua in (true, false)]
const blackjack_statelookup = makelookup(blackjackstates)
const π_blackjack_random = ones(Float32, 2, length(blackjackstates)) /2
#deal a card from an infinite deck and return either the value of that card or an ace
deal() = rand(cards)
#takes a previous sum, usable ace indicator, and a card to be added to the sum. Returns the updated sum and whether an ace is still usable
function addsumace(s::Int64, ua::Bool)
if !ua
s >= 11 ? (s+1, false) : (s+11, true)
else
(s+1, true)
end
end
function addsum(s::Int64, ua::Bool, c::Int64)
c == 1 && return addsumace(s, ua)
if !ua
(s + c, false)
else
if (s + c) > 21
(s + c - 10, false)
else
(s + c, true)
end
end
end
function dealer_sim(dealer_sum::Int64, dua::Bool)
(dealer_sum >= 17) && return dealer_sum
(new_sum, ua) = addsum(dealer_sum, dua, deal())
dealer_sim(new_sum, ua)
end
playersim(state, ::Stick, π, statehistory, actionhistory) = (state.sum, statehistory, actionhistory)
function playersim(state, ::Hit, π, statehistory, actionhistory)
(s, ua) = addsum(state.sum, state.ua, deal())
(s > 21) && return (s, statehistory, actionhistory)
newstate = BlackjackState(s, state.upcard, ua)
i_s = blackjack_statelookup[newstate]
i_a = sample_action(π, i_s)
newaction = blackjack_actions[i_a]
playersim(newstate, newaction, π, push!(statehistory, newstate), push!(actionhistory, newaction))
end
playersim(state::BlackjackState, action::BlackjackAction, π::Matrix{Float32}) = playersim(state, action, π, [state], Vector{BlackjackAction}([action]))
#score a game in which the player didn't go bust
function scoregame(playersum, dealersum)
#if the dealer goes bust, the player wins
dealersum > 21 && return 1.0f0
#if the player is closer to 21 the player wins
playersum > dealersum && return 1.0f0
#if the dealer sum is closer to 21 the player loses
playersum < dealersum && return -1.0f0
#otherwise the outcome is a draw
return 0.0f0
end
endmetadatashow_logsèdisabled®skip_as_script«code_folded$1cc46e33-6885-4d6f-805e-9ff928f1cf23cell_id$1cc46e33-6885-4d6f-805e-9ff928f1cf23code;const racetrackspeeds = unique(norm.(racetrack_velocities))metadatashow_logsèdisabled®skip_as_script«code_folded$f79d97bb-341a-46ad-bdfc-d080af13e2dfcell_id$f79d97bb-341a-46ad-bdfc-d080af13e2dfcode2md"""
#### Monte Carlo ϵ-Soft Solution Method
"""metadatashow_logsèdisabled®skip_as_script«code_folded$6a11daf7-2859-41fa-9c3d-d1f3580dbb5fcell_id$6a11daf7-2859-41fa-9c3d-d1f3580dbb5fcode$md"""
### Example 5.1: Blackjack
"""metadatashow_logsèdisabled®skip_as_script«code_folded$985f0537-2bbe-4dbb-a113-8ac98d2e0a5fcell_id$985f0537-2bbe-4dbb-a113-8ac98d2e0a5fcodelsampleracepolicy(create_policy_function(πstar3_racetrack1, track1_mdp); policyname = "Monte Carlo ϵ-Soft")metadatashow_logsèdisabled®skip_as_script«code_folded$217ecc59-d6e3-48fa-9d6d-700a3947b805cell_id$217ecc59-d6e3-48fa-9d6d-700a3947b805code [monte_carlo_pred_Q(π_blackjack1, π_rand_blackjack, blackjack_mdp, 1.0f0; num_episodes = 1, historystateindex = blackjack_stateindex1, qinit = 0.0f0, override_state_init = true, samplemethod=Ordinary(), use_target_initial_action = true)[3][1:1] |> sum for i in 1:1000] |> v -> mean(v)metadatashow_logsèdisabled®skip_as_script«code_folded$a35de859-4046-4f6d-9ea9-b523d21cee5dcell_id$a35de859-4046-4f6d-9ea9-b523d21cee5dcode function make_value_grid(v_π)
vgridua = zeros(Float32, 10, 10)
vgridnua = zeros(Float32, 10, 10)
for (i_s, s) in enumerate(blackjackstates)
if s.ua
vgridua[s.sum-11, s.upcard] = v_π[i_s]
else
vgridnua[s.sum-11, s.upcard] = v_π[i_s]
end
end
return vgridua, vgridnua
endmetadatashow_logsèdisabled®skip_as_script«code_folded$12c0cd0b-eb4f-45a0-836b-53b3c5cdafd9cell_id$12c0cd0b-eb4f-45a0-836b-53b3c5cdafd9code>md"""
## 5.5 Off-policy Prediction via Importance Sampling
"""metadatashow_logsèdisabled®skip_as_script«code_folded$aaa9647c-afb6-44d1-ae1e-a2e957064080cell_id$aaa9647c-afb6-44d1-ae1e-a2e957064080code#updates the denominator used in the value update. For ordinary sampling, this is just the count of visits to that state. For weighted sampling, this is the sum of all importance-sampling ratios at that state
updatecount(::Ordinary, w::T) where T<:Real = one(T)metadatashow_logsèdisabled®skip_as_script«code_folded$b57462b6-8f9c-4553-9c05-134ff043b00dcell_id$b57462b6-8f9c-4553-9c05-134ff043b00dcodemd"""
> ### *Exercise 5.9*
> Modify the algorithm for first-visit MC policy evaluation (section 5.1) to use the incremental implementation for sample averages described in Section 2.4
Returns(s) will not maintain a list but instead be a list of single values for each state. Additionally, another list Counts(s) should be initialized at 0 for each state. When new G values are obtained for state, the Count(s) value should be incremented by 1. Then Returns(s) can be updated with the following formula:
$\begin{flalign}
\text{Returns}(s) &= \left [ \text{Returns}(s) \times (\text{Counts}(s) - 1) + G \right ] / \text{Counts}(s) \\
&= \text{Returns}(s) + \frac{G - \text{Returns}(s)}{\text{Counts}(s)}
\end{flalign}$
"""metadatashow_logsèdisabled®skip_as_script«code_folded$f506e8ba-b073-4f59-91b4-3fe99822d2a4cell_id$f506e8ba-b073-4f59-91b4-3fe99822d2a4codeXconst scalelookup = Dict(s => round(Int64, 150*(s / maxspeed)) for s in racetrackspeeds)metadatashow_logsèdisabled®skip_as_script«code_folded$bf19e6cf-1fb5-49c9-974e-1613d90ef4cfcell_id$bf19e6cf-1fb5-49c9-974e-1613d90ef4cfcodeb(πstar_blackjack2, Qstar_blackjack2) = monte_carlo_ϵsoft(blackjack_mdp, 0.1f0, 1.0f0, 1_000_000)metadatashow_logsèdisabled®skip_as_script«code_folded$77cf7fee-0ad8-4d22-b376-75833307db93cell_id$77cf7fee-0ad8-4d22-b376-75833307db93codeٌbegin
using StatsBase, Statistics, PlutoUI, HypertextLiteral, LaTeXStrings, PlutoPlotly, Base.Threads, LinearAlgebra
TableOfContents()
endmetadatashow_logsèdisabled®skip_as_script«code_folded$d11bfcf9-b964-4c67-afdc-53d81f051fd5cell_id$d11bfcf9-b964-4c67-afdc-53d81f051fd5code_function monte_carlo_pred_V(π_target::Matrix{T}, π_behavior::Matrix{T}, mdp::MDP_Opaque{S, A, F, G}, γ::T; num_episodes::Integer = 1000, vinit::T = zero(T), V::Vector{T} = ones(T, length(mdp.states)) .* vinit, historystateindex::Integer = 1, samplemethod::ImportanceMethod = Ordinary(), override_state_init::Bool = false, sampleinds = 1:num_episodes) where {T <: AbstractFloat, S, A, F, G}
check_policy(π_target, mdp)
check_policy(π_behavior, mdp)
@assert all(x -> x != 0, π_behavior) #behavior policy must have full coverage
#initialize
counts = zeros(T, length(mdp.states))
valuehistory = zeros(T, length(sampleinds))
weighthistory = ones(T, length(sampleinds))
sampleind = 1
for i in 1:num_episodes
#if only interested in one state then always initialize there
s0 = override_state_init ? mdp.states[historystateindex] : mdp.state_init()
i_a0 = sample_action(π_behavior, mdp.statelookup[s0])
a0 = mdp.actions[i_a0]
(states, actions, rewards) = mdp.simulator(s0, a0, π_behavior)
#update value function for each trajectory
w = updateV!(mdp, V, counts, π_target, π_behavior, states, actions, rewards, γ, samplemethod)
#for selected state check value
if i == sampleinds[sampleind]
valuehistory[sampleind] = V[historystateindex]
weighthistory[sampleind] = w
sampleind += 1
end
end
return valuehistory, V, weighthistory
endmetadatashow_logsèdisabled®skip_as_script«code_folded$19e42f50-5301-41b9-becb-2368c26b6236cell_id$19e42f50-5301-41b9-becb-2368c26b6236code [monte_carlo_pred_Q(π_blackjack1, π_rand_blackjack, blackjack_mdp, 1.0f0; num_episodes = 10, historystateindex = blackjack_stateindex1, qinit = 0.0f0, override_state_init = true, samplemethod=Ordinary(), use_target_initial_action = true)[3] |> mean for i in 1:1000] |> v -> mean(v)metadatashow_logsèdisabled®skip_as_script«code_folded$924f4e74-e3a0-42eb-89da-1f9836275588cell_id$924f4e74-e3a0-42eb-89da-1f9836275588codefunction off_policy_MC_control(mdp::MDP_Opaque, γ::T; π_b::Matrix{T} = make_random_policy(mdp), num_episodes::Integer = 1000, qinit::T = zero(T)) where T<: AbstractFloat
Q = initialize_state_action_value(mdp; qinit = qinit)
counts = initialize_state_action_value(mdp; qinit = zero(T))
π_star = create_greedy_policy(Q)
vhold = zeros(T, length(mdp.actions))
for i in 1:num_episodes
s0 = mdp.state_init()
i_a0 = sample_action(π_b, mdp.statelookup[s0])
a0 = mdp.actions[i_a0]
(states, actions, rewards) = mdp.simulator(s0, a0, π_b)
g = zero(T)
w = one(T)
t = length(states)
for t = length(states):-1:1
g = γ*g + rewards[t]
i_s = mdp.statelookup[states[t]]
i_a = mdp.actionlookup[actions[t]]
counts[i_a, i_s] += w
Q[i_a, i_s] += (w/counts[i_a, i_s])*(g - Q[i_a, i_s])
#update the target policy to be greedy at state s
vhold .= Q[:, i_s]
make_greedy_policy!(vhold)
π_star[:, i_s] .= vhold
#end episode if trajectory is no longer possible under target policy
π_star[i_a, i_s] == 0 && break
#note that here I replace the numerator with the probability under the target policy instead of 1. That is because π_star here may be stochastic in the case of a tie
w *= (π_star[i_a, i_s] / π_b[i_a, i_s])
end
# #there's no check here so this is equivalent to every-visit estimation
# function update!(t = length(states); g = zero(T), w = one(T))
# t == 0 && return nothing
# g = γ*g + rewards[t]
# i_s = mdp.statelookup[states[t]]
# i_a = mdp.actionlookup[actions[t]]
# counts[i_a, i_s] += w
# Q[i_a, i_s] += (w/counts[i_a, i_s])*(g - Q[i_a, i_s])
# #update the target policy to be greedy at state s
# vhold .= Q[:, i_s]
# make_greedy_policy!(vhold)
# π_star[:, i_s] .= vhold
# #end episode if trajectory is no longer possible under target policy
# π_star[i_a, i_s] == 0 && return nothing
# w /= π_b[i_a, i_s]
# update!(t-1, g=g, w=w)
# end
# update!()
end
return π_star, Q
endmetadatashow_logsèdisabled®skip_as_script«code_folded$6dc0de46-2164-4580-b186-a73cb5b5167dcell_id$6dc0de46-2164-4580-b186-a73cb5b5167dcodew#given a position, velocity, and action takes a forward step in time and returns the new position, new velocity, and a set of points that represent the space covered in between
function project_path(p, v, a)
(vx, vy) = v
(dx, dy) = a
vxnew = clamp(vx + dx, 0, 4)
vynew = clamp(vy + dy, 0, 4)
#both velocity components cannot be zero except when the race starts
if (vxnew + vynew) == 0
if rand() < 0.5
vxnew += 1
else
vynew += 1
end
end
#position the car ends up at
pnew = (p[1] + vxnew, p[2] + vynew)
#how to check if the path intersects the finish line or the boundary? Form a square from vxnew and vynew and see if the off-track area or finish line is contained in that square
pathsquares = Set((x, y) for x in p[1]:pnew[1] for y in p[2]:pnew[2])
(pnew, (vxnew, vynew), pathsquares)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$63814164-f305-49b3-ab51-675c822d7b18cell_id$63814164-f305-49b3-ab51-675c822d7b18codeCconst racetrack_velocities = [(vx, vy) for vx in 0:4 for vy in 0:4]metadatashow_logsèdisabled®skip_as_script«code_folded$4337b83f-b648-4b55-9d2a-4fffcf701111cell_id$4337b83f-b648-4b55-9d2a-4fffcf701111codehtml"""
"""metadatashow_logsèdisabled®skip_as_script«code_folded$1b78b25d-3942-4a6b-a2bd-7d97242da9fecell_id$1b78b25d-3942-4a6b-a2bd-7d97242da9fecodeLmonte_carlo_ES(mdp::MDP_Opaque, γ::T, num_episodes; Q_init::Matrix{T} = initialize_state_action_value(mdp; qinit = zero(T)), π_init::Matrix{T} = make_random_policy(mdp; init = one(T)), override_state_init = false) where T <: Real = monte_carlo_ES(mdp, π_init, Q_init, γ, num_episodes; override_state_init = override_state_init) metadatashow_logsèdisabled®skip_as_script«code_folded$9524a3f5-fca3-4ce9-b04d-0cb6c0cd0c90cell_id$9524a3f5-fca3-4ce9-b04d-0cb6c0cd0c90code #off policy control learns very slowly because each episode from the random policy takes thousands of steps to even finish the race. Even after 1_000 episodes almost no learning has occured.
begin
run1_1
showrace(track1, create_policy_function(πstar1_racetrack1, track1_mdp))
endmetadatashow_logsèdisabled®skip_as_script«code_folded$2ed0d4bb-bb6e-4adf-ad7c-8ddeb8c20b84cell_id$2ed0d4bb-bb6e-4adf-ad7c-8ddeb8c20b84codeq_offpol[2][:, blackjack_stateindex1] #the second value should converge to -0.27726 same as the value function for the policy that hits on this state. The first value is the value of sticking on this state which should be lower since it is a worse actionmetadatashow_logsèdisabled®skip_as_script«code_folded$a0d61852-9942-42de-b554-572c4526a3a8cell_id$a0d61852-9942-42de-b554-572c4526a3a8code function make_track_mdp(track; maxsteps = Inf)
states = [(position = p, velocity = v) for p in union(track.start, track.body) for v in racetrack_velocities]
state_init() = (position = rand(track.start), velocity = (0, 0))
statelookup = makelookup(states)
function take_action(π, s)
i_s = statelookup[s]
i_a = sample_action(π, i_s)
racetrack_actions[i_a]
end
simulator(s0, a0, π) = race_track_episode(s0, a0, s -> take_action(π, s), track, maxsteps = maxsteps)
MDP_Opaque(states, racetrack_actions, state_init, simulator)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$bb617e58-2700-4f0d-b8c8-3a266142fb70cell_id$bb617e58-2700-4f0d-b8c8-3a266142fb70codeBconst racetrack_actions = [(dx, dy) for dx in -1:1 for dy in -1:1]metadatashow_logsèdisabled®skip_as_script«code_folded$0d9c5d60-878a-45bb-8707-275cf10be41fcell_id$0d9c5d60-878a-45bb-8707-275cf10be41fcode@bind run2_2 Button("Run race")metadatashow_logsèdisabled®skip_as_script«code_folded$b6eac49e-6742-4594-87a5-821437846b0dcell_id$b6eac49e-6742-4594-87a5-821437846b0dcode.#using ordinary importance sampling calculates statistics on weights observed after n episodes of training including what percentage of weights are 0, 1, 2 etc...
function test(n)
[monte_carlo_pred_Q(π_blackjack1, π_rand_blackjack, blackjack_mdp, 1.0f0; num_episodes = n, historystateindex = blackjack_stateindex1, qinit = 0.0f0, override_state_init = true, samplemethod=Ordinary(), use_target_initial_action = true)[3][1:n] |> v -> n - sum(v .== 0) for _ in 1:10000] |> v -> (mean(v), median(v), mode(v), mean(v .== 0), mean(v .== 1), mean(v .== 2))
endmetadatashow_logsèdisabled®skip_as_script«code_folded$61d8cfc6-a50c-4546-9e1f-dc73d4764bb9cell_id$61d8cfc6-a50c-4546-9e1f-dc73d4764bb9code\#there's no check here so this is equivalent to every-visit estimation
function updateQ!(mdp, Q, counts, π_target::Matrix{T}, π_behavior::Matrix{T}, states, actions, rewards::Vector{T}, γ::T, samplemethod::ImportanceMethod; t = length(states), g_old = zero(T), w = one(T)) where T<:Real
#terminate at the end of a trajectory
(t == 0) && return w
if (w == zero(T)) && isa(samplemethod, Weighted)
return w
end
#accumulate future discounted returns
g = γ*g_old + rewards[t]
i_s = mdp.statelookup[states[t]]
i_a = mdp.actionlookup[actions[t]]
counts[i_a, i_s] += updatecount(samplemethod, w)
Q[i_a, i_s] += updatevalue(samplemethod, Q[i_a, i_s], g, w, counts[i_a, i_s])
updateQ!(mdp, Q, counts, π_target, π_behavior, states, actions, rewards, γ, samplemethod; t = t-1, g_old = g, w = w * π_target[i_a, i_s] / π_behavior[i_a, i_s])
endmetadatashow_logsèdisabled®skip_as_script«code_folded$847a074c-1d23-4de3-a039-322aeb9f7613cell_id$847a074c-1d23-4de3-a039-322aeb9f7613codetest(2)metadatashow_logsèdisabled®skip_as_script«code_folded$d2625507-4787-4b1c-9a91-108012e42cc7cell_id$d2625507-4787-4b1c-9a91-108012e42cc7codefunction make_rotation_style(vx, vy)
((vx==0) && (vy==0)) && return """"""
"""
[vx='$vx'][vy='$vy']::before {
content: '→';
transform: rotate($(atand(vy, vx))deg) scale($(scalelookup[norm([vx, vy])])%);
}
"""
endmetadatashow_logsèdisabled®skip_as_script«code_folded$94be5289-bba7-4490-bdcd-0d217a31c665cell_id$94be5289-bba7-4490-bdcd-0d217a31c665code#calculate value function for blackjack policy π and save results in plot-ready grid form
function eval_blackjack_policy(π, episodes; γ=1f0)
v_π = monte_carlo_pred_V(π, blackjack_mdp, γ; num_episodes = episodes)
make_value_grid(v_π)
endmetadatashow_logsèdisabled®skip_as_script«code_folded$f7616806-97ab-4b09-accc-4e047691f879cell_id$f7616806-97ab-4b09-accc-4e047691f879code\#track is defined as a set of points for each of the start, body, and finish
const track2 = ( start = make_row_set(0, 22, 0),
finish = make_col_set(31, 21, 29),
body = union( union((make_row_set(0, 22, y) for y in 1:2)...),
union((make_row_set(i, 22, y) for (i, y) in zip(1:14, 3:16))...),
make_row_set(14, 23, 17),
make_row_set(14, 25, 18),
make_row_set(14, 26, 19),
make_row_set(14, 29, 20),
union((make_row_set(xstart, 31, y) for (xstart, y) in zip([13, 12, 11, 11, 11, 11, 12, 13, 16], 21:29))...))
)metadatashow_logsèdisabled®skip_as_script«code_folded$70d9d39f-020d-4f25-810c-82a143a3335bcell_id$70d9d39f-020d-4f25-810c-82a143a3335bcode;const π_rand_blackjack = make_random_policy(blackjack_mdp)metadatashow_logsèdisabled®skip_as_script«code_folded$780f2fd9-49c3-48bc-b790-dde5be1dc81bcell_id$780f2fd9-49c3-48bc-b790-dde5be1dc81bcodetrack1_mdp.statesmetadatashow_logsèdisabled®skip_as_script«code_folded$833bb53c-bc2b-47fb-9429-d0f6d92efb42cell_id$833bb53c-bc2b-47fb-9429-d0f6d92efb42code@bind run1_1 Button("Run race")metadatashow_logsèdisabled®skip_as_script«code_folded$e370dbb3-3bd9-4dc8-b8ca-8aad8711905ccell_id$e370dbb3-3bd9-4dc8-b8ca-8aad8711905ccodeD@htl("""
""")metadatashow_logsèdisabled®skip_as_script«code_folded$2646c9a2-46b1-4700-9290-ddc7dc9a59afcell_id$2646c9a2-46b1-4700-9290-ddc7dc9a59afcodeupdatecount(::Weighted, w) = wmetadatashow_logsèdisabled®skip_as_script«code_folded$892b5d8e-ac51-48f1-8288-65e9f68acd2dcell_id$892b5d8e-ac51-48f1-8288-65e9f68acd2dcode [monte_carlo_pred_V(π_blackjack1, π_rand_blackjack, blackjack_mdp, 1.0f0; num_episodes = 10, historystateindex = blackjack_stateindex1, vinit = 0.0f0, override_state_init = true, samplemethod=Ordinary())[3][1:10] |> sum for i in 1:1000] |> v -> (mean(v), count(v .== 0)/1000)
#for the target vs behavior policy, after one episode the mean weight including hte 0 values is about 2, let's say that all of these terminate in either 1 or -1. Then we'd have a mean reward value of 2 or -2 which has a squared error of ~5 and 3 respectively depending on whether a win or loss is more likely since the denominator will be 1. This is with ordinary importance sampling. In contrast with weighted importance sampling the divisor will be 2 on average too and each estimate will be an actual return value experienced by the behavior policy or 0 for impossible trajectories. Each of these will be worse than the 0 estimate. About 72% of the episodes will have a 0 weight after the first episode but only 3.5% will not have any update after 10 episodes. So for weighted importance sampling we have 72% 0 values and 28% the normal values. The key difference is that for ordinary importance sampling the 28% of values that aren't zero have a weight of about 7 whereas for weighted sampling all the weights are 1 for the value estimate after normalization. With an initial value estimate of 0, the squared error would be about 0.077. Seeing the error for the weighted results after 1 episode on average, it is about 0.25 which is consistent with about 28% of the runs having error values of 0.52 or 1.63 instead of 0.77. One thing I'm wondering though is why doesn't the error go up for Ordinary importance sampling after more of the episodes have non zero weighting. Key point is that the initial value of V doesn't matter. Some of the values are 0 just because the weighting is 0 and the corresponding denominator is still 1. Remember that as the second episode is added it is likely that most of those values will get cut in half due to a 0 weight trajectory and the count going up. Whereas for weighted sampling, all the 0's that get replaced will get worse while the others that have a new estimate won't be changed at all if they get a 0 weight trajectory. This behavior policy seems to on average product a trajectory that is possible with the target policy only 28% of the time so the most likely thing is just replacing existing 0's and not changing the other estimates. With normal importance sampling though, all those existing estimates will get cut in half and then some new ones will come in. Also it is likely that each run would need 4 non zero samples before that estimate is better than the initial 0 value, so that explains why the weighted sampling error doesn't drop until after 10 episodes where the average number of non zero samples is higher than that. After 7 episodes the average number of non zero weight trajectories is 2. At 10 episodes the median and mode non zero weights is 3metadatashow_logsèdisabled®skip_as_script«code_folded$acb08e38-fc87-43f4-ac2d-6c6bf0f2e9e6cell_id$acb08e38-fc87-43f4-ac2d-6c6bf0f2e9e6codevfunction estimate_mdp_state(mdp, π::Matrix{T}, stateindex, num_episodes) where T<:AbstractFloat
staterewards = zeros(T, num_episodes)
s0 = mdp.states[stateindex]
for i in 1:num_episodes
i_a0 = sample_action(π, stateindex)
a0 = mdp.actions[i_a0]
(states, actions, rewards) = mdp.simulator(s0, a0, π)
staterewards[i] = last(rewards)
end
return staterewards
endmetadatashow_logsèdisabled®skip_as_script«code_folded$fca388bd-eb8b-41e2-8da0-87b9386629c1cell_id$fca388bd-eb8b-41e2-8da0-87b9386629c1code+md"""
## 5.6 Incremental Implementation
"""metadatashow_logsèdisabled®skip_as_script«code_foldedënotebook_id$c6e0de0c-3901-11f0-234e-bd09c571f662in_temp_dir¨metadata