Reinforcement Learning {#sec:afs}
=======================================================

Preliminaries {#sec:preliminaries}
-------------

### Reinforcement Learning {#sec:rl}

Reinforcement Learning (RL) is family of algorithms aimed at solving Markov Decision Processes (MDPs). A MDP is represented as a tuple $(\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma)$, where $\mathcal{S}$ is a set of states (also called state space), $ \mathcal{A}$ is a set of actions (also called action space), $\mathcal{P}$ is a set of state transition rules $$\mathcal{P}(s', s, a) = \mbox{Prob}(S_{t+1} = s' | S_t = s, A_t = a),$$ specifying the distribution over the state space for the next state given a current state and action, $\mathcal{R}:\mathcal{S}\times \mathcal{A} \rightarrow \mathbb{R}$ is a reward function and $0 < \gamma \le 1$ is a discount factor.

The RL paradigm consists of two major elements: an agent and an environment. The agent follows a policy, defined as a function $ \pi:\mathcal{S} \rightarrow \mbox{dist}(\mathcal{A})$ which maps each state to a distribution over the action space. Doing so, it interacts with the environment by choosing actions from $\mathcal{A}$ that may let it move between states. At each step $t$ of the episode, being in state $s_t$, the agent chooses an action $a_t$ from $\pi(s_t)$, obtains a (negative, zero or positive) reward $r_t=\mathcal{R}(s_t, a_t)$ 