Chapter 1: Introduction to Reinforcement Learning

A state is whatever the agent observes and conditions its decision on; an action is any decision it can make; a reward is the scalar score the environment returns. The reward is deliberately a single number rather than a vector, because comparing candidate behaviours requires a total ordering — with two competing objectives there is no fact of the matter about which policy is better without a weighting that collapses them into one. Note the indexing convention: the action $A_t$ taken in state $S_t$ produces reward $R_{t+1}$, not $R_t$. The reward is indexed by when it arrives, which keeps the timing unambiguous once discounting is introduced.

A state is Markov if it summarizes everything from the history that matters for the future — formally, the distribution of the next state and reward depends on the current state and action alone. This is what makes a value function well defined, because it licenses attaching a single number to a state rather than to an entire history. Crucially the property belongs to the state representation rather than to the world: the same environment is Markov or not depending on what you choose to observe. Almost all of the theory in this course assumes it, so understanding when it fails tells you when the guarantees stop applying.

The reward hypothesis is the claim that every goal can be expressed as the maximization of expected cumulative reward. It is an assumption rather than a theorem, and it is the load-bearing one in the whole framework: accept it and goal-directed behaviour becomes an optimization problem. The practical consequence is that designing the reward is designing the goal, and the agent will optimize precisely what you wrote rather than what you meant. Rewarding a cleaning robot for collected dust invites it to dump dust and re-collect it — specification gaming, which is a reward-design failure rather than a learning failure.

Discounting weights a reward arriving $k$ steps in the future by $\gamma^k$, which serves three purposes simultaneously. It keeps the return finite in continuing tasks, it expresses a real preference for sooner rewards, and it bounds the horizon over which consequences must be tracked. A useful rule of thumb is that $\gamma$ produces an effective horizon of roughly $1/(1-\gamma)$ steps: rewards much beyond that contribute almost nothing. Small $\gamma$ therefore yields myopic agents that converge quickly; $\gamma$ near one yields far-sighted agents whose value estimates carry much higher variance and converge much more slowly.

A deterministic policy maps each state to one action; a stochastic policy gives a distribution over actions. A basic theorem covered in Chapter 2 says every finite MDP has an optimal policy that is deterministic, so randomness is never required to attain the optimum. Stochastic policies remain essential in practice for three separate reasons: they drive the exploration without which evaluative feedback teaches nothing, they are differentiable in a way an arg-max is not, and they are genuinely optimal in partially observable or adversarial settings where the theorem's assumptions fail. The theorem constrains the final answer, not the path taken to reach it.

Both functions are expectations of the same return, differing only in what is fixed at the first step. $v_\pi(s)$ averages over the policy's action choice; $q_\pi(s,a)$ pins that first action and averages afterwards. The asymmetry that matters is practical rather than theoretical. Selecting the best action from $q$ is an arg-max over stored numbers, whereas selecting it from $v$ requires evaluating each action's expected next state — which needs the transition dynamics. The action-value function has effectively cached the model's contribution inside the learned quantity, which is why it can be estimated from samples alone.

The tension is that information and reward are collected by the same actions, so acquiring one costs the other. What makes it genuinely hard rather than merely awkward is that early estimates are noisy, and a greedy agent's mistakes are self-sealing: an action that happened to yield a poor sample is never retried, so its estimate is never corrected. The damage is permanent rather than transient. This is also why exploration cannot simply be front-loaded into an initial phase in non-stationary environments, where the best action can change and a converged agent must retain some capacity to notice.

The standard mechanism takes the greedy action with probability $1 - \varepsilon$ and a uniformly random action otherwise, guaranteeing every action retains positive probability forever. Its appeal is simplicity and the fact that it satisfies the exploration condition convergence proofs require. Its weakness is that exploratory moves are uniform: a clearly terrible action is sampled exactly as often as a promising untried one, so the cost of exploring scales badly with the number of actions. Smarter schemes such as optimistic initialization or upper-confidence bounds direct exploration toward genuinely uncertain actions instead.