← Reference · Nestor G Pestelos Jr

Artificial Intelligence

Reinforcement Learning

A citable reference on Reinforcement Learning (RL): Markov Decision Processes, Bellman optimality equations, value and policy iteration, policy gradient theorems, Actor-Critic methods, PPO, DPO, and GRPO.

1. Formal Definition and Markov Decision Processes

Reinforcement Learning (RL) is a computational framework in machine learning where an agent learns to make sequential decisions by interacting with an environment to maximize cumulative numerical reward.[1] Unlike supervised learning, which relies on explicit input-output label pairs, the agent receives evaluative feedback through scalar reward signals generated by environmental transitions.

1.1 The MDP 5-Tuple

Sequential decision problems in RL are formally framed as Markov Decision Processes (MDPs), defined by the 5-tuple \((S, A, P, R, \gamma)\):[1]

• \(S\): The state space containing all valid environmental configurations.
• \(A\): The action space available to the agent (discrete or continuous).
• \(P(s' \mid s, a) = \mathbb{P}(S_{t+1} = s' \mid S_t = s, A_t = a)\): The transition probability distribution satisfying the Markov property:
  $$\mathbb{P}(S_{t+1} = s_{t+1} \mid S_t = s_t, A_t = a_t, \dots, S_0 = s_0, A_0 = a_0) = \mathbb{P}(S_{t+1} = s_{t+1} \mid S_t = s_t, A_t = a_t)$$
• \(R(s, a, s') = \mathbb{E}[R_{t+1} \mid S_t = s, A_t = a, S_{t+1} = s']\): The reward function mapping state-action transitions to scalar values.
• \(\gamma \in [0, 1)\): The discount factor weighting immediate versus future rewards.

1.2 Returns, Trajectories, and Policies

An interaction trajectory \( au\) is a sequence of states, actions, and rewards: \( au = (s_0, a_0, r_0, s_1, a_1, r_1, \dots, s_T)\). The discounted return \(G_t\) from time step \(t\) onward is:

The agent behaves according to a policy \(\pi\). A stochastic policy \(\pi(a \mid s) = \mathbb{P}(A_t = a \mid S_t = s)\) maps states to action probability distributions; a deterministic policy \(\mu(s)\) maps each state directly to a specific action. The goal of the agent is to find an optimal policy \(\pi^*\) that maximizes the expected return \(J(\pi) = \mathbb{E}_{ au \sim \pi}[G_0]\).

1.3 Value Functions

Value functions measure expected long-term return under a given policy:

• State-Value Function \(V^\pi(s)\): Expected return starting from state \(s\) under policy \(\pi\):
  $$V^\pi(s) = \mathbb{E}_\pi \left[ \sum_{k=0}^\infty \gamma^k R_{t+k+1} \;\middle|\; S_t = s ight]$$
• Action-Value Function \(Q^\pi(s, a)\): Expected return taking action \(a\) in state \(s\), then following policy \(\pi\):
  $$Q^\pi(s, a) = \mathbb{E}_\pi \left[ \sum_{k=0}^\infty \gamma^k R_{t+k+1} \;\middle|\; S_t = s, A_t = a ight]$$
• Advantage Function \(A^\pi(s, a)\): The relative value of taking action \(a\) compared to the policy average:
  $$A^\pi(s, a) = Q^\pi(s, a) - V^\pi(s)$$

2. Bellman Equations and Optimality

Value functions satisfy recursive relationships known as Bellman equations, decomposing the value of a state into immediate reward plus discounted downstream value.[2]

2.1 Bellman Expectation Equations

For any stationary policy \(\pi\), the value functions satisfy:

2.2 Bellman Optimality Equations

An optimal policy \(\pi^*\) achieves the maximum value across all states: \(V^*(s) = \max_\pi V^\pi(s)\) and \(Q^*(s, a) = \max_\pi Q^\pi(s, a)\). The Bellman optimality equations express these conditions without explicit policy reference:

2.3 Contraction Mapping and Convergence

The Bellman optimality operator \(\mathcal{T}^*\) defined by \((\mathcal{T}^* V)(s) = \max_a \sum_{s'} P(s' \mid s, a)[R(s, a, s') + \gamma V(s')]\) is a \(\gamma\)-contraction mapping in the infinity norm:

By the Banach Fixed-Point Theorem, applying \(\mathcal{T}^*\) iteratively from any initial value function \(V_0\) converges geometrically to the unique optimal value function \(V^*\) when \(\gamma < 1\). This property provides the theoretical foundation for value iteration and Q-learning.[1, 3]

3. Taxonomy of Reinforcement Learning Algorithms

3.1 Model-Based vs. Model-Free

Model-Based RL algorithms learn or utilize an explicit model of environment transitions and reward dynamics. The agent uses this internal simulation to plan future action sequences before execution (for example, Monte Carlo Tree Search in AlphaZero).[4]

Model-Free RL algorithms bypass transition modeling and learn value functions or policies directly from sampled experience. While requiring higher sample complexity, model-free methods avoid compounding model bias in complex high-dimensional environments.

3.2 Value-Based Methods

In Q-Learning (Watkins, 1989), the agent updates action-value estimates off-policy using Temporal Difference (TD) learning:[3]

Deep Q-Networks (DQN) (Mnih et al., 2015) scale Q-learning to high-dimensional state spaces using deep neural networks parameterized by \( heta\).[5] DQN stabilizes non-linear function approximation through two core mechanisms:

• Experience Replay: Transitions \((s_t, a_t, r_t, s_{t+1})\) are stored in a rolling replay buffer and sampled uniformly in mini-batches to break temporal correlation.
• Target Networks: A secondary parameter set \( heta^-\) computes TD targets, updated periodically to eliminate moving-target instability during gradient descent.

3.3 Policy Gradient Methods

Policy-based methods parameterize the policy directly as \(\pi_ heta(a \mid s)\) and optimize the objective \(J( heta) = \mathbb{E}_{ au \sim \pi_ heta}[R( au)]\) via gradient ascent. The Policy Gradient Theorem (Sutton et al., 1999) establishes that the objective gradient does not require differentiation through state transition probabilities:[6]

In the Monte Carlo REINFORCE algorithm (Williams, 1992), empirical episode return \(G_t\) serves as an unbiased sample estimate of \(Q(S_t, A_t)\).[7]

3.4 Actor-Critic Architectures

Pure policy gradients suffer from high variance. Actor-Critic methods resolve this by training a Critic network \(V_\phi(s)\) to estimate expected value and replacing \(Q(s, a)\) with the Advantage function \(A(s, a) = Q(s, a) - V(s)\).

Proximal Policy Optimization (PPO) (Schulman et al., 2017) stabilizes policy updates by constraining the step size using a clipped surrogate objective:[8]

where \(r_t( heta) = rac{\pi_ heta(a_t \mid s_t)}{\pi_{ heta_{ ext{old}}}(a_t \mid s_t)}\) is the probability ratio and \(\epsilon\) is a clipping parameter (typically \(0.1\) or \(0.2\)).

4. The Exploration-Exploitation Tradeoff

An RL agent balances exploitation (selecting actions known to yield high reward) with exploration (trying unfamiliar actions to discover potentially superior strategies). Common formal mechanisms include:

• \(\epsilon\)-Greedy: Select the highest-value action with probability \(1-\epsilon\), and a uniform random action with probability \(\epsilon\), where \(\epsilon\) is decayed over training.
• Upper Confidence Bound (UCB): Select actions balancing estimated mean return \(\hat{Q}(a)\) with estimation uncertainty based on visitation counts \(N(a)\):
  $$A_t = rg\max_a \left[ Q_t(a) + c \sqrt{rac{\ln t}{N_t(a)}} ight]$$
• Maximum Entropy RL (Soft Actor-Critic): Augments the objective with a policy entropy bonus \(\mathcal{H}(\pi(\cdot \mid s))\), encouraging broad state-space coverage and multi-modal policy discovery:[9]
  $$J(\pi) = \mathbb{E}_{ au \sim \pi} \left[ \sum_{t=0}^\infty \gamma^t \Big( R(S_t, A_t, S_{t+1}) + lpha \mathcal{H}ig(\pi(\cdot \mid S_t)ig) \Big) ight]$$

5. Reinforcement Learning in Large Language Models

In modern language model post-training, the state space corresponds to the prompt context, actions are generated tokens, and the environment transition is deterministic token concatenation.[10]

5.1 RLHF with PPO

Reinforcement Learning from Human Feedback (RLHF) aligns pretrained language models with user preferences using a three-stage pipeline (Christiano et al., 2017; Ouyang et al., 2022):[10, 11]

1. Supervised fine-tuning (SFT) on prompt-response demonstrations.
2. Reward model training on pairwise human preference comparisons \((y_w \succ y_l)\) via the Bradley-Terry preference model:
   $$\mathcal{L}_{ ext{RM}}(\psi) = -\mathbb{E}_{(x, y_w, y_l)} \left[ \log \sigmaig(r_\psi(x, y_w) - r_\psi(x, y_l)ig) ight]$$
3. PPO policy optimization maximizing reward while applying a Kullback-Leibler (KL) divergence penalty against the reference model \(\pi_{ ext{ref}}\) to prevent policy collapse:
   $$ ext{obj}( heta) = \mathbb{E}_{(x, y) \sim \mathcal{D}_{\pi_ heta}} \left[ r_\psi(x, y) - eta D_{ ext{KL}}ig(\pi_ heta(y \mid x) \,\|\, \pi_{ ext{ref}}(y \mid x)ig) ight]$$

5.2 Direct Preference Optimization (DPO)

Direct Preference Optimization (DPO) (Rafailov et al., 2023) derives an exact closed-form substitution for the optimal reward function in terms of policy probabilities:[12]

Substituting this parameterization directly into the pairwise preference loss eliminates the need for an explicit reward model or online reinforcement learning sampling loop:

5.3 GRPO and Verifiable Rewards (RLVR)

For formal reasoning domains (mathematics, formal logic, and software code generation), reward signals can be computed deterministically via rule-based verifiers such as unit test execution or mathematical equivalence checkers.

Group Relative Policy Optimization (GRPO) (Shao et al., 2024 / DeepSeekMath) eliminates the Critic neural network entirely to cut memory overhead during post-training.[13] For each prompt \(q\), GRPO samples a group of \(G\) candidate outputs \(\{o_1, o_2, \dots, o_G\}\), scores each output with reward verifier \(r_i\), and standardizes rewards across the group to compute advantage values:

The policy is updated with a clipped objective regularized by a direct token-level KL divergence penalty:

6. References

1. ^ Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, 2nd ed. (MIT Press, 2018). URL: incompleteideas.net.
2. ^ Richard Bellman, Dynamic Programming (Princeton University Press, 1957).
3. ^ Christopher J. C. H. Watkins and Peter Dayan, "Q-learning," Machine Learning 8(3), 279–292 (1992). DOI: 10.1007/BF00992698.
4. ^ David Silver, Thomas Hubert, Julian Schrittwieser, et al., "A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play," Science 362(6419), 1140–1144 (2018). DOI: 10.1126/science.aar6404.
5. ^ Volodymyr Mnih, Koray Kavukcuoglu, David Silver, et al., "Human-level control through deep reinforcement learning," Nature 518(7540), 529–533 (2015). DOI: 10.1038/nature14236.
6. ^ Richard S. Sutton, David McAllester, Satinder Singh, and Yishay Mansour, "Policy Gradient Methods for Reinforcement Learning with Function Approximation," Advances in Neural Information Processing Systems 12 (NeurIPS 1999). URL: NeurIPS Proceedings (PDF).
7. ^ Ronald J. Williams, "Simple statistical gradient-following algorithms for connectionist reinforcement learning," Machine Learning 8(3), 229–256 (1992). DOI: 10.1007/BF00992696.
8. ^ John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov, "Proximal Policy Optimization Algorithms," arXiv:1707.06347 (2017). DOI: 10.48550/arXiv.1707.06347.
9. ^ Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine, "Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor," International Conference on Machine Learning (ICML 2018). URL: arXiv:1801.01290.
10. ^ Long Ouyang, Jeffrey Wu, Xu Jiang, et al., "Training language models to follow instructions with human feedback," Advances in Neural Information Processing Systems 35 (NeurIPS 2022). URL: arXiv:2203.02155.
11. ^ Paul F. Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei, "Deep reinforcement learning from human preferences," Advances in Neural Information Processing Systems 30 (NeurIPS 2017). URL: arXiv:1706.03741.
12. ^ Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D. Manning, and Chelsea Finn, "Direct Preference Optimization: Your Language Model is Secretly a Reward Model," Advances in Neural Information Processing Systems 36 (NeurIPS 2023). URL: arXiv:2305.18290.
13. ^ Zhihong Shao, Peiyi Wang, Qihao Zhu, et al., "DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models," arXiv:2402.03300 (2024). DOI: 10.48550/arXiv.2402.03300.