Formulating Complex Problems as Markov Decision Processes

265 concepts231 papers2 proposals

When faced with a complex optimization problem—whether it is solving a cryptic crossword puzzle, structuring a decision tree, or diagonalizing a massive matrix—our default engineering instinct is often to build a clever heuristic. We design algorithms that look at the current state of the problem and make the best immediate choice.

However, this greedy strategy frequently falls into local optima because it cannot anticipate the downstream consequences of its choices. To escape this trap, a powerful paradigm shift has emerged across diverse research domains: reframing static, combinatorial, or procedural tasks as Markov Decision Processes (MDPs). By transforming a problem from a static search space into a sequential trajectory, researchers can leverage reinforcement learning (RL) and dynamic programming to discover non-obvious, globally optimal strategies.

The Anatomy of an MDP Reframing

To understand why this formulation works, we must look at how it redefines a problem. A standard MDP breaks an environment down into a tuple of states ($S$), actions ($A$), transitions ($P$), and rewards ($R$). The core assumption—the Markov property—is that the future depends only upon the current state and action, not the historical path taken to get there.

When applied to non-traditional domains, this abstraction maps intuitive concepts to formal mathematical structures:

  • State ($S$): The current configuration of the problem. In crossword puzzle resolution, Chen et al. define the state as a partially completed grid. In machine learning architecture, Kohler et al. reframe decision tree induction by treating states as subsets of training data at specific depths.
  • Action ($A$): The available choices or transformations. This could mean selecting a word slot and populating it with a candidate answer, or choosing a specific feature split for a node in a decision tree.
  • Transition ($P$): How the state changes given an action. This can be deterministic (e.g., filling in a word slot) or stochastic (e.g., how a server responds to an attempted exploit payload).
  • Reward ($R$): The feedback guiding the agent toward the global objective.

As Adriaensen et al. demonstrate in automated algorithm design, this sequential framing allows the optimizer to receive incremental feedback throughout the execution of a program, rather than waiting for a single, delayed terminal cost value.

[Current State] ---> (Action Selection via Policy) ---> [Next State]
       ^                                                      |
       |__________________ (Incremental Reward) ______________|

Escaping the Greedy Trap

Why go through the trouble of setting up this machinery? The primary benefit is that it unlocks long-term planning under uncertainty.

Consider financial portfolio management. A traditional predictive model might look at market indicators and isolate its focus to immediate price predictions. However, Neuneier demonstrates that modeling asset allocation as an MDP enables the optimization of sequential decision-making by explicitly accounting for the long-term impact of current actions on future wealth, factoring in transaction costs and market volatility over time.

A similar breakthrough occurs in numerical linear algebra. The classical Jacobi method for matrix diagonalization relies on human-designed heuristics to choose rotation sequences. By framing this iterative numerical task as an MDP, Zollicoffer et al. trained reinforcement learning agents to discover non-obvious rotation strategies that reduce the total number of operations required for large-scale matrices, outperforming traditional greedy heuristics.

Inverse Planning: Reading the Agent's Mind

The beauty of the MDP formulation is that it operates symmetrically. If an optimization problem can be mapped as an MDP, we can use inverse planning to analyze how humans navigate that same problem space. Instead of using a policy to generate actions, we observe a sequence of actions (a trajectory) and infer the underlying policy or mental model of the person who generated it.

Rafferty et al. elegantly apply this concept to digital education for diagnosing student algebra misconceptions. By modeling equation solving as an MDP—where states represent the algebraic configuration and actions represent the application of transformation rules—the authors treat the learner as an agent navigating a state space.

Instead of grading a student based purely on a final right-or-wrong answer, this framework analyzes their step-by-step solution trajectory. If a student makes an incorrect transition, the inverse planning model can calculate which flawed mathematical rule would make that specific action rational from the student's perspective, allowing for highly targeted pedagogical feedback.

A Unifying Framework for Solvers

Ultimately, treating complex tasks as sequential decision processes provides a clean, modular interface between domain-specific problems and generalized machine learning algorithms.

This is perhaps best exemplified by libraries like Ecole, introduced by Prouvost et al.. Ecole exposes the internal, complex heuristic decisions of industrial-strength combinatorial optimization solvers (like SCIP) as MDPs. By defining standard state observations and action spaces for tasks like variable selection or node branching, it allows external reinforcement learning agents to learn optimal control policies directly from the solver's execution path.

Whether the goal is to solve a puzzle, optimize a database join order, or diagnose a student's learning gaps, the MDP formulation provides the mathematical scaffolding necessary to turn static search spaces into dynamic, learnable landscapes.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_markov_decision_process_formulation_mark_dc01a7a7,
  title = {Markov Decision Process formulation (markov decision process formulation)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/markov-decision-process-formulation-markov-decision-process-formulation/rdr_dc01a7a7fbbe4697a88f37750d56cdf2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_markov_decision_process_formulation_mark_dc01a7a7_v1,
  title = {Markov Decision Process formulation (markov decision process formulation)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/markov-decision-process-formulation-markov-decision-process-formulation/rdr_dc01a7a7fbbe4697a88f37750d56cdf2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake