31:T4e4,{ const svg = d3.select(DOM.svg(renderSize.width, renderSize.height)); const env = build_environment() const step_time = 10 renderer.maze(svg) const player = renderer.init_player(svg, env.state) const reward_display = renderer.init_reward(svg) const reward_avg_display = renderer.init_avg(svg) const reward_list = [] const reward_window = 100 while(true){ let done = false let total_reward = 0 for(let step = 0; step < 2000 && !done; ++step) { yield new Promise(resolve => { setTimeout(() => { const result = env.take_action(Math.floor(Math.random()*5)) done = result.done total_reward += result.reward renderer.move_player(player, env.state, step_time) renderer.update_reward(reward_display, total_reward) resolve(svg.node()) }, step_time) }) } env.reset() renderer.move_player(player, env.state, step_time) reward_list.push(total_reward) const reward_window_list = reward_list.slice(-reward_window, reward_list.length) const reward_avg = reward_window_list.reduce((a,b) => a + b)/ reward_window_list.length renderer.update_avg(reward_avg_display, reward_avg.toFixed(2)) } return svg.node() }32:T44b,{ const q_table = q_table_builder(() => 0.5 - Math.random()) return md`## Creating the table Next we need to create the Q-Table. Since we need to create a row for each possible state and a column for each possible action, our state table will be ${(states.max_x - states.min_x)} x ${(states.max_y - states.min_y)} x 4 or ${(states.max_x - states.min_x) * (states.max_y - states.min_y) * 4} total cells. Abbreviated ${tex `Q`}: | x | y | NORTH | EAST | SOUTH | WEST | |---|---|------:|-----:|------:|-----:| ${q_table_to_md_table(q_table)} ... and so on. So, for instance, the expected rewards for moving NORTH from position (2, 1) would be ${q_table[1][2][0].toFixed(2)} while moving EAST from that position would be ${q_table[1][2][1].toFixed(2)}. All values begin at zero or may be initialized randomly. For demonstration purposes, this is a very opaque view of the table, but we can show it a different way. By overlaying indicators onto the maze, we will be able to see how the table is building out. Opacity is used to indicate estimated value of taking that action at that state. `}33:T867,{ const svg = d3.select(DOM.svg(renderSize.width, renderSize.height)); const learning_rate = learning_settings.alpha const discount = learning_settings.gamma const step_time = 10 const env = build_environment() renderer.maze(svg) const q_table = q_table_builder(() => 0) const q_table_display = renderer.init_q(svg, q_table) const player = renderer.init_player(svg, env.state) const reward_display = renderer.init_reward(svg) const reward_avg_display = renderer.init_avg(svg) const reward_list = [] const reward_window = 100 const get_max = (state) => { return q_table[state.y][state.x].reduce((acc, val, action) => { if(acc == null || acc.value < val) return {action: action, value: val} return acc }, null) } while(true){ let done = false let episode_reward = 0 for(let step = 0; step < 2000 && !done; ++step) { yield new Promise(resolve => { setTimeout(() => { const state = {x: env.state.x, y: env.state.y} const state_max = get_max(env.state) const action = state_max.action const result = env.take_action(action) const new_state_max = get_max(result.state) const update = (1 - learning_rate)*state_max.value + learning_rate * (result.reward + discount * new_state_max.value) q_table[state.y][state.x][action] = update done = result.done episode_reward += result.reward renderer.move_player(player, env.state, step_time) renderer.update_reward(reward_display, episode_reward) renderer.update_indicator(q_table_display[state.y][state.x], q_table[state.y][state.x]) resolve(svg.node()) }, step_time) }) } env.reset() renderer.move_player(player, env.state, step_time) reward_list.push(episode_reward) const reward_window_list = reward_list.slice(-reward_window, reward_list.length) const reward_avg = reward_window_list.reduce((a,b) => a + b)/ reward_window_list.length renderer.update_avg(reward_avg_display, reward_avg.toFixed(2)) } return svg.node() }34:T967,{ const svg = d3.select(DOM.svg(renderSize.width, renderSize.height)); const learning_rate = learning_settings.alpha const discount = learning_settings.gamma const epsilon = epsilon_settings.epsilon const step_time = 10 const env = build_environment() renderer.maze(svg) const q_table = q_table_builder(() => 0) const q_table_display = renderer.init_q(svg, q_table) const player = renderer.init_player(svg, env.state) const reward_display = renderer.init_reward(svg) const reward_avg_display = renderer.init_avg(svg) const reward_list = [] const reward_window = 100 const get_max = (state) => { return q_table[state.y][state.x].reduce((acc, val, action) => { if(acc == null || acc.value < val) return {action: action, value: val} return acc }, null) } while(true){ let done = false let episode_reward = 0 for(let step = 0; step < 2000 && !done; ++step) { yield new Promise(resolve => { setTimeout(() => { const state = {x: env.state.x, y: env.state.y} let state_max = get_max(env.state) if(Math.random() < epsilon) { const rand_action = Math.floor(Math.random()*5) state_max = {action: rand_action, value: q_table[state.y][state.x][rand_action]} } const action = state_max.action const result = env.take_action(action) const new_state_max = get_max(result.state) const update = (1 - learning_rate)*state_max.value + learning_rate * (result.reward + discount * new_state_max.value) q_table[state.y][state.x][action] = update done = result.done episode_reward += result.reward renderer.move_player(player, env.state, step_time) renderer.update_reward(reward_display, episode_reward) renderer.update_indicator(q_table_display[state.y][state.x], q_table[state.y][state.x]) resolve(svg.node()) }, step_time) }) } env.reset() renderer.move_player(player, env.state, step_time) reward_list.push(episode_reward) const reward_window_list = reward_list.slice(-reward_window, reward_list.length) const reward_avg = reward_window_list.reduce((a,b) => a + b)/ reward_window_list.length renderer.update_avg(reward_avg_display, reward_avg.toFixed(2)) } return svg.node() }35:Ta56,{ const svg = d3.select(DOM.svg(renderSize.width, renderSize.height)); const learning_rate = learning_settings.alpha const discount = learning_settings.gamma const epsilon = drunken_settings.use_eps ? epsilon_settings.epsilon : 0 const drunkenness = drunken_settings.mu const step_time = 10 const env = build_environment() renderer.maze(svg) const q_table = q_table_builder(() => 0) const q_table_display = renderer.init_q(svg, q_table) const player = renderer.init_player(svg, env.state) const reward_display = renderer.init_reward(svg) const reward_avg_display = renderer.init_avg(svg) const reward_list = [] const reward_window = 100 const get_max = (state) => { return q_table[state.y][state.x].reduce((acc, val, action) => { if(acc == null || acc.value < val) return {action: action, value: val} return acc }, null) } while(true){ let done = false let episode_reward = 0 for(let step = 0; step < 2000 && !done; ++step) { yield new Promise(resolve => { setTimeout(() => { const state = {x: env.state.x, y: env.state.y} let state_max = get_max(env.state) if(Math.random() < epsilon) { const rand_action = Math.floor(Math.random()*5) state_max = {action: rand_action, value: q_table[state.y][state.x][rand_action]} } const action = state_max.action let taken_action = action if(Math.random() < drunkenness) { taken_action = Math.floor(Math.random()*5) } const result = env.take_action(taken_action) const new_state_max = get_max(result.state) const update = (1 - learning_rate)*state_max.value + learning_rate * (result.reward + discount * new_state_max.value) q_table[state.y][state.x][action] = update done = result.done episode_reward += result.reward renderer.move_player(player, env.state, step_time) renderer.update_reward(reward_display, episode_reward) renderer.update_indicator(q_table_display[state.y][state.x], q_table[state.y][state.x]) resolve(svg.node()) }, step_time) }) } env.reset() renderer.move_player(player, env.state, step_time) reward_list.push(episode_reward) const reward_window_list = reward_list.slice(-reward_window, reward_list.length) const reward_avg = reward_window_list.reduce((a,b) => a + b)/ reward_window_list.length renderer.update_avg(reward_avg_display, reward_avg.toFixed(2)) } return svg.node() }36:T52b,lookups = { const done_lookup = (cell) => { switch (cell) { case 'e': return true; case 'x': return false; default : return false; } } const reward_lookup = (cell) => { switch (cell) { case 'e': return 1000; case 'x': return -100; default : return -1; } } const color_lookup = (cell) => { switch (cell) { case '#': return "black"; case '.': return "gray"; case 's': return "orange"; case 'e': return "yellow"; case 'x': return "green"; default: return "orange"; } } const can_move_lookup = (cell) => { switch (cell) { case '#': return false; default: return true; } } const maze_lookup = (row,col) => maze[row].charAt(col) const start_lookup = () => { for(let row = states.min_y; row < states.max_y; row++){ for(let col = states.min_x; col < states.max_y; col++){ if(maze_lookup(row, col) == 's') return {x: col, y: row} } } } return { start_loc: start_lookup, reward: (row, col) => reward_lookup(maze_lookup(row, col)), done : (row, col) => done_lookup(maze_lookup(row, col)), color: (row, col) => color_lookup(maze_lookup(row, col)), can_move: (row, col) => can_move_lookup(maze_lookup(row, col)) } }37:T53f,build_environment = () => { const state = lookups.start_loc() const action_to_delta = action => { switch (action){ case 0: // North return {dx: 0, dy: -1} case 1: // East return {dx: 1, dy: 0} case 2: // South return {dx: 0, dy: 1} case 3: // West return {dx: -1, dy: 0} default: return {dx: 0, dy: 0} } } const clamp = (value, hi, lo) => { if(value > hi) return hi; if(value < lo) return lo; return value } const apply_action = (state, action) => { const delta = action_to_delta(action) const x = clamp(state.x + delta.dx, states.max_x, states.min_x) const y = clamp(state.y + delta.dy, states.max_y, states.min_y) const can_move = lookups.can_move(y,x) if(can_move){ state.x = x state.y = y } } const take_action = (action) => { apply_action(state, action) return { state: state, reward: lookups.reward(state.y, state.x), done: lookups.done(state.y, state.x) } } const reset = () => { const init_state = lookups.start_loc() state.x = init_state.x state.y = init_state.y } return { state: state, take_action: take_action, reset: reset, actions: { NORTH: 0, EAST: 1, SOUTH: 2, WEST: 3 } } }38:T12a0,renderer = { const flip_row = (row) => states.max_y - row + .5 const render_maze = (svg) => { const mazeGroup = svg.append("g") .attr("stroke", "#000") .attr("opacity", .75) maze.forEach((str,row) => { str.split("").forEach((cell, col) => { mazeGroup.append("rect") .attr("x", renderScale.x(col)) .attr("y", renderScale.y(flip_row(row))) .attr("width", renderScale.x(col) - renderScale.x(col-1)) .attr("height", renderScale.y(row - 1) - renderScale.y(row)) .attr("fill", lookups.color(row, col)) }) }) } const render_player = (svg, pos) => { const playerGroup = svg.append("g") .attr("stroke", "#0F0") .attr("stroke-opacity", 0.0) .attr("opacity", 1) const player = playerGroup.append("circle") .attr("cx", renderScale.x(pos.x + .5)) .attr("cy", renderScale.y(flip_row(pos.y) - .5)) .attr("r", 10) .attr("fill", "blue") return player } const move_player = (player, pos, durationMs = 1000) => { player.transition().duration(durationMs) .attr("cx", renderScale.x(pos.x + .5)) .attr("cy", renderScale.y(flip_row(pos.y) - .5)) } const render_reward = (svg) => { return svg.append("text") .attr("fill", "#0F0") .attr("x", renderScale.x(.25)) .attr("y", renderScale.y(-.25)) .text("Reward: 0") } const update_reward = (display, reward) => { display.text(`Reward: ${reward}`) } const render_avg = (svg) => { return svg.append("text") .attr("fill", "#0F0") .attr("x", renderScale.x(.25)) .attr("y", renderScale.y(flip_row(0) - .50)) .text("Average Reward: --") } const update_avg = (display, reward) => { display.text(`Average Reward: ${reward}`) } const calc_action_offset = (action) => { switch (action){ //NORTH case 0: return {dx: 0, dy: .35}; //EAST case 3: return {dx: -.35, dy: 0}; //SOUTH case 2: return {dx: 0, dy: -.35}; //WEST case 1: return {dx: .35, dy: 0}; default: return {dx: 0, dy: 0}; } } const calc_action_path = (x, y, action, size) => { const half_size = size/2; const offset = calc_action_offset(action) const center = {x: Math.round(renderScale.x(x + .5 + offset.dx)), y: Math.round(renderScale.y(flip_row(y) - .5 + offset.dy))} switch (action){ //NORTH case 0: return `${center.x - half_size},${center.y + half_size} ${center.x},${center.y - half_size} ${center.x + half_size},${center.y + half_size}`; //EAST case 3: return `${center.x - half_size},${center.y} ${center.x + half_size},${center.y - half_size} ${center.x + half_size},${center.y + half_size}`; //SOUTH case 2: return `${center.x - half_size},${center.y - half_size} ${center.x},${center.y + half_size} ${center.x + half_size},${center.y - half_size}`; //WEST case 1: return `${center.x + half_size},${center.y} ${center.x - half_size},${center.y - half_size} ${center.x - half_size},${center.y + half_size}`; default: return `${center.x - half_size},${center.y + half_size} ${center.x},${center.y - half_size} ${center.x + half_size},${center.y + half_size}`; } } const build_indicator = (group, x, y,action, value=0) => { const path = calc_action_path(x, y, action, 10) return group.append("polygon") .attr("points", path) .attr("opacity", .25) } const render_qtable = (svg, table) => { if(!display_settings.show_indicator) { return table.map(y => y.map(x => 0)) } const tableGroup = svg.append("g") .attr("fill", "lightblue") .attr("opacity", 1) return table.map((xs, y) => xs.map((actions, x) => actions.map((value,action) => { return build_indicator(tableGroup, x, y, action, value) }))) } const update_indicator = (indicators, values) => { if(!display_settings.show_indicator) { return } const filtered = values.filter(isFinite) const min = filtered.reduce((a,b) => a < b ? a : b) const shifted = filtered.map(val => val - min) const total = shifted.reduce((a,b) => a+b) let normed = shifted.map(val => val / total) if(normed.some(isNaN)) { normed = filtered.map(val => 1/filtered.length) } for(let i = 0; i < indicators.length; ++i) { indicators[i].attr("opacity", normed[i]) } } return { maze: render_maze, init_player: render_player, move_player: move_player, init_reward: render_reward, update_reward: update_reward, init_q: render_qtable, update_indicator: update_indicator, init_avg: render_avg, update_avg: update_avg } }39:[] 2f:{"title":"Q-Table Reinforcement Learning","cells":[{"id":0,"value":"md`# Q-Table Reinforcement Learning`","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"md`[Q-Learning](https://en.wikipedia.org/wiki/Q-learning) is a model-less reinforcement learning technique that focuses on learning an optimal policy for deciding which action ${tex `a`} to take at a given state ${tex `\\vec s`}. Q-Table is a technique that utilizes a table ${tex `Q`} where rows represent the potential states, and columns represent actions. The cells of the table ${tex `Q(\\vec s, a)`} represent the expected total reward ${tex `r`} of taking that action from that state.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":49,"value":"md`## Defining the problem\nFirst, let's define a problem to solve. A simple problem might be defining a maze for the agent to travel through.\n\nThe states might represent the position of the agent ${tex `(x,y)`}. Currently we're defining a maze of size ${(states.max_x - states.min_x) }x${ (states.max_y - states.min_y)} Since all combinations are taken into account, there are ${(states.max_x - states.min_x) * (states.max_y - states.min_y)} states total.\n\nActions can be defined as moving North, East, South, and West. This gives us 4 total actions which each get a column.\n\nPositive rewards might only be given to the agent when the exit is reached. A movement cost can be implemented as a negative reward. Penalties for stepping on a dangerous cell can also be represented as a larger negative reward.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":110,"value":"{\n const svg = d3.select(DOM.svg(renderSize.width, renderSize.height));\n renderer.maze(svg)\n return svg.node()\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":245,"value":"md`## Creating an environment\nNow that we've defined a the problem constraints, we'll define an environment that can be interacted with. The environment consists of a state and a method that allows us to take an action. In our case, the actions of North, East, South, and West have been mapped to (0, 1, 2, 3) respectively. Lets see what randomly choosing actions looks like:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":283,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":403,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":462,"value":"{\n const svg = d3.select(DOM.svg(renderSize.width, renderSize.height));\n\n renderer.maze(svg)\n const q_table = q_table_builder(() => Math.random())\n const q_table_display = renderer.init_q(svg, q_table)\n \n return svg.node()\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":749,"value":"viewof display_settings = {\n\n const formData = html``\n return form(formData)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":569,"value":"md`## Adding Learning\nSo, at any given point, the agent will simply pick the ${tex `a`} that gives the highest value of ${tex `Q(s,a)`} and follow that action. If ${tex `Q`} doesn't change, that simply puts the agent on a fixed route through the maze. If ${tex `Q`} says to head into a wall... well, the agent will keep running into that wall forever. So, we need to update ${tex `Q`} given some feedback.\n\nThe formula for updating ${tex `Q`} is:\n\n${tex `Q(\\vec{s},a)=(1 - \\alpha)Q(\\vec{s},a) + \\alpha(r + \\gamma max_{a'}Q(\\vec{s}',a'))`}\nwhere ${tex `\\alpha`} is the learning rate, ${tex `r`} is the reward received for taking action ${tex `a`} at state \n${tex `\\vec{s}`}, ${tex `\\gamma`} is the discount factor for how much we trust the accuracy of the future reward, and ${tex `max_{a'}Q(\\vec{s}',a')`} is the maximum estimated reward from the new state ${tex `\\vec{s}'`}. Let's see what happens when we put an agent that can learn into the grid. We'll initialize all starting values as 0.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":592,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":643,"value":"viewof learning_settings = {\n\n const formData = html``\n formData.button.onclick = event => {\n event.preventDefault(); // Don’t submit the form.\n formData.dispatchEvent(new CustomEvent(\"change\"));\n };\n \n return form(formData)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":660,"value":"md`## Strategically Making Mistakes\nOnce a path is created the rest of the map is pretty much unexplored. Sometimes a more efficient route could be made by exploration. One way to explore those options is by occationally choosing an action at random, rather than always choosing the greatest value.\n\nWe'll use a variable called ${tex `\\epsilon`}. Each round we'll generate a random number. If that number is less than epsilon, we'll take a random action, rather than the one recommended by ${tex `Q`}.\n\nUsually, epsilon is lowered over time during the learning process, until it is eliminated, but is not in this demonstration to show how ${tex `\\epsilon`} works. You'll see that the path converges similar to the path discovered in the previous example, but has more directions slightly off the path that lead back to the path.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":678,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":682,"value":"viewof epsilon_settings = {\n \n const formData = html``\n formData.button.onclick = event => {\n event.preventDefault(); // Don’t submit the form.\n formData.dispatchEvent(new CustomEvent(\"change\"));\n };\n \n return form(formData)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":715,"value":"md`## Getting Tipsy\nOk. So what? This doesn't seem like anything ${tex `A*`} couldn't handle __much__ faster.\n\nOne of the interesting properties of this technique is the ability to handle stochastic controls. In the previous case, we occasionally made random choices for exploration. But, what if, when we told the player which way to move, sometimes they didn't go the direction we told them? What if they were drunk?\n\nLet's define a drunkeness factor ${tex `\\mu`}. Every round, after we decide what we believe to be the best action, we'll generate a random number. If it less than ${tex `\\mu`}, the agent will take a random action, but we'll still update the table with the action that the agent was told to make.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":731,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":736,"value":"viewof drunken_settings = {\n \n const formData = html``\n formData.button.onclick = event => {\n event.preventDefault(); // Don’t submit the form.\n formData.dispatchEvent(new CustomEvent(\"change\"));\n };\n \n return form(formData)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":64,"value":"maze = {\n // # - wall\n // x - danger\n // s - start position\n // e - exit position\n // . - empty floor\n return([\n '############',\n '#.......#..e',\n '#.......#..#',\n '#...#...#..#',\n '#...#...#..#',\n '#...#...#..#',\n '#...#......#',\n '#...#......#',\n '#...#####.##',\n '#...xxxxx.x#',\n '#...x.....x#',\n '#s....xxxxx#',\n '############'\n])\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":257,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":413,"value":"q_table_to_md_table = (table) => {\n return table.slice(0,2).reduce((acc, ys, y) => acc + ys.slice(0,5).reduce((acc, xs, x) => acc + xs.reduce((acc, action) => acc + `${action.toFixed(2)}|`, `|${x}|${y}|`) + \"\\n\", \"\"), \"\")\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":247,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"},{"id":231,"value":"$38","pinned":false,"hidden":false,"mode":"ojs"},{"id":99,"value":"q_table_builder = (src = () => 0) => Array.from({length: (states.max_y - states.min_y + 1)}, _ => Array.from({length: (states.max_x - states.min_x + 1)}, _ => Array.from({length: 4}, _ => src())))","pinned":false,"hidden":false,"mode":"ojs"},{"id":78,"value":"states = {\n return {\n min_x : 0,\n min_y : 0,\n max_y : maze.length - 1,\n max_x : maze.map(str => str.length).reduce((a,b) => a < b ? b : a) - 1\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":114,"value":"chartMargin = ({top: 12, right: 10, bottom: 26, left: 26})","pinned":false,"hidden":false,"mode":"ojs"},{"id":118,"value":"renderSize = {\n const side = Math.min(width, 500)\n const cell_width = 50\n const count_x = states.max_x - states.min_x\n const count_y = states.max_y - states.min_y\n return {width: count_x * cell_width, height: count_y * cell_width}\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":121,"value":"renderScale = {\n const min = Math.min(states.min_x, states.min_y)\n const max = Math.max(states.max_x, states.max_y)\n return {\n x: d3.scaleLinear().domain([min, max+1]).range([chartMargin.left, renderSize.width - chartMargin.right]),\n y: d3.scaleLinear().domain([min, max+1]).range([renderSize.height - chartMargin.bottom, chartMargin.top])\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":112,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":644,"value":"import { form } from \"@mbostock/form-input\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":650,"value":"//using styles from https://webdesign.tutsplus.com/tutorials/how-to-build-web-form-layouts-with-css-grid--cms-28776\nhtml``","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W39","stdlib":"1","titling":"auto"}