MDP (Markov Decision Process)

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.

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.