https://www.youtube.com/watch?v=2GwBez0D20A&list=PLwRJQ4m4UJjNymuBM9RdmB3Z9N5-0IlY0&index=1 # Questions - How to best handle multi-optimization problems? Static weighting of rewards? Multiple agents? - What if there's a partial order of actions or non-determinism for choosing the "best" action vs always having a best action. # Rough history - 2013 Deepmind DQN for games like Atari - 2014 Berkeley TRPO for robotics - 2015 Deepmind AlphaGo - 2016 Berkeley TRPO+GAE 3D locomotion, GPS/Brett real robot - 2017 OpenAI PPO Dota2 - 2018 Berkeley DeepMimic - 2019 DeepMind AlphaStar - 2019 OpenAI PPO+DR Rubik's Cube # Lecture 1 - Motivation - Markov Decision Processes (MDPs) - Exact Solution Methods - Value iteration V* and Q* - Policy Iteration - Maximum Entropy Formulation # Markov Decision Processes (MDPs) - Agent is in an env - Chooses and takes an action - Env changes - Reward associated with that action / state change Def: $MDP(S,A,T,R,\gamma, H)$ is a Markov decision process s.t. - S:set states - A:set actions - transition(s:S,a:A) -> S defines a probability `P(s'|s, a)` ie the probability that given a transition from state `s` to `s'` the agent to action `a` - reward `R(s,a,s') -> ?` - s0:S start state (or start state distribution) - $\gamma$ discount factor adjusts for present day reward vs future reward - $H$ horizon - over how long goal is to maximize the expected reward over time $ max_{\pi} E\left[ \sum_{0}^H{\gamma^t R(S_t, A_t, S_{t+1})} | \pi \right] $ # Exact Solution Methods ## Value Iteration One way to solve this is with value iteration $V^*$ (Bellman Update) starting with H=0,1,... Thm: Value iteration converges to the optimal value function for the discounted infinite horizon problem, which satisfies the Bellman equations ![[_Media/Markov Decision Process Value Iteration.png]] Since it's stationary, we don't need to store an action x state x all time, just an action for each state. ## Q-values Q-values $Q^*(s,a)$ is the expected utility of starting in state $s$ and taking action $a$ (and acting optimally after that). ie the expected value of having committed to an action. ![[_Media/Markov Decision Process - Q value.png]]![[_Media/Markov Decision Process - Q-value iteration.png]] Q-values nice because it's easy to read off the optimal action at any state. ## Policy Iteration For smaller MDPs it's very tractable to iterate over all states / values to converge on an exact solution over an infinite horizon given an optimal policy. Sometimes it's convenient to iterate on the policy to find the optimal policy (choice of action) to take at each step. Often converges faster than value-iteration. Policy evaluation + Policy Improvement (with 1 step lookahead) For a given policy $\pi$ we can calculate the expected reward. ![[_Media/Markov Decision Process - Policy Evaluation.png]] ![[_Media/Markov Decision Process - Policy Iteration.png]] ## Max entropy formulation What if instead of finding the single most-optimal policy, we could find the distribution over near-optimal solutions. Motivation - more robust policy: if the environment changes (but it's a smooth / local / small change) a good assumption might be that the distribution over near-optimal solutions still contains a good one. Motivation - more robust learning: If you're forming a distribution, you can use past training (runs / examples) as a prior. In the real word, active learning will happen e.g. gather data or intervene, improve policy, gather more data, ... **Entropy** - The measure of uncertainty over a random variable X - The number of bits required to encode X (on average) [[Entropy]] **Max Entropy MDP** ![[_Media/Markov Decision Processes - Max Entropy Formulation.png]] - With a deterministic policy, H(pi) == 0 ie becomes just like value-iteration. - Otherwise, we have a distribution over policies (ie a distribution over choice of actions) - Note that on the surface there's a tradeoff between maximizing reward or maximizing entropy. But recall "more robust learning" - on very complex problem spaces. Favoring some policy entropy will keep encourage exploring more in earlier learning. One way to solve this is with constraint optimization (e.g. by min-maxing the Lagrangian). # Lecture 2 - Deep Q-Learning Exact methods have limitations - Requires access to the dynamics model (state transitions) -> sampling-based approximations - Works for smaller state-spaces because they need to iterate over all states and actions. Impractical for larger MDPs -> Q/V function fitting **Outline** - Q-Learning - Deep Learning / Neural Nets - Deep Q Networks (DQN) ## (Tabular) Q-Learning - Q-value iteration (assumes access to the transition model and the ability to iterate) - We can re-write the Q-Value iteration as an expectation distributed according to probability $P(s'|s, a)$ - In tabular Q-Learning, we replace the expectation with sampling - can keep a an exponentially moving weighted average as we draw samples to approximate the expectation ![[_Media/Tabular Q-learning - concepts.png]] Action Sampling approaches - Random action - greedy - action that maximizes $Q_k(s,a)$ - $\epsilon-Greedy$ choose random action with probability $\epsilon$, otherwise choose greedily. ie allows for exploration while sampling the dynamics of the system Properties of Q-learning - Q-Learning converges to optimal policy (even if you're acting sub-optimally) aka off-policy-learning Caveats - You have to explore "enough" - need to eventually shrink the learning rate to be "small enough"... but not too quickly ![[_Media/Q-learning rate.png]] Tabular methods don't scale - Tetris 10^60 states - Atari 10^308 (ram) 10^16992 (pixels) - Continuous environments with crude discretization - 2d crawler 10^2 - 3d Hopper 10^10 - Humanoid 10^100 ## Approximate Q-Learning Instead of a table, we have a parameterized Q function $Q_\theta(s,a)$ - traditionally, Q-func was a weighted sum of features - neural net, decision tree etc ![[_Media/Approximate Q learning deep neural net update rule.png]] ## Deep Q Networks (DQN) DQN (DeepMind atari 2013) was a breakthrough for deep-Q learning ![[_Media/DQN Training Algorithm.png]] - Also uses a Huber Loss instead of squared loss on the Bellman error - RMSProp instead of SDG. RL is more sensitive to optimization choices (e.g. how much we explore vs how we shrink the learning rate over time) - anneal exploration rate form 1 to 0.1 or 0.05 over the first million frames Improvements - Double DQN (DDQN): keep 2 sets of weights $\theta$ to reduce over-estimation and stabilize training - almost all approaches are DDQN these days - Prioritized Experience Replay - "Rainbow: combining Improvements in Deep Reinforcement Learning" Matteo Hessel et al 2017. Combines multiple approaches to achieve (at the time) state of the art. - Double DQN (DDQN) - Prioritized Replay DDQN - Dualing DQN - Distributional DQN - Noisy DQN