Markov Decision Process (MDP)

The State Space is the set of all possible situations or configurations the environment can be in. A state s ∈ S contains all relevant information for decision-making. The Markov Property asserts that the future depends only on the current state, not the history of past states.

• Examples: A robot's position and velocity on a grid; the current board configuration in a game of chess.
• Key Distinction: The state must be sufficient for predicting the next state and reward, fulfilling the Markov condition.

The Action Space is the set of all possible moves or decisions the agent can make. For a given state s, the available actions may be a subset A(s) ⊆ A.

• Types: Can be discrete (e.g., {left, right, up, down}) or continuous (e.g., a torque value between -1 and 1).
• In Robotics: Often corresponds to motor commands or joint velocities sent to actuators. The design of the action space directly impacts the complexity of the control policy.

The Transition Function, or dynamics model, defines the environment's stochasticity. Formally, P(s' | s, a) is the probability of transitioning to state s' after taking action a in state s.

• Mechanism: Encodes the rules of the world, including physics and uncertainty.
• Model-Based vs. Model-Free: If P is known, the agent can use planning (e.g., dynamic programming). If unknown, the agent must learn through interaction (model-free RL).
• Deterministic Case: A special case where P(s' | s, a) = 1 for a single outcome.

The Reward Function provides the agent with a scalar feedback signal R(s, a, s') after each transition. It formally encodes the goal of the task.

• Design Principle: Rewards should be sparse enough to avoid hacking but dense enough to provide learning signal. Poorly shaped rewards can lead to unintended behaviors.
• Cumulative Return: The agent's objective is to maximize the expected discounted sum of future rewards: G_t = R_{t+1} + γR_{t+2} + γ²R_{t+3} + ...

The Discount Factor γ ∈ [0, 1] is a hyperparameter that determines the present value of future rewards. It quantifies the agent's preference for immediate versus long-term reward.

• γ = 0: The agent is myopic, caring only about the immediate next reward.
• γ → 1: The agent is far-sighted, valuing future rewards almost equally. Used in episodic tasks with natural termination.
• Mathematical Role: Ensures the infinite sum of rewards converges in continuing tasks and makes the Bellman equations well-posed.

While not a defining component of the MDP itself, the Policy π(a|s) is the agent's strategy—a mapping from states to probability distributions over actions. From the MDP components, we derive two critical functions for evaluating policies:

• State-Value Function V^π(s): The expected return starting from state s and following policy π.
• Action-Value Function Q^π(s, a): The expected return after taking action a in state s and thereafter following π.

The core problem of RL is to find the optimal policy π* that maximizes these value functions.

Board games are perfect-information MDPs. The state is the board configuration. Actions are legal moves. The transition is deterministic (move execution). Reward is +1 for win, -1 for loss, 0 for draw. The immense state space requires function approximation (like AlphaZero's neural networks) to estimate values and learn a superhuman policy through self-play and reinforcement learning.

This is a classic operations research problem modeled as an MDP. The state is current stock levels. The action is how much to order. Transition probabilities model stochastic customer demand. The reward is profit from sales, minus holding and shortage costs. The optimal policy specifies order quantities for each stock level to maximize long-term profit, balancing the risk of overstocking against stockouts.

Personalized medicine can be framed as an MDP. The state is patient health metrics and treatment history. Actions are treatment choices (e.g., drug type, dosage). Transitions model the probabilistic progression of the disease and side effects. Reward is a composite of health improvement, quality of life, and cost reduction. The goal is to learn a treatment policy that maximizes a patient's long-term health outcome.

Managing data traffic in a communications network is a complex MDP. The state includes queue lengths and channel conditions. Actions involve routing paths and bandwidth allocation. Transitions depend on random packet arrivals and link failures. Reward is based on throughput and minimized latency. The optimal policy dynamically allocates resources to maintain service quality under uncertainty.

The Bellman equation is the recursive decomposition at the heart of solving an MDP. It defines the optimal value of a state as the immediate reward plus the discounted value of the best possible next state.

• Value Iteration & Policy Iteration: These fundamental dynamic programming algorithms directly apply the Bellman equation to compute optimal value functions and policies.
• Optimality Principle: The equation formalizes the principle that an optimal policy has the property that whatever the initial state and decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

A Partially Observable Markov Decision Process (POMDP) generalizes the MDP framework for environments where the agent cannot directly observe the true underlying state. Instead, it receives an observation that provides probabilistic information about the state.

• Belief State: The agent maintains a probability distribution over possible states, known as a belief state, which becomes the new basis for decision-making.
• Critical for Robotics: POMDPs are essential for modeling real-world robotics tasks where sensors are noisy and provide incomplete data, such as robot localization or manipulation with occluded objects.

In an MDP, a policy is the agent's strategy for selecting actions. It defines a mapping from states to actions (deterministic) or to a probability distribution over actions (stochastic).

• *Optimal Policy (π)**: The policy that maximizes the expected cumulative discounted reward from any state.
• Policy Space: The set of all possible policies. Reinforcement learning algorithms search this space, either directly (Policy Gradient Methods) or indirectly via value functions.

A value function quantifies 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 then following policy π. Also known as the Q-function.
• Goal of RL: Most algorithms aim to accurately estimate these functions (e.g., Q-Learning, DQN) to derive an optimal policy.

This distinction defines how an RL agent interacts with the MDP's unknown dynamics.

• Model-Based RL: The agent learns (or is given) an explicit model of the environment's transition function T and reward function R. It uses this model for planning (e.g., via Model Predictive Control) to improve sample efficiency.
• Model-Free RL: The agent learns a policy or value function directly from experience without ever constructing an explicit model of the environment dynamics. Q-learning and Policy Gradient methods are model-free.

The fundamental trade-off an agent faces in an MDP with unknown rewards and dynamics.

• Exploitation: Choosing the action that currently seems best according to the agent's learned value estimates.
• Exploration: Choosing a sub-optimal action to gather more information about the environment, which may lead to higher long-term reward.
• Balancing Mechanisms: Algorithms employ strategies like ε-greedy, Upper Confidence Bound (UCB), or intrinsic curiosity rewards to manage this trade-off and avoid converging to sub-optimal policies.