MDP (Markov Decision Process)

The state space is the set of all possible configurations or situations the environment can be in. Each state s ∈ S is a complete description of the world at a specific time, sufficient to determine future dynamics. For example, in a robot navigation task, a state could be its precise (x, y) coordinates on a grid. The Markov property assumes the future state depends only on the current state and action, not the full history.

The action space is the set of all primitive decisions or controls available to the agent. From any given state s, the agent can choose an action a ∈ A(s), where A(s) denotes the actions applicable in state s. Actions can be discrete (e.g., {up, down, left, right}) or continuous (e.g., a torque value). The size and structure of the action space directly impact the complexity of finding an optimal policy.

The transition function, P(s' | s, a), defines the dynamics of the environment. It is a probability distribution over next states s' given the current state s and action a. This function encodes the inherent uncertainty in the world. For a deterministic environment, P(s' | s, a) = 1 for a single outcome. In stochastic environments, it represents a probability mass or density function, such as a robot's movement succeeding with 90% probability or slipping with 10%.

The reward function provides the agent's objective, defining the immediate desirability of transitioning from state s to state s' via action a. It is typically expressed as R(s, a, s') or the expected reward R(s, a). Rewards are scalar signals that the agent seeks to maximize over time. For instance, reaching a goal might yield +10, falling into a pit -10, and every other step -1 to encourage efficiency. The reward function is the sole specification of the task's goal.

The discount factor, γ ∈ [0, 1], is a hyperparameter that determines the present value of future rewards. It is used to compute the return, which is the sum of discounted future rewards: G_t = R_{t+1} + γR_{t+2} + γ²R_{t+3} + .... A γ close to 1 makes the agent far-sighted, heavily weighing long-term outcomes. A γ close to 0 makes it myopic, focusing on immediate rewards. It also ensures the return is finite in infinite-horizon problems.

While not a defining component of the MDP itself, the solution is a policy π(a|s)—a strategy mapping states to actions (or distributions over actions). From the MDP components, we derive value functions that evaluate policies:

• State-Value Function V^π(s): Expected return starting from state s and following π.
• Action-Value Function Q^π(s, a): Expected return after taking action a in state s, then following π. The core objective of solving an MDP is to find an optimal policy π* that maximizes these value functions.

A Partially Observable Markov Decision Process extends the MDP framework to model environments where the agent cannot directly perceive the true state. Instead, it receives observations that provide noisy or incomplete information. The agent must maintain a belief state—a probability distribution over possible states—and its policy maps belief states to actions. This is critical for real-world applications like robotics (sensor noise) and dialogue systems (uncertain user intent).

In the context of an MDP, a policy (denoted π) is a complete decision-making strategy. It defines the agent's behavior by specifying which action to take in any given state. Policies can be:

• Deterministic: A direct mapping from state to action (π(s) = a).
• Stochastic: A probability distribution over actions for each state (π(a|s)). The objective of solving an MDP is to find an optimal policy π* that maximizes the expected cumulative reward from any state.

The Bellman equation is the foundational recursive relationship that decomposes the long-term value of a state or state-action pair into immediate and future rewards. For a value function V(s), it is: V(s) = max_a [ R(s,a) + γ Σ_s' P(s'|s,a) V(s') ] This equation is the cornerstone of dynamic programming algorithms like Value Iteration and Policy Iteration, which solve MDPs by iteratively applying this consistency condition until convergence to the optimal value function.

Model-Based Reinforcement Learning refers to algorithms where the agent learns (or is given) an explicit model of the environment's dynamics—the transition function P(s'|s,a) and reward function R(s,a). The agent can then use this internal model for planning, simulating trajectories to evaluate actions without interacting with the real environment. This approach is often more sample-efficient than model-free RL but requires an accurate model, which can be difficult to learn.

Monte Carlo Tree Search is a heuristic search algorithm for optimal decision-making in sequential problems, often used in conjunction with MDPs or their deterministic counterparts. It combines tree search with random sampling. MCTS builds a search tree incrementally by:

1. Selection: Traversing the tree using a policy (e.g., UCT).
2. Expansion: Adding a new child node.
3. Simulation: Running a random rollout to a terminal state.
4. Backpropagation: Updating node statistics with the result. It famously powered AlphaGo, balancing exploration and exploitation in vast state spaces.

A Hierarchical MDP introduces temporal abstraction to tackle long-horizon problems. The Options Framework formalizes this, where an option is a temporally extended action consisting of:

• An initiation set (states where the option can start).
• An internal policy (a sequence of primitive actions).
• A termination condition (when the option stops). This allows an agent to operate at multiple levels of abstraction, using high-level options (e.g., 'navigate to room') that are composed of lower-level primitives, dramatically improving planning efficiency.