Notes

Content of the Lecture

• Introduction to Reinforcement Learning
  • Reinforcement Learning and the Brain.
  • Example of RL Neuroscience Experiments.
  • The Rescorla-Wagner Rule.
  • The Temporal Difference Rule.
  • The Basic Idea of Q-Learning.
• Reinforcement Learning in Machines
  • Basic Components of RL.
  • Policy and Value Function Based RL.
  • MC, MRPs and MDPs.
  • The Problem of Finding the Optimal Policy.
  • The Bellmann (Expectation) Equation.
  • RL and Deep Q-Learning.

Introduction - Reinforcement Learning & the Brain

What is Reinforcement Learning? Reinforcement Learning fuses ideas from neuroscience and AI. The model describes how an agent can interact with an environment and in that environment learn to improve its actions when it comes to gathering a targeted reward.

What makes reinforcement learning different from other machine learning paradigms?

• There is only a reward/supervision signal after each action.
• Feedback is often delayed and not instantaneous.
• Time needs to be taken into account.
• The agent's actions affect the subsequent data it receives.

Dopamine: Reward Prediction Error Papers: "Predictive Reward Signal of Dopamine Neurons"

From Schultz (89): "Dopamine neurons are activated by rewarding events that are better than predicted, remain uninfluenced by events that are as good as predicted, and are depressed by events that are worse than predicted. Most dopamine neurons show phasic activations [...] reward-predicting [...] However, only few phasic activations follow aversive (causing avoidance of a thing) stimuli. By signalling rewards according to a prediction error, dopamine responses have the formal characteristics of a teaching signal postulated by reinforcement learning theories."

If the neocortex mostly performs unsupervised learning why does the VTA strongly project to almost all cortical areas and what is the effect of DA on a cortical neuron?

• Ventral structure does not project to dorsal (where we assume RL is happening).
• Gated reinforcement learning: we only want to learn relevant information.
• Dopamine is connected to plasticity because it is very sensitive to new/unseen data.

The figure above pictures an animal experiment: Dopamine neurons report rewards according to an error in reward prediction. Top: drop of liquid (reward) occurs although no reward is predicted at this time. Middle: conditioned stimulus predicts a reward, and the reward occurs according to the prediction, hence no error in the prediction of reward. Bottom: conditioned stimulus predicts a reward, but the reward fails to occur because of lack of reaction by the animal. (CS = Conditioned Stimulus; R = Primary Reward).

The predicted reward is further modified by other factors:

• Timing of Reward: Across species, it is clear that signals related to prediction errors are modulated by cues that predict delayed reward. Animals prefer an immediate reward over a delayed reward even when the delayed reward is more economically valuable in the long run. Paper: "Impact of Size and Delay on Neural Activity in the Rat Limbic Corticostriatal System".
• Adaptation to a New Situation: We found that midbrain dopamine neurons rapidly adapted to the information provided by reward-predicting stimuli. Responses shifted to the expected reward value, and the gain adjusted to the variance of reward value. Paper: "Adaptive Coding of Reward Value by Dopamine Neurons".

Models of Learning Reward Prediction Even though these models here are called predicting models, we are looking at update rules which means the system changes over time -- it learns. We might connect one of these learning rules to a MDP or RL to find an optimal behavior function for our agent.

Rescorla - Wagner Rule

Rescorla Wagner Rule Model of classical conditioning in which learning is conceptualized in terms of associations between conditioned and unconditioned stimuli. Change in value $V\left( s_{t} \right)$ is proportional to the difference between actual and predicted reward.

$$V\left( s_{t} \right) \leftarrow V\left( s_{t} \right) + \eta\left\lbrack R - sum\left( V\left( s_{t} \right) \right) \right\rbrack$$

where: $s_{t}$ is the stimulus, $V\left( s_{t} \right)$ is the associative strength of conditioned stimulus $s_{t}$, R is the reward, $\eta$ is the learning rate, $sum\left( V\left( s_{t} \right) \right)$ is the sum of associative strengths of all conditioned stimuli (including $s_{t}$) that are presented on this trial (the n-th trial) and $|\left\lbrack R - sum\left( V\left( s_{t} \right) \right) \right\rbrack|$ is the surprise.

Two assumptions/hypotheses:

• Learning is driven by the error signal (formalized as notion of surprise).
• Summation of predictors is linear.

Temporal Difference Rule & Q-Learning

Temporal Difference (TD) Rule to Q-Learning Key Idea of the Temporal Difference Rule (TDR): update the value of the current state based on the immediate reward and the estimated value of the next state. Interpretation: we must not look only at immediate rewards but future rewards should be taken into consideration as well on a discounted valuation. We assume that the path our agents takes to navigate the system is given.

$$V\left( s_{t} \right) \leftarrow V\left( s_{t} \right) + \eta\left\lbrack r_{t + 1} + \gamma V\left( s_{t + 1} \right) - V\left( s_{t} \right) \right\rbrack$$

where $V\left( s_{t} \right)$ is the previous estimate, $r_{t + 1}$ is the next reward, $\gamma V\left( s_{t + 1} \right)$ is the discounted value on the next step and $r_{t + 1} + \gamma V\left( s_{t + 1} \right)$ represents the TD target.

Lets now include the fundamental concept of an action to this equation. This adds one dimension to the value function and gives the agent a choice. This new function is called $Q(s,\ a)$

$$Q(s,\ a) = \mathbb{E}_{(r',\ s')|s,a}\lbrack r + \gamma\max_{a^{'}}\lbrack Q(s',\ a')\rbrack\rbrack$$

By just a few trivial steps one can show that the TD rule is used to get the convex combination in the Q-Learning update rule between old and new Q value seen in the literature:

Given this rule, we can create and update a map over future states and actions. We can optimize w.r.t. the action to get an optimal path (policy). The key idea is that we do not need to know any transition probabilities to learn (model), we just need an unbiased estimate from out world (sample). We can get these samples by just playing the "game". If we store the actions a and rewards r from these samples, we can directly apply Q-learning. Thus, Q-learning is considered model-free. Keep in mind that (in the end), the optimal policy can be deducted from the optimal value function V*:

$$V^{*}(x) = max_{a}Q^{*}(x,a)$$

Basic Components of Reinforcement Learning - Policy & Value Functions

Introduction to Reinforcement Learning

We saw the concept of looking at expected reward and choosing actions to maximize this reward, but the idea was not well embedded into a generalizing concept. Reinforcement Learning (RL) exactly puts a name on this framework, which includes Q-Learning as well. RL is about an agent taking suitable action to maximize reward in a particular situation. It is employed by various software and machines to find the best possible behavior or path it should take in a specific situation.

In the pictures: influences from and to the agent in RL to the surrounding world. At each step t, the agent executes an action $A_{t}$ which the environment receives. The agent receives an observation $O_{t}$ of the environment, for example through a sensor and the agent is rewarded $R_{t}$ by its behavior from the environment.

Reinforcement Learning is based on the reward hypothesis: All goals of an agent can be described by the maximization of expected cumulative reward. A reward $R_{t}$ is a scalar feedback signal. It indicates how well the agent is doing at step t. The agent's job is to maximize cumulative reward.

Example rewards:

• Fly stunt maneuvers in a RC helicopter (+ following desired trajectory, - crashing).
• Defeat the world champion at Backgammon (+ winning, - loosing).
• Manage an investment portfolio (+ more, - less money).
• Making a humanoid robot walk (+ reward for forward motion, - reward for falling over).
• Play Atari games better than human (+ reward for increasing score, - reward for decreasing score).

The Goal is to select actions that maximize total future rewards:

• Actions may have long-term consequences.
• Reward may be delayed.
• It may be better to sacrifice immediate reward to gain more long-term reward.
• For example: a financial investment may take months to mature, re-fuelling an helicopter might prevent a crash in several hours, blocking an opponent move might help winning chances many moves from now.

The fact that reward presented to the agent is not always immediate leads to the exploration/exploitation dilemma. An agent does not intrinsically know the future implications of its actions, or the dynamics of the environment.

The Agent State

At each point in time, the agent is in a state, because this information state is all that is necessary to fully determine the agent, it is also said that the state is markovian. This means we can throw away the history ($H_{t})$ of previous actions, observations and rewards:

$$H_{t} = A_{1}O_{1}R_{1},\ldots,A_{t}O_{t}R_{t}$$

• The agent state $S_{t}$ is the agent's internal representation:
  • Whatever information the agent uses to pick the next action.
  • It is the information used by RL algorithms.
• It can be any function of the history: $S_{t} = f(H_{t})$.

For the reasons explained above: $P\left( S_{t + 1} \middle| S_{t} \right) = P\left( S_{t + 1} \middle| S_{1:t} \right)$. An RL agent may compute different functions on top of its state. An RL agent may include one or more of these components:

• Policy: The agent's behavior function.
• Value Function: How good is each state and/or action?
• Model: The agent's representation of the environment.

Policy The agents behavior function called policy maps from state s to action a. The policy may be stochastic or deterministic:

• Deterministic Policy: $a = \pi(s)$
• Stochastic Policy: $\pi\left( a|s \right) = P\left( A_{t} = a \middle| S_{t} = s \right)$

Value Function The value function is a prediction of future rewards and does so by assigning a number to every state s, it is used to evaluate the goodness/badness of states. It depends on a policy $\pi$ to determine where the agent could go and a probability distribution $p\left( X^{'} \middle| \pi(X),X \right)$. We compute this value as an expectation over the joint distribution: $p\left( S_{1},S_{2},S_{3},\ldots \right)$.

The value function is defined as: $$v_{\pi}\mathbb{= E}\left\lbrack r\left( s_{0},\pi\left( s_{0} \right) \right) + \gamma r\left( s_{1},\pi\left( s_{1} \right) \right) + \gamma^{2}r\left( s_{2},\pi\left( s_{2} \right) \right) + \ldots \right\rbrack$$

In the lecture slides is formulated as:

Model A model predicts what the environment will do next. From the previous section we see that we require a probability distribution that depends on direct actions a or a policy returning action $\pi$:

$$P_{s_{t},s_{t + 1}} = p\left( S_{t + 1} = s_{t + 1} \middle| S_{t} = s_{t},\pi\left( s_{t} \right) \right) = p\left( S_{t + 1} = s_{t + 1} \middle| S_{t} = s_{t},A_{t} = a_{t} \right)$$

That predicts the next (immediate) reward:

$$R_{s_{t}}\mathbb{= E}\left\lbrack R_{t + 1} \middle| S_{t} = t,A_{t} = a_{t} \right\rbrack$$

In the lecture slides is formulated as:

where P predicts the next state and R predicts the next (immediate) reward.

This is called the model. Model free RL uses tricks to not compute/require this distribution. As it is often intractable (Imagine the state space being the input of a video game).

In the image, a small example of a mice showing all the agent related components together with some numbers. (Top left) Actions, start, end and definition of other states (the maze). (Top right) Immediate rewards. (Bottom) Policy and Value Function for each state.

• Agent may have an internal model of the environment.
• Dynamics: How actions change the state.
• Rewards: How much reward from each state.
• The model may be imperfect.
• Grid layout represents transition model $P_{s_{t},s_{t + 1}}^{a}$
• Numbers (top right) represent immediate rewards $R_{s_{t}}^{a}$ from each state s.

We have seen different RL-subtypes that need to be distinguished. Comment: from the Bellman Theorem we know that every value function induces a policy and every policy induces a value function:

• Value Based vs Policy Based
  • Value Based
    • No Policy (Implicitly given by value function, see Bellman Eq.)
    • Value Function
  • Policy Based
    • Policy
    • No Value Function (Even though values can be computed off a policy).
• Model Free vs Model Based
  • Model Free
    • Policy and/or Value Function
    • No Model distribution needed
  • Model Based
    • Policy and/or Value Function
    • Model distribution needed.

A more sophisticated example is represented by the Atari Games. The Atari video-gaming platform provides an ideal environment to test RL/Planning strategies. For some games, we don't know the rules and apply RL. This means we learn directly from interactive gameplay. Pick actions on a joystick and observe the pixels. For other games we know the rules. This allows to apply planning strategies where we might ask ourselves: What would the next state be? What would the score be? We can query the future by tree search to some extent.

Planning Even though planning appear later in the lecture it is actually the logical step before we arrive at RL. It is a more constrained view where a model of the environment is known. The agent performs computations with its model (without any external interaction). This is a simplification compared to RL where the environment is initially unknown and the agent may only discover it. By interacting with the environment. In RL, the agent improves its policy or value function. If the agent/solver has access to the model, i.e., $p(s'|s,a)$ and $r(s,a)$, and it employs it when optimizing the MDP, then we are in the planning settings (or dynamic programing, DP, setting). Otherwise, we are in the RL settings. Of course, sometimes, even though we have access to the model, still we do RL since it is hard to solve directly the MDP, and we prefer to interact with the MDP rather than solving it, i.e., we ignore the model. In a planning scenario, we can query the future through the emulator. We can therefore play/plan ahead to find the optimal policy by tree search. As already mentioned, this might not be possible even for simple games. RL on the other hand can be as well referred to as "trial-and-error" learning. However, obviously we try to guide the agent to lose the least amount of reward that is possible.

Exploration / Exploitation Everyone is confronted with the same dilemma on a daily basis: should I keep doing what I do, or should I try something else. For example should I go to my preferred restaurant or should I try a new one, should I keep my current job or should I find a new one, etc...

In Reinforcement Learning, this type of decision is called exploitation when you keep doing what you were doing, and exploration when you try something new.

• Exploration finds more information about the environment.
• Exploitation exploits known information to maximize reward. It is usually important to explore as well as exploit.

Basics Remark: In my opinion these chapters build the foundation for RL but in the lecture they appear after RL and thus I kept that order. If you are a beginner to these topics, I highly recommend to gain some basic knowledge about probabilistic graphic models (PGM) (Bayesian Networks) first. They are used from here on, but were not introduced explicitly in the lecture.

Markov Chains (MC), Markov Reward Processes (MRPs) & Markov Decision Processes (MDPs)

Markov Chain (MC) A Bayesian Network is a kind of PGM that uses a directed (acyclic) graph to represent a factorized probability distribution and associated conditional independence over a set of variables.

Definition: A state $S_{t}$ is Markov if and only if:

$$P\left( S_{t + 1} \middle| S_{t} \right) = P\left( S_{t + 1} \middle| S_{1:t} \right)$$

where $s_{t}$ is the current state and $s_{t + 1}$ is the successor state.

The state captures all relevant information from the history. Once the state is known, the history may be thrown away. This means that the state is a sufficient statistic of the future.

The state transition matrix P defines transition probabilities from all states $m = s_{t}$ to all successor states $n = s_{t + 1}$: (Left) An example Markov Chain showing all state transition probabilities next to its node. (Right) The corresponding state transition matrix and results of a sampling procedure applied to this Markov chain. Be aware that this is not a PGM, the nodes are not random variables.

Markov Reward Process (MRP) A Markov reward process is a stochastic process which extends a Markov chain by adding a reward rate to each state. Definition: A Markov Reward Process is a tuple $(S,P,R,\gamma)$ where S is a finite set of states, P is a state transition probability matrix $P_{t,t + 1} = P\left( S_{t + 1} \middle| S_{t} \right)$, $R = \mathbb{E}\left\lbrack R_{t + 1} \middle| S_{t} = s \right\rbrack$ is a reward function and $\gamma$ is a discount in the interval (0,1).

Facts:

• Mathematically convenient to discount rewards. It avoids infinite returns in cyclic Markov processes.
• Uncertainty about the future may not be fully represented.
• If the reward is financial, immediate rewards may earn more interest than delayed rewards.
• Animal/Human behavior shows preference for immediate rewards.
• It is sometimes possible to use un-discounted Markov reward processes (i.e., $\gamma = 1$), e.g., if all sequences terminate.

We call $G_{t}$ the return which is the total discounted reward from time step t onward.

$$G_{t} = R_{t + 1} + \ \gamma\ R_{t + 2} + \ldots = \sum_{k = 0}^{\infty}{\gamma^{k}R_{t + k + 1}}$$

If we just look at $G_{t}$ we must assume that we know the chain of events that lead to the specific rewards R, however the MRP is a stochastic process. Therefore we may compute the conditional value function given that we know where we start ($s_{t})$. We have seen this function before in the RL chapter:

$$v_{s_{t}}\mathbb{= E}\left\lbrack R_{t + 1} + \gamma R_{t + 2} + \gamma^{2}R_{t + 3} + \ldots \middle| S_{t} = s \right\rbrack$$

which is just

$$v_{s_{t}}\mathbb{= E}\left\lbrack G_{t} \middle| S_{t} = s_{t} \right\rbrack$$

Hence, the state value function $v(s)$ of an MRP is the expected return starting from state s. It gives the long-term value of state s.

Markov Decision Process (MDP) Markov Decision Process (MDP) is a Markov reward process with decisions (actions that we can take). It is still an environment in which all states are Markov.

Definition: A Markov Reward Process is a tuple $(S,A,P,R,\gamma)$ where S is a finite set of states, A is a finite set of actions, P is a state transition probability matrix $P_{t,t + 1} = P\left( S_{t + 1} \middle| S_{t},A_{t} \right)$, $R = \mathbb{E}\left\lbrack R_{t + 1} \middle| S_{t} = s,A_{t} = a \right\rbrack$ is a reward function and $\gamma$ is a discount in the interval (0,1).

Markov Decision Processes formally describe an environment for Reinforcement Learning where the environment is fully observable. Almost all RL problems can be formalized as MDPs.

• Partially observable problems can be converted into MDPs.
• One Armed Bandits are MDPs with one state.

The MC seen before extended to be a MRP is here extended again to be an MDP. However, we should be careful with the comparisons. In the MRP, our agent was guided purely by randomness and we had no choice. Now, the agent is able to directly influence its path. Note that some of the transitions are deterministic. For example, if we quit Facebook, we are for sure back to studying, however if were in the pub, we might be too drunk and randomness influences the outcome.

One can see that we are very close now to what we introduced in the RL section, however, one key piece is missing. Given that we have choice as an agent now, how do we know the optimal behavior?

Bellmann (Expectation) Equation

Bellman Equation The Bellman Equation (BE), named after Richard E. Bellman, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming (aka. RL when the environment is known MDP). It allows us to "solve" the MDP problem, the problem of not knowing how to act in an environment where we are able to take action.

BE in MRP In the most simple case, we can just evaluate the Bellman expectation equation in an MRP where we have no policy to optimize.

This is the immediate reward $R_{t + 1}$ plus the discounted value of the successor state $\gamma v\left( S_{t + 1} \right)$. This is again close to the temporal difference rule. If we move the reward from the next state to the current one (by definition), we can pull $R_{s_{t}}$ out of it and compute the expected value through the sum and the equation becomes:

$$v_{s_{t}} = R_{s_{t}} + \gamma\sum_{s_{t + 1} \in S}^{}{P_{s_{t},s_{t + 1}}v\left( s_{t + 1} \right)}$$

In figure below, we have an example computation of the value of the red node in an MRP.

One might argue that this leads to action values by choosing the next state based on its value "score". Also this can be solved explicitly as a linear system.

BE in MDP In MDP, we must somehow include the actions. Over the entire task, the actions we take are defined to be the policy. Since we can optimize this policy, one might ask how to do this using the Bellman optimality equation.

• The state-value function $v_{\pi}(s)$ of an MDP is the expected return starting from state s, and then following policy$\ \pi$.
• The action-value function $q_{\pi}(s,a)$ is the expected return starting from state s, taking action a, and then following policy $\pi$.

We may rewrite both in a similar manner as we did in the MRP case.

And if we again shift the reward:

As you can see, the notation becomes quite tedious. From now on we use $S_{t} = s\ and\ \, S_{t + 1} = s^{'}$. The same applies to actions. In the figure below we have an example of policy based computation of the value of the red node in an MDP.

Finding the optimal action-value (Q) function We can now define the optimal value function:

$$v^{*}(s) = max\left( v_{\pi}(s) \right)$$

and the optimal action-value (q) function:

$$q^{*}(s,a) = max\left( q_{\pi}(s,a) \right)$$

You may have noticed that we depend on the policy for $v^{*}(s)$ and $q^{*}(s,a)$. An optimal policy can be found by maximizing the optimal Q-function $q^{*}(s,a)$:

There is always a deterministic optimal policy for any MDP. If we know $q^{*}(s,a)$, we immediately have the optimal policy. In the last step, this theorem allows us to assemble the Bellman optimality update equations. We now use the optimal value function ($v^{*}(s) = max\left( v_{\pi}(s) \right))$ to get the optimal Q-function:

$$q_{\pi}^{*}(s,a) = R_{t}^{a} + \gamma\sum_{s^{'} \in S}^{}P_{s,s^{'}}^{a}v^{*}\left( s^{'} \right)$$

Note that the agent has to average, because we can't choose. This is decided by the environment. Finally we may write down the Bellman optimality equations for $v^{*}$ and $q^{*}$:

Bellman figured out that our policy being optimal means that we can be greedy w.r.t these optimality equations. If we update over and over again, we will converge to a fixed point which is the optimality policy.

• The Bellman Optimality Equation is non-linear.
• No closed form solution (in general).
• Many iterative solution methods.
  • Iterative Policy Evaluation.
  • Iterative Value Evaluation.
  • Q-Learning.

Deep Reinforcement (Q) Learning

Deep Reinforcement (Q) Learning Paper: "Human-Level Control Through Deep Reinforcement Learning".

In the previous sections, distribution were always treated as discrete tables. This is not possible for large state/action spaces. Therefore, functional approximations to these functions must be found. We have already seen that deep neural networks (DNN) are function approximators in their nature. One can parametrize a policy or Q-function and use DNN to estimate its parameters directly from state space. For optimization purposes, we define a loss function. This loss follows from moving Q inside of expectation.

$$L = \frac{1}{2}\left\lbrack r + max_{a^{'}}Q\left( s^{'},a^{'} \right) - Q(s,a) \right\rbrack^{2}$$

We find the optimal action-value function $Q^{*}$ by parametrizing it with $\theta$ (make it DNN compatible).

$$Q^{*}(s,a) = max_{\pi}\mathbb{E\lbrack}r_{t} + \gamma r_{t + 1} + \gamma^{2}r_{t + 2} + \ldots|s_{t} = s,a_{t} = a,\pi\rbrack$$

and then minimize the loss w.r.t $\theta$. Comment: Often, we approximate $\mathbb{E}$ by sampling. The following represents the loss function to update the Q-learning rule:

$$L_{i}\left( \theta_{i} \right) = \mathbb{E}_{s,a,r,s^{'}\sim U(D)}\left\lbrack \left( r + \gamma max_{a^{'}}Q\left( s^{'},a^{'} \middle| \theta_{i}^{-} \right) - Q\left( s,a \middle| \theta_{i} \right) \right)^{2} \right\rbrack$$

This is again the temporal difference rule.

In the picture above we have a deep RL system trained directly from input (Atari game video output) to actions of the controlling joystick.

On-policy methods estimate the value of a policy while using it for control. In Off-policy methods, the policy used to generate behavior, called the behavior policy, may be unrelated to the policy that is evaluated and improved, called the estimation policy.

From the Sutton book: "The on-policy approach in the preceding section is actually a compromise - it learns action values not for the optimal policy, but for a near-optimal policy that still explores. A more straightforward approach is to use two policies, one that is learned about and that becomes the optimal policy, and one that is more exploratory and is used to generate behavior. The policy being learned about is called the target policy, and the policy used to generate behavior is called the behavior policy. In this case we say that learning is from data "$o \hookleftarrow$" the target policy, and the overall process is termed "$o \hookleftarrow$-policy learning".