Chapter 2: Markov Decision Process: Turning Problems intro Solvable Models
This introduction frames Markov decision processes as a way to break down and reconnect complex business decisions over time.
After this chapter you will be able to
- Analysis and synthesis. Explain why breaking a complex business problem into parts must be paired with bringing those parts back together.
- MDP framework for decisions. Describe the high-level role of Markov decision processes in organizing complex business decisions.
- State as a snapshot. Explain what a state represents in sequential decision-making and how it helps describe a complex system.
- Deterministic and Known Transitions. Distinguish deterministic transitions from stochastic transitions with known probabilities, using the software-service example.
- Unknown Stochastic Transitions. Explain what makes transitions unknown in the software-service example and why estimated probabilities may not remain reliable.
- Markov property and computation. Explain the Markov property and why it simplifies sequential modeling.
- Simulated customer transition experiment. Trace how the simulation compares next-state distributions with and without previous-state information, and describe its result.
- Markovian state design. Explain how state design supports the Markov property in a business process.
- Chains versus decision processes. Distinguish a Markov chain’s passive observation from a Markov decision process’s active decisions under uncertainty.
- Decision process components. Describe the roles of state, action, transition probability, and reward in an MDP, using a business example.
- Policies and long-term outcomes. Explain what a policy does and why a good policy considers a sequence of decisions and long-term outcomes rather than only immediate gains.
- Dynamic Pricing MDP. Describe the state, action, reward, and transitions in the online-store pricing example.
- Call Center Scheduling MDP. Describe how the call center example represents staffing decisions, their costs and service effects, and changing conditions.
- Preventive Maintenance MDP. Describe the machine-maintenance example in terms of state, maintenance choices, costs, and uncertain equipment changes.
- Customer Retention MDP. Describe the subscription-retention example using customer state, engagement choices, retention rewards, and uncertain outcomes.
- Markovian State Design. Explain why a state should summarize decision-relevant information and how omitted history can undermine the Markov assumption.
- Factory state and actions. Describe the factory's daily actions and state, and explain why the state includes inventory and machine setup.
- Sampled factory state transitions. Trace how an action and sampled demand produce the factory's next state, and explain why the example uses transition functions rather than a large matrix.
- Profit based reward design. Explain how the factory reward combines revenue with costs and penalties to guide decisions toward profit over the planning horizon.
- Heuristic production policies. Distinguish the example's heuristic production policies and explain what their comparison suggests about long-term trade-offs and the limitations of fixed rules.
- Policy simulation and evaluation. Trace the daily simulation of a policy and describe the profit outputs used to compare policies over the horizon.
- Reward as learning signal. Explain how reward communicates the quality of decisions to an agent and why expressing a business goal as a learnable signal matters.
- Business objectives and constraints. Explain why business reward design must account for both multiple objectives and constraints, using examples from the section.
- Sparse and stepwise feedback. Distinguish sparse end-of-episode rewards from dense or stepwise rewards, and explain why intermediate feedback can help an agent learn during a multi-step task.
- Business objectives as rewards. Describe how a business objective can be translated into numerical stepwise rewards, using the fashion retailer's inventory trade-offs as an example.
- Constraint visibility in state. Explain why constraint information should be included in the state, especially when constraints change.
- Graded Soft Constraint Penalties. Explain how penalty shaping handles soft constraints and enables trade-offs between priorities.
- Hard constraints and masking. Explain why hard constraints require action masking rather than penalties alone, using a capacity limit as an example.
- Masking and gentle penalties. Describe how combining masking with gentle penalties handles invalid and borderline actions differently in the forklift example.
- Reward scale imbalance. Explain how mismatched reward and penalty scales can produce extreme agent behavior, using an example from the section.
- Comparable reward component scales. Describe converting reward components to a common unit and normalizing them when reliable monetary values are unavailable.
- Proxy reward shortcuts. Explain how rewarding a proxy can lead an agent to optimize the reward while undermining the true business objective.
- Balanced recommendation reward. Describe how the recommendation example combines signals to discourage clickbait and better reflect sales and engagement.
Section by section
Introduction
This introduction frames Markov decision processes as a way to break down and reconnect complex business decisions over time.
- Analysis and synthesis: Explain why breaking a complex business problem into parts must be paired with bringing those parts back together.
Why it matters: Breaking a problem apart is useful only if the pieces can be reconnected meaningfully. - MDP framework for decisions: Describe the high-level role of Markov decision processes in organizing complex business decisions.
Why it matters: This framing connects individual decisions to the changing business problem as a whole.
Key terms: systems thinking, analysis, synthesis, Markov decision process, uncertainty, dynamics
2.1 State: Anatomy of sequential decision making
This section introduces states as snapshots of a system and contrasts deterministic, known stochastic, and unknown stochastic transitions.
- State as a snapshot: Explain what a state represents in sequential decision-making and how it helps describe a complex system.
Why it matters: States give us a manageable way to describe a system at the point of decision. - Deterministic and Known Transitions: Distinguish deterministic transitions from stochastic transitions with known probabilities, using the software-service example.
Why it matters: The distinction shows whether a model predicts one certain next state or expresses uncertainty using probabilities. - Unknown Stochastic Transitions: Explain what makes transitions unknown in the software-service example and why estimated probabilities may not remain reliable.
Why it matters: Knowing the possible states does not guarantee that transition behavior is known or stable.
Key terms: state, sequential decision-making, deterministic transition system, stochastic systems with known transitions, transition probabilities, exploratory data analysis, stochastic systems with unknown transitions
2.2 Markov chain and Markov property
This section explains the Markov property, illustrates it with a simulated customer-state chain, and connects it to practical state design.
- Markov property and computation: Explain the Markov property and why it simplifies sequential modeling.
Why it matters: This property makes many sequential decision problems more manageable. - Transition graph and matrix: Describe how the software-service example represents transitions between customer states.
Why it matters: These representations organize the probabilities used to model how customers move between states. - Simulated customer transition experiment: Trace how the simulation compares next-state distributions with and without previous-state information, and describe its result.
Why it matters: The experiment gives a concrete illustration of what it means for history not to change the next-state distribution once the current state is known. - Markovian state design: Explain how state design supports the Markov property in a business process.
Why it matters: What you include in the state determines whether ignoring separate history is a reasonable modeling choice.
Key terms: Markov property, Markovian, curse of dimensionality, transitions, graph, transition matrix, simulation, empirical distribution, Buy Pro, Install Basic
2.3 Markov decision process
This section introduces Markov decision processes as models of action under uncertainty and explains their components and long-term policies.
- Chains versus decision processes: Distinguish a Markov chain’s passive observation from a Markov decision process’s active decisions under uncertainty.
Why it matters: This distinction explains why an MDP can model business decisions rather than just predict what happens. - Decision process components: Describe the roles of state, action, transition probability, and reward in an MDP, using a business example.
Why it matters: These components turn a business situation into a model of choices, uncertain outcomes, and feedback. - Policies and long-term outcomes: Explain what a policy does and why a good policy considers a sequence of decisions and long-term outcomes rather than only immediate gains.
Why it matters: A policy links decisions across time, helping avoid choices that look good now but cause problems later.
Key terms: Markov chain, Markov decision process, prediction, optimization, state, action, transition probability, transition function, reward, policy
2.4 Examples of Markov decision processes
This section models four business situations as Markov decision processes and explains why state and reward design matter.
- Dynamic Pricing MDP: Describe the state, action, reward, and transitions in the online-store pricing example.
Why it matters: This example shows how everyday pricing decisions fit into an MDP. - Call Center Scheduling MDP: Describe how the call center example represents staffing decisions, their costs and service effects, and changing conditions.
Why it matters: The example shows how an MDP can express a cost-versus-service trade-off. - Preventive Maintenance MDP: Describe the machine-maintenance example in terms of state, maintenance choices, costs, and uncertain equipment changes.
Why it matters: This example connects present maintenance costs to uncertain future machine condition. - Customer Retention MDP: Describe the subscription-retention example using customer state, engagement choices, retention rewards, and uncertain outcomes.
Why it matters: This example shows how customer engagement decisions can be modeled despite uncertain behavior. - Markovian State Design: Explain why a state should summarize decision-relevant information and how omitted history can undermine the Markov assumption.
Why it matters: A state that hides important history can leave the agent unable to predict and plan effectively. - Business Goal Reward Alignment: Explain how reward design shapes behavior and why a narrow reward can conflict with broader business goals.
Why it matters: The reward tells the agent what to pursue, which may not match the business's broader aims.
Key terms: state, action, reward, transitions, dynamic pricing, workforce scheduling, queue length, staffing level, preventive maintenance, operating condition
2.5 Build a Markov Decision Process for Production Planning
This section builds and simulates a production-planning Markov decision process, comparing heuristic policies by their profit over time.
- Factory state and actions: Describe the factory's daily actions and state, and explain why the state includes inventory and machine setup.
Why it matters: A useful state captures the information needed to make consequential production decisions. - Demand and variability distributions: Distinguish the Poisson model for daily order counts from the Normal model for aggregate production-time variability.
Why it matters: Choosing a distribution suited to the uncertainty makes a simulation more representative of the business problem. - Sampled factory state transitions: Trace how an action and sampled demand produce the factory's next state, and explain why the example uses transition functions rather than a large matrix.
Why it matters: The transition connects production decisions and uncertain demand to tomorrow's factory situation. - Profit based reward design: Explain how the factory reward combines revenue with costs and penalties to guide decisions toward profit over the planning horizon.
Why it matters: A reward based on net profit makes the trade-offs behind production decisions visible. - Heuristic production policies: Distinguish the example's heuristic production policies and explain what their comparison suggests about long-term trade-offs and the limitations of fixed rules.
Why it matters: Comparing rules shows why a decision that looks good today may be costly over the full horizon. - Policy simulation and evaluation: Trace the daily simulation of a policy and describe the profit outputs used to compare policies over the horizon.
Why it matters: Simulation turns a production rule into a profit trajectory that can be compared with other rules.
Key terms: state, action, inventory level, machine setup, Markovian, Poisson distribution, lambda, Normal distribution, mean, standard deviation
2.6 Reward engineering and constraint handling strategies
This section explains reward as a scalar learning signal and the need to balance business objectives and constraints when designing it.
- Reward as learning signal: Explain how reward communicates the quality of decisions to an agent and why expressing a business goal as a learnable signal matters.
Why it matters: The reward signal translates what the business wants into feedback the algorithm can use. - Business objectives and constraints: Explain why business reward design must account for both multiple objectives and constraints, using examples from the section.
Why it matters: A useful business reward must reflect both what the business wants to achieve and the limits it operates within.
Key terms: reward, scalar signal, reward engineering, multi-objective, reward function, objectives, constraints
2.6.1 Design rewards to be stepwise, whenever possible
This section explains why and how to provide stepwise rewards for multi-step business problems instead of relying only on end-of-episode feedback.
- Sparse and stepwise feedback: Distinguish sparse end-of-episode rewards from dense or stepwise rewards, and explain why intermediate feedback can help an agent learn during a multi-step task.
Why it matters: Reward timing affects how much guidance the agent receives while learning a multi-step task. - Business objectives as rewards: Describe how a business objective can be translated into numerical stepwise rewards, using the fashion retailer's inventory trade-offs as an example.
Why it matters: A numerical reward turns a business objective into feedback an agent can optimize. - Intermediate feedback through approximations: Explain how approximate measures can provide intermediate feedback when the ultimate business outcome is delayed or difficult to break down.
Why it matters: Approximate signals can offer guidance even when the ultimate outcome is not yet observable.
Key terms: episodic problems, sparse reward, dense reward, stepwise reward, Key Performance Indicators, numerical rewards, stepwise rewards, stockout, approximations, intermediate feedback
2.6.2 Inject constraint information into the state
This section explains how including constraint information in an agent’s state supports context-aware decisions and reduces reliance on learning constraints through penalties.
- Constraint visibility in state: Explain why constraint information should be included in the state, especially when constraints change.
Why it matters: Visible constraints give the agent useful decision context before it repeatedly encounters avoidable violations. - Constraint information in practice: Describe how constraint-related features in one of the section’s examples can inform an agent’s decisions.
Why it matters: Concrete state features connect abstract restrictions to the decisions the agent must make.
Key terms: state representation, constraints, state injection, state, current temperature, item sensitivity, power budget
2.6.3 Handle soft constrains with stepwise penalties
This section explains how graded rewards and penalties let an agent handle soft constraints while balancing competing priorities.
- Graded Soft Constraint Penalties: Explain how penalty shaping handles soft constraints and enables trade-offs between priorities.
Why it matters: Graded penalties let an agent weigh tolerable violations against other goals. - Pickup Time Reward Tiers: Describe how the ride-sharing example uses reward tiers to encourage punctuality while tolerating some delay.
Why it matters: The pickup example shows how a reward schedule can distinguish punctuality, tolerable delay, and excessive delay.
Key terms: soft constraints, penalty shaping, gradual penalty, graded feedback, pickup_time, reward system, gradient of penalties
2.6.4 Use action masking with penalties to handle hard constraints
This section explains how action masking and gentle penalties can enforce hard constraints while encouraging safer feasible actions.
- Hard constraints and masking: Explain why hard constraints require action masking rather than penalties alone, using a capacity limit as an example.
Why it matters: Masking keeps the agent from selecting actions that would make a solution invalid. - Masking and gentle penalties: Describe how combining masking with gentle penalties handles invalid and borderline actions differently in the forklift example.
Why it matters: The hybrid approach prevents illegal choices while encouraging safer options among the choices that remain.
Key terms: hard constraints, action masking, state, feasibility, gentle penalties, weight limit, borderline cases
2.6.5 Avoid mismatched scales with reward normalization / balancing
This section explains how mismatched reward scales distort agent behavior and introduces ways to balance reward components and guide learning.
- Reward scale imbalance: Explain how mismatched reward and penalty scales can produce extreme agent behavior, using an example from the section.
Why it matters: Reward magnitudes can make an agent pursue behavior that conflicts with the intended balance of objectives. - Comparable reward component scales: Describe converting reward components to a common unit and normalizing them when reliable monetary values are unavailable.
Why it matters: Comparable scales help prevent one objective from overwhelming the rest solely because of its numerical magnitude. - Adaptive Lagrangian constraint balancing: Describe how Lagrangian methods adapt the importance of constraints rather than relying on rigid penalties.
Why it matters: Adjusting constraint importance can avoid the over- or under-punishment of fixed penalties. - Potential-based reward shaping: Describe the stated purpose of potential-based reward shaping.
Why it matters: Intermediate feedback can guide learning while retaining the intended ultimate goal.
Key terms: scale imbalance, reward components, risk penalties, common unit, normalization, reward and penalty values, Lagrangian methods, constraints, rigid penalties, potential-based reward shaping
2.6.6 Avoid deceptive shortcuts in reward function
This section explains how proxy rewards can produce deceptive shortcuts and how better reward design and monitoring can discourage them.
- Proxy reward shortcuts: Explain how rewarding a proxy can lead an agent to optimize the reward while undermining the true business objective.
Why it matters: A high reward can conceal behavior that makes the actual business outcome worse. - Balanced recommendation reward: Describe how the recommendation example combines signals to discourage clickbait and better reflect sales and engagement.
Why it matters: Combining relevant signals can make the reward favor the outcome the business actually wants. - Reward behavior monitoring: Describe how simulations, audits and scenario testing help detect unwanted behavior even when a proxy appears suitable.
Why it matters: Checking actual behavior can reveal reward loopholes before they become costly. - Business simulation environment: Describe the role and basic components of a simulation environment before an agent learns.
Why it matters: The environment gives an agent a business-relevant place to experiment and learn.
Key terms: proxy, true objective, deceptive shortcut, click count, revenue, bounce rate, normalized combination, simulations, audits, scenario testing
2.7 Summary
Where this is used later
- The domino decision rule: Bellman equations (chapter 4) · The Markov property underlies the one-step decomposition.
- Conceptual framework for designing business environment (chapter 3) · Environment design relies on representing the business situation.
- Solving bellman equations: Generalized Policy Iteration (chapter 4) · Provides the concept of a policy for policy iteration.
- Perishable product dynamic pricing environment (chapter 3) · The dynamic pricing environment builds on framing pricing as sequential decisions.
- Trailer loading and packing environment (chapter 3) · Reward engineering and constraint-handling strategies.
- The gap between an algorithm and a system (chapter 12) · Reward engineering and constraint handling strategies.
- Warehouse order picking environment (chapter 3) · The use of stepwise rewards.
- Hands-on code: solving a resource allocation problem (chapter 4) · Using penalties to represent undesirable outcomes.
Concepts explained in this chapter
- Markov decision processA Markov decision process is a formal model of sequential decision-making in which an agent selects actions in states, receives rewards, and causes probabilistic transitions whose relevant future behavior depends on the current state.
- Markov propertyThe Markov property is the condition that the distribution of future states and rewards depends on the current state and action rather than on unrepresented earlier history.
- transition probabilityA transition probability is the probability of moving from one state to another in a stochastic system.
- stateA state describes the relevant condition of an environment at a particular point in a sequential decision process.
- reward functionA reward function is a mapping that assigns numerical feedback to states, actions, transitions, or outcomes in a decision process.
- reward signalA reward is a numerical feedback signal indicating the desirability of an outcome or transition after an agent's action.
- Poisson distributionThe Poisson distribution gives the probability of a count of independent events occurring during a fixed interval at a roughly constant average rate.
- backorderA backorder is an unfulfilled customer demand recorded for later fulfillment because available inventory was insufficient.
- greedy policyA greedy policy selects the product with the lower current stock level, resolving equal stock levels by choosing scooter.
- holding costHolding cost is the expense incurred for keeping unsold inventory over time.
- inventory levelAn inventory level is the quantity of a product currently held and available for sale or use.
- machine setupA machine setup is the configuration of production equipment required to manufacture a particular product.
- market demandCustomer demand is the quantity of products customers request during a specified period, with stochastic demand varying unpredictably over time.
- never switch policyA never switch policy continues producing the configured product until a target inventory is reached and then idles without changing setup.
- normal distributionA Gaussian distribution is a continuous probability distribution characterized by a mean and standard deviation.
- production planningProduction planning is the process of deciding what products to manufacture, in what quantities, and when, subject to capacity, demand, and cost considerations.
- setup costA setup cost is the expense incurred when configuring or switching production equipment for a product.
- setup-aware policyA setup-aware policy uses inventory thresholds and the current production setup to avoid unnecessary product switches while responding to critical shortages.
- Markov chainA Markov chain is a stochastic model describing how a system evolves among states when the next state depends probabilistically on the current state.
- actionAn action is a choice made by an agent that can affect the subsequent state of its environment.
- policyA policy is a decision rule, possibly probabilistic, that assigns actions or action probabilities to states for an agent.
- AI agentAn entity in reinforcement learning that observes an environment, selects actions, and improves its behavior from feedback.
- state transitionA state transition is a change from one environment state to another resulting from an action and possibly random effects.
- state designState design is the technique of selecting and structuring state information so that it captures the factors needed to predict relevant future outcomes and make decisions.
- reward engineeringThe process of specifying how outcomes or behaviors are evaluated and mapped to reward feedback.
- dense rewardA stepwise reward is feedback assigned at individual decision steps rather than only at the end of an episode or process.
- Markov processA Markov process is a stochastic process whose future behavior is conditionally independent of the past given its current state.
- dynamic pricingDynamic pricing is the adjustment of prices over time in response to changing demand, inventory conditions, expiration, or competitive factors.
- workforce shift schedulingWorkforce scheduling is the assignment of staff levels and working periods to meet anticipated demand while balancing labor cost and service requirements.
- environmentAn environment is the external system or setting with which an agent interacts and whose responses produce consequences for the agent's actions.
- sparse rewardA sparse reward is a feedback signal provided at only a small number of points, rather than continuously throughout a task.
- constraintA restriction that limits the values or combinations allowed in an optimization problem, including which actions are valid in a state.
- curse of dimensionalityThe curse of dimensionality is the rapid growth of computational complexity as the number of dimensions or tracked variables increases.
- probability distributionA probability distribution specifies the probabilities assigned to the possible values of a random variable.
- simulationSimulation is the execution of a model that reproduces interactions or outcomes of an environment without operating directly in the real environment.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
