Markov Decision Process

Many problems require a sequence of decisions whose consequences unfold over time and are not fully predictable. The Markov decision process is the standard formalization. It specifies the situations the agent can be in, the actions available, the probability of moving from one situation to another given an action, and the immediate reward received.

The Markov property is the simplifying assumption that makes the framework tractable: the distribution over the next state depends only on the current state and the chosen action, not on how the agent arrived there. This is less restrictive than it first appears, because anything from the history that genuinely matters can be folded into the state definition, at the cost of a larger state space.

What is sought is a policy, a mapping from states to actions. The value of a policy at a state is the expected total reward from following it onward. Because a good decision now depends on the value of the states it leads to, and those values depend on subsequent decisions, the problem is inherently recursive; the Bellman equation expresses exactly this self-consistency and is the foundation of the algorithms that solve MDPs.

Future rewards are discounted by a factor between zero and one applied per step. This serves two purposes: it keeps the total finite over an unbounded horizon, and it encodes a genuine preference for sooner rewards. A discount near zero produces myopic behaviour, while one near one produces far-sighted behaviour at the cost of slower and less stable learning.

Consider a robot on a grid where each cell is a state and the actions are the four compass moves. Movement is unreliable: the intended direction succeeds most of the time and occasionally slips sideways. Reaching the goal cell yields a large positive reward, falling into a hazard a large negative one, and each ordinary step a small negative one to discourage dawdling.

The optimal policy is not simply the shortest path. Because movement can slip, a route that passes immediately beside a hazard carries real risk of falling in, and the policy may prefer a longer route that keeps its distance. The value function encodes this by assigning lower value to states adjacent to hazards.

The small per-step cost matters more than it looks. Without it, a policy that wanders indefinitely without ever reaching the hazard loses nothing, so the agent has no incentive to finish. Reward design of this kind is where most practical difficulty in applying reinforcement learning actually lives.