In real life applications, the state space and action space which Reinforcement Learning is based on are usually very complicated. It is extremely hard to solve the problems with simple policy and value iterations. So we may need the help of deep learning to model the environment, the policy and the value functions. 
Recently, deep reinforcement learning enjoys the current state-of-art performance, which utilizes the popular neural networks. 

University of Michigan - Ann Arbor

Reinforcement learning is a general approach to solve reward-based problem. The building of it is based on mathematical foundations. We can also view it as a sequential decision making and control problem mathematically. For example, when driving a car, we need to make decisions about turning left/right or going straight after the previous decisions. And the key ingredient in reinforcement learning is Markov Decision Process.

Math Behind Reinforcement Learning

https://cims.nyu.edu/~donev/Teaching/WrittenOral/Projects/XintianHan-WrittenAndOral.pdf
https://www.davidsilver.uk/teaching/     
(David Silver's tutorial of reinforcement learning)
http://rail.eecs.berkeley.edu/deeprlcourse/
https://katefvision.github.io/
http://incompleteideas.net/rlai.cs.ualberta.ca/RLAI/RLAIcourse/RLAIcourse2006.html
http://web.stanford.edu/class/cs234/schedule.html

Useful Tutorials about Math behind Reinforcement Learning

A Markov Process is a tuple (S,P), where
• S is a (finite) set of states
• P is a state transition probability matrix. $P_{ss'} = P[S_{t+1}=s'|S_t = s]$.

We make some constrains on states. 
A sequence of states is Markov if and only if the probability of moving to the next state $S_{t+1}$ depends only on the present state $S_t$ and not on the previous states $S_1, S_2, · · · , S_{t−1}$. That is, for all t,
$P[S_{t+1}|S_t] = P[S_{t+1}|S_1, S_2, · · · , S_t].$
In reinforcement learning, Markov Process is time-homogeneous. That is, the probability of the transition is independent of t:
$P[S_{t+1} = s'|S_t = s] = P[S_t = s'|S_{t−1} = s]$.


Markov Process

A Markov decision process is a tuple (S, A,P, γ, R), where:
• S is a finite set of states.
• A is a finite set of actions.
• P is the state transition probability matrix, $P^a_{ss'} = P[S_{t+1} = s'|S_t = s, A_t = a]$.
• γ ∈ $[0, 1]$ is called the discount factor.
• R : S × A → R is a reward function.

The dynamic of Markov Decision Process proceeds as follows: 
We start in some state $s_0$, and choose some actions $a_0 ∈ A$ to take. As a result of our choice, the state of the Markov Decision Process randomly transits to some successor state $s_1$, drawn from $P^{a_0}_{s_0s_1}$. Then, from state $s_1$, we pick another action $a_1$. Again, we come to some state $s_2$, and so on.

Markov Decision Process

Our final goal is to choose actions over time so that we could maximize the expected value of the return. The definition of return is as below:
The return $G_t$ is the total discounted reward from time-step t.
$G_t = R_{t+1} + γR_{t+2} + · · · = \sum_{k=0}^{∞}γ^kR_{t+k+1}$, where γ is the discounted factor.
When γ close to 0 leads to “myopic” evaluation; γ close to 1 leads to “far-sighted” evaluation.

Return

Limitations of Reinforcement Learning

A policy decides which action is selected by the agent at some state. Two criteria can be used to classify policies.

First, depending on whether policy is time-dependent or not, we can categorize them as either stationary or non-stationary. If the cumulative rewards the agent aims to optimize are limited to a finite number of future steps, we could use non-stationary policies. But in most cases, we will use stationary policies.

Second, policies can also be categorized under the criterion of being either 
deterministic or stochastic. In the deterministic case, what action will be taken at some certain state is determined. In the stochastic case, given the action and state, the policy will return the probability that action a may be chosen in state s.

Policy

In reinforcement learning, value functions are crucial for estimating the long-term desirability of states or actions. They quantify the expected return, which is the total accumulated reward an agent anticipates. The two main types are:

1.  **State-Value Function ($v_\pi$)**: Also known as the **value function**, this assesses the expected discounted return (i.e., accumulated rewards) for an agent starting from a particular state 's' and following a specific policy 'π'. The expectation is performed over all possible trajectories originating from that state.

2.  **Action-Value Function ($q_\pi$)**: Also known as the **Q-value function**, this measures the expected return if an agent begins in state 's', performs action 'a', and subsequently adheres to policy 'π'.

A key element in these calculations is the discount factor, $\gamma$ (where $0 \le \gamma \le 1$), which adjusts the importance of future rewards.

State-Value and Action-Value Functions

A state-action sequence, or trajectory (τ), documents the path an agent takes through an environment. While the core concept is consistent, the notation used to represent these sequences can vary. For instance, a trajectory may be denoted as starting from time step 1, such as τ = {(s₁, a₁), (s₂, a₂), ...}, often to align with other notation in a specific context, like sequence prediction. Alternatively, it is common in reinforcement learning literature to see trajectories starting from time step 0, with varying lengths, such as τ = {(s₀, a₀), ..., (sT, aT)} or τ = {(s₀, a₀), ..., (sT-₁, aT-₁)}. These notational differences are a matter of convention and do not alter the fundamental principles or models being discussed.

Learn Before

Related