Markov Decision Processes: States, Actions, and Transitions
Published:
A photograph may not be a state
Intuition first. Two images show a ball at the same height. In one case it is rising; in the other it is falling. Position alone does not predict where it will be next. Adding velocity makes a better state description for this simple physical system.
A state is a modelling choice about the information needed for the future. An observation is the information delivered to the agent. A camera frame, noisy measurement, or partial map need not be Markov.
Specify the decision process
For a finite MDP, use \(\mathcal S\) for states, \(\mathcal A\) for actions, and \(P(s'\mid s,a)\) for the probability of the next state. Let \(r(s,a,s')\) be the expected reward on that transition and \(\pi(a\mid s)\) the policy’s action probability.
The Markov condition says that, given the state and action, earlier history adds no predictive information about the next state:
A full task also specifies how episodes start and end. For a fixed-duration task, remaining time may need to be included in the state because the best action can depend on the deadline. MDP lecture, finite-horizon semantics.
Worked example: put reward on the transition
Consider a deterministic chain with one action per state:
| Transition | Reward after the action |
|---|---|
| A to B | 0 |
| B to Goal | 1 |
Goal is terminal: no more reward follows it. With \(\gamma=0.9\),
Starting at B receives the reward immediately after its first action, so it is not discounted. Starting at A receives that same reward after one intervening step, so it gets one factor of \(\gamma\). Giving B value 0.9 would insert a step that is absent from the defined task.
Writing down transitions and rewards before calculating values prevents this common indexing error.
Transitions and policies are different distributions
Suppose “move right” succeeds with probability 0.8 and otherwise leaves the agent in place. That uncertainty belongs to \(P\). If the policy chooses right with probability 0.6, that uncertainty belongs to \(\pi\).
In this toy example, the probability of both selecting right and moving successfully is \(0.6\times0.8=0.48\). Even a deterministic policy may produce varied trajectories because the environment is stochastic.
What to do with incomplete observations
A sequence of recent measurements can reveal velocity that one image hides. A recurrent policy can maintain a memory, while a state estimator can maintain a distribution over hidden states. Neither approach magically makes the problem fully observed; its effectiveness depends on the available evidence.
For a robot, also distinguish a physical state from a simulator’s privileged state. A training policy that sees exact object positions must have an explicit plan for obtaining equivalent information at deployment.
Continue with Bellman equations to compute values for a policy, or compare robot sensing for the observation side.
References
- Silver, D. Reinforcement Learning course: Markov Decision Processes.
- Farama Foundation. Handling Time Limits.