Sequential Decision Making with Markov Processes, Explained

UPI Study › Courses › Introduction to Artificial Intelligence › Free lessons › Lesson 4.9 Free with a free account

Sequential Decision Making with Markov Processes

Introduction to Artificial Intelligence · Chapter 4: Search, Heuristics, and Game StrategySection 4.9 · lesson 31 of 6913 min · free with a free account

← Working with Constraint Satisfaction ProblemsNext lesson: Probabilistic Graphical Models for Learning →

Earn 3 college credits for Introduction to Artificial IntelligenceRecommended for credit by NCCRS · Computer Science 373 · self-paced · one payment, lifetime access
Enroll in Introduction to Artificial Intelligence · $250 →Download the syllabus (PDF)

In this lesson

Plan under uncertainty with Markov decision processes, value iteration, and policy iteration.

  • Describe the parts of a Markov decision process and the Markov property
  • Calculate discounted returns and Q-values using the Bellman equation
  • Compare value iteration and policy iteration for finding an optimal policy
  • Explain how reward design changes an agent's optimal behavior

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,811 words). Read along, or search it.

Opening Problem

A Warehouse Robot With Slipping Wheels

A delivery robot moves through a warehouse. Each turn it takes now decides which aisles it can reach later. And its wheels slip. Sometimes it ends up beside the square it aimed for. Near a loading dock with a steep drop, the smart route may be the longer one, away from the edge. How can an agent plan a whole sequence of moves, when any move might not go where it intended?

Definition

Markov Decision Processes and the Markov Property

The standard framework is the Markov decision process, or MDP. An agent chooses actions again and again, the results are uncertain, and each step can bring a reward. It rests on the Markov property: the next state depends only on the current state and the action, not on how the agent got there. For a robot on a grid, where it goes next depends on the square it's on, and the move it tries. Its earlier path doesn't matter.

Key Parts

States, Actions, Transitions, Rewards, Discount, Policy

An MDP has six parts. The states are the situations the agent can be in: here, each square of a grid. The actions are its choices: up, down, left or right. The transition model gives the chance of each next state. The intended move happens 80 percent of the time, and each sideways slip, 10 percent. The reward is a number received for entering a state. The discount factor, gamma, says how much less a later reward is worth. And a policy is a rule that gives an action for every state.

Running Example

A Four-by-Three Grid World

Here's the world we'll use throughout: a grid of four columns and three rows, with a wall in the middle of the second row. The top-right square is the goal, worth plus 10. Just below it is a pit, worth minus 10. Entering either one ends the run. Every other square costs a little, minus 0.1, so time isn't free. The robot starts in the bottom-left corner. When it tries to move, it goes the intended way 80 percent of the time, and slips to either side 10 percent each. Bumping into a wall leaves it where it was. And the discount factor is 0.9.

Policies

Why a Fixed Plan Is Not Enough

Without randomness, a plan, a fixed list of moves, would be enough. Here it isn't. Plan up, up, right, right, right. Slip on the first step, and the rest of the plan no longer fits. A policy says what to do from every square. Wherever a slip lands the robot, the policy still has an answer. Solving an MDP means finding the optimal policy: the one that earns the most reward on average.

Discounted Return

How Gamma Shrinks Distant Rewards

Over a run, the robot collects a stream of rewards. To compare runs, add them up, but count a reward k steps away as worth gamma to the k times its value. That total is the discounted return. Sooner is better than later, distant rewards are less certain, and the total stays finite. Take a reward of 10. With gamma 0.9, it's worth 5.90 when it's five steps away, and 1.22 at twenty steps. With gamma 0.5, five steps away it's worth only 0.31. With 0.99, it's still worth 8.18 at twenty steps. A small gamma makes the agent short-sighted. A gamma near 1 makes it patient.

Quick Check

A Reward of 4 Now or 10 Later

Quick check. A robot can grab a reward of 4 one step from now, or a reward of 10 six steps from now. It can't have both. Which does it choose if gamma is 0.5? And which if gamma is 0.9? Pause, and decide. The 4 at 0.5, and the 10 at 0.9. With gamma 0.5, the 4 is worth 2 now, and the 10 only about 0.16. With gamma 0.9, the 4 is worth 3.6, and the 10 about 5.31. Same rewards, different patience. Picking the same reward both times is tempting, but the discount alone flips the decision.

Bellman Equation

Values as a One-Step Look-Ahead

Now, how good is a square? The value of a state is the discounted return the agent can expect, starting there and then acting well. The Bellman idea makes values computable. A state's value is the expected next reward, plus the discounted value of the state it lands in. A long chain of decisions becomes a one-step look-ahead, because the next state's value already sums up everything after it. In symbols: V star of s is the largest, over actions, of a sum over next states: each one's chance, times its reward plus gamma times its value.

Q-Values

Q-Values and the Bellman Expectation Equation

The bracket, summed for one action, is that action's Q-value: how good it is to take action a in state s, then act optimally. The optimal policy just picks the action with the highest Q-value, in every state. And for a fixed policy, drop the largest over actions, and use the policy's own action. That's the Bellman expectation equation: the value of a given policy.

Worked Example

One Sweep Beside the Pit

Let's try one sweep by hand. Every square starts at value 0. Take the square just left of the pit. Moving up: 80 percent, it moves up and pays 0.1. 10 percent, it slips into the wall and stays. 10 percent, it slips into the pit: minus 10. That's minus 1.09. Moving down gives the same, minus 1.09. Left is safe: every outcome costs 0.1, so minus 0.10. And right heads straight for the pit: minus 8.02. So on the first sweep, the safe move wins, because the goal's value hasn't reached this square yet. Next to the goal, it's different. Moving right is worth 0.8 times 10, less two small slips: 7.98. The goal's pull has started to spread.

Value Iteration

Sweep Until Values Stop Changing

Value iteration turns the Bellman equation into an update rule. Start every value at 0. Sweep: for every state, compute each action's Q-value from the current values, and keep the largest. Check the largest change in any value. If it's below a small threshold, stop. Otherwise, sweep again. Finally, read off the policy: in each state, the action with the highest Q-value.

Convergence

Values Spread Outward Like a Wave

Watch the values over the sweeps. The square next to the goal jumps to 7.98 on sweep 1, and settles at 9.39. Two squares from the goal stays negative for one sweep, then rises to 5.63, and ends at 8.12. The top-left corner turns positive on sweep 3. And the starting square stays near zero until sweep 5, then climbs to 5.01. Information moves outward like a wave. A square becomes valuable only after a neighbor already is. The largest change shrinks every sweep. With a threshold of one millionth, it stops after 23 sweeps. The policy usually settles much sooner.

Optimal Policy

The Careful Route Away From the Pit

Here's the policy value iteration reads off. From the start, the robot goes up, then right along the top row. That's longer than the bottom route. But the bottom route runs beside the pit, where one slip costs 10, so the careful route earns more on average. Notice the bottom-right square. It walks left, away from the pit, accepting a longer trip. The start square's final value is 5.01.

Quick Check

Q-Value of Moving Forward

Quick check, with new numbers. A robot in a hallway tries to move forward. 80 percent of the time, it reaches a square valued 6. 10 percent, it slips to a square valued 2, and 10 percent, to a square valued 0. Each step pays minus 0.1, and gamma is 0.9. What is the Q-value of moving forward? Pause, and work it out. About 4.4. Each outcome is the step reward, plus 0.9 times the next value. That's 0.8 times 5.3, plus 0.1 times 1.7, plus 0.1 times minus 0.1: 4.24, plus 0.17, minus 0.01. 4.9 forgets the discount. And 5.3 forgets the slips: it counts only the intended outcome.

Policy Iteration

Evaluate, Improve, and Repeat

Policy iteration reaches the same answer by another route. Start with any policy, even a poor one. Policy evaluation: work out every state's value, if the agent follows this policy forever. That uses the Bellman expectation equation. Policy improvement: in every state, switch to the action with the highest Q-value under those values. If no state changed its action, stop. The policy is optimal. Otherwise, evaluate again. Each round is at least as good as the last, and there are only finitely many policies, so it must stop, at the optimum. On our grid, start from always move down. The robot just slides along the bottom edge, and the start square is worth minus 1. Round 1 changes five squares, but the start still sits at minus 1. Round 2 changes three, and the start jumps to 4.86. Rounds 3 and 4 change two squares, then one, and the start reaches 5.01. Round 5 changes nothing, so it stops. The improvements near the goal had to reach the start before the start could benefit.

Comparison

Value Iteration Versus Policy Iteration

So which method wins? Value iteration does many cheap sweeps: here, 23. Policy iteration does a few expensive rounds, each a full evaluation and an improvement: here, four, plus a final check. Value iteration reads off its policy at the end. Policy iteration knows its policy is final when a round changes nothing. Both find the same optimal policy.

Reward Effects

Changing Only the Step Reward

Grid worlds show something important: an agent doesn't follow what we meant. It follows the rewards we wrote down. Keep the grid, the slips and the discount, and change only the step reward. At minus 0.1, the robot takes the careful route, away from the pit. At minus 5, every step hurts, so it hurries. From the bottom-right square, it steps up toward the pit: a long safe walk costs more than the pit. At plus 1.5, each step pays. Staying alive is worth about 1.5 over 1 minus 0.9: 15, which beats the goal's 10. So it avoids both exits, and wanders the grid forever.

Reward Design

Agents Follow the Rewards Written Down

Reward design is part of the problem. A cleaning robot paid for each piece of trash it collects might learn to scatter trash, and collect it again. When an agent behaves oddly, check the rewards first.

Limitations

Known Models, Full Observation, Every State

These methods have limits. They need a known model: the transition chances and the rewards. Without them, an agent must learn from experience, a topic for later. They assume the agent can see exactly which state it's in. And they store a value for every state. Twelve squares is easy. A board game with astronomically many positions isn't, so large problems need approximations.

Key Takeaways

MDPs and Their Solutions Summed Up

To sum up. An MDP models repeated choices with uncertain results: states, actions, transitions, rewards and a discount. A policy gives an action for every state, because slips can land the agent anywhere. The Bellman equation turns a long sequence into a one-step look-ahead. Value iteration sweeps values, and policy iteration evaluates and improves. Both find the same optimal policy, and what it does depends on the rewards.

Reflection

Setting Rewards for a Robot Vacuum

Something to think about. A robot vacuum earns plus 1 for each square it cleans, and minus 1 each time it bumps a wall. It also pays a small penalty for every minute it runs. What might it learn if that penalty is too low? Too high? How would you set the rewards?

About Introduction to Artificial Intelligence at UPI Study

Introduction to Artificial Intelligence (Computer Science 373) is a self-paced online course of 69 video lessons in 9 chapters, from intelligent agents and search to game strategy, neural networks, logic and reasoning, machine learning, language, robotics and AI ethics. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: AI vs Current Trends in CS and IT

Why take it here

Why students take Introduction to Artificial Intelligence with UPI Study

How machines search, reason and learnIntroduction to Artificial Intelligence covers how AI systems are built: intelligent agents, search and heuristics, game strategy, logic, neural networks, machine learning, language and perception, and the ethics of AI. It is a common upper-level course in computer science degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Introduction to Artificial Intelligence carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Sequential Decision Making with Markov Processes

What is a Markov decision process?
A Markov decision process, or MDP, models an agent that makes repeated choices with uncertain results and receives rewards along the way. It has states, actions, a transition model giving the chance of each next state, rewards, and a discount factor. It relies on the Markov property: the next state depends only on the current state and action, not on the agent's earlier path.
What does the discount factor gamma do in a Markov decision process?
The discount factor gamma, between 0 and 1, sets how much less a later reward is worth: a reward k steps away counts as gamma to the k times its value. With gamma 0.9, a reward of 10 five steps away is worth about 5.90. A small gamma makes an agent short-sighted, while a gamma near 1 makes it patient. It also keeps total returns finite.
What is the Bellman equation?
The Bellman equation says a state's optimal value equals the best action's expected result: the next reward plus the discounted value of the state the agent lands in, averaged over the possible outcomes. Each next state's value already sums up everything after it, so a long sequence of decisions becomes a one-step look-ahead. That expected result for a single action is its Q-value, and the optimal policy picks the action with the highest Q-value.
What is the difference between value iteration and policy iteration?
Value iteration repeatedly sweeps every state, updating its value with the Bellman equation until changes fall below a threshold, then reads off the policy. Policy iteration starts with any policy, evaluates its values, improves it by choosing the highest Q-value action in each state, and stops when no action changes. Value iteration uses many cheap sweeps, policy iteration fewer costly rounds; both reach the same optimal policy.

About the Introduction to Artificial Intelligence course

How many college credits is Introduction to Artificial Intelligence?
Introduction to Artificial Intelligence (Computer Science 373) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Introduction to Artificial Intelligence cost and what is included?
$250, paid once, with lifetime access: all 69 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Introduction to Artificial Intelligence take?
It is self-paced with no deadlines. The 69 lessons total about 16 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Introduction to Artificial Intelligence.

69 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Introduction to Artificial Intelligence →Download the syllabusEvery course with PRO →
Introduction to Artificial Intelligence
3 credits · NCCRSEnroll →