25:["$","title",null,{"children":"Easy 21 assignment | Nam Chu Hoai | Observable"}] 4b:T482,md`Let's implement the basic mechanics of the game. The rules are given as follows: - The game is played with an infinite deck of cards (i.e. cards are sampled with replacement) - Each draw from the deck results in a value between 1 and 10 (uniformly distributed) with a colour of red (probability 1/3) or black (probability 2/3). - There are no aces or picture (face) cards in this game - At the start of the game both the player and the dealer draw one black card (fully observed) - Each turn the player may either stick or hit - If the player hits then she draws another card from the deck - If the player sticks she receives no further cards - The values of the player’s cards are added (black cards) or subtracted (red cards) - If the player’s sum exceeds 21, or becomes less than 1, then she “goes bust” and loses the game (reward -1) - If the player sticks then the dealer starts taking turns. The dealer always sticks on any sum of 17 or greater, and hits otherwise. If the dealer goes bust, then the player wins; otherwise, the outcome – win (reward +1), lose (reward -1), or draw (reward 0) – is the player with the largest sum. `4c:T4d5,runMonteCarlo = async function(count) { // run the episodes and update the value function for(let i=0;i { const key = JSON.stringify(state) const lens = R.lensProp(key) const count = R.pipe(R.view(lens), R.defaultTo(0), R.inc) monteCarloValueCounter[key] = count(monteCarloValueCounter) const addRewardTo = R.pipe(R.view(lens), R.defaultTo(0), R.add(discountedRewards(episode, index))) const rewardSum = addRewardTo(monteCarloTotalReturn) monteCarloTotalReturn[key] = rewardSum }) if (i % 10 == 0) mutable rerender = true break; } } } }4d:T4f7,runTD = async function(count) { // run the episodes and update the value function for(let i=0;i { const { playerSum, dealerSum } = state const key = JSON.stringify({ playerSum, dealerSum, action }) const lens = R.lensProp(key) const discountedReward = discountedRewards(episode, index) const value = R.pipe( R.view(lens), R.defaultTo(0), (oldValue) => oldValue - LEARNING_RATE * (oldValue - discountedRewards(episode, index)) )(tdValueFunction) tdValueFunction[key] = value }) if (action == 'STICK' || !isValidSum(state.playerSum)) { if (i % 100 == 0) mutable rerenderTD = true break } } } }4e:[] 47:{"id":"463a5655142eb4e6","slug":"easy-21-assignment","title":"Easy 21 assignment","thumbnail":"49e6948c32d344dc2c345a4ad60b022fce24238dbb6cde8e66bcf0239727cbc5","access_level":"public","create_time":"$D2018-02-20T07:20:17.962Z","update_time":"$D2020-01-25T19:52:30.637Z","view_time":null,"first_public_time":"$D2018-02-22T08:46:05.450Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"8c7b1983f2298832","login":"nambrot","name":"Nam Chu Hoai","avatar_url":"https://avatars-next.observableusercontent.com/d3d0e82db167fae3abb515e0ef89f76cd32028647d141d8ceb610e0229602bed","tier":"starter_2024","bio":"Currently focusing on fundamentals such as FP, stream processing and other data-related workloads. Looking for next opportunities with deeply technical teams.","followed_by_you":false,"follows_you":false},"version":753,"publish_version":753,"role":null,"authored":false,"authors":[{"type":"individual","id":"2cb330cd2a51bd63","login":"nambrot","name":"Nam Chu Hoai","avatar_url":"https://avatars-next.observableusercontent.com/d3d0e82db167fae3abb515e0ef89f76cd32028647d141d8ceb610e0229602bed","tier":null,"bio":"Currently focusing on fundamentals such as FP, stream processing and other data-related workloads. Looking for next opportunities with deeply technical teams.","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"2cb330cd2a51bd63","login":"nambrot","name":"Nam Chu Hoai","avatar_url":"https://avatars-next.observableusercontent.com/d3d0e82db167fae3abb515e0ef89f76cd32028647d141d8ceb610e0229602bed","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Easy 21 assignment","cells":[{"id":0,"value":"md`# Easy 21 assignment`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":7,"value":"md`This is my attempt at doing the [RL course by David Silver](http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html)'s [Easy 21 assignment](http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/Easy21-Johannes.pdf) in an Observable Notebook`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":12,"value":"md`### Implementation of Easy21`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":75,"value":"$4b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"function step(state, a) {\n if (isValidSum(state.playerSum)) {\n switch(a) {\n case 'STICK':\n const dealerSum = getFinalDealerValue(state.dealerSum)\n const newState = { ...state, dealerSum }\n return { newState, reward: getRewardFromState(newState) }\n break;\n case 'HIT':\n const playerSum = addCard(state.playerSum) \n return { newState: { ...state, playerSum }, reward: isValidSum(playerSum) ? 0 : -1 }\n \tbreak;\n }\n } else\n return { newState: state, reward: 0 }\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"function isValidSum(sum) {\n return sum <= 21 && sum >= 1;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":109,"value":"function getRandomCard(color) {\n function getRandomInt(max) {\n return Math.floor(Math.random() * Math.floor(max));\n }\n return {\n \tvalue: getRandomInt(10) + 1,\n \tcolor: color\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":45,"value":"function addCard(currentSum) {\n const card = getRandomCard(Math.random() > 0.3 ? 'black' : 'red')\n if (card.color == RED)\n return currentSum - card.value\n else\n return currentSum + card.value\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":57,"value":"function getFinalDealerValue(currentSum) {\n if (currentSum < 17)\n return getFinalDealerValue(addCard(currentSum))\n return currentSum;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":60,"value":"function getRewardFromState(state) {\n if (!isValidSum(state.playerSum))\n return -1\n if (!isValidSum(state.dealerSum) || state.playerSum > state.dealerSum)\n return 1;\n if (state.playerSum === state.dealerSum)\n return 0;\n return -1;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":115,"value":"function getRandomStartingState() {\n \treturn {\n dealerSum: getRandomCard('black').value,\n playerSum: getRandomCard('black').value\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":87,"value":"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":94,"value":"md`### Policy Evaluation\n\nThe first step is to do what's called Policy Evaluation. A policy is a function that given a state, will return the action to be taken. Such policy has a value function \\`V\\`, i.e. an approximation of being in each state. Related to that is a action-value function \\`Q\\` that quantifies not only the value of a state, but the value of a state-action pair.\n\nI just realized that I started this assignment early since it asks for control to which I haven't gotten yet. So I'll just declare a simple policy and do a MC and TD evaluation of it. My policy will be to HIT when i'm below 17. Let's start with a Monte carlo evaluation. Monte carlo evaluation runs complete episodes and then attributes the total discounted reward to each state in the episode.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":119,"value":"mutable monteCarloTotalReturn = ({})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":153,"value":"mutable monteCarloValueCounter = ({})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":397,"value":"// so that we can force dependent cells to update manually\nmutable rerender = true","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":552,"value":"function discountedRewards(episode, index) {\n const relevantRewards = R.pluck('reward')(R.drop(index, episode))\n const discountFactors = R.times((x) => Math.pow(DISCOUNT, x), relevantRewards.length)\n return R.sum(\n R.zipWith((x, y) => x*y, relevantRewards, discountFactors)\n )\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":126,"value":"$4c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":165,"value":"monteCarloValueFunction = {\n \t!rerender;\n const mergedObject =\n R.mergeWithKey(\n (key, totalReturn, count) => totalReturn / count,\n monteCarloTotalReturn,\n monteCarloValueCounter)\n return R.values(\n \t\tR.mapObjIndexed((val, key) => R.merge({ reward: val }, JSON.parse(key)), mergedObject))\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":386,"value":"md`Here do we actually run the experiment with the number of episodes`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":259,"value":"runMonteCarlo(10)\n// just run 10 times to see something","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":212,"value":"viewof numberOfMCEpisodes = html`\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":414,"value":"{\n let show = false;\n const div = html`

\n \n \n \n

`;\n div.querySelector(\"#toggle\").onclick = () => {\n runMonteCarlo(numberOfMCEpisodes)\n };\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":430,"value":"mutable totalRuns = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":176,"value":"valueFunctionVisualization = { return vegalite({\n data: {values: monteCarloValueFunction},\n mark: {\"type\": \"point\", \"filled\": true, \"size\": 200},\n width: 500,\n height: 500,\n encoding: {\n x: {\"field\": \"dealerSum\", \"type\": \"quantitative\"},\n y: {\"field\": \"playerSum\", \"type\": \"quantitative\"},\n color: {\"field\": \"reward\", \"type\": \"quantitative\", \"scale\": {\n \"domain\": [-0.3, 0.3],\n \"range\": [\"green\", \"yellow\"]\n }},\n }\n})}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":514,"value":"function unpack(rows, key) {\n return rows.map(function(row) { \n return row[key]; \n });\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":391,"value":"md`You should see that being in the 14-17 range is actually bad, because we will hit and likely get busted`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":497,"value":"md `### Action Value Function\n\nWhile the value function gives us some representation of our intuition of how valuable each state is, it doesn't quite tell us what we should do, since we evaluate a static policy. What would be more interesting I think is to calculate the action value function \\`Q\\`, that would try to quantify the value of a specific state-action pair.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":548,"value":"tdValueFunction = ({})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":641,"value":"mutable rerenderTD = true","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":538,"value":"$4d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":604,"value":"runTD(10)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":686,"value":"getKey = ({playerSum, dealerSum}, action) => {\n return JSON.stringify({ playerSum, dealerSum, action })\n }","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":643,"value":"visualizingTDValueFunction = {\n !rerenderTD;\n let values = []\n for(let playerSum=0;playerSum<=21;playerSum++){\n for(let dealerSum=0;dealerSum<=21;dealerSum++){\n values.push({playerSum, dealerSum}) \n }\n }\n \n return R.map((state) => {\n return {...state, reward: (tdValueFunction[getKey(state, 'STICK')] - tdValueFunction[getKey(state, 'HIT')] )* 3}\n }, values)\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":659,"value":"viewof numberOfTDEpisodes = html`\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":539,"value":"mutable totalTDRuns = 0","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":661,"value":"{\n let show = false;\n const div = html`

\n \n \n \n

`;\n div.querySelector(\"#toggle\").onclick = () => {\n runTD(numberOfTDEpisodes)\n };\n return div;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":656,"value":"vegalite({\n data: {values: visualizingTDValueFunction},\n mark: {\"type\": \"point\", \"filled\": true, \"size\": 200},\n width: 500,\n height: 500,\n encoding: {\n x: {\"field\": \"dealerSum\", \"type\": \"quantitative\"},\n y: {\"field\": \"playerSum\", \"type\": \"quantitative\"},\n color: {\"field\": \"reward\", \"type\": \"quantitative\", \"scale\": {\n \"domain\": [-1, 1],\n \"range\": [\"yellow\", \"blue\"]\n }},\n }\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":749,"value":"md`Since the value we are plotting is the value of sticking minus the value of hitting, negative or yellow values indicate that it is more valuable to hit, vs. positive and blue values indicate that it is more valuable to stick. You should see that this allows for a conclusion of a more nuanced policy stick a bit more often when the dealerSum is in our favor`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":148,"value":"R = require(\"ramda\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":46,"value":"RED = 'red'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":168,"value":"vegalite = require(\"@observablehq/vega-lite@0.1\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":52,"value":"BLACK = 'black'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":509,"value":"Plotly = require(\"https://cdn.plot.ly/plotly-latest.min.js\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":561,"value":"DISCOUNT = 0.5","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":593,"value":"LEARNING_RATE = 0.1","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W4e","stdlib":"1"}} 24:null