To grasp how Markov decision processes work, imagine you are playing a game of chess against a computer. You move your queen to check the computer’s king. The computer now has to decide where to move to avoid losing. In this scenario, the king is considered the agent. Meanwhile, the position of the king when checked in square E8 is known as its current state (S). From this position, the king has the option to take various actions (A)—such as moving up (E7), to its right (D8), or to its left (F8).

The computer evaluates each possible action based on the expected outcomes, seeking to avoid a checkmate and put itself in a favorable position for future moves against you. In other words, the computer must determine the potential reward of each action. After evaluating all possible actions, the computer decides to move to D8, making it its new state (S’). Once the move is made and the intended successful outcome is reached, the computer will refine its approach for future actions by associating similar board states with actions that have historically led to better outcomes.¹

The series of steps that the computer took is known as a Markov decision process (MDP). In an MDP, a computer uses a mathematical model to evaluate an agent’s current state (checked at E8), the environment of the system (the game of chess), possible actions (move to E7, D8, or F8), and the rewards of all these potential new states. Markov decision processes are focused only on the current state of the agent, not historical states. For example, the computer would not consider where the king was before E8, as MDPs assume that the current state of an agent holds all relevant information about its previous state.²

Markov decision processes are useful in systems where there are a variety of choices available in uncertain environments. Computers can be trained to automate decision-making in a wide range of dynamic settings to maximize rewards. For instance, if you were attending a conference and your company wanted to minimize travel costs, an MDP could help them determine the most optimal route. A fisherman could use an MDP to estimate how many salmon to fish each year to maximize profit but ensure long-term yield. Urban planners can use the decision-making process to decide the optimal duration of a red light at an intersection to ensure safety and avoid long wait times.³

In short, Markov decision processes are applied in various sectors to solve complex problems by breaking them down into management states. Whether used in computer science, resource management, or urban planning, MDPs offer a structured way to navigate uncertainties and maximize positive rewards. 

Model: A prediction on how a given action will affect the state (S) of the agent, including what the new state (S’) will be when an action (A) is taken. If it’s not guaranteed that the action will result in S’, the model will evaluate the probability that S taking A will result in S’.¹

Agent: The entity that interacts in an environment and will make sequential actions.

State: The current position that the agent is in, as well as every state the agent could be in, depending on the action it takes. MDPs assume that the current state of an agent holds all relevant information about previous states, and therefore previous states do not need to be considered when making a decision.¹

Action: One action (A) from a set of all possible actions an agent can take in its current state (S).¹

Reward: The expected outcomes, both positive and negative, that the agent will experience for each available action.²

Policy: An agent’s strategy for choosing actions that is considered to be the best possible outcome for an agent in its current state, which can be applied again later in similar circumstances. There can be multiple policies, but the goal is typically to find the optimal policy, which maximizes cumulative rewards. A policy is not a single action but rather a mapping from states to actions, guiding the agent’s behavior across all states.¹

Markov Chains:  A mathematical system where an agent experiences transitions from one state to another based on probable outcomes. Markov chains show how probabilistic methods can be applied to independent events using only the current state of an agent to determine possible future outcomes instead of historical sequences of states.⁴

Stochastic: A description of an environment in which outcomes are uncertain and there is a degree of randomness. MDPs operate in a stochastic system, evaluating the probable consequences of new states.

Dynamic Programming: A method used in mathematics and computer science that breaks down complex problems into simpler subproblems to arrive at a solution.

Bellman Equation: A mathematical equation that divides decisions into smaller subproblems. This form of dynamic programming explores the immediate reward from an action as well as potential long-term rewards for future actions in order to find the optimal policy.² The Bellman equation suggests that a long-term reward for a given action is equal to the reward from the current action combined with expected rewards from future actions.⁵

Machine Learning: A subfield of artificial intelligence where computer systems learn by drawing inferences from patterns in data to improve their function over time without needing explicit instructions. Policies developed by MDPs allow a machine to develop algorithms to replicate advantageous actions in the future. 

Reinforcement Learning: A sub-field of machine learning that trains a computer to make decisions based on the potential rewards of a choice. In MDPs, the agent considers the reward of each possible action to make the optimal decision.⁶

In the 17th century, gambling and games of chance were all the rage. Two French mathematicians, Pierre de Fermat and Blaise Pascal, wanted to determine how winnings should be divided if a game of chance is interrupted before completion. The two quarreled over how it should be done, with Fermat developing a method that enumerated all possible outcomes for the remaining rounds of the game, a solution that his colleague viewed as accurate but unwieldy. Pascal instead approached the problem with a more elegant, recursive strategy that relied on principles of expectation and probability by using the idea of expected value to allocate the winnings, taking into account the probabilities of different outcomes in future moves without listing them out explicitly. Their correspondence on this problem of points is recognized as the birth of modern probability theory.⁷

Probability models allowed people to make informed decisions even when the environment included a degree of randomness or uncertainty, leading to smarter choices. Over time, probability theory became prominent in both practical applications, like managing risk when determining insurance rates, as well as theoretical areas, such as game theory. However, one challenge that persisted with probability-based modeling techniques was the problem of predicting sequences of dependent events. In its early days, probability theory mainly dealt with independent events and static systems, where outputs are independent of past or future states and do not change over time.

In 1906, Russian mathematician Andrey Markov paved the way for a new domain of probability theory that could handle dynamic, evolving systems called Markov chains.⁶ This is a mathematical model that determines the probability of different outcomes based on the present state of a system. A crucial aspect of Markov chains is that the model does not consider the earlier history of a system but looks only at its present state.⁸ This strategy provided a new and relatively simple way for probability models to address complex systems, like predicting future stock prices or weather patterns.

American mathematician Richard Bellman expanded the concept of Markov chains in the 1950s, showing how they could be applied to decision-making principles by introducing the concept of an agent with multiple choices available to them for transitioning into a new state. By breaking down complex problems into simpler steps, agents could make better choices. Bellman also introduced the self-named Bellman Equation, which factors in the potential immediate and long-term rewards and outcomes of each choice.² Combined, the Bellman equation, dynamic programming, and Markov Chains led to Bellman’s overall development of Markov decision processes.

In 2012, American mathematician Lloyd Shapley used the Markov decision process to create the Shapley value, a mathematical way to distribute payouts based on individual contributions—a formalized method to achieve what Fermat and Pascal originally attempted, bringing Markov decision processes full circle!⁹

Pierre de Femart and Blaise Pascal

French mathematicians who laid the foundation for the modern probability theory through a discovery made in a game of chance where they had to divide winnings from an unfinished game. They each created independent solutions that divided the winnings up by possible outcomes of the remaining rounds. Fermat also contributed to the development of calculus, while Pascal invented one of the first calculators.⁷

Andrey Markov

A Russian mathematician best known for his mathematical and scientific contributions to probability theory. Through the development of Markov chains, Andrey Markov demonstrated that predictions could still be made in stochastic environments where there is a degree of uncertainty. Although the outcome of an action may be determined by chance, Markov showed that evaluating the probability of several possible outcomes can help people make decisions.¹⁰

Richard Bellman

An American mathematician who made significant contributions to computer science, Bellman is best known for developing the Bellman equation and dynamic programming, which when combined with Markov Chains, created Markov decision processes.⁵

Lloyd  Shapley

An American mathematician who won the Nobel Memorial Prize in Economic Sciences in 2012 for his contributions to game theory. Lloyd Shapley developed the Shapley value, which showed that in a cooperative game, players who make unequal contributions can cooperate to reach a more favorable common goal and still allow for a fair resource allocation based on individual contributions.¹¹ Shapley’s paper on stochastic games—the first formulation of a dynamic, multi-stage game involving transition probabilities—combined game theory with Markov decision processes.⁹ 

Markov decision processes provide a framework for making decisions in uncertain environments and are a foundational concept in reinforcement learning. Computers can apply MDPs to build algorithms that effectively demonstrate the relationship between states, actions, and rewards, and depending on the outcome, the computer will learn how to optimize decisions for similar scenarios in the future. This concept can be useful in various fields, such as robotics, healthcare, and financial management.

Advancing Robotics

Markov decision processes enable robots to make decisions in response to ever-changing environments, learning from each action to improve future outcomes. They allow robots to explore different strategies in real time, refining their actions based on feedback to navigate obstacles more efficiently.

For example, an automatic vacuum that finds itself stuck in the corner of a room can use an MDP to evaluate the outcome of its next move. It could turn to the right, turn to the left, or do a 180-degree turn. Over time, the vacuum would learn that a 180-degree turn is the most effective way to get unstuck from this position, and can make that decision every time. 

This development is significant for advancing robotics, as it provides a way for robots to improve autonomously rather than only on pre-programmed instructions. Markov decision processes allow robots to learn from their own actions and improve over time.

Optimizing Healthcare

Healthcare providers make a vast amount of decisions daily that will have profound impacts on their patients and families. In some cases, a single decision can mean the difference between life and death. There are many potential treatment plans that doctors can suggest, with varying degrees of effectiveness. To complicate matters further, a patient’s individual biology can influence the outcome of a treatment and there are finite resources available. To put it simply, there is a great deal of uncertainty in this environment.¹²

In such a complex, dynamic system, MDPs can be very valuable in helping doctors break down complex challenges into smaller steps and make data-driven decisions about interventions and treatment plans. As MDPs improve over time due to reinforcement learning, they can tailor approaches based on specific symptoms of patient profiles, leading to more efficient treatment responses. 

Improved Financial Management

Financial decisions are often sequential: what you choose to do today with your money will impact the decisions you will be able to make at a later date. However, it can be difficult to know where to invest your money in the uncertain environments that are stock markets. 

An MDP can evaluate the risks and rewards of each stock based on the current state of the stock and determine the probability of both favorable and unfavorable fluctuations. This can help people decide the best asset allocation strategy. 

For example, an MDP could explore the potential risks and rewards of two different stocks. Stock A is low risk and low reward, steadily increasing over time, whereas Stock B is high risk and high reward, fluctuating significantly but potentially yielding higher returns. A Markov decision process can determine when is the right time to invest in either stock for optimal returns.

While Markov decision processes can help us make decisions in uncertain conditions, they make several assumptions that are not always reflective of real-life scenarios. Some of its limitations include that it relies on the Markovian property, which simplifies decision-making to a single agent and requires extensive data for effective analysis. 

Assumption of Markovian Property

A crucial aspect of Markovian decision processes is that the transition probabilities and outcomes depend only on the current state of the agent and system, not any past states. However, in real life, past states and actions often significantly impact our future decisions and their outcomes.¹³

Let’s say a customer service bot receives a complaint from a customer. If the bot is only looking at the customer’s current complaint, it may not make the decision that is best to minimize the customer’s frustrations and reduce costs. For example, if it's the first complaint, the best decision may be to give the customer a refund or discount. However, if it’s their fifth complaint, and the bot fails to recognize this pattern because it is only considering the current state (the present complaint), then the company could risk being exploited by repeatedly offering refunds or discounts. 

Assumption of Single Decision-Makers

MDPs assume that there is a single agent making decisions and that the agent makes rational decisions. However, in many real-life situations, there are multiple agents at the table negotiating with one another to come to a decision that all stakeholders are happy with. Imagine you are picking a place to eat dinner with your partner. An MDP would only take into account your preferences in evaluating the potential reward (a yummy dinner), but not your partners. The optimal solution is more likely to be something that satisfies both of your cravings, not the one that best satisfies yours.  In these instances, game theory is better suited to explain and analyze strategic interactions between multiple agents.

Require Vast Amounts of Data

Although Markov decision processes ignore the earlier history of a system or agent, they still require a lot of data to come to an optimal decision. The process requires analysis of what transitions or actions are available, the outcomes of each of those transitions or actions, and how likely it is that the assumed outcome will happen. While advances in technology have made it easier for a computer to process and analyze vast amounts of data, there aren’t many options for easy-to-use software that can run MDPs, making them inaccessible to many.¹⁴ The same limits show up in medicine: a 2024 review by Singh and colleagues of MDPs in cancer treatment planning points to the need for accurate input data and the heavy computing burden of solving large MDP problems.

Using an MDP Model to Determine Airline Meals

It may feel like flights are ridiculously expensive these days, but the airline industry actually operates on surprisingly low-profit margins. To turn a profit, airlines must increase efficiency while reducing unnecessary costs.

One area where airlines can make smart decisions to reduce costs is in the provision of meals. Airlines have to determine the number of meals they stock each aircraft with to provide good customer service while also keeping costs as low as possible. There are uncertain variables in this decision-making process, even for a single flight: they can’t predict with certainty the final passenger load, the meals that passengers will choose, and how many passengers will elect to have a meal. Airlines can change the number of meals ordered from a caterer at different intervals, but the closer it is to the flight time, the more expensive it becomes to make last-minute adjustments. That’s why airlines need to decide the number of meals based on the most probable outcomes.

Researchers from the University of British Columbia conducted a study to show how a Markov decision process could be used by airlines to optimize meal provision. They analyzed 40 Canadian Airline flights departing from the same destination and applied an MDP to determine the best policy. The MDP evaluated all possible actions and outcomes to determine how many meals should be ordered based on the length of the flight and estimated passenger count. 

The researchers concluded that by using a Markov decision process, airlines could benefit from an 18% reduction in overage costs for long flights. This analysis also revealed that for short flights, airlines typically overestimate meals, leading to increased costs. The MDP provided important insights to help airlines determine how many meals to order per flight depending on its duration.¹⁵ 

Implementing Markov Decision Processes in Healthcare

Each day, doctors have to make decisions regarding the best treatment plan for their patients. This can include choosing whether or not to operate, weighing the likelihood that the surgery will resolve the issue against potential negative side effects.

Researchers in the Department of Surgery in a Texas hospital explored how a Markov decision process could support doctors in the management of patients with hernias. An inguinal hernia is when tissue protrudes through a weak spot in the abdominal muscle, leading to pain and discomfort. Inguinal hernias are very common and can be repaired surgically, but often when patients come in with an inguinal hernia, doctors will find occult hernias, which are hernias that the patient did not previously notice. Doctors have to decide whether they should also repair the occult hernia during the operation.¹⁶ 

Let’s apply this scenario to the different facets of an MDP:

• State: The number of both inguinal and occult hernias discovered.
• Actions: The possible choices a surgeon can make when they discover an occult hernia while repairing an inguinal hernia. Their options are either to repair only the inguinal hernia or repair both the inguinal and occult hernias.
• Transition Model: The probability of movement from the current state to a new state for each action. (For example, what is the probability that a patient will develop complications if a single hernia is removed versus multiple?)
• Reward: The advantages of each outcome based on actions taken. Positive rewards would include successful removal of the hernia(s), no complications, and no recurrence of hernias.

By evaluating all the probable outcomes of each action, the study found that it is not necessary for doctors to remove occult hernias because the risk of the occult hernia becoming problematic later on is low, while the complication rate of removing two hernias at once is higher than just removing one.¹⁶ This study showcases how MDPs can be leveraged in medical decision-making for optimal outcomes. 

Decision Biases Among Lawyers: Conjunction Fallacy

Sometimes, people misjudge the probability of an event occurring based on the level of detail in which these events are described. The more detail that is given, the higher the chance that someone will believe an event is likely to occur. This is known as the conjunction fallacy. In this article, TDL’s former Managing Director Tom Spiegler explores how lawyers fall victim to this decision-making bias. 

Data-Driven Decision Making

In a Markov decision process, humans and computers use data (probability of outcomes and their rewards) to determine which action to take. Data-driven decisions allow us to make smart choices that optimize outcomes and minimize costs. In this reference guide, The Decision Lab takes a deep dive into data-driven decision-making and how it helps us make decisions in a world of information overload. 

1. GeeksforGeeks. (2024, July 5). Markov decision process. GeeksforGeeks. Retrieved October 28, 2024, from https://www.geeksforgeeks.org/markov-decision-process/
2. Whitfield, B. (2024, August 13). What is a Markov decision process? Built In. Retrieved October 28, 2024, from https://builtin.com/machine-learning/markov-decision-process
3. Kanade, V. (2022, December 20). What is a Markov decision process? Spiceworks. Retrieved October 28, 2024, from https://www.spiceworks.com/tech/artificial-intelligence/articles/what-is-markov-decision-process
4. Bohare, R. (2017, March 31). Markov chains: A take on life. Towards Data Science. Retrieved October 28, 2024, from https://towardsdatascience.com/markov-chains-a-take-on-life-35614859c99c
5. Singh, A. (2020, January 26). Reinforcement learning: Solving MDPs using dynamic programming (part 3). Towards Data Science. Retrieved October 28, 2024, from https://towardsdatascience.com/reinforcement-learning-solving-mdps-using-dynamic-programming-part-3-b53d32341540
6. Porter, T. M. (2005, September 9). Probability. Britannica. Retrieved October 28, 2024, from https://www.britannica.com/science/probability
7. Hayes, B. (n.d.). First links in the Markov chain. American Scientist. Retrieved October 28, 2024, from https://www.americanscientist.org/article/first-links-in-the-markov-chain
8. History of Data Science. (2021, June 3). Andrey Markov: A mathematician on a mission. Retrieved October 28, 2024, from https://www.historyofdatascience.com/andrey-markov-a-mathematician-on-a-mission/
9. Roth, A. (2016, April 11). Lloyd Shapley: A founding giant of game theory. Lindau Nobel Laureate Meetings. Retrieved October 28, 2024, from https://www.lindau-nobel.org/lloyd-shapley-a-founding-giant-of-game-theory/
10. Gregersen, E. (2012, October 16). Lloyd Shapley. Britannica. Retrieved October 28, 2024, from https://www.britannica.com/biography/Lloyd-Shapley
11. Begen, M., & Patrick, J. (2011). Markov decision processes and its applications in healthcare. In J. L. Hall (Ed.), Handbook of healthcare delivery systems. Retrieved October 28, 2024, from https://www.researchgate.net/publication/281272258_Markov_Decision_Processes_and_Its_Applications_in_Healthcare
12. LinkedIn AI Collaborative. (n.d.). How can you overcome limitations of Markov decision processes? LinkedIn. Retrieved October 28, 2024, from https://www.linkedin.com/advice/0/how-can-you-overcome-limitations-markov-decision-ifcgf
13. Alagoz, O., Hsu, H., Schaefer, A. J., & Roberts, M. S. (2009). Markov decision processes: A tool for sequential decision making under uncertainty. Medical Decision Making, 30(4), 474–483. https://doi.org/10.1177/0272989X09353194
14. Goto, J., Lewis, M., & Puterman, M. (2002, February 13). Coffee, tea, or ...? A Markov decision process model for airline meal provisioning. Retrieved October 28, 2024, from https://people.orie.cornell.edu/melewis/pubs/canadian_air.pdf
15. Balakavi, A. (2023, November 2). Markov decision process in healthcare. LinkedIn. Retrieved October 28, 2024, fromhttps://www.linkedin.com/pulse/markov-decision-process-healthcare-anusha-balakavi-nnbmc/
16. Singh, P., et al. (2024). Multimodality treatment planning using the Markov decision process: A comprehensive study of applications and challenges. Research on Biomedical Engineering. https://doi.org/10.1007/s42600-024-00349-4