## Basics of Reinforcement Learning We first discuss general intuition behind RL and gradually move towards a formalised definition and notation for RL. ### Reinforcement Learning is Everywhere Reinforcement learning is fundamental to the nature of learning and therefore intuitive to understand. In fact, any problems involving the notion of control (i.e., choosing the right action at the right time in order to achieve some goal) in some environment can potentially be considered as a RL problem. We as humans learn the right actions simply through experience (i.e., trial and error). ### How to model Reinforcement Learning? While humans are evolved to be rather efficient at trial-and-error-based learning, how can we build a computer programme (often called an agent) that can also learn from experience and solve problems without relying on explicitly coded instructions? What does *experience* even mean to a computer programme? This is the challenge the machine learning community has been trying to solve -- a computational account for reinforcement learning. Let's start with a simple example ([CartPole](https://gym.openai.com/envs/CartPole-v0/)) where we will introduce all the necessary concepts for us to talk about RL. Let's imagine that we are trying to design an agent that can learn how to control a cart such that the pole on top of it does not fall, shown in Figure 1.

Figure 1: Pole on a cart that we can move right or left, such that the pole should stay balanced. The goal of this example/game is for the **agent** to keep the pole standing on the cart as long as possible without loosing balance by moving the cart right or left. The more steps the agent can keep the pole balanced for, the better - step count practically represents a **reward** for playing the game well. If the pole angles by more than 15 degrees to the left or to the right or the cart moves more than 2.4 units from the center, the agent loses the game. The learning **environment** is the bounds of the game and the position of the cart as well as the pole. The current position of the pole and the cart represents the current **state** of the game. Given the current state of the game the agent needs to decide whether at a given time step it needs to move the cart to the right or left. Moving right or left represents an **action** that the agent can take at some given time step that influences the environment and brings the agent into a new state. ### Formalising Reinforcement Learning Let us formalise the different **terms** that we have just introduced into a general reinforcement learning-like problem that will help us construct an algorithmic approach to learning. The diagram below in Figure 2 is a high-level abstraction of a typical RL model applicable to most RL problems including the cart-pole example.

Figure 2: Fundamental parts of a reinforcement learning algorithm. Throughout recursive interactions, the agent can perform actions $A$ (move right or left) in order to reach different states $S$ (angling of the pole, position of the cart) in an environment (bounds of the game). A state at time step $t$ is denoted as $S_t$. A state captures the dynamic of the agent-environment interaction at a specific point in time. We denote action taken at time step $t$ as $A_t$. Every action is associated with a reward denoted as $R\_{t+1}$. In our example this is constant $+1$ for every step/state that the pole remains balanced. Note that the reward associated with action $A_t$ is received *after* the action is taken hence the subscript $t+1$. As a result of taking an action $A\_{t}$, the game also transitions to a new state $S\_{t+1}$. We will call each independent attempt at playing the game, from start to finish, an *episode* and each episode consists of multiple time steps. The algorithm might need to go through multiple episodes (100+) to learn the effective action given some state, as is the case with humans. #### Expected Rewards We need to talk a bit more about rewards. Generally, rewards act as a teaching signal that guides the agent to become better at navigating the environment. Rewards are often decomposed into two parts: short-term and long-term rewards. Short term rewards refer to the *immediate* reward ($R\_{t+1}$) an agent can get by taking a certain action. Long term rewards refer to the [*expected rewards*](https://en.wikipedia.org/wiki/Bellman_equation) the agent can potentially receive from *all* the subsequent states the current action might lead to. To master a RL problem, it is crucial that the agent does not get too caught up on short-term rewards. Given this notation and the introduction of the notion of expected reward we can contemplate a *policy* such that our agent learns to take an appropriate action $A_t$, given the state $S_t$, to maximise the expected reward. The approach that we will introduce here is Q-learning.