Markov Decision Process (MDP)

The exhaustive set of all possible situations the agent can encounter. A state must capture all relevant information needed to make a decision, satisfying the Markov property—the future depends only on the current state, not the history.

• Fully Observable: The agent sees the complete environment state (e.g., chess board position)
• Partially Observable: The agent receives noisy observations (modeled as a POMDP)
• Continuous vs. Discrete: Inventory levels are continuous; grid-world locations are discrete

Example: In a warehouse robot MDP, a state might encode (x_position, y_position, battery_level, current_task).

The set of all possible moves or decisions available to the agent in each state. Actions transition the environment from one state to another, though the outcome may be stochastic.

• Deterministic Actions: Always produce the same next state (e.g., moving a robot arm by a fixed increment)
• Stochastic Actions: Produce a distribution over next states (e.g., a drone navigating wind gusts)
• Action Masking: Invalid actions in certain states are filtered out (e.g., you cannot 'grasp' if no object is detected)

Example: In a supply chain MDP, actions might be {reorder_100_units, reorder_500_units, do_nothing}.

The dynamics model defining the probability of landing in state s' given the agent took action a in state s. This encodes the environment's stochasticity.

• P(s' | s, a) is the core mathematical function
• Deterministic Transitions: P = 1 for exactly one next state, 0 for all others
• Learned vs. Known: In model-based RL, the agent learns P; in model-free RL, it is never explicitly modeled

Example: A delivery truck choosing 'speed up' has a 90% chance of arriving early and a 10% chance of a weather delay. This uncertainty is captured in the transition matrix.

The scalar feedback signal that defines the goal. The agent's objective is to maximize the cumulative reward over time, not just the immediate reward. The reward function shapes behavior.

• R(s, a): Reward for taking action a in state s
• R(s, a, s'): Reward that also depends on the resulting state
• Sparse vs. Dense: +1 only for winning a game (sparse) vs. -1 per time step to encourage speed (dense)
• Reward Shaping: Adding intermediate rewards to accelerate learning without changing the optimal policy

Example: In a factory scheduling MDP, a reward of +100 for on-time delivery and -50 for each hour of delay.

A parameter between 0 and 1 that determines the present value of future rewards. It mathematically bounds the infinite sum of rewards and controls the agent's horizon.

• γ ≈ 0: Myopic agent, cares only about immediate reward
• γ ≈ 1: Farsighted agent, values future rewards almost as much as immediate ones
• Economic Interpretation: Analogous to an interest rate; γ = 1/(1+r)
• Episodic Tasks: Can use γ = 1 because the horizon is finite

Example: In portfolio optimization, γ = 0.95 reflects a long-term investment horizon. In a short-horizon logistics task, γ = 0.8 prioritizes immediate delivery deadlines.

The agent's strategy—a mapping from states to actions. The policy is the output of solving an MDP and can be deterministic or stochastic.

• Deterministic Policy π(s): Always selects the same action for a given state
• Stochastic Policy π(a|s): Defines a probability distribution over actions, enabling exploration
• Optimal Policy π*: Maximizes the expected cumulative discounted reward from any starting state
• Value Functions V(s) and Q(s,a): Derived quantities that evaluate how good a state or state-action pair is under a policy

Example: An optimal inventory policy might be: 'If stock < 50 units, order 200 units; otherwise, do nothing.' This is the π* that maximizes long-term profit.

MDPs model inventory management as a sequential decision problem where the state is current stock level, the action is order quantity, and the reward balances holding costs against stockout penalties. The optimal policy specifies exactly how much to order at each inventory level, accounting for stochastic demand and variable lead times. Unlike static reorder point systems, MDP-based policies adapt dynamically to changing demand distributions and supplier reliability, minimizing total cost over the planning horizon.

Equipment degradation in warehouses and factories follows stochastic patterns that MDPs capture through partially observable states. The agent observes sensor readings (vibration, temperature) representing the machine's hidden health state, then chooses actions: run, inspect, or repair. Rewards encode production throughput minus maintenance costs and failure penalties. The resulting policy prescribes optimal inspection intervals that minimize unplanned downtime while avoiding unnecessary preventive maintenance.

Distributing inventory across a network of regional warehouses and retail locations creates a high-dimensional MDP. The state space captures stock levels at every node; actions represent transshipment quantities between locations. Transition probabilities model demand at each location and shipping delays. Solving this MDP yields policies that automatically rebalance inventory across the network, reducing both stockouts and excess holding costs through coordinated rather than siloed decisions.

When a port closure or supplier failure occurs, the supply chain enters a disrupted state requiring rapid reconfiguration. MDPs model this as a contingency planning problem where actions include activating backup suppliers, rerouting shipments, or expediting orders. The reward function penalizes both disruption duration and recovery cost. The optimal policy provides a pre-computed playbook: for each type and severity of disruption, it specifies the cost-minimizing recovery sequence.

Dynamic vehicle dispatch under uncertain demand and traffic conditions is naturally framed as an MDP. The state includes vehicle locations, pending orders, and traffic conditions. Actions assign new orders to specific vehicles. Transition probabilities capture travel time variability and new order arrivals. The reward maximizes on-time deliveries minus fuel and labor costs. This approach outperforms static routing by continuously re-optimizing assignments as conditions evolve throughout the day.

Choosing suppliers involves sequential decisions under evolving information about reliability, quality, and pricing. The MDP state tracks each supplier's performance history and current market conditions. Actions allocate purchase orders across the supplier base. Transition probabilities model supplier learning curves and market fluctuations. The optimal policy balances diversification against consolidation, automatically shifting volume toward reliable suppliers while maintaining relationships with backup options.

The mathematical backbone of MDP solving. Dynamic Programming decomposes the sequential decision problem into overlapping subproblems, storing their solutions to avoid redundant computation. The Bellman Equation is the core recursive relationship that expresses the value of a state in terms of immediate reward plus the discounted value of successor states. Algorithms like Value Iteration and Policy Iteration use dynamic programming to converge on an optimal policy when the full MDP model is known.

A computational approach to learning MDP solutions when the transition probabilities and reward functions are unknown. Instead of requiring a complete model, a reinforcement learning agent interacts with an environment, observing states and rewards, and incrementally improves its policy through trial and error. Key algorithms include:

• Q-Learning: Learns the value of state-action pairs directly from experience
• SARSA: An on-policy alternative that updates based on the action actually taken
• Deep Q-Networks (DQN): Uses neural networks to approximate Q-values in high-dimensional state spaces

The fundamental dilemma at the heart of MDP solving. An agent must balance exploitation—choosing the action currently believed to yield the highest reward—against exploration—trying suboptimal actions to gather more information about the environment. Strategies include:

• Epsilon-greedy: Select a random action with probability ε, otherwise exploit
• Upper Confidence Bound (UCB): Choose actions based on their potential upside given uncertainty
• Thompson Sampling: Make decisions probabilistically according to the posterior distribution of each action's value

A generalization of the MDP framework where the agent cannot directly observe the true underlying state. Instead, it receives noisy observations that provide partial information. The agent must maintain a belief state—a probability distribution over all possible states—and update it using Bayesian inference after each action and observation. POMDPs are essential for modeling real-world scenarios like robot navigation with limited sensors or medical diagnosis with incomplete test results.

A heuristic search algorithm that builds a decision tree by randomly sampling trajectories through the state space and using the results to focus computation on the most promising branches. MCTS combines the precision of tree search with the generality of random sampling, making it effective for large MDPs where exhaustive search is impossible. It famously powered AlphaGo and is widely used in game-playing AI and sequential planning problems with enormous branching factors.

An engineering control method that solves an optimization problem over a finite, receding time horizon at each time step. Unlike MDPs which seek a stationary policy for an infinite horizon, MPC explicitly optimizes a sequence of actions for a short window into the future, executes only the first action, and then re-optimizes from the new state. This makes MPC highly robust to model errors and is the dominant approach in industrial process control, autonomous vehicle path planning, and robotics.