28:null 29:["$","title",null,{"children":"HINF 485 Demo: Reinforcement Learning | Adam Krawitz | Observable"}] 2f:T2db9,30:T3455,31:T6c41,32:T3b24,33:T798c,34:T1d56,### Visualizing #### World The elements of the visualization can be individually hidden or shown. While I've tried to design it so that the visualization is still understandable with all elements shown, it can be busy, so it might be easier to understand by only looking at a subset. | Show | | | | ---- | |**State**| Start state, end state, wall |

| | | Negative, zero, or positive reward |

| | **Agent** | Agent |

| | **Value** | Negative, zero, or positive expected value |

| | **Policy** | Negative, zero, or positive preference |

| | **History**| Visited states and successful and unsuccessful actions |

| | **<All>** | <State, agent, value, policy, and history> |

| **Note:** Moving the mouse over (or tapping on mobile) the contents of a cell will bring up a tooltip with details. This seems to work better when the simulation is stopped.35:T87a,## Postscript In the examples of reinforcement learning you worked with in this assignment: * The agent fully perceived each state * There were a finite set of discrete states * There were a finite set of discrete actions * The result of each action in each state was deterministic * The rewards (and punishments) never changed * There were no other agents in the world These are all simplifications that made the algorithm easier for us to work with and understand. However, none of these is generally true of the real world: * Agents usually have only partial knowledge about the current state of the world * The world can exist in an (effectively) infinite number of states * The agent can perform an (effectively) infinite number of different actions * The result of taking an action is unpredictable and unreliable * Rewards (and punishments) change or occur probabilistically * There are other agents in the world who are modifying it through their actions Fortunately, more flexible reinforcement learning methods have been developed to deal with these relaxed constraints. One of the key changes that can be made is to represent the value function and policy using neural networks instead of table lookups. This can have powerful benefits, because the neural networks allow the agent to generalize from states that it has experienced to states it has never encountered before. A notable early example of using a neural network with temporal difference learning is [Tesauro's (1995) TD-Gammon](https://doi.org/10.1145/203330.203343) that learned to play backgammon at the level of the top players in the world. An updated take on the actor-critic architecture for use with deep neural networks is called asynchronous advantage actor-critic (A3C) ([Mnih et al., 2016](https://doi.org/10.48550/arXiv.1602.01783)). A3C is currently considered one of the most powerful methods in AI. Reinforcement learning in general, temporal difference methods more specifically, and the actor-critic architecture in particular are foundational to major advances in the understanding of natural intelligence and the development of artifical intelligence in the last 25 years.36:T1047,actorCriticSim = function(sim, controls, {states, rewards, actions, parameters = {}, options = {}} = {}) { // Default values parameters = { alpha: 0.5, beta: 0.5, gamma: 0.8, epsilon: 0.2, ...parameters, }; options = { ...options, }; if (controls.reset || !sim) { // (Re)set the simulation sim = {...states, ...rewards, ...actions, ...parameters, ...options}; // States sim.states = math.zeros([sim.rows, sim.columns]); sim.beginStates.forEach((beginState) => { sim.states[beginState[0]][beginState[1]] = actorCriticEnum.STATES.BEGIN; }); sim.endStates.forEach((endState) => { sim.states[endState[0]][endState[1]] = actorCriticEnum.STATES.END; }); sim.wallStates.forEach((wallState) => { sim.states[wallState[0]][wallState[1]] = actorCriticEnum.STATES.WALL; }); // Rewards sim.rewards = math.zeros([sim.rows, sim.columns]); sim.stateRewards.forEach((stateReward) => { stateReward.states.forEach((state) => { sim.rewards[state[0]][state[1]] = stateReward.reward; }); }); // Actions sim.totalActions = sim.actions.length; // Task sim.episode = 0; sim.maxSteps = 400; sim.step = 0; // Agent sim.value = math.zeros([sim.rows, sim.columns]); sim.policy = math.zeros([sim.rows, sim.columns, sim.totalActions]); sim.state = sim.beginStates[math.randomInt(sim.beginStates.length)]; sim.action = null; sim.reward = null; sim.error = null; } else { // Check for end of episode if ((sim.step === sim.maxSteps) || (sim.states[sim.state[0]][sim.state[1]] === actorCriticEnum.STATES.END)) { // Begin the next episode sim.episode++; sim.step = 0; sim.action = null; sim.reward = null; sim.error = null; // Jump to a randomly selected begin state sim.state = sim.beginStates[math.randomInt(sim.beginStates.length)]; } else { // Take the next step sim.step++; // Calculate probabilities based on policy const probabilities = math.divide( // math.exp(sim.policy[sim.state[0]][sim.state[1]]), math.map(sim.policy[sim.state[0]][sim.state[1]], math.exp), // math.sum(math.exp(sim.policy[sim.state[0]][sim.state[1]])), math.sum(math.map(sim.policy[sim.state[0]][sim.state[1]], math.exp)), ); // Select action if (Math.random() > sim.epsilon) { // Follow policy sim.action = math.pickRandom(math.range(0, sim.totalActions), probabilities); } else { // Select randomly sim.action = math.pickRandom(math.range(0, sim.totalActions)); } // Find next state and get reward sim.reward = sim.moveReward; let nextState = [ sim.state[0] + sim.actions[sim.action][0], sim.state[1] + sim.actions[sim.action][1], ]; if ((nextState[0] < 0) || (nextState[0] >= sim.rows) || (nextState[1] < 0) || (nextState[1] >= sim.columns)) { // Off edge of grid nextState = sim.state; sim.reward += sim.edgeReward; } else if (sim.states[nextState[0]][nextState[1]] === actorCriticEnum.STATES.WALL) { // Hit wall nextState = sim.state; sim.reward += sim.wallReward; } // Get state reward sim.reward += sim.rewards[nextState[0]][nextState[1]]; // Calculate TD error sim.error = sim.reward + sim.gamma * sim.value[nextState[0]][nextState[1]] - sim.value[sim.state[0]][sim.state[1]]; // Update value sim.value[sim.state[0]][sim.state[1]] = sim.value[sim.state[0]][sim.state[1]] + sim.alpha * sim.error; // Update policy sim.policy[sim.state[0]][sim.state[1]][sim.action] = sim.policy[sim.state[0]][sim.state[1]][sim.action] + sim.beta * sim.error * (1 - probabilities[sim.action]); // Update state sim.state = nextState; // Check for stopping at end of episode if (controls.skip && ((sim.step === sim.maxSteps) || (sim.states[sim.state[0]][sim.state[1]] === actorCriticEnum.STATES.END))) { controls.stopSkip(); } } } return sim; }37:T2e9f,// Next: key, step by step or episode, map "language"? actorCriticViz = function(viz, sim, history, controls, {cellSize = 50, showState = true, showAgent = true, showPolicy = true, showValue = false, showHistory = true} = {}) { const borderColor = colors.gray.brighter(0.25); const innerBorderColor = colors.gray.brighter(0.5); const beginColor = colors.green; const endColor = colors.red; const wallColor = colors.brown; const agentColor = colors.gray.darker(2.5); const stepColor = colors.pink; const rewardScale = d3.scaleDivergingSqrt( [-100, 0, 100], d3.piecewise(d3.interpolateHcl, [colors.orange, colors.white, colors.blue]), ); const valueScale = d3.scaleDivergingSqrt( [-100, 0, 100], d3.piecewise(d3.interpolateHcl, [colors.orange, colors.white, colors.blue]), ); const policyScale = d3.scaleDivergingSqrt( [-100, 0, 100], d3.piecewise(d3.interpolateHcl, [colors.orange, colors.white, colors.blue]), ); const stateSize = 100; const rewardSize = 84; const agentSize = 70; const valueSize = 42; const policySize = 60; const stepSize = 8; return svg` `; }38:T613,actorCriticHistViz = async function(viz, sim, history, controls, {showSteps = true, showErrors = true, showRewards = true} = {}) { const basePlot = vl.markLine({point: true}) .encode( vl.x().fieldQ('episode').title('Episode').scale({nice: false}).axis({tickMinStep: 1}), ) .width(width) .height(120); const plots = [ ...(showSteps ? [ basePlot .title('Step History') .encode( vl.y().fieldQ('steps').title('Steps Taken'), vl.tooltip([ {field: 'episode', title: 'Episode'}, {field: 'steps', title: 'Steps Taken'}, ]), )] : []), ...(showErrors ? [ basePlot .title('Error History') .encode( vl.y().fieldQ('errors').title('Total TD Error'), vl.tooltip([ {field: 'episode', title: 'Episode'}, {field: 'errors', title: 'Total TD Error', format: '.2f'}, ]), )] : []), ...(showRewards ? [ basePlot .title('Reward History') .encode( vl.y().fieldQ('rewards').title('Total Reward'), vl.tooltip([ {field: 'episode', title: 'Episode'}, {field: 'rewards', title: 'Total Reward'}, ]), )] : []), ]; return html` ${ await vl.vconcat(...plots) .data(history.episodes) .autosize({type: 'fit-x', contains: 'padding'}) .render({renderer: 'svg'}) } ` }39:[{"id":"277ba8ce681204e0ab036969c960dd4508e248d9699c44c63667d5a199a20ddc89b539aa17efabd2af0ee5c109f13d0c4b5a25641df41a74e41cf8472c9df28c","href":"https://static.observableusercontent.com/files/277ba8ce681204e0ab036969c960dd4508e248d9699c44c63667d5a199a20ddc89b539aa17efabd2af0ee5c109f13d0c4b5a25641df41a74e41cf8472c9df28c","name":"actor-critic.png","type":"image/png","lastModified":1683330267271.037,"size":13249},{"id":"8e68a13354af7ed9caf7bc44ebc96e6a783282feff7282bee65cbed2dfb44ee6799f480d8f230452132fdba7cfd4685bb2234e0f4d024fb4980f2dcab5c74a45","href":"https://static.observableusercontent.com/files/8e68a13354af7ed9caf7bc44ebc96e6a783282feff7282bee65cbed2dfb44ee6799f480d8f230452132fdba7cfd4685bb2234e0f4d024fb4980f2dcab5c74a45","name":"sarsa.png","type":"image/png","lastModified":1683330267271.037,"size":4543}] 2c:{"id":"94def32bc2112e2c","slug":null,"title":"HINF 485 Demo: Reinforcement Learning","thumbnail":"699b0e24362dea596b37938d643b9ae53b2dbc49042c8803f2f209a563eda5c7","access_level":"public","create_time":"$D2023-05-05T23:44:27.271Z","update_time":"$D2023-05-08T16:15:32.189Z","view_time":null,"first_public_time":"$D2023-05-10T18:32:42.994Z","fork":true,"stars":0,"starred":false,"owner":{"type":"team","id":"3861495db0d6917b","login":"akrawitz","name":"Adam Krawitz","avatar_url":"https://avatars-next.observableusercontent.com/232e39a655b3dffeaad79a6e590471290f026876224f3f7c9825f12c3f0147bc","tier":"starter_2024"},"version":3089,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"f056c267619fba67","login":"akrawitz","name":"Adam Krawitz","avatar_url":"https://avatars-next.observableusercontent.com/8b0aba291db32e92917b2b37e94c3c5568c23f50e1e769e8f76508b16293220c","tier":null}],"members":[{"type":"individual","id":"f056c267619fba67","login":"akrawitz","name":"Adam Krawitz","avatar_url":"https://avatars-next.observableusercontent.com/8b0aba291db32e92917b2b37e94c3c5568c23f50e1e769e8f76508b16293220c","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"subscribed":null,"forks":0,"collection":{"id":"8ee1672695697eae","slug":"uvic-hinf-485","title":"UVic HINF 485 Demonstrations","owner":{"id":"3861495db0d6917b","login":"akrawitz","name":"Adam Krawitz"}},"type":"notebook","body":{"title":"HINF 485 Demo: Reinforcement Learning","cells":[{"id":0,"value":"# HINF 485 Demo: Reinforcement Learning","pinned":false,"hidden":false,"mode":"md"},{"id":1677,"value":"assignmentToc({headers: 'h2,h3,h4'})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1680,"value":"## Introduction\nIn this demonstration we will explore temporal-difference learning in an actor-critic architecture. This is one of a [large number of different reinforcement learning algorithms](http://incompleteideas.net/book/RLbook2020.pdf#page=7). It is of particular relevance to us because of work suggesting the actor-critic architecture and the method of temporal differences as a plausible neural implementation of reinforcement learning in the basal ganglia (e.g. Houk, Adams, Barto, 1995). In the form presented here, it also lends itself to relatively straightforward visualization. ","pinned":false,"hidden":false,"mode":"md"},{"id":2534,"value":"

\n ${await FileAttachment(\"actor-critic.png\").image()}\n

The actor-critic architecture.\n
Figure 6.15 from Section 6.6, Sutton & Barto (1998).

\n","pinned":false,"hidden":false,"mode":"html"},{"id":1693,"value":"### World\nThe environments in which our agent will operate are versions of a \"Grid World\". The world consists of a set of **cells** arranged in a rectangular grid with a certain number of rows and columns (3 rows by 6 columns in the example below). At each time step, the agent occupies a single cell. The agent begins each new episode in a ** start state ** (indicated by a green outline, as in the lower left cell in the example below). The episode is over when the agent reaches an ** end state ** (indicated by a red outline, as in the lower right cell in the example below). If a cell contains a ** wall ** (indicated by a brown background, as for the bottom two cells in the third column in the example below), then it cannot be entered by the agent.","pinned":false,"hidden":false,"mode":"md"},{"id":1718,"value":"$2f","pinned":false,"hidden":false,"mode":"html"},{"id":1982,"value":"#### Actions\nThe agent moves from cell to cell by taking an **action** on each time step, which can, potentially, move it up, down, left, or right (depending on which actions are allowed in a given world, and whether there is an adjacent non-wall cell in the chosen direction).","pinned":false,"hidden":false,"mode":"md"},{"id":1737,"value":"#### Reward\nEach cell has a scalar reward value, which can be ** negative ** indicating a punishment, ** zero **, or ** positive ** (represented by the background color of the cell, from orange for a large negative reward, to white for no reward, to blue for a large positive reward - as in the lower right cell in the example above).\n\nIn addition, the agent can receive a reward or punishment for (1) each action it takes, (2) trying to move off of the edge of the grid, and/or (3) trying to move into a cell containing a wall. The values for these actions can be specified for each world.","pinned":false,"hidden":false,"mode":"md"},{"id":2549,"value":"### Agent\nThe ** agent ** (represented by the black \"star\" shape in the upper left cell in the example above) is in a particular cell, i.e. state, at each time step. The agent's **goal is to maximize reward**. \n\nWhen the agent moves into a cell, it receives the reward value of that cell. And, as described above, the agent can also be rewarded or punished (1) for each action, (2) for attempting to move off the grid, and/or (3) for attempting to move into a wall.","pinned":false,"hidden":false,"mode":"md"},{"id":2523,"value":"

\n ${await FileAttachment(\"sarsa.png\").image()}\n

The sequence of states, actions, and rewards.\n
From Section 6.4, Sutton & Barto (1998).

\n","pinned":false,"hidden":false,"mode":"html"},{"id":2551,"value":"The ** history ** of where the agent has gone during the current episode consists of a sequence of states connected by actions (viewed as a sequence of small pink circles indicating occupied states connected by pink line segments indicating actions, with attempted movements off the edge or into walls indicated by t-bars at the end of line segments as in the attempted movement up from the currently occupied cell in the example below).","pinned":false,"hidden":false,"mode":"md"},{"id":2157,"value":"$30","pinned":false,"hidden":false,"mode":"html"},{"id":1701,"value":"#### Actor: Policy\nThe agent consists of an actor and a critic. The **actor** has a **policy**, *π*, to choose an action, *a*, in a state, *s*, at each time step, *t*. The policy specifies the probability of selecting each possible action in each possible state. The probability is calculated from a **preference**, *p*, for each combination of state and action, using Luce’s choice axiom, also known as softmax:","pinned":false,"hidden":false,"mode":"md"},{"id":1826,"value":"\\pi_t(s, a) = \\Pr\\{a_t \\!=\\! a \\mid s_t \\!=\\! s\\} = \\frac{e^{p(s, a)}}{\\sum_b{e^{p(s, b)}}}","pinned":false,"hidden":false,"mode":"tex"},{"id":2120,"value":"The actor maintains a preference for each action in each state. The preference can be ** negative **, ** zero **, or ** positive ** (as indicated by the four small diamonds in each cell representing the four possible actions from each state in the example below).","pinned":false,"hidden":false,"mode":"md"},{"id":2116,"value":"$31","pinned":false,"hidden":false,"mode":"html"},{"id":1705,"value":"#### Critic: Value Function\nThe **critic** has a **value function**, *V*, that represents the agent's current beliefs about the expected value of each state. This expected value represents not only the immediate reward to be received in that state, but also the future rewards to be received in each subsequent state, discounted for the passage of time at a **discount rate**, *γ*: ","pinned":false,"hidden":false,"mode":"md"},{"id":1946,"value":"\\begin{aligned}\nV(s_t) &= \\sum^\\infty_{k=0}{\\gamma^k r_{t+1+k}} \\\\\n &= r_{t+1} + \\gamma r_{t+2} + \\gamma^2 r_{t+3} + ... \n\\end{aligned}","pinned":false,"hidden":false,"mode":"tex"},{"id":1954,"value":"By the same token, the value for the *next* state would be:","pinned":false,"hidden":false,"mode":"md"},{"id":1958,"value":"V(s_{t+1}) = r_{t+2} + \\gamma r_{t+3} + \\gamma^2 r_{t+4} + ... ","pinned":false,"hidden":false,"mode":"tex"},{"id":1965,"value":"Putting these equations together, we can observe that:","pinned":false,"hidden":false,"mode":"md"},{"id":1890,"value":"\\begin{aligned}\nV(s_t) &= r_{t+1} + \\gamma r_{t+2} + \\gamma^2 r_{t+3} + ... \\\\\n &= r_{t+1} + \\gamma (r_{t+2} + \\gamma r_{t+3} + ...) \\\\\n &= r_{t+1} + \\gamma V(s_{t+1})\n\\end{aligned}","pinned":false,"hidden":false,"mode":"tex"},{"id":1942,"value":"Thus, the expected value of a state can be expressed recursively in terms of the reward in that state plus the discounted expected value of the next state!\n\nThe critic maintains a value for each state. The value can be ** negative **, ** zero **, or ** positive ** (as indicated by the single large diamond in each cell representing the value for each state in the example below).","pinned":false,"hidden":false,"mode":"md"},{"id":2130,"value":"$32","pinned":false,"hidden":false,"mode":"html"},{"id":1933,"value":"#### Action Selection & Temporal Difference Error\n\nOn each time step, with probability *ε*, the **exploration factor**, the actor **explores** randomly, or with probability 1 − *ε*, it **exploits** it's policy.\n\nThe critic then evaluates the result of the chosen action by calculating a **temporal difference (TD) error**, also known as a **reward prediction error (RPE)**, *δ*, based on the recursive expression of value shown above:","pinned":false,"hidden":false,"mode":"md"},{"id":2016,"value":"\\delta_t = r_{t+1} + \\gamma V(s_{t+1}) - V(s_t)","pinned":false,"hidden":false,"mode":"tex"},{"id":2031,"value":"#### Updating\nThe TD error is then used to update both the actor's policy function and the critic's value function.\n\nThe value function is updated, per a **value learning rate**, *α*, so that the critic has a more accurate representation of value, using the *TD(0)* method:","pinned":false,"hidden":false,"mode":"md"},{"id":2048,"value":"V(s_t) \\leftarrow V(s_t) + \\alpha \\delta_t","pinned":false,"hidden":false,"mode":"tex"},{"id":2067,"value":"The policy function is updated, per a **policy learning rate**, *β*, so that the actor is more likely to choose the value maximizing action in the future:","pinned":false,"hidden":false,"mode":"md"},{"id":2069,"value":"p(s_t, a_t) \\leftarrow p(s_t, a_t) + \\beta \\delta_t","pinned":false,"hidden":false,"mode":"tex"},{"id":2149,"value":"We can simultaneously view the preferences for the policy function and the values for the value function, with the value for each state shown in the central square, and the preferences for each action arrayed in the triangles around it, as in this example:","pinned":false,"hidden":false,"mode":"md"},{"id":2145,"value":"$33","pinned":false,"hidden":false,"mode":"html"},{"id":2624,"value":"### Parameters\nTo summarize, the model has four parameters that can be set:\n\n| Parameter | Letter | Description | Range |\n| :-: | :-: | - | - |\n| **_α_** | alpha | Learning rate for updating the value function, ${tex`V(s_t)`} | 0 (no learning) to 1 (full learning) |\n| **_β_** | beta | Learning rate for updating the policy function, ${tex`p(s_t, a_t)`} | 0 (no learning) to 1 (full learning) |\n| **_γ_** | gamma | Temporal discounting factor for the value function, ${tex`V(s_t)`} | 0 (complete discounting) to 1 (no discounting)\n| **_ε_** | epsilon | Exploration factor for choosing a random action versus following the policy function, ${tex`p(s_t, a_t)`} | 0 (never exploring/always exploiting) to 1 (always exploring/never exploiting)","pinned":false,"hidden":false,"mode":"md"},{"id":2190,"value":"## Simulations\n### Running\nWe use the standard controls, with one addition, to run our Actor-Critic models:\n- To erase all learning and return to the initial policy and value functions with zero preferences and values, and return the agent to a start state, click **Reset**.\n- To advance the simulation one time step, click **Step**.\n- To run the simulation until the end of an _episode_, click **Skip**.\n- To run unlimited time steps in succession, click **Start**.\n- To stop the simulation click **Stop**. This works after **Start** or **Skip** if you want to stop before the end of the episode.\n- To run the simulation faster or slower, drag the **Speed** slider (leftward = slower, rightward = faster).\n\nIf the previous time step brought the agent to an end state, then the episode is over, and the next step will start a new episode and return the agent to a start state.","pinned":false,"hidden":false,"mode":"md"},{"id":2197,"value":"$34","pinned":false,"hidden":false,"mode":"md"},{"id":2602,"value":"#### History Plots\nThe **Step History** plots the number of steps taken to reach the end state in each episode. The **Error History** plots the total temporal difference error (TD error) experienced over the course of the episode. And the **Reward History** plots the total reward/punishment earned over the course of each episode.","pinned":false,"hidden":false,"mode":"md"},{"id":1484,"value":"## Model 1. LineWorld\nTo start things off, we are going to work with a one dimension world, where the only actions are to move left or right. Not very exciting, but it can make it easier to understand some of the basic concepts. Our world is a row of ten states. Our agent will always start on the far left, and the only available reward, worth +100, is the end state on the far right. There are no rewards or punishments for making moves or running into the left edge of the world. So the _only_ reward available is for making it to the end state at the far right.","pinned":false,"hidden":false,"mode":"md"},{"id":1485,"value":"viewof conLine = controls({skip: true})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1486,"value":"viewof vizConLine = actorCriticVizControls()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1490,"value":"simLine = actorCriticSim(this, conLine, {states: lineStates, rewards: lineRewards, actions: lineActions, parameters: {alpha: 0.5, beta: 0.5, gamma: 0.8, epsilon: 0.2}})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1489,"value":"historyLine = actorCriticHist(this, simLine, conLine)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1487,"value":"actorCriticViz(this, simLine, historyLine, conLine, vizConLine)","pinned":false,"hidden":false,"mode":"ojs"},{"id":2573,"value":"actorCriticHistViz(this, simLine, historyLine, conLine, {showRewards: false})","pinned":false,"hidden":false,"mode":"ojs"},{"id":2611,"value":"The parameter settings for our model are:\n* **α** = 0.5\n* **β** = 0.5\n* **γ** = 0.8\n* **ε** = 0.2\n\nLet's hide (uncheck) the Policy function, so that we can focus on the Value function. Note that initially, the value of every state is zero, because the agent knows nothing about its world. Now run the simulation for one full episode by clicking the **Skip** button.","pinned":false,"hidden":false,"mode":"md"},{"id":2668,"value":"Now run 8 more episodes (for a total of 9 episodes). Watch how long it takes the agent to reach the end state on each episode. I don't know about you, but there is something almost magical about the way it goes from taking hundreds of steps to zipping across the world with hardly a misstep. Except of course, there is no magic at all, just reinforcement learning at work, so let's dig into it a bit more.\n\nAs the agent learned across the 9 episodes, the increase in the value function started at the far right, at the last states the agent entered, and slowly extended leftward until it finally reached the start state. (Move the cursor over the start state, and you will see from the tooltip that it has a small positive value now!) This is the phenomenon of expected value (and thus reward prediction error) propagating \"backward\" in time from the time of the reward to an earlier point in time in the trial, as seen in the classic paper by Schultz, Dayan, and Montague (1997)!","pinned":false,"hidden":false,"mode":"md"},{"id":2693,"value":"Let's now shift our attention from the value function to the policy function. So, hide (uncheck) the **Value**, and show (check) the **Policy**. For each state, there is a policy associated with each action. You can move the cursor over each one to see the details in a tooltip. Note that the policy for moving right in each state is positive. Interestingly, the policy for moving left from most, if not all, states is negative. ","pinned":false,"hidden":false,"mode":"md"},{"id":2710,"value":"Run some more episodes. Sometimes, the agent is \"perfect\", in that it only moves to the right and arrives at the end state in the optimal number of steps, 10. But, despite all of the training it has, it still takes extra steps on a regular basis. ","pinned":false,"hidden":false,"mode":"md"},{"id":1479,"value":"## Model 2. GridWorld\nNow that we've gotten a feel for things, and thought about how the TD-error RL algorithm works, lets break the dimensional bonds holding our agent back, and move to a two-dimensional grid world!\n\nIn the world below, the start state is in the upper left and the end state, with a reward of +100, is in the upper right. In addition, there is a punishment of -100 towards the bottom right, and a wall blocking the direct path from start state to end state. To make our world more realistic, I've also added punishments of -1 for each action (moving takes energy!) and -5 for hitting a wall or an edge (running into solid objects hurts!).\n","pinned":false,"hidden":false,"mode":"md"},{"id":18,"value":"viewof conGrid = controls({skip: true})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1297,"value":"viewof vizConGrid = actorCriticVizControls()","pinned":false,"hidden":false,"mode":"ojs"},{"id":1156,"value":"simGrid = actorCriticSim(this, conGrid, {states: gridStates, rewards: gridRewards, actions: gridActions, parameters: {alpha: 0.5, beta: 0.5, gamma: 0.8, epsilon: 0.2}})","pinned":true,"hidden":false,"mode":"ojs"},{"id":314,"value":"historyGrid = actorCriticHist(this, simGrid, conGrid)","pinned":false,"hidden":false,"mode":"ojs"},{"id":370,"value":"actorCriticViz(this, simGrid, historyGrid, conGrid, vizConGrid)","pinned":false,"hidden":false,"mode":"ojs"},{"id":824,"value":"actorCriticHistViz(this, simGrid, historyGrid, conGrid)","pinned":false,"hidden":false,"mode":"ojs"},{"id":2748,"value":"Again, the parameter settings for our model are:\n* **α** = 0.5\n* **β** = 0.5\n* **γ** = 0.8\n* **ε** = 0.2\n\nAnd, as we did with LineWorld, let's hide (uncheck) the **Policy** function, so that we can focus on the Value function. Run the simulation for one full episode by clicking the **Skip** button.","pinned":false,"hidden":false,"mode":"md"},{"id":2768,"value":"Now let the simulation run for another 25 or so episodes, so that is has gotten to the point where it is reaching the end state in around 15 steps on a fairly consistent basis.","pinned":false,"hidden":false,"mode":"md"},{"id":2786,"value":"Now, go ahead and show (check) the **Policy**, but this time, leave the **Value** displayed as well.","pinned":false,"hidden":false,"mode":"md"},{"id":3027,"value":"$35","pinned":false,"hidden":false,"mode":"md"},{"id":1147,"value":"md`## Definitions`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1345,"value":"tooltips = tippify({allowHTML: true})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1223,"value":"### Simulation","pinned":false,"hidden":false,"mode":"md"},{"id":1508,"value":"actorCriticEnum = Object.freeze({\n STATES: Object.freeze({\n EMPTY: 0,\n BEGIN: -Infinity,\n END: Infinity,\n WALL: 1,\n }),\n ACTIONS: Object.freeze({\n LEFT: [0, -1],\n UP: [-1, 0],\n RIGHT: [0, 1], \n DOWN: [1, 0],\n }),\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":6,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":272,"value":"actorCriticHist = function(history, sim, controls) {\n // (Re)set the history\n if (controls.reset || !history) {\n history = {episodes: [], steps: []};\n }\n\n // New episode\n if (sim.step === 0) {\n history.steps = [];\n }\n \n // Step\n history.steps.push({\n step: sim.step,\n state: sim.state,\n action: sim.action,\n error: sim.error,\n reward: sim.reward,\n });\n \n // End of episode \n if ((sim.step === sim.maxSteps) || (sim.states[sim.state[0]][sim.state[1]] === actorCriticEnum.STATES.END)) {\n// (sim.states[sim.state[0]][sim.state[1]] === actorCriticEnum.STATES.END) {\n history.episodes.push({\n episode: sim.episode,\n steps: sim.step + 1,\n errors: math.sum(history.steps.map((step) => { return step.error ?? 0; })),\n rewards: math.sum(history.steps.map((step) => { return step.reward ?? 0; })),\n });\n }\n \n return history;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1227,"value":"### Visualization","pinned":false,"hidden":false,"mode":"md"},{"id":1307,"value":"actorCriticVizControls = function() {\n const checkbox = Inputs.checkbox(['State', 'Agent', 'Value', 'Policy', 'History'],{label: 'Show', value: ['State', 'Agent', 'Value', 'Policy', 'History']});\n return Object.defineProperty(html`

${checkbox}

`, \"value\", {\n get() {\n return {\n showState: checkbox.value.includes('State'),\n showAgent: checkbox.value.includes('Agent'),\n showValue: checkbox.value.includes('Value'),\n showPolicy: checkbox.value.includes('Policy'),\n showHistory: checkbox.value.includes('History'),\n };\n },\n set({showState: state, showAgent: agent, showValue: value, showPolicy: policy, showHistory: history}) {\n\n }\n });\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":237,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"},{"id":806,"value":"$38","pinned":false,"hidden":false,"mode":"ojs"},{"id":957,"value":"","pinned":false,"hidden":false,"mode":"html"},{"id":1231,"value":"### Data","pinned":false,"hidden":false,"mode":"md"},{"id":1465,"value":"lineStates = ({\n rows: 1,\n columns: 10,\n beginStates: [[0, 0]],\n endStates: [[0, 9]],\n wallStates: [],\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":2088,"value":"lineRewards = ({\n moveReward: 0,\n edgeReward: 0,\n wallReward: 0,\n stateRewards: [{reward: 100, states: lineStates.endStates}],\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":2089,"value":"lineActions = ({\n actions: [\n actorCriticEnum.ACTIONS.LEFT,\n actorCriticEnum.ACTIONS.RIGHT,\n ],\n});","pinned":true,"hidden":false,"mode":"ojs"},{"id":1408,"value":"gridStates = ({\n rows: 5,\n columns: 6,\n beginStates: [[0, 0]],\n endStates: [[0, 5]],\n wallStates: [[0, 2], [1, 2], [2, 2]],\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1442,"value":"gridRewards = ({\n moveReward: -1,\n edgeReward: -5,\n wallReward: -5,\n stateRewards: [{reward: 100, states: gridStates.endStates}, {reward: -100, states: [[3, 5]]}],\n})","pinned":true,"hidden":false,"mode":"ojs"},{"id":1451,"value":"gridActions = ({\n actions: [\n actorCriticEnum.ACTIONS.LEFT,\n actorCriticEnum.ACTIONS.UP,\n actorCriticEnum.ACTIONS.RIGHT,\n actorCriticEnum.ACTIONS.DOWN,\n ],\n});","pinned":true,"hidden":false,"mode":"ojs"},{"id":8,"value":"md`## Resources`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1660,"value":"Load assignment styles.","pinned":false,"hidden":false,"mode":"md"},{"id":1664,"value":"import {assignmentStyles} from '@akrawitz/assignment-styles'","pinned":false,"hidden":false,"mode":"ojs"},{"id":1667,"value":"assignmentStyles","pinned":false,"hidden":false,"mode":"ojs"},{"id":1670,"value":"Load assignment table of contents.","pinned":false,"hidden":false,"mode":"md"},{"id":1674,"value":"import {assignmentToc} from '@akrawitz/assignment-toc'","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"md`Load simulation controls.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"import {controls} from \"@akrawitz/simulation-controls\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":330,"value":"md`Load pleasant colors.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":333,"value":"import {colors} from \"@akrawitz/pleasant-colors\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1339,"value":"Load tooltips.","pinned":false,"hidden":false,"mode":"md"},{"id":1342,"value":"import {tippify} from \"@akrawitz/tippify\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":86,"value":"md`Load [math.js](https://mathjs.org/), \"an extensive math library for JavaScript and Node.js\".`","pinned":false,"hidden":false,"mode":"ojs"},{"id":92,"value":"math = require(\"mathjs\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":452,"value":"md`Load [d3-scale](https://github.com/d3/d3-scale), \"scales are a convenient abstraction for a fundamental task in visualization: mapping a dimension of abstract data to a visual representation\" and [d3-interpolate](https://github.com/d3/d3-interpolate), \"this module provides a variety of interpolation methods for blending between two values.\"`","pinned":false,"hidden":false,"mode":"ojs"},{"id":451,"value":"d3 = require('d3-scale', 'd3-interpolate')","pinned":false,"hidden":false,"mode":"ojs"},{"id":811,"value":"md`The [Vega-Lite JavaScript API](https://github.com/vega/vega-lite-api/) provides a convenient way to write [Vega-Lite](https://vega.github.io/vega-lite) specifications in a programmatic fashion.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":808,"value":"import {vl} from '@vega/vega-lite-api'","pinned":false,"hidden":false,"mode":"ojs"},{"id":1174,"value":"md`## References\n* [Sutton and Barto (1998)](http://incompleteideas.net/book/first/the-book.html)\n * [6.1 TD Prediction](http://incompleteideas.net/book/first/ebook/node61.html)\n * [6.6 Actor-Critic Methods](http://incompleteideas.net/book/first/ebook/node66.html)\n* [Temporal-Difference Learning: SARSA(0)](/@j-kan/temporal-difference-learning-sarsa-0)\n`","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W39","stdlib":"1","titling":"auto"}} 2d:"$2c:body"