Markov Decision Process

Every reinforcement learning problem has the same ingredients:

• State: what the agent currently observes (a board position, a robot’s joint angles).
• Action: what it can do next.
• Transition: how the state changes after an action, possibly with randomness.
• Reward: a number received after each step.
• Discount factor γ: how much future rewards count. With γ = 0.9, a reward ten steps away is worth about a third of the same reward now.

The agent’s strategy is its policy: which action to take in each state. The value of a state is the total discounted reward you expect from there when following the policy. The Markov property says the current state contains everything needed to predict what happens next, so the past does not matter beyond it.

Optimal values obey a neat recursive relationship, the Bellman equation: the value of a state is the best immediate reward plus the discounted value of where you end up. Algorithms like Q-learning are clever ways of solving it from experience.

The math

The optimal action-value function satisfies

$$Q^*(s, a) = \mathbb{E}\big[r + \gamma \max_{a'} Q^*(s', a') \,\big|\, s, a\big]$$

and the optimal policy picks $\arg\max_a Q^*(s, a)$.