41:null 42:["$","title",null,{"children":"Temporal-Difference Learning: SARSA(0) | Jim Kan | Observable"}] 48: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)49:T75c,md` ## TD prediction (Silver lecture 4) ### MC vs TD - MC updates ${tex`V(S_t)`} toward _actual_ return ${tex`G_t`} - TD(0) updates ${tex`V(S_t)`} toward _estimated_ return ${tex`R_{t+1} + \gamma V(S_{t+1})`} Thus TD(0) learns immediately with every step, while MC only learns from complete sequences. #### Bias/variance tradeoff - MC: high variance, zero bias - not very sensitive to initial value - TD: low variance, some bias - usu. more efficient - more sensitive to initial value The return ${tex`G_t`} for a given episode/Monte Carlo sample is an **unbiased** estimate of the state-value ${tex`v_{\pi}(S_t)`} The true TD target ${tex`R_{t+1} + \gamma v_{\pi}(S_{t+1})`} is an **unbiased** estimate of ${tex`v_{\pi}(S_t)`} But TD target ${tex`R_{t+1} + \gamma V(S_{t+1})`} is a **biased** estimate of ${tex`v_{\pi}(S_t)`} since the ${tex`V(S_{t+1})`} term could be anything -- it's not guaranteed to have any correspondence to reality. However, TD target is much lower variance than the return ${tex`G_t`}, since it only depends on one random action + transition + reward, whereas the return depends on many. * MC fits to the observed returns (minizing MSE), whatever they are - does not exploit Markov property - can be better on non-Markov environments * TD fits to the MDP (the max likelihood Markov model) ##### Bootstrapping & sampling Bootstrapping: use current estimates to perform updates instead of going all the way to the end (i.e. the total return) Sampling: instead of using full width of the tree rooted at the current state, only sample a single path to produce an update ${tex.block` \begin{aligned} V(S_t) &\leftarrow V(S_t) + \alpha (G_t - V(S_t)) &(MC) \\ V(S_t) &\leftarrow V(S_t) + \alpha (R_{t+1} + \gamma V(S_{t+1})- V(S_t)) &(TD) \\ V(S_t) &\leftarrow \mathbb{E}_{\pi}[R_{t+1} + \gamma V(S_{t+1})] &(DP) \end{aligned} `} `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:[] 46:{"id":"3fed94c043aee0a3","slug":"temporal-difference-learning-sarsa-0","title":"Temporal-Difference Learning: SARSA(0)","thumbnail":null,"access_level":"public","create_time":"$D2018-04-17T00:32:45.289Z","update_time":"$D2020-12-01T07:11:40.254Z","view_time":null,"first_public_time":"$D2018-04-30T09:43:04.011Z","has_unpublished_edits":null,"fork":true,"stars":7,"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":3386,"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":7,"collection":{"id":"d2769ec0679b5a7e","slug":"reinforcement-learning","title":"Reinforcement Learning","owner":{"id":"df82e3ae90c3ba68","login":"j-kan","name":"Jim Kan"}},"type":"notebook","body":{"titling":"auto","title":"Temporal-Difference Learning: SARSA(0)","cells":[{"id":0,"value":"md`# Temporal-Difference Learning: SARSA(0)`","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 SARSA, as described in section 6.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}__ 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":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":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":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":"$48","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\n\ni.e. the thing that's doing the walking.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2345,"value":"currentAgent = sarsa","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3247,"value":"$49","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2326,"value":"md`## TD control (SARSA)\n\n* initialize ${tex`Q(s,a)`} arbitrarily, except ${tex`Q(s_{terminal}, *) = 0`}\n* repeat for each episode:\n\t* initialize ${tex`S`}\n\t* choose ${tex`A`} from ${tex`S`} using policy derived from ${tex`Q`}\n\t* repeat until ${tex`S`} is terminal:\n\t\t* ${tex`(S, A) \\Rightarrow R, S'`}\n\t\t* choose ${tex`A'`} from ${tex`S'`} using policy derived from ${tex`Q`}\n\t\t${tex.block`\n\t\t\t\\begin{aligned}\n\t\t\t\tQ(S, A) &\\leftarrow Q(S, A) + \\alpha [ R + \\gamma Q(S', A') - Q(S, A)]\t\\\\\n\t\t\t\tS &\\leftarrow S'\t\\\\\n\t\t\t\tA &\\leftarrow A'\n\t\t\t\\end{aligned}\n\t\t`}\n\nConverges to optimal action-value function ${tex`Q(s,a) \\rightarrow q_*(s,a)`} under:\n* GLIE sequence of policies ${tex`\\pi_t(a|s)`}\n* Robbins-Monro sequence of step sizes ${tex`\\alpha_t`}: \n${tex.block`\n \\begin{aligned}\n \\sum_{t=1}^{\\infty} {\\alpha}_t &= \\infty\t\\\\\n \\sum_{t=1}^{\\infty} {\\alpha}_t^2 &\\lt \\infty\t\n \\end{aligned}\n`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3359,"value":"md`We'll use the same schedule for α as for ε.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3355,"value":"alphaSchedule = glieEpsilon","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1404,"value":"sarsaUpdateQ = (episode, isDone, memory) => {\n const aStep = episode[episode.length-1];\n const alpha = alphaSchedule(); // 0.4; // 1/(aStep.episodeNumber+1);\n \n memory.Q[aStep.current.observation] = memory.Q[aStep.current.observation] || {};\n memory.Q[aStep.next.observation] = memory.Q[aStep.next.observation] || {};\n \n const Qsa = memory.Q[aStep.current.observation][aStep.current.action] || 0.00001 * Math.random();\n const Qsa_prime = aStep.done ? 0 : (memory.Q[aStep.next.observation][aStep.next.action] || 0.00001 * Math.random());\n \n const newQsa = Qsa + alpha * (aStep.reward + gamma * Qsa_prime - Qsa);\n \n memory.Q[aStep.current.observation][aStep.current.action] = newQsa;\n memory.episodeNumber = aStep.episodeNumber;\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":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":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":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":1776,"value":"sarsa = ({\n initialConditions: memoryInitialValues,\n policyFn: glieEpsilonGreedyPolicy,\n learnFn: sarsaUpdateQ,\n stepwise: true\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":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":3320,"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":3258,"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":3260,"value":"wallFn = ([x,y]) => {\n return (x === 3 && (y < gridDimensions.y - 2))\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"}} 47:"$46:body"