POMDP-to-belief-state-MDP reduction
Concrete Problems in AI Safety — inherited
The formal result that any partially observable Markov decision process can be reduced to a belief-state MDP for which an equivalent reward function exists.
When an agent cannot observe the true state of the world, its situation is modeled as a POMDP -- and a classical result shows any POMDP can be recast as an ordinary decision process over the agent's beliefs, with an equivalent reward.
The page presents that reduction, from partial observability to a fully observed belief space, then explains why a fix this clean is one nobody can afford to run. Partially observed goals, the problem this result solves in theory only, is the natural next stop.
From partial observability to a fully observed belief space
A partially observable Markov decision process (POMDP) extends the standard MDP formalism to settings where an agent cannot directly observe the true state $s \in S$, only an observation $o$ drawn from a distribution $O(o \mid s, a)$ conditioned on the (hidden) state and the action taken. A classical result in the control-theory and operations-research literature on POMDPs, predating this paper by decades, shows that any POMDP can be reduced to a fully observed MDP over belief states: a belief $b$ is a probability distribution over $S$ representing the agent's current uncertainty, updated by Bayes' rule after each action and observation, $$b'(s') \;=\; \eta \, O(o \mid s', a) \sum_{s \in S} T(s' \mid s, a)\, b(s),$$ for normalizing constant $\eta$, and the agent's policy becomes a mapping from belief states to actions rather than from hidden states to actions. Because the belief-state process is itself Markov, standard MDP theory — including the existence of an optimal reward-maximizing policy — applies directly once the state space is redefined as the (continuous, high-dimensional) space of beliefs. Concrete Problems invokes this reduction to make a specific point: it implies that a reward function does exist, defined purely in terms of an agent's actions and observations, that is provably equivalent to optimizing the true, unobserved objective (concrete-problems, §"Partially Observed Goals:", p. 8).
A correct fix nobody can afford to use
The paper is explicit that this theoretical guarantee is not a practical remedy. The edge Partially observed goals — has an impractical theoretical fix in → POMDP-to-belief-state-MDP reduction notes that the reduction "typically involves complicated long-term dependencies over the agent's entire observation history and is prohibitively hard to compute or use" (concrete-problems, §"Partially Observed Goals:", p. 8) — the belief-state space grows enormous, and reasoning over full observation histories quickly becomes intractable for any realistic task. This is why designers still fall back on cheap, hackable proxies such as "did the robot see a mess": the belief-state fix that would make partial observability harmless is known to exist and simultaneously known to be unusable at the scale real systems operate at. The relationship is therefore cause-and-non-cure rather than cause-and-cure. The concept sits in the Why reward proxies get gamed: the anatomy of reward hacking theme and the The paper names exactly where its own fix stops working connective theme, and belongs to the Reward hacking: how proxies get gamed, and the general law behind it supertheme as the theoretical ceiling against which Partially observed goals's practical difficulty is measured.