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

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. 

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.

Notational Variations in State-Action Sequences (Trajectories)

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.

University of Michigan - Ann Arbor

The fundamental concepts that form the basis of reinforcement learning are:

 - Agent
 - Environment
 - Action
 - State
 - Reward

The agent learns through repeated interaction with the environment. To be successful, the agent needs to:
 - Learn the interaction between states, actions, and subsequent rewards.
 - Determine which action will provide the optimal outcome.

Fundamental Concepts for 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

Here is a useful website for starters to understand reinforcement learning: https://missinglink.ai/guides/deep-learning-healthcare/tensorflow-reinforcement-learning-introduction-and-hands-on-tutorial/

Useful Website for Reinforcement learning

In reinforcement learning, the environment encompasses everything external to the agent with which it interacts. It processes the agent's action in its current state and responds by providing a reward and transitioning the agent to a new state. For example, in a physical system, the environment could be the laws of physics. From the agent's perspective, the environment often functions as a black box.

Environment in Reinforcement Learning

In reinforcement learning, a state (s) represents the current situation or configuration of the environment. It is a snapshot of all relevant information at a specific moment that the agent uses to make a decision. This information can include the agent's position, the status of other entities, and any other data that defines the current circumstances.

State in Reinforcement Learning

In reinforcement learning, the agent is the component that functions as the learner or decision-maker. It interacts with an environment by perceiving its state, performing actions, and learning from the resulting feedback. For instance, an agent could be a robot navigating a path or a trading algorithm making financial decisions. In the context of Large Language Models (LLMs), the LLM itself often serves as the agent.

Agent in Reinforcement Learning

An action is the set of all possible moves the agent can make. Agents choose from a list of possible actions. In video games, for example, the list might include: running right or left, jumping high or low, crouching or standing still.

Action in Reinforcement Learning

In reinforcement learning, a reward is a signal sent from the environment to the agent that provides feedback on an action's success. This feedback, which can be positive or negative, guides the agent's learning process by indicating the desirability of the actions taken. The agent's primary objective is to modify its policy over time to maximize the cumulative reward it receives.

Reward in Reinforcement Learning

Here is a free pdf version of a book about Reinforcement Learning:
http://incompleteideas.net/book/RLbook2020.pdf

Useful Book for Reinforcement Learning

Math Behind Reinforcement Learning

It is very challenging in the reinforcement learning to find a perfect balance between using previously used effective action(**exploitation**) and exploring new ones (**exploration**).

In order to solve this problem, simple $\epsilon$-Greedy algorithm can be used, in which we with some small probability $\epsilon$ we would select action randomly (**exploration**) and with $1 - \epsilon$ probability use previously selected effective action(**exploitation**).  

Exploration/Exploitation trade-off

Classification of Reinforcement Learning Methods

On-policy methods attempt to evaluate or improve the policy that is used to make decisions. In contrast, off-policy methods evaluate or improve a policy different from that used to generate the data. Classicla on-policy methods include Sarsa Algorithm. As a comparison, Q-learning method is a classical off-policy method.

On-policy vs Off-policy

Compared to value based methods, actor-critic methods focus on modeling the probability distribution of policies. For value-based methods, the logic is more like a greedy algorith, we want to maximize the value function for every step. As a result, we need to search through the action space to get the best action. But in actor-critic method, they are like using actor to perform actions based on the probability distribution of policies and using critics to judge the performance and adjust the probability distribution. They don't directly always choose the best action. 

Actor-Critic Methods

van Hasselt, H., Guez, A., & Silver, D. (2016). Deep Reinforcement Learning with Double Q-Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1). Retrieved from https://paperswithcode.com/paper/deep-reinforcement-learning-with-double-q

Deep Reinforcement Learning with Double Q-learning

One of the most popular reinforcement learning algorithms, known to sometimes learn unrealistically high action values since it includes a maximization step that tends to prefer overestimated values.

Q-learning

Borges, Alexandre and Arlindo L. Oliveira. “Combining Off and On-Policy Training in Model-Based Reinforcement Learning.” ArXiv abs/2102.12194 (2021): n. pag.
https://arxiv.org/pdf/2102.12194.pdf

Combining Off and On-Policy Training in Model-Based
Reinforcement Learning

MuZero is a model-based reinforcement learning method which contains a representation function, a dynamics function, and a prediction function.The representation function encodes an observation sequence into a hidden state. The dynamics function evaluates the current hidden state and a potential action to determine the potential next hidden state and a reward value. Lastly, the prediction function is the policy generation function. They use similar parameters and are optimized according to a combined loss function.

A Monte Carlo Tree Search (MCTS) is often used when training to evaluate action trees from the current/ root state.

MuZero

In a reinforcement learning framework, the process of training a Large Language Model (LLM) iteratively evaluates and improves the model's policy. At each step $$t$$, the current state $$s_t$$ is defined by the initial input prompt $$\mathbf{x}$$ and the tokens generated so far $$\mathbf{y}_{<t}$$. The LLM acts as the policy, denoted by the predicted distribution $$\Pr(y_t|\mathbf{x},\mathbf{y}_{<t})$$, to choose an action $$a_t$$, which is the next token $$y_t$$. After $$y_t$$ is predicted, a reward model evaluates the sequence $$(\mathbf{x},\mathbf{y}_{<t}, y_t)$$ to determine how well it aligns with the desired textual outcome. This evaluation produces reward scores that are then used to compute the value functions $$V(s_t)$$ and $$Q(s_t,a_t)$$. Finally, these value functions provide the necessary feedback to guide the subsequent training and refinement of the LLM's policy.

Reinforcement Learning Process for LLMs

A robot is being trained to find the exit in a maze. At any given position, the robot can choose to move forward, turn left, or turn right. The system keeps track of the robot's current coordinates within the maze. The robot's objective is to reach the exit as efficiently as possible. It receives a large positive signal for reaching the exit, a large negative signal for hitting a wall, and a small negative signal for each step it takes. Based on this scenario, identify the five fundamental components of this learning system and briefly explain the specific role of each.

Analyzing a Learning System

A robot is being trained to navigate a maze to find a piece of cheese. Analyze this scenario by matching each element of the training process to its corresponding fundamental concept.

The core of reinforcement learning is the interaction between an agent and a dynamic environment, which is modeled as a sequential process. At every time step, the agent assesses the environment's current state and uses its policy to select an action. After executing the action, the environment provides feedback consisting of a reward and a new state. This cycle of observing, acting, and receiving feedback continues until the agent accomplishes its objective.

Agent-Environment Interaction Loop in Reinforcement Learning

A cat is learning to use a new automated feeder that dispenses food when a lever is pressed. Initially, the cat paws at the lever randomly. After several attempts, it presses the lever and food is dispensed. The cat begins to press the lever more frequently. Which of the following statements best analyzes the relationship between the core components in this learning scenario?

Learn Before

Related

Learn After