41:null 42:["$","title",null,{"children":"Reinforcement Learning notes | Jim Kan | Observable"}] 48:T46c,md`#### state-value function The expected return starting from state _s_ ${tex.block` \begin{aligned} v(s) &\doteq \mathbb{E}[ G_t | S_t = s] \\ &= \mathbb{E}[ R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... | S_t = s] \\ &= \mathbb{E}[ R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + ...) | S_t = s] \\ &= \mathbb{E}[ R_{t+1} + \gamma G_{t+1} | S_t = s] \\ &= \mathbb{E}[ R_{t+1} + \gamma v(S_{t+1}) | S_t = s] \\ \\ v(S_{t+1}) &= \sum_{s' \in S} \mathbb{P} [S_{t+1} = s' | S_t = s] v(s') \\ &= \sum_{s' \in S} P_{ss'} v(s') \\ \\ v(s) &= R_s + \gamma \sum_{s' \in S} P_{ss'} v(s') \end{aligned} `} The last becomes the __Bellman Equation for MRPs__. Or in matrix form: ${tex.block`v = R + \gamma P v`} where ${tex`v`} is a column vector: ${tex.block` \begin{bmatrix} v(S_1) \\ \vdots \\ v(S_n) \end{bmatrix} = \begin{bmatrix} R_1 \\ \vdots \\ R_n \end{bmatrix} + \gamma \begin{bmatrix} P_{11} & ... & P_{1n} \\ \vdots & & \\ P_{n1} & ... & P_{nn} \end{bmatrix} \begin{bmatrix} v(S_1) \\ \vdots \\ v(S_n) \end{bmatrix} `} `49:T499,md` ### Policy A **policy** consists of a probabilistic mapping from states _S_ to actions _A_, as manifested as a matrix with _|S|_ rows and _|A|_ columns, where each row encodes the probability of taking each action when in a state. ${tex.block` \pi(a | s) \in \mathbb{R}^{S \times A} `} #### GridWorld * \`env.P\` represents the transition probabilities of the environment. * \`env.P[s][a]\` is a \`(prob, next_state, reward, done)\` tuple. Actually, it looks like it's a list of tuples. Transitions in the GridWorld are deterministic, so there's only one tuple in this example instead of 16, since the other 15 possible next states have zero probability. In a non-deterministic environment, the probabilities from the 16 tuples would sum to 1. \`env.P\` corresponds to ${tex`p(s',r \mid s, a)`}. In general it should be a 16x4x16x4 tensor. ${tex`R`} should be a ${tex`16 \times 4`} matrix, and ${tex`R^{\pi}`} should then be a 16-vector: ${tex.block` \begin{aligned} R^a_s \in \mathbb{R}^{16 \times 4} \\ \pi(a | s) \times R^a_s = R^{\pi} \end{aligned} `} (just for GridWorld -- normally with a non-deterministic policy ${tex`R`} would be a tensor). `4a:T5f3,md`## MC control i.e. approximating optimal policies using iterative improvement as in GPI: alternating policy evaluation and policy improvement. ${tex.block`\pi(s) \doteq arg\max_{a \in A} q(s, a)`} On-policy learning - Policy evaluation: to be model-free, need to use ${tex`q(s,a)`} rather than ${tex`v_{\pi}(s)`} - Policy improvement: greedy improvement doesn't work because there's no exploration ⇒ ε-greedy policy improvement ${tex.block` \pi(s) = \begin{cases} \epsilon/m + 1 - \epsilon & \text{if } a^* = {argmax}_{a \in A} Q(s, a) \\ \epsilon/m & \text{otherwise} \end{cases} `} ### Greedy in the Limit with Infinte Exploration (GLIE) * All state-action pairs explored infinitely many times ${tex.block`\lim_{k \leftarrow \infty} N_k(s, a) = \infty `} * The policy converges on a greedy policy ${tex.block`\lim_{k \leftarrow \infty} \pi_k(a | s) = \textbf{1}(a = {argmax}_{a' \in A} Q_k(s, a')) `} ### GLIE MC control * For ${tex`k`}th episode sampled using ${tex`\pi`}: ${tex`\{ S_1, A_1, R_2, ..., S_T \} \sim \pi`}: * For each state and action in the episode: ${tex.block` \begin{aligned} N(S_t, A_t) &\leftarrow N(S_t, A_t) + 1 \\ Q(S_t, A_t) &\leftarrow Q(S_t, A_t) + \frac{1}{N(S_t, A_t)} [G_t - Q(S_t, A_t)] \end{aligned} `} * Improve policy based on new Q ${tex.block` \begin{aligned} \epsilon &\leftarrow 1/k \\ \pi &\leftarrow \epsilon\text{-greedy} (Q) \end{aligned} `} `4b: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} `} `4c:T72a,md`## TD(λ) ### n-step returns ${tex`G_t`} looking ahead n steps ${tex.block` G_t^{(n)} = R_{t+1} + \gamma R_{t+2} + ... + \gamma^{n-1} R_{t+n}+ \gamma^{n} V(S_{t+n}) `} * ${tex`n = 1`} corresponds to TD(0) * ${tex`n = \infty`} corresponds to MC ### λ returns Weighted combination of all n-step returns ${tex.block`G_t^{\lambda} = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_t^{(n)} `} ### backward view Computational cost equal to TD(0) This formulation (the forward view) requires waiting for the end of the episode, since that's when we find out what the return is for the episode. This is inconvenient because we would prefer to update incrementally. The backward view fixes this by maintaining an __eligibility trace__ for each state. In the backward view, instead of waiting for the end of the episode, we keep a scaling factor for each state we pass through that represents the contribution of that state to where we are now. With each step, the contribution (eligibiilty) decays by some multiplier. Once we reach the end (or any state where we get a reward) and can calculate the return, we can retroactively assign credit/blame to each state according to its eligibility. ### algorithm * keep eligibility trace ${tex`E_t(s)`} for every state s ${tex.block` \begin{aligned} E_0(s) &= 0 \\ E_t(s) &= \gamma \lambda E_{t-1}(s) + \textbf{1}(S_t = s) \end{aligned} `} * update ${tex`V(s)`} for every state s proportionally to TD-error ${tex`\delta_t`} and ${tex`E_t(s)`} ${tex.block` \begin{aligned} \delta_t &= R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \\ V(s) &\leftarrow V(s) + \alpha \delta_t E_t(s) \end{aligned} `} - ${tex`\lambda = 0`} corresponds to TD(0) - ${tex`\lambda = 1`} corresponds to MC `4d:T472,md`## Sarsa(λ) Similarly to the development of TD(λ), we can define: ### n-step Sarsa i.e. look ahead n steps instead of just 1. Here we are interested in Q rather than G: ${tex.block` q_t^{(n)} = R_{t+1} + \gamma R_{t+2} + ... + \gamma^{n-1} R_{t+n}+ \gamma^{n} Q(S_{t+n}) `} The update would then be: ${tex.block` Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [ q_t^{(n)} - Q(S_t, A_t)] `} ### ${tex`q^{\lambda}`} return ${tex.block`q_t^{\lambda} = (1-\lambda) \sum_{n=1}^{\infty} \lambda^{n-1} q_t^{(n)} `} ### algorithm * here we need an eligibility trace for each state-action pair: ${tex.block` \begin{aligned} E_0(s, a) &= 0 \\ E_t(s, a) &= \gamma \lambda E_{t-1}(s, a) + \textbf{1}(S_t = s, A_t = a) \end{aligned} `} * update ${tex`Q(s, a)`} for every (s, a) proportionally to TD-error ${tex`\delta_t`} and ${tex`E_t(s, a)`} ${tex.block` \begin{aligned} \delta_t &= R_{t+1} + \gamma Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t) \\ Q(S, A) &\leftarrow Q(S, A) + \alpha \delta_t E_t(s, a) \end{aligned} `} Note that now the size/granularity of the time step no longer matters `4e:T10cc,md`# Off-policy learning Evaluate __target policy__ ${tex`\pi(a|s)`} while following __behavior policy__ ${tex`\mu(a|s)`} or ${tex`b(a|s)`} * Learn from teacher/example * Reuse experience from other policies * Learn about _optimal_ policy while following _exploratory_ policy * Learn about _multiple_ policies while following one policy __Coverage__ requirement: every action taken under ${tex`\pi`} must also be taken, at least occasionally, under _b_. * ${tex`\pi`} will tend to be a deterministic optimal policy * _b_ will be stochastic ## importance sampling ${tex.block` \begin{aligned} \mathbb{E}_{X \sim P} [ f(X) ] &= \sum P(X) f(X) \\ &= \sum Q(X) \frac{P(X)}{Q(X)} f(X) \\ &= \mathbb{E}_{X \sim Q} \left [ \frac{P(X)}{Q(X)} f(X) \right ] \end{aligned} `} ### Off-Policy MC importance sampling Weight entire return according to similarity between policies: ${tex.block` G_t^{\pi / \mu} = \frac{\pi(A_t | S_t)}{\mu(A_t | S_t)} \frac{\pi(A_{t+1} | S_{t+1})}{\mu(A_{t+1} | S_{t+1})} ... \frac{\pi(A_T | S_T)}{\mu(A_T | S_T)} G_t `} ### Off-Policy TD importance sampling Only one importance sampling correction to TD target: ${tex.block` \frac{\pi(A_t | S_t)} {\mu(A_t | S_t)} ( R_{t+1} + \gamma V(S_{t+1}) ) `} * MC: high variance and practically useless, since every step needs to be corrected * TD: ok because only one step involved ## Q-learning (SARSAmax) Update the action-value function based on to the currently optimal action: ${tex.block` Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha [ R_{t+1} + \gamma \red{\max_a Q(S_{t+1}, a)} - Q(S_t, A_t) ] `} The policy still has an effect in that it determines which state–action pairs are visited and updated. This isn't quite right, but it still converges because the only requirement for convergence is that all pairs continue to be updated. * initialize ${tex`Q(s,a)`} arbitrarily, except ${tex`Q(s_{terminal}, *) = 0`} * repeat for each episode: * initialize ${tex`S`} * repeat until ${tex`S`} is terminal (each step of episode): * choose ${tex`A`} from ${tex`S`} using policy derived from ${tex`Q`} * ${tex`(S, A) \Rightarrow R, S'`} ${tex.block` \begin{aligned} Q(S, A) &\leftarrow Q(S, A) + \alpha [ R + \gamma \red{\max_a Q(S', a)} - Q(S, A)] \\ S &\leftarrow S' \end{aligned} `} #### Cliff walking example (S&B p.106): Q-learning learns the optimal policy of walking alongside the cliff, but the ε-greediness makes it occasionally step off the cliff. SARSA learns a safer but sub-optimal path that's farther away from the cliff. ### Expected Sarsa (S&B p.107): Given ${tex`S_{t+1}`}, move _deterministically_ in the same direction as Sarsa moves _in expectation_. ${tex.block` \begin{aligned} Q(S_t, A_t) &\leftarrow Q(S_t, A_t) + \alpha [ R_{t+1} + \gamma \red{\mathbb{E}[ Q(S_{t+1}, A_{t+1}) | S_{t+1}]} - Q(S_t, A_t) ] \\ &\leftarrow Q(S_t, A_t) + \alpha [ R_{t+1} + \gamma \red{\sum_a \pi(a|S_{t+1}) Q(S_{t+1}, a)} - Q(S_t, A_t) ] \end{aligned} `} ### Maximization bias (S&B p.108): Even if the expected value of action Ai is lower than the expected value of action Aj, if the variance of Ai is higher, then algorithms which select for the maximum value (Sarsa, Q-learning) will tend to pick Ai since the higher end is higher. > There will be a positive maximization bias if we use the maximum of the estimates as an estimate of the maximum of the true values. One way to view the problem is that it is due to using the same samples (plays) both to determine the maximizing action and to estimate its value. #### Double learning Split episodes into 2 sets, and learn 2 separate estimates ${tex`Q_1(a)`} and ${tex`Q_2(a)`}; use one to find the max action and the other to estimate values, and then swap. ${tex.block` \begin{aligned} A^* &= argmax_a Q_1(a) \\ Q_2(A^*) &= Q_2(argmax_a Q_1(a)) \end{aligned} `} #### Double Q-learning Randomly switch between ${tex.block` Q_1(S_t, A_t) \leftarrow Q_1(S_t, A_t) + \alpha [ R_{t+1} + \gamma \red{Q_2(S_{t+1}, argmax_a Q_1(S_{t+1},a))} - Q_1(S_t, A_t) ] `} and ${tex.block` Q_2(S_t, A_t) \leftarrow Q_2(S_t, A_t) + \alpha [ R_{t+1} + \gamma \red{Q_1(S_{t+1}, argmax_a Q_2(S_{t+1},a))} - Q_2(S_t, A_t) ] `} `4f:T411,md` ### stochastic gradient descent Find __w__ minimising MSE between approx value fn ${tex`\hat{v}(s, \mathbf{w})`} and true value fn ${tex`v_\pi(s)`} Objective function: ${tex.block` J(\mathbf{w}) = \mathbb{E}_\pi [ (v_\pi(S) - \hat{v}(S, \mathbf{w}))^2 ] `} Represent state by feature vector: ${tex.block` \mathbf{x}(S) = \begin{bmatrix} \mathbf{x}_1(S) \\ \vdots \\ \mathbf{x}_n(S) \end{bmatrix} `} __Linear value function approximation__: value function is linear combination of features: ${tex.block` \hat{v}(S, \mathbf{w}) = \mathbf{x}(S)^T\mathbf{w} `} Note that table lookup is a special case where the feature vectors are one-hot However, we don't know ${tex`v_\pi(S)`} (ground truth), so we approximate it with a _target_: - MC | return ${tex`G_t`} - TD(0) | TD target ${tex`R_{t+1} + \gamma \hat{v}(S_{t+1}, \mathbf{w})`} - TD(λ) | λ-return ${tex`G_t^\lambda`} `50:T662, md` ## Policy-based RL Instead of approximating value or action-value functions using parameters ${tex`\theta`} (here the policy is implicit, e.g. ε-greedy): ${tex.block` \begin{aligned} V_\theta(s) &\approx V_\pi(s) \\ Q_\theta(s, a) &\approx Q_\pi(s, a) \end{aligned} `} We now parameterize the policy directly, skipping the value function entirely: ${tex.block` \pi_\theta(s, a) = \mathbb{P} [ a | s, \theta] `} Scalability: parameter vector then carves up the large, possibly continuous state space into regions belonging to actions. ### +: Better convergence properties Value function may be complex, but policy function may be simple -- e.g. breakout, where estimating the exact value of each state is difficult, but the actions are basically move left and move right. ### +: Effective in high-D / continuous action spaces In value-based RL, always need to compute the argmax over all actions for each state; but for large spaces this itself can be intractable. ### +: Can learn stochastic policies __Predictability__: Greedy policy is deterministic; in some situations (e.g. iterated rock-paper-scissors) the optimal policy is stochastic, since deterministic policies always lose. __State aliasing__: if two states are indistinguishable via their feature representations, but require different actions (e.g. aliased gridworld), a deterministic policy will lose. ### -: inefficient/high variance - Typically converge to local optimum - Evaluating policy is typically inefficient/high variance Using the max is optimal, agressive/greedy. Not using max is more stable, but is probably less optimal. `51:T64f,md`### Policy gradient ${tex.block` \Delta \theta = \alpha \nabla_\theta J(\theta) `} ### Finite differences method Compute each partial derivative by perturbing ${tex`\theta`} by ${tex`\epsilon`}: ${tex.block` \frac{\partial J(\theta)}{\partial \theta_k} \approx \frac{ J(\theta + \epsilon u_k) - J(\theta) }{\epsilon} `} where ${tex`u_k`} is the unit vector in the _k_-th dimension. ### Likelihood ratio / score function ${tex.block` \begin{aligned} \nabla_\theta \pi_\theta(s,a) &= {\pi_\theta(s,a)} \frac{\nabla_\theta \pi_\theta(s,a)}{\pi_\theta(s,a)} \\ &= {\pi_\theta(s,a)} \red{\nabla_\theta \log \pi_\theta(s,a)} \end{aligned} `} The score function is the red part. ### Softmax policy Weights are linear combination of features ${tex`{\phi (s, a)^T \theta}`} exponentiated and normalized to form probabilities ${tex.block` \pi_\theta(s,a) \propto e^{\phi (s, a)^T \theta} `} Score function: feature value minus average feature value ${tex.block` \nabla_\theta \pi_\theta(s,a) = \phi(s,a) - \mathbb{E}_{\pi_\theta} [\phi (s,\cdot)] `} ### Gaussian policy For continuous action spaces, sample action from Gaussian: ${tex.block` a \sim N(\mu(s), \sigma^2) `} where the mean is a linear combination of state features, plus some random deviation around the mean: ${tex.block` \mu(s) = \phi(s)^T \theta `} Score function: proportional to difference between action taken from the mean for each feature ${tex.block` \nabla_\theta \pi_\theta(s,a) = \frac{(a - \mu(s)) \phi(s) }{\sigma^2} `} ### Policy Gradient theorem ### MC Policy Gradient (REINFORCE) `52:[] 46:{"id":"0e91eeb36f64f9a3","slug":"reinforcement-learning-notes","title":"Reinforcement Learning notes","thumbnail":"a55ddd8d9b86623528710b1c6ade7fadef7a457a87743d6cbb7883665e9345ce","access_level":"public","create_time":"$D2018-01-31T19:36:21.384Z","update_time":"$D2018-05-10T00:44:07.484Z","view_time":null,"first_public_time":"$D2018-05-02T18:09:01.832Z","has_unpublished_edits":null,"fork":false,"stars":14,"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":1166,"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":14,"collection":{"id":"d2769ec0679b5a7e","slug":"reinforcement-learning","title":"Reinforcement Learning","owner":{"id":"df82e3ae90c3ba68","login":"j-kan","name":"Jim Kan"}},"type":"notebook","body":{"titling":"auto","title":"Reinforcement Learning notes","cells":[{"id":376,"value":"md`# Reinforcement Learning notes\n\nfrom [David Silver's lectures](http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html) and [Sutton & Barto, 2nd edition](http://incompleteideas.net/book/the-book-2nd.html).\n\nSee also:\n\n- https://beta.observablehq.com/@j-kan/a-random-walk-through-the-grid-world\n- https://beta.observablehq.com/@j-kan/on-policy-monte-carlo-control-for-soft-policies\n- https://beta.observablehq.com/@j-kan/temporal-difference-learning-sarsa-0\n- https://beta.observablehq.com/@j-kan/sarsa-lambda\n- https://beta.observablehq.com/@j-kan/q-learning\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":0,"value":"md`\n## Markov Decision Processes\n\nSutton & Barto, chapter 3\n\nStates, actions, rewards: ${tex``}\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":20,"value":"tex.block` \np(s',r \\mid s, a) \n \\doteq Pr\\{ S_t = s', R_t = r \\mid S_{t-1} = s, A_{t-1} = a \\} \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":36,"value":"md`Expected rewards for state–action pairs: `","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"tex.block`\n\\begin{aligned}\n\nr(s,a) \n &\\doteq \\mathbb{E}[ R_t | S_{t-1} = s, A_{t-1} = a]\t\\\\\n\n &= \\sum_{r \\in R}^{} r \\sum_{s' \\in S} p(s',r \\mid s, a)\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":407,"value":"md`Silver, lecture 2 slides:\n\n(notation corresponds to Sutton & Barto, first edition)\n\n### Markov Process (Markov Chain)\n\na tuple _< S, P >_ where\n\n- _S_ is a (finite) set of states\n- _P_ is a state transition probability matrix\n\n#### state transition matrix`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":410,"value":"tex.block`\n\\begin{aligned}\nP_{ss'} &= \\mathbb{P} [S_{t+1} = s' | S_t = s] \\\\\n\n &= \n\\begin{bmatrix}\n\tP_{11} & ... & P_{1n} \\\\ \n\t... & & ... \\\\ \n P_{n1} & ... & P_{nn}\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":427,"value":"md`### Markov Reward Process\n\nadds:\n\n- _R_: a reward function\n- γ : a discount factor, γ ∈ [0,1]\n\n#### reward function`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":429,"value":"tex.block`\nR_s = \\mathbb{E}[ R_{t+1} | S_t = s ]\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":445,"value":"md`#### return\n\nThe _return G_t_ is the total discounted reward from time-step _t_`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":453,"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":461,"value":"md`discounting:\n- eliminates infinite returns\n- encodes uncertainty about future rewards\n- adjusts preference for immediate vs delayed rewards`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":463,"value":"$48","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":469,"value":"md`### Markov Decision Process\n\nadds:\n- _A_ : a finite set of actions\n\nOnce we add actions, the model changes to:\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":472,"value":"tex.block`\n\\begin{aligned}\nP_{ss'}^{\\color{Red} a} &= \\mathbb{P} [S_{t+1} = s' | S_t = s, A_t = {\\color{Red} a} ] \\\\\nR_s^{\\color{Red} a} &= \\mathbb{E}[ R_{t+1} | S_t = s, A_t = {\\color{Red} a} ]\n\n\\end{aligned}\n`\n\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":482,"value":"md`#### policy\n\na distribution over actions given states:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":484,"value":"tex.block`\n\\pi(a|s) = \\mathbb{P}[ A_t = a | S_t = s ]\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":490,"value":"md`#### state-value function (MDP)\n\nexpected return starting from state _s_, and then following policy π\n\n${tex.block`\n\\begin{aligned}\n\nv_{\\pi}(s) &\\doteq \\mathbb{E}_{\\pi}[ G_t | S_t = s]\t\\\\\n &= \\mathbb{E}_{\\pi}[ R_{t+1} + \\gamma v(S_{t+1}) | S_t = s]\t\n\\end{aligned}\n`}\n\nThe last line is the __Bellman Expectation Equation for state-values__.\n\nOr, in matrix form:\n\n${tex.block`v_{\\pi} = R^{\\pi} + \\gamma P^{\\pi} v_{\\pi}`}\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":492,"value":"md`#### action-value function\n\nexpected 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`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":613,"value":"md`Note that these two can be defined in terms of each other:\n\n${tex.block`\n\\begin{aligned}\n\nv_{\\pi}(s) &= \\sum_{a \\in A} \\pi(a | s) q_{\\pi}(s,a)\t\\\\\nq_{\\pi}(s,a) &= R_s^a + \\gamma \\sum_{s' \\in S} P_{ss'}^a v_{\\pi}(s)\n\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":405,"value":"md`For a given policy _π_, \na Markov Decision Process ${tex``}\nreduces to a Markov Reward Process ${tex``}:\n\n${tex.block`\n\\begin{aligned}\n\tP_{ss'}^{\\pi} &= \\sum_{a \\in A} \\pi(a | s) P_{ss'}^a\t\\\\\n\tR_s^{\\pi} &= \\sum_{a \\in A} \\pi(a | s) R_s^a\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":626,"value":"md`#### Bellman Optimality equations\n\n${tex.block`\n\\begin{aligned}\n\nv_{*}(s) &= \\max_{a \\in A} q_{*}(s,a)\t\\\\\nq_{*}(s,a) &= R_s^a + \\gamma \\sum_{s' \\in S} P_{ss'}^a v_{*}(s)\n\n\\end{aligned}\n`}\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":89,"value":"md`### Bellman equations\n\nSutton & Barto, section 3.5, p.46-50`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":307,"value":"md`The Bellman equation for *v_π* :`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":91,"value":"tex.block`\n\\begin{aligned}\n\tv_{\\pi}(s) \n\t\t&\\doteq \\mathbb{E}_{\\pi}[G_{t} | S_{t} = s ]\\\\\n\t &= \\mathbb{E}_{\\pi}[R_{t+1} + \\gamma G_{t+1} | S_{t} = s \\\\\n\t\t&= \\mathbb{E}_{\\pi}[R_{t+1} + \\gamma v_{\\pi}(S_{t+1}) | S_{t} = s ] \\\\\n &= \\sum_{a} \\pi(a|s) \\sum_{s', r} p(s',r \\mid s, a)[r + \\gamma v_{\\pi}(s')]\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":105,"value":"md`For each triple ${tex``}, we:\n\n- compute its probability ${tex.block`\\pi(a|s) p(s',r | s,a)`}\n- weight the quantity in brackets ${tex.block`G_t = r + \\gamma v_{\\pi}(s')`} by that probability\n- and then sum over all possibilities to get an expected value.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":123,"value":"md`#### backup diagrams\n\nThis one focuses on the state-value function:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":126,"value":"{ \n function flatten(ll) {\n return ll.reduce((acc, l) => [...acc].concat(l), []);\n }\n \n const numActions = 3;\n const numNextStates = 2;\n \n const actions = d3.range(1, numActions+1);\n const nextStates = flatten(actions.map(i => d3.range(1, numNextStates+1).map(j => `s${i}${j}`)));\n const nextStateTransitions = flatten(actions.map(i => d3.range(1, numNextStates+1).map(j => `a${i} -> s${i}${j} [label=\"p, r\"]`)));\n \n return dot`\ndigraph G {\n ${dotStyles.defaults}\n\n subgraph root {\n rank=same;\n node [ color=1 ];\n s ;\n }\n\n subgraph env1 {\n rank=same;\n node [ color=2 ];\n ${actions.map(i => `a${i} [label=\"s, a${i}\"]`).join(';\\n')};\n }\n\n subgraph sp {\n rank=same;\n node [ color=1, label=\"s'\" ];\n ${nextStates.join('; ')};\n }\n\n ${actions.map(a => `s -> a${a} [label=\"π\"];`).join('\\n')}\n\n ${nextStateTransitions.join('\\n')}\n}` \n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":208,"value":"md`\n- Node ${tex`s`} corresponds to ${tex`v_{\\pi}(s)`}\n- Nodes ${tex`s,a`} correspond to ${tex`q_{\\pi}(s, a)`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":216,"value":"md`The corresponding backup diagram for the action-value function looks like this:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":219,"value":"dot`\ndigraph G {\n\n ${dotStyles.defaults}\n\n subgraph root {\n rank=same;\n node [ color=2,label=\"s, a\" ];\n sa ;\n }\t\n\n subgraph s1 {\n rank=same;\n node [ color=1, label=\"s'\"];\n s1;\n s2;\n s3;\n }\n\n subgraph sp {\n rank=same;\n node [ color=2, label=\"s', a'\" ];\n sa11; \n sa12; \n sa21; \n sa22; \n sa31; \n sa32;\n }\t\n\n\tsa -> s1, s2, s3 [label=\"p, r\"];\n\n\ts1 -> sa11, sa12 [label=\"π\"];\n\ts2 -> sa21, sa22 [label=\"π\"];\n\ts3 -> sa31, sa32 [label=\"π\"];\n}` ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":233,"value":"md`# Exact methods\n\nSutton & Barto chapter 4 (dynamic programming)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":41,"value":"$49","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":237,"value":"md`The **optimal state-value function**:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":241,"value":"tex.block`v_{*}(s) \\doteq \\max_{\\pi} v_{\\pi}(s)`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":245,"value":"md`The **optimal action-value function**:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":252,"value":"tex.block`\n\\begin{aligned}\n\nq_{*}(s, a) &\\doteq \\max_{\\pi} q_{\\pi}(s, a) \\\\\n\t&= \\mathbb{E}[R_{t+1} + \\gamma v_{*}(S_{t+1}) | S_{t} = s, A_{t} = a ]\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":85,"value":"md`### Iterative Policy Evaluation\n\nSutton & Barto, section 4.1, p.60-61\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":119,"value":"md`The Bellman value equation now changed into an update rule:`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":87,"value":"tex.block`\n\\begin{aligned}\n\tv_{k+1}(s) \n\t\t&\\doteq \\mathbb{E}_{\\pi}[R_{t+1} + \\gamma v_{k}(S_{t+1}) | S_{t} = s ] \\\\\n &= \\sum_{a} \\pi(a|s) \\sum_{s', r} p(s',r \\mid s, a)[r + \\gamma v_{k}(s')]\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":121,"value":"md`\n* Input π, the policy to be evaluated \n* Initialize an array ${tex`V(s) = 0 , \\forall s \\in S^+`}\n* Repeat\n * ${tex`\\Delta \\leftarrow 0`}\n * For each s ∈ S:\n * ${tex`v \\leftarrow V(s)`}\n * ${tex`V(s) \\leftarrow \\sum_a \\pi(a|s) \\sum_{s',r} p(s',r|s,a)[r + \\gamma V(s')]`}\n * ${tex`\\Delta \\leftarrow max(\\Delta, |v - V(s)|) `}\n\n* until ${tex`\\Delta < \\theta`} (a small positive number) \n* Output ${tex`V \\approx v_{\\pi}`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":258,"value":"md`### Policy iteration\n\nBasically, this means alternating between:\n* *policy evaluation* using the above procedure, and\n* *policy improvement* via picking the new best action for each state given the updated value\n\n...until convergence, where the policy no longer changes -- sort of like EM.\n\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":290,"value":"md`### Value iteration\n\nThis is basically the same as policy iteration, but it does not wait for the policy evaluation step to converge; rather, it stops after one round (update of each state).`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":292,"value":"tex.block`\n\\begin{aligned}\n\tv_{k+1}(s) \n\t\t&\\doteq \\max_{a} \\mathbb{E}[R_{t+1} + \\gamma v_{k}(S_{t+1}) | S_{t} = s, A_{t} = a ] \\\\\n &= \\max_{a} \\sum_{s', r} p(s',r \\mid s, a)[r + \\gamma v_{k}(s')]\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":295,"value":"md`This is the Bellman *optimality* equation turned into an update rule.`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":300,"value":"md`### Generalized policy iteration\n\nSutton and Barto, p.70:\n\n> Almost all reinforcement learning methods are well \t\ndescribed as GPI. That is, all have identifiable policies and value functions, with the policy always being improved with respect to the value function and the value function always being driven toward the value function for the policy.\n\n> [...]\n\n> The evaluation and improvement processes in GPI can be viewed as both competing and cooperating. They compete in the sense that they pull in opposing directions. Making the policy greedy with respect to the value function typically makes the value function incorrect for the changed policy, and making the value function consistent with the policy typically causes that policy no longer to be greedy.\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":314,"value":"md`# Monte Carlo methods (model free)\n\n- Sutton & Barto chapter 5\n- Silver lecture 4 & 5\n\n## MC prediction: _v_π (s)_\n\nEstimate/learn the state-value function, i.e. the expected returns from each state if following a given policy. \n\nMC prediction/policy evaluation substitutes _empirical mean_ return for _expected_ return.\n\nThe return \n_G_t_ \nfor a given episode/Monte Carlo sample is an **unbiased** estimate of the state-value _v_π(S_t)_\n\nFor first-visit MC, the return on each visit is an IID estimate of v_π(s)\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":357,"value":"md`### MC prediction with incremental updating\n\n${tex.block`\n V(S_t) \\leftarrow V(S_t) + \\alpha (G_t - V(S_t)) \n`}\n\nwhere\n\n${tex.block`\n \\alpha = \\frac{1}{N(S_t)}\n`}\n\n...or, in general, α could be anything\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":360,"value":"md`### MC estimation of action values: _q_π (s,a)_\n\nS&B chapter 5.2, p.79\n\nThe state-value function is only useful given a model of the system dynamics. In the absence of a model, it's better to estimate state-action pairs _q_π(s,a)_.\n\nWith state-action pairs, however, we have the exploitation vs. exploration problem that we didn't have with just state values, since for example a deterministic policy will only ever pick one action, so we never visit the other alternatives. \n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":400,"value":"md`Exploring starts: each action from the initial state has non-zero probability`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":372,"value":"$4a","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":526,"value":"$4b","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":679,"value":"$4c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":783,"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":829,"value":"$4d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":819,"value":"$4e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":863,"value":"md`# Value function approximation\n\nSilver lecture 6\n\nReplace lookup table with function approximation:\n\n${tex.block`\n\\begin{aligned}\n\t\\hat{v}(s, \\mathbf{w}) &\\approx v_\\pi(s)\t\\\\\n\t\\hat{q}(s, a, \\mathbf{w}) &\\approx q_\\pi(s, a)\n\n\\end{aligned}\n`}\n\n- Note that this enables generalization from seen states to unseen states\n- Use MC or TD learning to learn __w__\n\n${tex.block`\n\\begin{aligned}\n\ts &\\overset{\\mathbf{w}}{\\longrightarrow} \\hat{v}(s, \\mathbf{w})\t\\\\ \\\\\n\t(s,a) &\\overset{\\mathbf{w}}{\\longrightarrow} \\hat{q}(s, a, \\mathbf{w})\t\\\\ \\\\\n\ts &\\overset{\\mathbf{w}}{\\longrightarrow} \n \\begin{bmatrix}\n \\hat{q}(s, a_1, \\mathbf{w})\t\\\\\n \\vdots\t\t\t\t\t\t\t\\\\ \n \\hat{q}(s, a_m, \\mathbf{w})\n \\end{bmatrix}\n\\end{aligned}\n`}\n\nFunction approximator must work for non-stationary, non-iid data (since that's what RL is about)\n`\n","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":992,"value":"$4f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":995,"value":"md`### Batch RL\n\nGains sample efficiency than online methods like stochastic gradient descent\n\n#### Least squares prediction\n\nConsider experience as a dataset of ${tex``} pairs:\n\n${tex.block`\nD = { , , ... }\n`}\n\nFind __w__ by minimising sum-squared error:\n\n${tex.block`\nLS(\\bold{w}) = \\sum_{t=1}^T (v_T^\\pi - \\hat{v}(s_t, \\bold{w}))^2\n`}\n\n#### SGD with experience replay\n\nSame as online SGD but sample ${tex``} from experience _D_; converges to least squares solution.\n\n#### Deep-Q-Networks with experience replay\n\n* consider experience instead as a dataset of transitions ${tex``} \n* sample minibatch from D and run SGD\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1016,"value":"md`# Policy gradient\n\nSilver lecture 7\n\n(from Jonny Hyman's Youtube comment:)\n\n> For those confused: \n> - whenever he speaks of the u vector he's talking about the θ vector (slides don't match). \n> - At 1:02:00 he's talking about slide 4.\n> - At 1:16:35 he says ${tex`\\hat{V}`} but slides show ${tex`V_v`} \n> - He refers to Q in Natural Policy Gradient, which is actually ${tex`G_\\theta`} in the slides\n> - At 1:30:30 the slide should be 41 (the last slide), not the Natural Actor-Critic slide\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1086,"value":"$50","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1038,"value":"md`\n## objective functions\n\nFor policy ${tex`\\pi_\\theta(s, a)`}, maximize ${tex`J(\\theta)`}:\n\nStart value:\n\n${tex.block`\nJ_1(\\theta) = V^{\\pi_\\theta}(s_1) = \\mathbb{E}_{\\pi_\\theta}[v_1]\n`}\n\nAverage value:\n\n${tex.block`\nJ_{avV}(\\theta) = \\sum_s d^{\\pi_\\theta}(s) V^{\\pi_\\theta}(s)\n`}\n\nAverage reward per time step:\n\n${tex.block`\nJ_{avR}(\\theta) = \\sum_s d^{\\pi_\\theta}(s) \\sum_a \\pi_\\theta(s, a) R_s^a\n`}\n\n${tex`d^{\\pi_\\theta}(s)`} is the stationary distribution of the Markov chain for ${tex`\\pi_\\theta`}\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1064,"value":"$51","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1102,"value":"viewof btn = html``","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1104,"value":"dotStyles = ({ defaults: `\n graph [\n labelloc = \"b\",\n fontname=\"Times\",\n fontsize=12,\n overlap=false ];\n\n node [\n style=filled,\n shape=circle,\n colorscheme=accent5,\n color=1,\n fontname=\"Times\",\n fontsize=12];\n\n edge [\n fontname=\"Times\",\n fontsize=12,\n margin=2,\n overlap=false ];\n` })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":128,"value":"dot = {\n const Viz = await require(\"https://unpkg.com/viz.js@1.8.0/viz-lite.js\").catch(() => window.Viz);\n return function(strings) {\n let string = strings[0] + \"\", i = 0, n = arguments.length;\n while (++i < n) string += arguments[i] + \"\" + strings[i];\n string = Viz(string);\n return html([string.slice(string.indexOf(\"