Markov Decision Process (MDP)

A state is a complete description of the environment at a specific time. It encapsulates all information necessary for the agent to make a decision. In fleet orchestration, a state could represent:

• The position, velocity, and battery level of every robot.
• The location and status (pending, in-progress, completed) of all active tasks.
• The current layout of the warehouse, including dynamic obstacles. The set of all possible states is the state space. A key property is the Markov Property, meaning the future state depends only on the current state and action, not the full history.

An action is a choice available to the agent that causes a transition from the current state to a new state. The set of valid actions can depend on the current state. For a mobile robot, actions might include:

• Navigate to a specific coordinate.
• Pick up a payload.
• Charge at a docking station.
• Wait (a null action). In a heterogeneous fleet, the action space differs per agent type (e.g., a manual forklift vs. an AMR). The agent's goal is to learn a policy—a mapping from states to actions—that maximizes long-term reward.

The transition function, denoted 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 taken (a). It models uncertainty in outcomes. For example:

• An action move_north has a 90% probability of success, a 5% chance of staying put (due to wheel slip), and a 5% chance of moving northeast.
• A task pick_item may have a 98% success rate and a 2% chance of failure requiring a retry. In deterministic environments, the transition probability is 1.0 for a single outcome. This function is core to planning and simulation.

The reward function, R(s, a, s'), provides a scalar feedback signal to the agent after taking action a in state s and transitioning to state s'. It defines the goal of the MDP. Rewards are typically designed to:

• Encourage desired outcomes: +100 for completing a high-priority delivery on time.
• Penalize costs or failures: -1 for each unit of energy consumed, -1000 for a collision.
• Shape behavior: Small positive reward for moving toward a goal. The agent's objective is to maximize the expected cumulative reward (often discounted over time), not immediate reward. This function encodes the business or operational objective.

The discount factor, gamma (γ), is a value between 0 and 1 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.
• γ close to 1 (e.g., 0.99): The agent is far-sighted, valuing future rewards almost as much as immediate ones. Mathematically, it ensures the infinite sum of future rewards converges. In practical terms, a high gamma in fleet scheduling encourages policies that optimize for long-term efficiency and battery health, not just the next task.

A policy, π(a|s), is the agent's strategy—a rule for selecting actions in each state. Solving an MDP means finding an optimal policy (π)* that maximizes expected cumulative reward. Value functions evaluate policies:

• 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 after taking action a in state s and then following π. The Bellman equations recursively define these values. Reinforcement Learning algorithms, like Q-Learning, directly approximate Q*(s,a) to derive the optimal policy without knowing the full transition model.

In robotics, MDPs model the robot's state (e.g., position, battery level), actions (move forward, turn), and transition probabilities (accounting for wheel slippage or sensor noise). The reward function encodes goals (reach target) and penalties (collision, high energy use). Solving the MDP yields a robust navigation policy. This is critical for:

• Autonomous mobile robots (AMRs) in warehouses.
• Self-driving car decision-making at intersections.
• Drone path planning in uncertain wind conditions.

MDPs optimize the sequential allocation of limited resources over time under uncertainty. States represent resource levels and demand, actions are allocation decisions, and rewards measure efficiency or revenue.

• Compute Cluster Scheduling: Allocating jobs to servers with uncertain runtimes.
• Battery-Aware Fleet Orchestration: Deciding when to send an AMR to charge vs. execute a task.
• Network Packet Routing: Choosing paths with stochastic link delays. The solution provides a policy that balances immediate gains against future resource availability.

MDPs model classic inventory control problems where a manager must decide order quantities each period. The state is current stock level, actions are order sizes, and transition dynamics incorporate stochastic customer demand. Rewards are profit from sales minus holding and stockout costs. The optimal policy often takes a threshold form (e.g., "order up to S"). This framework extends to multi-echelon supply chains and perishable goods management.

MDPs formulate personalized medical treatment as a sequential decision process. The state captures patient vitals and disease progression, actions are treatment choices (drug A, surgery, monitor), and transition probabilities model uncertain patient responses. Rewards encode patient outcomes (quality-adjusted life years). Solving the MDP yields an adaptive treatment policy that recommends the best action given the current patient state, forming the basis for clinical decision support systems.

In quantitative finance, MDPs model portfolio management and optimal execution. The state includes asset prices, portfolio holdings, and market signals. Actions are trading decisions (buy/sell volumes). Transition uncertainty captures market volatility. The reward is often a risk-adjusted return (e.g., Sharpe ratio). The resulting policy dictates dynamic asset allocation or trade scheduling to minimize market impact. This bridges stochastic control theory with modern algorithmic trading strategies.

The Bellman Equation is the foundational recursive equation that decomposes the value of a state (or state-action pair) into the immediate reward plus the discounted value of the successor state. It is the cornerstone of dynamic programming solutions for MDPs.

• For State Value: V(s) = max_a [ R(s,a) + γ * Σ_s' P(s'|s,a) * V(s') ]
• For Action Value (Q): Q(s,a) = R(s,a) + γ * Σ_s' P(s'|s,a) * max_a' Q(s',a')
• Purpose: Enables the computation of optimal value functions via iterative methods like Value Iteration and Policy Iteration.

Dynamic Programming refers to a collection of algorithms that solve complex problems by breaking them down into simpler overlapping subproblems. In the context of MDPs, DP provides the primary model-based solution methods when the transition probabilities and reward function are fully known.

• Core Algorithms: Policy Iteration (evaluate then improve policy) and Value Iteration (directly iterate on the value function).
• Requirement: Requires a perfect model of the environment, limiting direct application to real-world systems where the model is unknown.
• Foundation: Serves as the theoretical basis for understanding more advanced RL algorithms.

Stochastic Programming is a framework for optimization under uncertainty where some problem parameters are random variables with known (or estimable) probability distributions. The goal is to find a decision policy that optimizes the expected value of outcomes.

• Contrast with MDPs: While both handle uncertainty, Stochastic Programming typically focuses on multi-stage decision problems with a finite number of stages and scenarios, often without the Markov property.
• Common Forms: Two-stage and multi-stage stochastic programs with recourse.
• Applications: Used in finance (portfolio optimization), energy (unit commitment), and supply chain planning under demand uncertainty.