Notes

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.