42:null 43:["$","title",null,{"children":"On-policy Monte Carlo control (for ε-soft policies) | Jim Kan | Observable"}] 49:T42d,displayedEpisodes = { const [newEpisodeNumber, newEpisode] = currentEpisode; if (!this) return [currentEpisode]; const [curEpisodeNumber, curEpisode] = this[this.length - 1]; if (newEpisodeNumber < curEpisodeNumber) { // reset return [currentEpisode]; } else if (newEpisodeNumber === curEpisodeNumber) { this[this.length - 1] = currentEpisode; return this; } else { return this.concat([currentEpisode]).slice(-numberOfEpisodesToDisplay); } } // randomWalks = d3.range(numberOfEpisodes).map(() => episode(randomWalkPolicy, maxPathLength)) // walks = slowEpisodes(env, numberOfEpisodes, epsilonGreedyPolicy, maxPathLength, firstVisitMC, 500) // walks = slowEpisodes(env, numberOfEpisodes, randomWalkPolicy, maxPathLength, noLearning, 50) // walks = slowEpisodes(env, numberOfEpisodes, epsilonGreedyPolicy, maxPathLength, false, 50) // walks = entireEpisodes(env, numberOfEpisodes, epsilonGreedyPolicy, maxPathLength, sarsaLearnQ, 200) // walks = genExperiment(env, currentAgent) // walks = genExperiment(env, sarsa)4a:T48e,viewof sigma = { const form = html` `; function update() { const sigma_x = form.sigma_x.valueAsNumber; const sigma_y = form.sigma_y.valueAsNumber; const p = form.p.valueAsNumber; const cov_xy = p * sigma_x * sigma_y const sigma = [[sigma_x*sigma_x, cov_xy], [cov_xy, sigma_y * sigma_y]].map(vv => vv.map(round)) form.value = sigma; form.value.sigma_x = sigma_x; form.value.sigma_y = sigma_y; form.value.p = p; } form.sigma_x.oninput = update; form.sigma_y.oninput = update; form.p.oninput = update; update(); return form; }4b:[] 47:{"id":"ea7f2c7cbd499d23","slug":"on-policy-monte-carlo-control-for-soft-policies","title":"On-policy Monte Carlo control (for ε-soft policies)","thumbnail":"b417d501eaf919e683aec21078b32da5787d2d0ba78f579383970271437889d7","access_level":"public","create_time":"$D2018-04-30T09:00:20.811Z","update_time":"$D2019-04-15T00:22:27.641Z","view_time":null,"first_public_time":"$D2018-04-30T09:26:00.293Z","has_unpublished_edits":null,"fork":{"id":"3fed94c043aee0a3","slug":"temporal-difference-learning-sarsa-0","title":"Temporal-Difference Learning: SARSA(0)","owner":{"id":"df82e3ae90c3ba68","login":"j-kan","name":"Jim Kan"}},"stars":4,"starred":false,"owner":{"type":"team","id":"df82e3ae90c3ba68","login":"j-kan","name":"Jim Kan","avatar_url":"https://avatars-next.observableusercontent.com/6cf6d5dc58f463a8174b46278a86f73fa681db6ba244bb56e46eb254d64af045","tier":"starter_2024","bio":"","following":false},"version":3286,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"07757bcd007742e1","login":"j-kan","name":"Jim Kan","avatar_url":"https://avatars-next.observableusercontent.com/6cf6d5dc58f463a8174b46278a86f73fa681db6ba244bb56e46eb254d64af045","tier":null,"bio":"","following":false}],"members":[{"type":"individual","id":"07757bcd007742e1","login":"j-kan","name":"Jim Kan","avatar_url":"https://avatars-next.observableusercontent.com/6cf6d5dc58f463a8174b46278a86f73fa681db6ba244bb56e46eb254d64af045","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":6,"collection":{"id":"d2769ec0679b5a7e","slug":"reinforcement-learning","title":"Reinforcement Learning","owner":{"id":"df82e3ae90c3ba68","login":"j-kan","name":"Jim Kan"}},"type":"notebook","body":{"titling":"auto","title":"On-policy Monte Carlo control (for ε-soft policies)","cells":[{"id":0,"value":"md`# On-policy Monte Carlo control (for ε-soft policies)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2660,"value":"md`This serves as a testbed for simple implementations of reinforcement learning algorithms -- primarily for my own edification as I make my way through [this](http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html) and [this](http://incompleteideas.net/book/the-book-2nd.html), and then maybe [this](https://sites.google.com/view/deep-rl-bootcamp/home) (my notes from these can be found [here](https://beta.observablehq.com/@j-kan/reinforcement-learning-notes)).\n\nThis notebook implements on-policy MC control (for ε-soft policies), as described in section 5.4 of Sutton and Barto.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2206,"value":"md`\nHere we have a series of __${maxEpisodes}__ random walks around a __${gridDimensions.x} x ${gridDimensions.y}__ grid, where walks are limited to a horizon of __${horizon}__ steps.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2549,"value":"viewof maxEpisodes = labeledSlider(\n '', 'number of walks')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2084,"value":"viewof horizon = labeledSlider(\n '',\n 'horizon (maximum number of steps per walk)');","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":763,"value":"viewof gridDimensions = {\n const defaultX = 15;\n const defaultY = 10\n const maxValue = Math.min(displayDimensions.x, displayDimensions.y)/minGranularity;\n \n const form = html`\n`;\n \n form.value = { x: form.x.valueAsNumber, y: form.y.valueAsNumber };\n form.x.oninput = () => form.value.x = form.x.valueAsNumber;\n form.y.oninput = () => form.value.y = form.y.valueAsNumber;\n // ${this ? this.value : 30}\n \n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":69,"value":"gridWorldDisplay = displayGridWorld(displayDimensions, rewardGrid, displayedEpisodes, showQ && mutable memory.Q)\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":958,"value":"viewof numberOfEpisodesToDisplay = labeledSlider(\n '',\n 'number of walks to display')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1788,"value":"viewof displayUpdateInterval = labeledSlider(\n ``, \n 'pause between display updates (in ms)')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2182,"value":"viewof displayStepwise = inlineSpinner(\n `update display after every \n `,\n (val) => val === 'step')\n ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1708,"value":"viewof showQ = labeledCheckbox(` show arrows indicating current Q values`)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2213,"value":"md`\nThe display currently shows the most recent __${Math.min(numberOfEpisodesToDisplay, memory.stats.length)}__ of __${memory.stats.length}__ walks, updating after every new __${displayStepwise ? 'step' : 'walk'}__, with a __${displayUpdateInterval}__ millisecond pause in between.\n\nThe green circle represents the start state, and the red circle represents the end state, which if filled indicates a successful outcome. ${showPathCircles ? `The grey circles mark the steps along the path of the most recent walk.` : ''}\n\n${showQ ? \n `\n\nThe small arrows in each cell indicate the action-value (Q) for each state/action pair.\n` : ''}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2663,"value":"md`Here are some plots for tracking progress:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1907,"value":"md`Episode length (number of steps per walk) for the _n_-th walk:` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1812,"value":"statsPlot(d => d.episodeLength, memory.stats, displayDimensions)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1913,"value":"md`Episode total (discounted) return vs walk number:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1883,"value":"statsPlot(d => d.totalReturn, memory.stats, displayDimensions)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1916,"value":"md`ε value vs walk number:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2520,"value":"statsPlot(d => d.epsilon, memory.stats, displayDimensions)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2665,"value":"md`Click this to make the agent start again from the beginning.` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2601,"value":"viewof go = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2338,"value":"currentEpisode = {\n return go, \n (displayUpdateInterval > 0) \n ? slowly(() => genExperiment(env, currentAgent, displayStepwise), displayUpdateInterval)\n : genExperiment(env, currentAgent, displayStepwise);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2341,"value":"$49","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2356,"value":"md`# Agent`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2667,"value":"md`i.e. the thing that's doing the walking.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2345,"value":"currentAgent = agentMonteCarlo(everyVisitMC)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2412,"value":"agentMonteCarlo = (policyEvaluationFn) => ({\n initialConditions: memoryInitialValues,\n policyFn: glieEpsilonGreedyPolicy,\n learnFn: policyEvaluationFn,\n stepwise: false\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2329,"value":"md`## Monte Carlo methods (model free)\n\n- Sutton & Barto chapter 5\n- Silver lecture 4 & 5\n\n### Monte Carlo prediction\n\nEstimate/learn the state-value function _v_π (s)_, i.e. the expected returns from each state if following a given policy. \n\nMC prediction/policy evaluation substitutes _empirical mean_ return for _expected_ return.\n\nThe return \n_G_t_ \nfor a given episode/Monte Carlo sample is an **unbiased** estimate of the state-value _v_π(S_t)_\n\nFor first-visit MC, the return on each visit is an IID estimate of v_π(s)\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2332,"value":"md`### MC prediction with incremental updating\n\n${tex.block`\n V(S_t) \\leftarrow V(S_t) + \\alpha (G_t - V(S_t)) \n`}\n\nwhere\n\n${tex.block`\n \\alpha = \\frac{1}{N(S_t)}\n`}\n\n...or, in general, α could be anything\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2334,"value":"md`### MC estimation of action values: _q_π (s,a)_\n\nS&B chapter 5.2, p.79\n\nThe state-value function is only useful given a model of the system dynamics. In the absence of a model, it's better to estimate state-action pairs _q_π(s,a)_.\n\nWith state-action pairs, however, we have the exploitation vs. exploration problem that we didn't have with just state values, since for example a deterministic policy will only ever pick one action, so we never visit the other alternatives. \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3132,"value":"md`#### First-visit MC prediction\n\nEstimate ${tex`q_\\pi(s,a)`} by averaging the returns on the first visit per episode to each state/action pair.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1436,"value":"firstVisitMC = (walk, isDone, memory) => {\n \n function isFirstVisit(i, step) {\n for (let j = 0; j < i; ++j) {\n if (walk[j].current.observation === step.current.observation\n && (walk[j].current.action === step.current.action)) {\n return false;\n }\n return true; \n }\n }\n \n if (isDone) { \n let G = 0; // discountedReturn(walk);\n for (let i = walk.length -1; i > 0; --i) {\n const step = walk[i]; \n G = gamma * G + (step.reward || 0);\n \n if (isFirstVisit(i, step)) {\n memory = rememberMC(step.current.observation, step.current.action, G, memory);\n }\n }\n }\n return memory;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3135,"value":"md`The same thing, but use the last visit per episode.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1930,"value":"lastVisitMC = (walk, isDone, memory) => {\n \n if (isDone) { \n let G = 0; // discountedReturn(walk);\n let visited = {};\n \n for (let i = walk.length -1; i > 0; --i) {\n const step = walk[i]; \n const sa = [step.current.observation, step.current.action];\n \n G = gamma * G + (step.reward || 0);\n \n if (!visited[sa]) {\n visited[sa] = 1;\n memory = rememberMC(step.current.observation, step.current.action, G, memory);\n }\n }\n }\n return memory; \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3137,"value":"md`#### Every-visit MC prediction\n\nEstimate ${tex`q_\\pi(s,a)`} by averaging the returns on every visit to each state/action pair.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1257,"value":"everyVisitMC = (walk, isDone, memory) => {\n if (isDone) { \n let G = 0; // discountedReturn(walk);\n for (let i = walk.length -1; i > 0; --i) {\n const step = walk[i]; \n G = gamma * G + (step.reward || 0);\n memory = rememberMC(step.current.observation, step.current.action, G, memory);\n }\n }\n return memory; \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2336,"value":"md`### Monte Carlo control\n\ni.e. approximating optimal policies using iterative improvement as in GPI: alternating policy evaluation and policy improvement.\n\n${tex.block`\\pi(s) \\doteq arg\\max_{a \\in A} q(s, a)`}\n\nOn-policy learning\n\n- Policy evaluation: to be model-free, need to use ${tex`q(s,a)`} rather than ${tex`v_{\\pi}(s)`}\n\n- Policy improvement: greedy improvement doesn't work because there's no exploration ⇒ ε-greedy policy improvement\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2392,"value":"md`### ε-greedy policy\n\nGreedy improvement doesn't work because there's no exploration ⇒ ε-greedy policy improvement\n${tex.block`\n\\pi(s) = \n \\begin{cases}\n \\epsilon/m + 1 - \\epsilon & \\text{if } a^* = {argmax}_{a \\in A} Q(s, a) \\\\ \n \\epsilon/m & \\text{otherwise}\n \\end{cases}\n`}\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2985,"value":"epsilon = 0.1","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1165,"value":"function epsilonGreedyPolicy(env, observation, _epsilon = epsilon) {\n const nA = env.actions.length;\n const Qs = Qvec(env, observation)\n \n const maxVal = Math.max(...Qs);\n const nBests = Qs.filter((q) => q === maxVal).length;\n \n return Qs.map((q) => _epsilon/nA + ((q === maxVal) ? (1.0 - _epsilon)/nBests : 0));\n // break ties randomly\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2323,"value":"md`### Greedy in the Limit with Infinte Exploration (GLIE)\n\n* All state-action pairs explored infinitely many times\n\t\n\t${tex.block`\\lim_{k \\leftarrow \\infty} N_k(s, a) = \\infty `}\n\n* The policy converges on a greedy policy\n\n\t${tex.block`\\lim_{k \\leftarrow \\infty} \\pi_k(a | s) = \n\t\t\t\t\t\\textbf{1}(a = {argmax}_{a' \\in A} Q_k(s, a')) `}\n\n### GLIE MC control\n\n* For ${tex`k`}th episode sampled using ${tex`\\pi`}: ${tex`\\{ S_1, A_1, R_2, ..., S_T \\} \\sim \\pi`}:\n\t* For each state and action in the episode:\n\t\t${tex.block`\n\t\t\t\\begin{aligned}\n\t\t\t\tN(S_t, A_t) &\\leftarrow N(S_t, A_t) + 1 \t\\\\\n\t\t\t\tQ(S_t, A_t) &\\leftarrow Q(S_t, A_t) +\n\t\t\t\t\t\t\t\t\t\t\t\\frac{1}{N(S_t, A_t)} [G_t - Q(S_t, A_t)]\n\t\t\t\\end{aligned}\n\t\t`}\n\t* Improve policy based on new Q\n\t\t${tex.block`\n\t\t\t\\begin{aligned}\n\t\t\t\t\\epsilon &\\leftarrow 1/k \t\\\\\n\t\t\t\t\\pi &\\leftarrow \\epsilon\\text{-greedy} (Q)\n\t\t\t\\end{aligned}\n\t\t`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2279,"value":"function glieEpsilon() {\n return 10/(10 + mutable memory.stats.length);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1946,"value":"function glieEpsilonGreedyPolicy(env, observation) {\n // const epsilon = 10/(10 + mutable memory.stats.length);\n \n return epsilonGreedyPolicy(env, observation, glieEpsilon());\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1799,"value":"md`## Memory\n\nAgents might need to remember things based on their experience; that's what this part is for.\n\nBasically, anything mutable goes in here. The specifics of what is remembered here will depend on what algorithm the agent is following. \n\nAt a minimum, we will keep some tracking statistics per episode to help with evaluating the agent's progress: the total episode length, and each episode's discounted return.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1380,"value":"mutable memory = memoryInitialValues()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2000,"value":"function memoryInitialValues() {\n return {\n Q: {},\n stats: []\n };\n}\n ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1759,"value":"function eraseMemory() {\n mutable memory = memoryInitialValues();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1748,"value":"function recordStats(epi) {\n mutable memory.stats = mutable memory.stats || [];\n mutable memory.stats.push({\n episodeLength: epi.length, \n totalReturn: discountedReturn(epi),\n epsilon: glieEpsilon()\n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2199,"value":"memory.stats","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2388,"value":"md`### Return\n\nThe _return G_t_ attained in a given episode is the total discounted reward received from time step _t_ onward, where ${tex`\\gamma`} is a _discount factor_ which attenuates the effects of future rewards.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2390,"value":"tex.block`\n\\begin{aligned}\nG_t &= R_{t+1} + \\gamma R_{t+2} + \\gamma^2 R_{t+3} + ... \t\\\\\n &= \\sum_{k=0}^{\\infty} \\gamma^k R_{t+k+1}\n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1163,"value":"gamma = 0.99","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2382,"value":"function discountedReturn(walk, _gamma = gamma) {\n return walk.reduce((acc, step) => acc * _gamma + (step.reward || 0), 0);\n}\n\n// discountedReturns = walks.map((walk) => round(discountedReturn(walk, 0.9), 5))","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2595,"value":"md`### Action-value function _q_π(s,a)_\n\nThe expected return starting from state _s_, taking action _a_, and then following policy _π_\n\n${tex.block`\n\\begin{aligned}\n\nq_{\\pi}(s, a) \n\t&\\doteq \\mathbb{E}_{\\pi}[ G_t | S_t = s, A_t = a]\t\\\\\n \t &= \\mathbb{E}_{\\pi}[ R_{t+1} + \\gamma q_{\\pi}(S_{t+1}, A_{t+1}) | S_t = s, A_t = a]\t\n\n\\end{aligned}\n`}\n\nThe last line is the __Bellman Expectation Equation for action-values__.\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2371,"value":"function rememberMC(obs, action, G, memory) {\n memory.rewardCount = memory.rewardCount || {};\n memory.rewardSum = memory.rewardSum || {};\n\n memory.rewardCount[obs] = memory.rewardCount[obs] || {};\n memory.rewardSum[obs] = memory.rewardSum[obs] || {};\n memory.Q[obs] = memory.Q[obs] || {};\n \n const rc = 1 + (memory.rewardCount[obs][action] || 0);\n const rs = G + (memory.rewardSum[obs][action] || 0);\n \n memory.rewardCount[obs][action] = rc;\n memory.rewardSum[obs][action] = rs;\n memory.Q[obs][action] = rs/rc;\n \n return memory;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1267,"value":"function Qvec(env, obs, defaultFn) {\n const Qs = mutable memory.Q[obs] || {};\n \n return env.actions.map(a => Qs[a] || (defaultFn ? defaultFn() : 0.000001 * Math.random()));\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2351,"value":"function dispQ(obs) {\n return { \n Qs: memory.Q[obs], \n Qsvec: Qvec(env, obs), \n P: glieEpsilonGreedyPolicy(env, obs)\n }\n}\n\n// dispQ([0,0])","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":480,"value":"md`# Environment\n\nGeneric functions for characterizing and interacting with any environment, loosely based on the [environment API](https://gym.openai.com/docs/#environments) from [OpenAI Gym](https://gym.openai.com/).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2782,"value":"import {reset, step, chooseAction, genEpisodeStep, genEpisode, slowGenEpisode} from \"@j-kan/a-random-walk-through-the-grid-world\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":618,"value":"md`## The Grid World environment\n\nThis captures the dynamics of a specific environment instance -- in this case, the Grid World where the reward surface is determined by a 2D difference of Gaussians function (described in greater detail below). The DoG generates a surface where the positive peak values are surrounded by a shallower ring of negative values.\n\nEach episode terminates when the Manhattan distance between the current state and the Gaussian peak is at most __${gwMaxDistanceFromPeak}__, or when reaching the specified maximum episode length of __${horizon}__. There is an additional __${extraSuccessBonus}__ point reward for reaching the goal (i.e. the Gaussian peak).\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3260,"value":"import {makeGridWorld} from \"@j-kan/a-random-walk-through-the-grid-world\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":472,"value":"env = makeGridWorld(rewardGrid, extraSuccessBonus, mu, gwMaxDistanceFromPeak)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2846,"value":"gwMaxDistanceFromPeak = 0.5","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2850,"value":"extraSuccessBonus = 10","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":469,"value":"md`### The reward surface`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":733,"value":"md`These parameters determine the shape of the 2D difference of Gaussians function that generates the reward surface. \n\nThis first set parameterizes the \"positive\" Gaussian:` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2734,"value":"tex.block`\n\\begin{aligned}\n\n\\boldsymbol{\\mu}\n &= [ \\mu_x, \\mu_y ] \n &= [ ${mu} ]\n\\\\\n\n\\rho &= & ${round(sigma.p)} \\\\\n\n\\boldsymbol{\\Sigma_+} &= \n \\begin{bmatrix}\n \\sigma_x^2 & \\rho\\sigma_x\\sigma_y \\\\ \n \\rho\\sigma_x\\sigma_y & \\sigma_y^2\n \\end{bmatrix}\n&=\n \\begin{bmatrix}\n ${sigma[0][0]} & ${sigma[0][1]} \\\\ \n ${sigma[1][0]} & ${sigma[1][1]}\n \\end{bmatrix} \n\\\\\n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":802,"value":"viewof mu = {\n const form = html`\n`;\n \n form.value = [ form.mu_x.valueAsNumber, form.mu_y.valueAsNumber ].map(round);\n form.mu_x.oninput = () => form.value[0] = round(form.mu_x.valueAsNumber);\n form.mu_y.oninput = () => form.value[1] = round(form.mu_y.valueAsNumber);\n \n return form;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":129,"value":"$4a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":734,"value":"md`where ρ is the Pearson correlation coefficient between x and y.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2736,"value":"md`These next parameters characterize the negative Gaussian relative to the shape of the positive Gaussian:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2740,"value":"tex.block`\n\\begin{aligned}\n\n\\boldsymbol{\\Sigma_-} &= \n k \\boldsymbol{\\Sigma_+}\n&=\n ${sigmaRatio}\n \\begin{bmatrix}\n ${sigma[0][0]} & ${sigma[0][1]} \\\\ \n ${sigma[1][0]} & ${sigma[1][1]}\n \\end{bmatrix} \n\\\\\n\nDoG(x,y) &= &\n \\mathcal{N}(\\boldsymbol{\\mu}, \\boldsymbol{\\Sigma_+}) - \n ${magnitudeRatio} \n \\mathcal{N}(\\boldsymbol{\\mu}, \\boldsymbol{\\Sigma_-}) \\\\\n\n\\end{aligned}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":737,"value":"md`Ratio of sigmas between the negative and positive Gaussians:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":730,"value":"viewof sigmaRatio = html`\t\n \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":744,"value":"md`Ratio of magnitude coefficients between the negative and positive Gaussians:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":739,"value":"viewof magnitudeRatio = html`\t\n \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":164,"value":"rewardSurfaceFn = xy => differenceOfGaussians2d(xy, {\n mu: mu, \n sigma: sigma, \n sigmaRatio: sigmaRatio, \n magnitudeRatio: magnitudeRatio \n })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3229,"value":"md`This function returns true if the grid position contains a wall, i.e. somewhere the agent can't go.\n\nWe mark wall positions in the reward grid as \\`NaN\\` values.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3231,"value":"wallFn = ([x,y]) => {\n return (x === 5 && (y < gridDimensions.y - 2))\n // return (x === 5 && (y % 2 === 0 || y % 5 === 0))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":159,"value":"rewardGrid = makeGrid(gridDimensions.x, gridDimensions.y, rewardSurfaceFn, wallFn)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2695,"value":"md`# Experiment`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2694,"value":"md`An experiment puts an agent in an environment and lets it run for a set number of episodes. This is the top-level entry point for this notebook.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2809,"value":"function* genExperiment(env, agent, stepwise=false) {\n \n let mem = agent.initialConditions(env); // (env); \n\n mutable memory = mem;\n\n for (let i = 0; i < maxEpisodes; ++i) {\n for (const episode of genEpisode(env, agent.policyFn, horizon)) {\n const latestStep = episode[episode.length-1];\n const isComplete = latestStep.done || episode.length >= horizon;\n\n mem = agent.learnFn(episode, isComplete, mem);\n mutable memory = mem;\n\n if (stepwise)\n yield [i, episode];\n \n if (isComplete) {\n recordStats(episode);\n if (!stepwise)\n yield [i, episode];\n }\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":460,"value":"md`### Appendix\n\nMiscellaneous display setup and configuration of no scientific interest.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":986,"value":"showPathCircles = true","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2613,"value":"import {episodeToPath, differenceOfGaussians2d, statsPlot, displayGridWorld, makeGrid, \n normalize, chooseRandomly, slowly,\n argmax, matrixSum, matrixScalarMult, matrixMin, matrixMax, round,\n labeledSlider, labeledCheckbox, inlineSpinner} from \"@j-kan/a-random-walk-through-the-grid-world\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":251,"value":"minGranularity = 12","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":64,"value":"displayDimensions = ({ \n x: 900, y: 600, \n margin: {\n left: 20, \n bottom: 20,\n \tright: 10,\n \ttop: 10 }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2828,"value":"MultivariateGaussian = require('https://bundle.run/multivariate-gaussian@3.3.1')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"d3 = require(\"https://d3js.org/d3.v5.min.js\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4b","stdlib":"1"}} 48:"$47:body"