JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Beyond the Standard MDP

Real worlds are partly hidden, sometimes shifting, and act on many timescales. Three extensions stretch the MDP to fit — and tell you when the plain version is enough.

When you can't see the whole state

The standard MDP assumes the agent sees the true state. Reality often hides part of it: a poker player can't see opponents' cards; a robot's camera misses what's behind it. This is a partially observable MDP (POMDP). The agent no longer receives the state — only an observation that hints at it.

This matters because the Markov property now fails on the observation: a single glimpse isn't a sufficient summary of the past. Two genuinely different situations can produce the same observation yet demand different actions — and an agent that reacts only to the latest observation will confuse them.

Belief states: betting on what's hidden

The elegant repair is the belief state: instead of guessing the one true state, the agent maintains a probability distribution over all the states it might be in, updated as new observations arrive. 'I'm 70% sure the door is locked, 30% sure it's open.'

A belief state is maintained by Bayesian updating: each new observation reshapes the probability distribution over hidden states.

Interactive Bayesian update turning a prior distribution into a posterior as evidence arrives.

The beautiful part: the belief state is Markov, even though the observation isn't. Each belief is a sufficient summary of the entire observation history, so a POMDP becomes an ordinary MDP whose states are beliefs. The catch is that this 'belief MDP' lives in a continuous, high-dimensional space — exact solutions are usually intractable, and in practice agents learn to approximate the belief, often with memory built from recurrent networks.

When the rules themselves change

The standard MDP also assumes the dynamics and rewards stay fixed — a stationary world. But markets shift, machinery wears, opponents adapt. In a non-stationary MDP the transitions or rewards drift over time, so a policy that was optimal last month may quietly go stale.

A Markov chain's fixed transition probabilities — in a non-stationary MDP these very probabilities drift over time.

Interactive Markov chain of states linked by transition-probability arrows.

Note this is different from a stochastic environment. Stochasticity is fixed randomness — the dice never change. Non-stationarity is the dice themselves changing. The usual responses are to keep learning continually, to weight recent experience more heavily, or to fold time (or a regime indicator) into the state so the enlarged problem is stationary again.

Actions that take time: semi-Markov MDPs

A plain MDP ticks one uniform step at a time. But 'navigate to the kitchen' takes longer than 'rotate 5 degrees'. A semi-Markov decision process (SMDP) lets actions last variable amounts of time, tracking how long each one runs and discounting the rewards over its real duration.

Q(s,a)=\mathbb{E}\!\left[\,R+\gamma^{\tau}\,\max_{a'}Q(s',a')\right]

The SMDP value update discounts by γ raised to the action's duration τ, so longer skills are weighed by how much time they consume.

SMDPs are the formal backbone of temporal abstraction: treating extended skills as single decisions. They underpin the options framework and hierarchical RL, where a high-level policy chooses skills ('open the door') and low-level policies execute the muscle movements. You don't need any of this for a clean, fully observed, fixed-step task — but it's how RL scales up to long, structured, real-world problems.