Markov Decision Process

An agent in a state picks an action, the world moves it to a new state and pays it a reward, and the loop repeats. The Markov part is the simplifying promise: the current state carries everything that matters, so the agent can forget how it got there. Almost every reinforcement learning result assumes this, and almost every real problem violates it a little.

States, actions, a transition function and a reward function, plus a discount that decides how far ahead to care. Where the state is not really Markov — a partially observed world, a conversation with history — the usual repair is to stuff enough of the past into the state that it becomes so, which is what a context window does for a language model.

Maximise E[Σ sub _t  γ super ^t  r sub _t ] over policies π, with γ ∈ [0,1) making the sum finite and setting the horizon: the effective lookahead is about 1/(1−γ) steps. At γ = 0.99 that is a hundred, and the difference between 0.99 and 0.999 is the difference between a hundred-step horizon and a thousand-step one.