Markov Decision Process (MDP)

The exhaustive set of all possible situations or configurations the agent can encounter. A state must capture all relevant information for decision-making, satisfying the Markov Property—the future depends only on the current state, not the history.

• Fully Observable: Agent sees the complete environment state (e.g., a chess board).
• Partially Observable: Agent receives noisy observations, formalized as a Partially Observable MDP (POMDP).
• Feature Representation: In practice, states are encoded as feature vectors (e.g., customer's last 5 purchases, session duration, device type).

The set of all possible moves or interventions available to the agent in each state. Actions can be discrete (e.g., offer A, B, or C) or continuous (e.g., adjusting a discount percentage).

• Context-Dependent: Available actions may vary by state (e.g., a 'refund' action is only valid post-purchase).
• Deterministic vs. Stochastic: A policy maps states to actions either deterministically or as a probability distribution.

Defines the environment's dynamics: the probability of moving from state s to state s' after taking action a. Formally, P(s' | s, a).

• Stochasticity: Captures inherent randomness—a customer receiving a discount may or may not convert.
• Model-Based vs. Model-Free: If P is known, the agent can plan. In most real-world scenarios, P is unknown and must be learned through interaction.

The scalar feedback signal defining the immediate goal. The agent receives R(s, a, s') after transitioning. This is the primary mechanism for encoding business objectives.

• Sparse vs. Dense: A purchase event is a sparse reward; click-through is a dense reward.
• Delayed Gratification: The MDP framework handles long-term credit assignment—a nurturing email today may yield revenue months later.

A value between 0 and 1 that determines the present value of future rewards. γ ≈ 0 makes the agent myopic (prioritizing immediate clicks); γ ≈ 1 makes it far-sighted (optimizing for Customer Lifetime Value).

• Mathematical Necessity: Ensures the infinite sum of rewards converges in continuing tasks.
• Uncertainty Proxy: Lower gamma implicitly accounts for uncertainty about the distant future.

The agent's strategy—a mapping from states to actions. The objective of solving an MDP is to find the optimal policy π* that maximizes expected cumulative reward.

• Deterministic Policy: π(s) = a (always send a discount to churn-risk users).
• Stochastic Policy: π(a|s) = probability (explore different offers for a segment).
• Stationarity: An optimal policy for a stationary MDP depends only on the current state, not the time step.

Self-driving cars use MDPs to navigate dynamic environments where every maneuver has probabilistic outcomes. The state space includes position, velocity, and surrounding objects, while actions encompass acceleration, braking, and steering. Transition probabilities model sensor noise and pedestrian unpredictability. The reward function penalizes collisions and rewards progress toward the destination. Solving the MDP yields a policy that balances safety with efficiency, often using Partially Observable MDPs (POMDPs) to handle occluded objects and sensor uncertainty.

Retailers formulate inventory replenishment as an MDP where states represent current stock levels and demand forecasts, actions are order quantities, and rewards balance holding costs against stockout penalties. The transition function captures stochastic demand patterns and supplier lead times. Solving for the optimal policy determines when and how much to reorder, directly minimizing carrying costs while maintaining service levels. This framework naturally handles multi-echelon supply chains where decisions at one warehouse cascade probabilistically to downstream nodes.

Clinicians use MDPs to model chronic disease management where states capture patient biomarkers and history, actions represent medication adjustments or lifestyle interventions, and rewards encode health outcomes minus side-effect penalties. The transition probabilities are learned from electronic health records, capturing how patients respond to treatments over time. The resulting policy provides a personalized, adaptive treatment strategy that adjusts as the patient's condition evolves, maximizing long-term health outcomes rather than optimizing for the next single visit.

Quantitative trading desks model market-making and execution as MDPs where states include current holdings, order book depth, and volatility signals. Actions are bid/ask quote placements and order sizes. The reward is realized profit-and-loss adjusted for inventory risk. Transition dynamics capture adverse selection and market impact. Solving the MDP yields an optimal execution policy that slices large orders to minimize slippage while managing inventory exposure, continuously adapting to shifting market microstructure conditions.

Industrial robots use MDPs to learn dexterous manipulation where states encode joint angles, gripper position, and visual observations of objects. Actions are continuous torque commands. The reward function is sparse, providing positive signal only upon successful grasp completion. Model-based MDP solvers leverage physics simulators to plan trajectories, while model-free reinforcement learning discovers novel grasping strategies through trial and error. This framework enables robots to handle novel objects with varying shapes, textures, and weights without explicit programming.

Task-oriented dialogue systems are formalized as MDPs where states represent the dialogue history and user intent belief, actions are system utterances or API calls, and rewards encode task completion minus turn count penalties. The transition function models user responses, including clarifications and digressions. Solving the MDP produces a dialogue policy that efficiently gathers required information while handling unexpected user inputs. Modern implementations combine MDPs with large language models, using the policy to guide high-level conversation flow while the LLM handles natural language generation.

The recursive decomposition that defines the value function in an MDP. It expresses the relationship between the value of a current state and the values of successor states, factoring in immediate reward and discounted future value. The Bellman Optimality Equation specifically defines the value under an optimal policy, forming the theoretical basis for dynamic programming and Q-learning.

A model-free reinforcement learning algorithm that learns the optimal action-value function, or Q-function, without requiring a model of the environment's transition probabilities. It iteratively updates Q-values using the Bellman equation as an update rule:

• Learns off-policy from raw experience
• Converges to an optimal policy given infinite exploration
• Forms the basis for advanced algorithms like Deep Q-Networks (DQN)

A class of algorithms that directly optimize a parameterized policy without maintaining a value function. Unlike value-based methods, policy gradients:

• Naturally handle continuous action spaces
• Learn stochastic policies for exploration
• Optimize by estimating the gradient of expected cumulative reward
• Key algorithms include REINFORCE, PPO, and TRPO

A function estimating the expected long-term cumulative reward from a given state. Two primary types exist:

• State-Value Function V(s): Expected return starting from state s under a policy
• Action-Value Function Q(s,a): Expected return starting from state s, taking action a These functions are central to temporal difference learning and actor-critic architectures.

The fundamental dilemma in sequential decision-making where an agent must choose between:

• Exploration: Gathering new information about uncertain state-action pairs to improve future decisions
• Exploitation: Leveraging current knowledge to maximize immediate reward MDP solutions must balance this tradeoff to avoid suboptimal local maxima. Techniques like epsilon-greedy and Thompson Sampling formalize this balance.

A hybrid learning method combining Monte Carlo ideas with dynamic programming. TD learning:

• Learns directly from raw experience without an environment model
• Bootstraps from current value estimates rather than waiting for final outcomes
• Underpins algorithms like SARSA and Q-learning
• Enables online, incremental learning in non-episodic MDPs