Markov Decision Process (MDP)

The complete set of distinct situations 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.

• Example: In last-mile delivery, a state might encode the vehicle's current grid location, remaining capacity, and the set of undelivered parcels.
• Design: A compact, informative state representation is critical; omitting key variables (like remaining driver hours) breaks the Markov assumption and degrades policy quality.

The set of all possible moves the agent can execute in a given state. Actions can be discrete or continuous and are the agent's only mechanism for influencing the environment.

• Discrete Actions: Navigate north, south, east, west on a grid; accept or reject a new order.
• Continuous Actions: Apply a specific steering angle and acceleration value.
• Constraint: The set of available actions may be state-dependent (e.g., you cannot 'deliver' if the vehicle is empty).

The core stochastic element, defining the probability of moving from state s to state s' after taking action a. It is formally expressed as P(s' | s, a).

• Deterministic vs. Stochastic: In a deterministic grid world, 'move north' always succeeds. In a stochastic delivery model, 'dispatch to zone A' has a 70% chance of on-time arrival and a 30% chance of delay due to traffic.
• Model-Based vs. Model-Free: If the transition function is known, the agent can plan internally. If unknown, the agent must learn it through real-world interaction.

A scalar feedback signal received after transitioning from state s to s' via action a. It defines the goal, not how to achieve it. The agent's objective is to maximize the cumulative discounted reward over time.

• Sparse Rewards: +100 for successful delivery, 0 otherwise. Simple but hard to learn from.
• Dense Rewards: -1 per time step (penalizing delay), +10 for each parcel dropped off. Provides constant learning signal.
• Shaping: Carefully designing intermediate rewards is essential for guiding the agent toward the terminal goal in complex routing problems.

The agent's brain—a mapping from states to actions. It dictates the behavior: π(a|s) is the probability of selecting action a in state s. The goal of solving an MDP is to find the optimal policy π*.

• Deterministic Policy: In state s, always take action a (e.g., always turn right at this intersection).
• Stochastic Policy: In state s, take action a1 60% of the time and a2 40% of the time. Useful for exploration and optimal play in games like rock-paper-scissors.

A value between 0 and 1 that determines the present value of future rewards. A reward received k steps in the future is worth γᵏ times its immediate value.

• γ ≈ 0 (Myopic): The agent aggressively prioritizes immediate rewards, ignoring long-term consequences. A delivery agent might refuse a slightly out-of-the-way pickup even if it leads to a high-value chain.
• γ ≈ 1 (Farsighted): The agent values future rewards almost as much as immediate ones, enabling long-term strategic planning like repositioning an empty vehicle to a high-demand area.

The two core concepts solved for in an MDP. A policy (π) is a mapping from states to actions—the driver's rulebook for which street to take next. A value function (V(s)) estimates the expected long-term reward from a given state, quantifying how 'good' it is to be at a specific location at a specific time.

• *Optimal Policy (π)**: The strategy that maximizes cumulative reward, such as minimizing total delivery time.
• State-Value Function: Predicts future on-time probability from the current vehicle location.

The recursive decomposition that makes solving MDPs computationally tractable. It states that the value of a state equals the immediate reward plus the discounted value of the next state, assuming optimal actions thereafter. This principle underpins dynamic programming solutions for the Vehicle Routing Problem (VRP).

• Bellman Optimality Equation: Defines the condition an optimal value function must satisfy.
• Discount Factor (γ): Models the preference for immediate on-time deliveries versus future ones, typically set between 0.9 and 0.99.

The 'Markov' property of an MDP: the future state depends only on the current state and action, not on the history. In last-mile delivery, this models the probabilistic nature of travel times. An action (taking a route) does not lead to a deterministic outcome but to a distribution of possible arrival times due to traffic and weather.

• Transition Probability P(s'|s,a): The probability of arriving at the next stop on time given the current location and chosen route.
• Markov Property: Simplifies complex historical traffic patterns into the current state of congestion.

The fundamental trade-off in learning an MDP without a pre-defined model. An agent must exploit known high-reward routes to ensure current delivery performance while also exploring new, potentially faster paths to improve future efficiency. This is critical for adapting to urban dynamics.

• ε-Greedy Strategy: A simple method where the agent chooses a random action with probability ε, otherwise exploits the best-known route.
• Upper Confidence Bound (UCB): A more sophisticated approach that balances the estimated value of a route with the uncertainty of that estimate.

An extension of the MDP framework where the agent cannot directly observe the true state of the world. A delivery vehicle only sees its own GPS location, not the full traffic state or all other drivers' intentions. The agent must maintain a belief state—a probability distribution over possible true states.

• Belief State Update: Uses Bayesian inference to update the understanding of traffic conditions based on new sensor readings.
• Application: Essential for coordinating autonomous mobile robots in a warehouse where sensor occlusion is common.