Reinforcement Learning

An MDP is written as states, actions, a transition function giving the probability of the next state, a reward function, and a discount factor gamma. Together they define a sequential decision problem an agent solves by choosing actions.

For every state and action, the model must give the probability of each possible next state and the expected reward. Value iteration averages over all successors in every update, so it plans inside the model rather than learning from experience.

Policy gradient methods tune the policy's parameters directly, so an action is sampled from a distribution. Value-based control has to maximise a value estimate over all actions at every step, which is intractable when the action is a real-valued vector.

V(s) is the expected return from state s when the agent follows its policy from there on. Q(s,a) is the expected return from taking action a in state s first, then following the same policy.

Gamma sets how much a reward arriving k steps later is worth now: it is weighted by gamma^k. Low gamma makes the agent short-sighted, high gamma far-sighted, and gamma below 1 keeps the total finite in a task that never ends.

Policy iteration repeats two steps. Evaluation sweeps every state, replacing its value with the expected return of the current policy. Improvement then rebuilds the policy greedily from those values; when no action changes, the policy is optimal.

REINFORCE weights the gradient of each action's log-probability by the return that followed it: theta <- theta + lr * G_t * grad log pi(a_t | s_t). Actions from high-return episodes get more probable. The reward itself is never differentiated.

Q-learning's target uses the maximum action value in the next state, so it learns the greedy policy while behaving some other way, which makes it off-policy. SARSA's target uses the action actually taken next, so it evaluates the exploring policy itself: on-policy.

After one transition, TD(0) moves the estimate a fraction of the way toward the observed reward plus the discounted estimate of the next state: V(s) <- V(s) + alpha * [r + gamma * V(s') - V(s)]. The bracketed quantity is the TD error.

Both split a value into immediate reward plus the discounted value of the next state. The expectation equation averages over the actions a fixed policy takes and is linear in the values; the optimality equation takes the maximum over actions, which makes it nonlinear and defines the best achievable value.

Reinforcement learning earns its cost when the only outcome you can measure arrives after a long sequence of decisions, so no per-decision target exists. If you can write an honest label for each decision, supervised learning is cheaper and safer.

A model-based agent has (or learns) the environment's transition and reward dynamics and can plan against them. A model-free agent never builds those dynamics; it estimates values or a policy directly from sampled experience. Temporal-difference learning is model-free.

The agent commits to whatever policy looked best while its value estimates were still mostly noise. States it stopped visiting keep their initial values, so the learning curve flattens early on a suboptimal policy that more exploration would have escaped.

Policy iteration evaluates the current policy to convergence, then makes it greedy, repeats. Value iteration folds both into one sweep that takes the maximum over actions. Both reach the same optimal values, trading cost per round against number of rounds.

Weighting by return minus a baseline centres the weights, so better-than-average actions are pushed up and worse-than-average ones down, instead of everything rising. Any baseline independent of the chosen action leaves the gradient unbiased.

A first-visit Monte-Carlo return is an actual sampled return, so on average it equals the true value — unbiased, but noisy because it accumulates every random reward to the end of the episode. A TD target uses the current estimate of the next state, which is wrong early on, so it is biased but far lower variance.

Trial-and-error learning needs enormous numbers of episodes, so reinforcement learning is feasible only where one episode is cheap, fast and safe. A simulator can yield a million overnight; an agent whose episode is a fiscal quarter yields four a year.

You lose more than one step's reward: a random action moves the agent into a new state, so the true cost is the return given up from there — the whole episode, if that state is unrecoverable.

Ask whether earlier history would change the action you take. If two patients with identical charts but opposite three-day trends need different decisions, the chart is not a Markov state, so fold trend summaries into it.

Because the reward is a proxy for what you want, and the agent optimises the proxy literally. It will find whatever loophole scores highest, so a rising reward curve is evidence the reward is being maximised, not that the task is being done.

In every state the greedy action is worth at least as much as the current policy's action, and that advantage applies again at the next step. Unrolling it shows the greedy policy's return dominates everywhere — the policy improvement theorem.

The policy gradient is an expectation over trajectories drawn from the current policy. One update moves the policy, so the batch now comes from a different distribution and estimates the wrong expectation. Every step needs fresh interaction.

Q-learning bootstraps from the greedy next action, so its values describe an agent that never steps off the cliff, and the short edge path looks best. SARSA bootstraps from the exploratory action actually taken, so occasional random falls depress the edge cells' values.

An early state's value is the expected discounted total of all reward that follows it, so an action paying nothing now still scores highly if it makes the payoff likelier later. Credit flows backwards through the Bellman recursion, one step at a time.

Trained only on logged decisions, an offline policy extrapolates the value of doses clinicians rarely gave, and maximisation selects exactly those over-optimistic estimates. You also cannot test it without acting, and the unrecorded reasons behind each dose confound the data.

Set every action's initial value above anything actually achievable and a purely greedy agent still explores: each action it tries returns less than promised, its estimate falls, and a still-untried action becomes the new maximum. Exploration is driven by disappointment.

Use potential-based shaping: add gamma times a potential of the next state minus the potential of the current state. Because these terms cancel along any trajectory, the optimal policy is provably unchanged while the agent still gets useful intermediate signal.

The policy is exactly optimal for the model you supplied, not for the world. Errors in the transition probabilities compound over the discounted horizon, and the planner actively exploits any transition whose probability or reward was estimated too optimistically.

Pick n on the delay between action and reward. Small n gives low-variance but myopic targets that propagate credit one state per pass; large n propagates credit fast but carries the noise of a long trajectory. Tune n empirically; intermediate values usually beat both extremes.