Markov Decision Process (MDP)

The complete set of distinct configurations the environment can occupy. A state s ∈ S must capture all information necessary to make a decision, satisfying the Markov property—the future is conditionally independent of the past given the present state.

• Fully Observable: The agent perceives the complete environment state (e.g., chess board position).
• Partially Observable (POMDP): The agent receives an observation o that provides incomplete information about the true state.
• Representation: States can be discrete grid cells, continuous vectors of sensor readings, or latent embeddings learned by a neural network.

The set of all possible moves or decisions available to the agent at each time step. The action space defines the agent's control authority over the environment.

• Discrete Actions: A finite set of choices (e.g., {up, down, left, right} in a grid world).
• Continuous Actions: A vector of real-valued parameters (e.g., joint torques for a robotic arm, throttle and steering angle for an autonomous vehicle).
• Action Masking: Invalid actions in a given state are filtered out to prevent the agent from selecting impossible moves.

The probabilistic model of environmental dynamics, denoted T(s' | s, a). It defines the probability of transitioning to state s' after taking action a in state s.

• Deterministic Transitions: The next state is a fixed function of the current state and action (e.g., moving a piece in chess).
• Stochastic Transitions: The outcome is governed by a probability distribution (e.g., a robot's wheel slipping on uneven terrain).
• Model-Based RL: The agent learns or is given an explicit model of T to plan ahead. Model-Free RL learns a policy directly from sampled experience without modeling T.

A scalar feedback signal R(s, a, s') emitted by the environment after each transition. The reward function encodes the desirability of state-action pairs and defines the agent's objective.

• Dense Rewards: Frequent feedback at every step (e.g., distance to a target).
• Sparse Rewards: Feedback only upon task completion (e.g., winning a game). These are harder to learn from but easier to specify.
• Reward Shaping: Adding intermediate bonus rewards to guide learning without changing the optimal policy. Reward Decomposition breaks the scalar signal into sub-rewards for explainability.

A parameter γ ∈ [0, 1] that determines the present value of future rewards. It controls the agent's planning horizon and trades off immediate versus delayed gratification.

• γ ≈ 0: Myopic agent that cares only about immediate reward R_t.
• γ ≈ 1: Far-sighted agent that heavily weights distant future rewards, enabling long-term planning.
• Mathematical Role: Ensures the infinite sum of discounted returns converges for continuing (non-episodic) tasks. The return is defined as G_t = Σ_{k=0}^{∞} γ^k R_{t+k+1}.

The agent's strategy or behavior function mapping states to actions. The policy is the decision-making core that the learning algorithm optimizes.

• Deterministic Policy π(s): Maps each state to a single action.
• Stochastic Policy π(a | s): Outputs a probability distribution over actions, enabling exploration.
• Policy Gradient Methods: Directly optimize the policy parameters by ascending the gradient of expected return. Policy Distillation compresses a complex neural policy into an interpretable form like a decision tree for auditing.

A policy (π) is the agent's strategy—a mapping from states to actions that defines behavior within an MDP. It is the core object of optimization in reinforcement learning.

• Deterministic policy: π(s) = a. A direct mapping that always selects the same action in a given state.
• Stochastic policy: π(a|s). A probability distribution over actions, enabling exploration and handling of partially observable environments.
• Optimal policy (π*): The policy that maximizes expected cumulative reward from any starting state.

The policy can be represented as a lookup table for discrete state spaces, a neural network for continuous control, or a linear function approximator. Policy gradient methods like REINFORCE and PPO directly optimize the policy parameters by ascending the gradient of expected return.

A value function estimates the expected cumulative reward an agent can obtain, providing a scalar assessment of the long-term desirability of states or state-action pairs.

• State-value function V(s): The expected return starting from state s and following policy π thereafter.
• Action-value function Q(s,a): The expected return starting from state s, taking action a, and following policy π thereafter. Also called the Q-function.
• Bellman Equation: The recursive decomposition that defines the relationship between the value of a state and the values of its successor states, forming the theoretical backbone of dynamic programming solutions.

Value-based methods like Q-learning and Deep Q-Networks (DQN) learn optimal Q-functions without explicitly representing a policy, selecting actions greedily based on maximum Q-values.

The transition function T(s'|s,a) defines the dynamics of the MDP—the probability of transitioning to state s' given that the agent takes action a in state s. It encodes the environment's physics, rules, and stochasticity.

• Deterministic transitions: T(s'|s,a) = 1 for exactly one successor state. Common in grid worlds and deterministic simulations.
• Stochastic transitions: A probability distribution over possible next states, capturing environmental uncertainty like wind in drone navigation or opponent behavior in games.
• Markov property: The transition depends only on the current state and action, not on the history of previous states. This conditional independence is what makes the process 'Markov'.

In model-based RL, the agent learns an approximate transition model from experience. In model-free RL, the agent never explicitly models T, instead learning value functions or policies directly from sampled transitions.

The reward function R(s,a,s') is the scalar feedback signal that defines the goal of the MDP. It specifies the immediate desirability of taking action a in state s and transitioning to state s'. The agent's objective is to maximize the cumulative sum of rewards over time.

• Dense rewards: Frequent feedback at every timestep, such as distance-to-goal metrics, which accelerates learning but can lead to unintended local optima.
• Sparse rewards: Feedback only upon task completion or significant milestones, making exploration challenging but producing more generalizable behaviors.
• Shaped rewards: Engineered intermediate rewards that guide the agent toward desired behaviors, requiring careful design to avoid reward hacking—where the agent exploits reward function flaws rather than solving the intended task.

Inverse Reinforcement Learning (IRL) reverses this process, inferring the reward function from expert demonstrations to explain or replicate skilled behavior.

The discount factor γ ∈ [0,1] determines the present value of future rewards, controlling the agent's planning horizon. It is a critical hyperparameter that shapes the optimal policy.

• γ close to 0: The agent is myopic, prioritizing immediate rewards. Useful for short-horizon tasks or when rapid adaptation is needed.
• γ close to 1: The agent is far-sighted, valuing distant rewards almost as highly as immediate ones. Essential for tasks with delayed gratification, such as investment planning or game strategies requiring long-term sacrifice.
• γ = 1: Only valid in episodic tasks with guaranteed termination. In continuing tasks, γ < 1 ensures the infinite sum of rewards converges to a finite value.

The discount factor appears in the discounted return Gₜ = Rₜ₊₁ + γRₜ₊₂ + γ²Rₜ₊₃ + ..., geometrically weighting future rewards. It also functions as a variance reduction mechanism, reducing the impact of uncertain distant outcomes on current value estimates.

The Bellman optimality equation provides the recursive definition of the optimal value functions, forming the mathematical foundation for solving MDPs. It states that the optimal value of a state equals the maximum expected return achievable by taking the best action and then acting optimally thereafter.

• For V*: V*(s) = maxₐ Σₛ' T(s'|s,a)[R(s,a,s') + γV*(s')]
• For Q*: Q*(s,a) = Σₛ' T(s'|s,a)[R(s,a,s') + γ maxₐ' Q*(s',a')]

This equation is the basis for:

• Value Iteration: Repeatedly applying the Bellman optimality operator until convergence to find V*.
• Policy Iteration: Alternating between policy evaluation and policy improvement.
• Q-learning: A model-free, temporal-difference method that directly estimates Q* from sampled experience without requiring knowledge of T.

The Bellman equation's recursive structure enables dynamic programming solutions for known MDPs and bootstrapping-based learning for unknown environments.