Markov Decision Processes and Reinforcement Learning

A Markov decision process, or MDP, describes repeated decisions when actions can have uncertain outcomes. The agent observes its current state, chooses an available action, receives a reward, and moves to a new state. These four parts describe one transition; a sequence of transitions describes a run.

Read a transition model

The state set is $S$, and $A(s)$ lists the actions allowed in state $s$. The transition model $T(s,a,s^{\mathrm{\prime }})=P(s^{\mathrm{\prime }}\mid s,a)$ gives the chance of reaching $s^{\mathrm{\prime }}$ after taking $a$ in $s$. For each state–action pair, all these probabilities are nonnegative and sum to 1. The reward $R(s,a,s^{\mathrm{\prime }})$ belongs to that transition. A negative reward represents a cost or penalty.

Consider a delivery robot with states High battery, Low battery, and Dead. Dead ends the episode. Its model is:

The two Work rows each sum to 1. For Work in Low, the expected immediate reward is $0.6(4)+0.4(-10)=-1.6$. This average is useful for planning, but an actual attempt earns either 4 or −10. Choosing Work chooses the distribution; it does not choose the successful outcome.

Put the relevant past into the state

The Markov property means that the current state and action contain the information needed to predict the next state:

The world may have a long history. That history matters through the variables included in the current state. A robot's location alone may be insufficient if its battery determines whether a job succeeds. Including the battery level lets the model distinguish situations with different risks.

A standard MDP assumes the agent observes the state exactly. If important parts of the state are hidden, the agent needs a belief about possible states; that leads to a partially observable MDP, or POMDP.

Recognize endings and random movement

A terminal state has value 0 because no rewards follow it. The reward on entering it still counts: the robot receives −10 on its last transition into Dead. Episodic tasks end at a terminal state; continuing tasks, such as ongoing temperature management, need no terminal state.

In a grid world, an intended move can succeed with probability 0.8 and slip in either perpendicular direction with probability 0.1 each. An attempted move into a wall leaves the agent in place. Probabilities of outcomes that reach the same square must be combined.

Deterministic transitions are a special case: one successor has probability 1. For a known start and a suitable goal-reaching task, a fixed plan can suffice. With uncertain outcomes, a policy specifies how to respond in whichever state actually occurs. Some texts write rewards as $R(s)$ or $R(s,a)$; check the timing convention before translating a formula.

A policy describes how the agent acts. A deterministic stationary policy $\pi (s)$ chooses one action for each state and keeps that choice over time. For the robot, "Work when High, Charge when Low" is such a policy. A stochastic policy $\pi (a\mid s)$ assigns probabilities to the available actions.

Calculate a return

The discounted return combines rewards across a run:

The first transition earns $r_0$ with weight 1. Each later reward receives one more factor of the discount $\gamma$. For rewards −1, −1, −1, and +10 followed by termination, using $\gamma =0.9$ gives

With $\gamma =0.5$, the same run gives $-1-0.5-0.25+10(0.125)=-0.5$. The delayed gain loses much of its weight. Discounting can represent a preference for earlier rewards, or the chance that the process continues to another step.

A policy is judged by its expected return, averaging over its possible runs. One lucky run does not establish that a policy is good. An optimal policy ${\pi }^{\ast }$ gives the largest expected return from every state. A finite discounted MDP has an optimal policy that is deterministic and stationary.

Keep an infinite future finite

For bounded rewards and $0\le \gamma <1$, the geometric series bounds every return. If $\mathrm{\mid }{r}_t\mathrm{\mid }\le R_{\max }$, then

The robot's largest reward magnitude is 10, so $\gamma =0.9$ gives $\mathrm{\mid }U\mathrm{\mid }\le 100$. Since its largest positive reward is 4, its return also cannot exceed $4\mathrm{/}(1-0.9)=40$. These are bounds, not claims that the robot can achieve them.

The quantity $1\mathrm{/}(1-\gamma )$ is a rough effective horizon: about 10 steps for $\gamma =0.9$. It is not a cutoff. A reward 10 steps later still receives weight ${0.9}^{10}\approx 0.35$. Undiscounted continuing tasks need special care: repeated positive rewards can make returns infinite. A fixed finite horizon makes the sum finite; episodic models also need well-behaved episode lengths for finite expected values.

Let time and step rewards affect decisions

With a deadline, the best action can depend on the time left. Consider a machine in Worn condition. Run earns 6 and leaves it Worn or Broken with equal probability. Repair earns −4 and makes it Good. In Good, Run earns 10; in Broken, Repair earns −20. With one step left, Worn favors Run: $6>-4$. With two steps left and $\gamma =0.9$, Repair gives $-4+0.9(10)=5$. Run gives $6+0.9[0.5(6)+0.5(-20)]=-0.3$. The extra time reverses the choice.

A grid world's living reward, earned on nonterminal steps, changes the cost of delay. Negative step rewards encourage reaching an exit; a larger penalty can make a nearby bad exit preferable to a long route. A sufficiently large positive step reward can favor staying in the grid. The exact choice also depends on discounting, distances, and slip risks.

Formulating an MDP turns a practical objective into decisions a computer can evaluate. Start by choosing when decisions happen. Then define an observable state, legal actions, transition probabilities, rewards, any terminal states, and a discount or horizon. The quality of the resulting policy depends on these choices.

Model machine maintenance

Suppose a machine is inspected once per decision step. Its condition is Good, Worn, or Broken. The model is:

Broken is not terminal: repair lets work continue. The task is continuing, with $\gamma =0.9$. Notice that available actions depend on the state; Run is unavailable when Broken.

Solving this model gives optimal values about 78.64 in Good, 66.78 in Worn, and 50.78 in Broken. In Worn, Repair has value $-4+0.9(78.64)\approx 66.78$. Run has value $6+0.9[0.5(66.78)+0.5(50.78)]\approx 58.90$. The negative immediate reward for repair buys access to a more productive future.

Choose enough state information

The state must support predictions of both outcomes and rewards. A moving ball's position alone omits its velocity, so two identical positions can have different next positions. A board-game position also needs whose turn it is. If remaining time changes which actions pay off, include it in a finite-horizon decision rule or augment the state with it.

Extra variables increase the state space. Ten yes/no variables allow $2^{10}=1024$ combinations. Keep information that changes predictions or rewards; storing the entire history can make a workable model needlessly large. The usual stationary MDP assumes the same transition and reward rules over time. Hidden state calls for a belief model, while strategic opponents call for a game model.

Make the reward express the objective

A cleaning robot rewarded for each piece of dirt collected can profit by spilling and recollecting dirt. This is reward hacking: successful optimization of a poor measure. A reward tied to the desired cleanliness avoids that particular loop. A sparse goal reward states success clearly but supplies little feedback during a long attempt.

Reward shaping adds feedback about progress. Arbitrary bonuses can change the objective. Two useful comparisons are:

• Multiplying all rewards by the same positive number preserves their policy ranking.
• Adding a constant to every reward preserves optimal policies in a continuing discounted task, because every policy gains the same discounted constant. In an episodic task, longer and shorter runs gain different amounts, so the ranking can change.

A policy-preserving shaping term has the form $F(s,a,s^{\mathrm{\prime }})=\gamma \mathrm{\Phi }(s^{\mathrm{\prime }})-\mathrm{\Phi }(s)$. Here $\mathrm{\Phi }$ assigns a potential to each state. With bounded potentials in a continuing discounted task, the added discounted terms cancel except for a start-state offset. For episodic tasks, setting every terminal potential to 0 removes the leftover terminal term. A nonzero terminal potential can change which ending, or which stopping time, is preferred.

A value measures the return available from a situation under a particular way of acting. It includes future rewards, weighted by their probabilities and timing. This makes values different from the reward earned on a single transition.

Distinguish the starting choice

The state value $V^{\pi }(s)$ is the expected discounted return starting in state $s$ and following policy $\pi$. The action value $Q^{\pi }(s,a)$ fixes the first action to $a$, then follows $\pi$ afterward. It does not mean taking $a$ at every later step.

Optimal values replace that continuation policy with the best possible behavior. Thus $V^{\ast }(s)$ is the best expected return from $s$, and $Q^{\ast }(s,a)$ is the best expected return after the first action is fixed. Their relationship is

The maximum is a number; the argmax identifies an action attaining it. If several actions tie, any tied action can be selected.

Read the robot's choices

For the delivery robot with $\gamma =0.9$, the optimal Q-values are:

Each row's maximum is the state's optimal value. High favors Work; Low favors Charge. Charge earns 0 immediately, but in Low it restores access to High and its better future opportunities. Work in Low still has positive optimal Q-value because a surviving robot can charge afterward.

The continuation policy matters. Under "always Work," the state values fall to about 8.27 in High and −3.48 in Low. The model has not changed; the decisions after each outcome have changed. A number labeled only "the value" is incomplete unless the intended policy or optimality is clear.

See choices and chance as separate layers

An expectimax tree alternates two kinds of nodes. At a state the agent selects an action; at a state–action pair, sometimes called a q-state, chance selects the next state according to the transition model. The agent maximizes across actions and averages across their outcomes.

A cyclic MDP repeats the same states at many tree locations. Dynamic programming stores a value for each state and reuses it. This avoids recomputing the same continuation problem every time a tree path returns to that state.

Extract a policy from the available values

With a Q-table, compare the action values in the current row. No transition model is needed. With state values alone, first calculate an action's expected reward plus discounted successor value:

That calculation needs transitions and rewards. Merely choosing the action that can reach the highest-value successor ignores how likely that successor is and what the action costs. A high expected value also leaves room for an unlucky run: it describes an average over outcomes, not a guaranteed reward on every attempt.

A run's return can be split after its first transition: the immediate reward plus the discounted return from the next state. Taking an expectation produces a Bellman equation. It connects a state's value to successor values, including the possibility of returning to the same state.

Evaluate a fixed policy

For a deterministic policy, only its selected action appears:

Each branch contributes its probability times its immediate reward plus future value. There is one equation per state. In a finite discounted MDP, these are linear equations with a unique solution.

For the robot's "always Work" policy, begin at Low. The two possible transitions give

Expand and collect the unknown: $V(L)=2.4+0.54V(L)-4$, so $0.46V(L)=-1.6$. Therefore $V(L)\approx -3.48$. The −10 reward remains even though Dead's future value is 0.

At High, both outcomes earn 4, so their immediate rewards combine to 4:

Collecting terms gives $0.37V(H)=4+0.27V(L)$. Using the unrounded Low value yields $V(H)\approx 8.27$. Keep full precision while substituting; round the reported values at the end.

Add the choice of action

For optimal values, calculate the expectation for each available action, then take the best:

The maximization sits outside the sum because the agent chooses one action before seeing the outcome. Choosing a different current action for each possible next state would give it information it does not yet have.

The Q-form fixes that first action but allows the best next action after observing the successor:

These optimality equations contain maxima, so a single fixed-policy linear solve does not directly solve them.

Check proposed values

Use the robot's candidate optimal values $V(H)\approx 31.50$ and $V(L)\approx 28.35$. At High, Work gives $4+0.9[0.7(31.50)+0.3(28.35)]\approx 31.50$. Charge gives $0.9(31.50)=28.35$. The larger result matches the candidate High value.

At Low, Work gives $0.6[4+0.9(28.35)]+0.4(-10)\approx 13.71$; Charge gives 28.35. The maximum matches the candidate Low value too. A check of only one state would leave the other equation untested. Small discrepancies are expected when the candidate values have been rounded.

Discount only the future term. Replacing $R+\gamma V$ with $\gamma (R+V)$ incorrectly delays the immediate reward by one step.

Policy evaluation asks how much expected return a fixed policy earns. The model and policy are known. No action choices are improved during this calculation; the output is $V^{\pi }$, which can later support a separate improvement step.

Solve the equations exactly

Take the policy "Work when High, Charge when Low" and $\gamma =0.9$. Charging Low gives no immediate reward and always reaches High, so $V(L)=0.9V(H)$. Working High gives

Substitute the first equation into the second:

Then $0.127V(H)=4$, giving $V(H)=4\mathrm{/}0.127\approx 31.50$ and $V(L)\approx 28.35$. This establishes the values of that policy. Proving it optimal also requires checking competing actions.

Exact evaluation solves one linear equation per nonterminal state. Standard dense elimination costs on the order of $\mathrm{\mid }S{\mathrm{\mid }}^3$ operations. The method is convenient for a small model because the relationships can be inspected directly.

Evaluate by repeated sweeps

An iterative alternative starts with $V_0(s)=0$ and applies the fixed-policy backup to every state:

Each new value uses the old array. For "always Work," the first three sweeps, in the order High then Low, give:

For example, the second Low value is $0.6[4+0.9(-1.6)]+0.4(-10)=-2.464$. High in that same sweep uses the old High value 4 and old Low value −1.6, giving $4+0.9[0.7(4)+0.3(-1.6)]=6.088$.

With a discount below 1, the sweeps converge to about 8.27 and −3.48. A dense fixed-policy sweep costs on the order of $\mathrm{\mid }S{\mathrm{\mid }}^2$ operations because each state sums over successors. Sparse transition models can skip successors with probability 0.

Interpret intermediate values

Starting at zero, $V_k(s)$ is the expected discounted reward over the next $k$ transitions under the fixed policy, with no value beyond that horizon. The first sweep sees only immediate rewards. The second includes one more transition. These intermediate values have a clear meaning even before convergence.

Updating in place uses some freshly computed values within the same sweep. With the usual discounted conditions it can also converge, but its intermediate arrays need not equal these synchronous finite-horizon values. In a hand calculation, keep separate old and new arrays when comparing synchronous sweeps.

Do not add a maximum over actions during evaluation. That would let the agent change its behavior and would answer a different question from the one the fixed policy defines.

Value iteration repeatedly asks what is best when one more decision is allowed. It starts from $V_0=0$ and backs up each state's best expected reward plus discounted successor value. The same calculation handles cycles because successor values come from a stored array.

Make one complete sweep

For every nonterminal state, calculate

For the robot's first sweep, all future terms are 0. High compares Work at 4 with Charge at 0, so $V_1(H)=4$. Low compares Work at $0.6(4)+0.4(-10)=-1.6$ with Charge at 0, so $V_1(L)=0$.

The second sweep uses this entire old array. At High, Work gives $4+0.9[0.7(4)+0.3(0)]=6.52$, while Charge gives $0.9(4)=3.6$. At Low, Work still gives −1.6, while Charge gives 3.6. Thus $V_2=(6.52,3.6)$. A third sweep gives about $(9.08,5.87)$.

If the new High value 6.52 were used immediately to update Low, the result would differ. That is an in-place update, not the synchronous second sweep just shown.

Understand what converges

From zero initialization, $V_k$ is the optimal expected return with exactly $k$ decision opportunities remaining, allowing terminal episodes to end sooner. Each sweep extends the useful planning horizon by one. The Bellman optimality operator is a contraction for $\gamma <1$: the largest error over states shrinks by at least a factor of $\gamma$ per application. Values converge to the unique $V^{\ast }$ from any finite starting array.

A dense sweep considers states, actions, and successors, costing on the order of $\mathrm{\mid }S{\mathrm{\mid }}^2\mathrm{\mid }A\mathrm{\mid }$ operations. A discount close to 1 usually slows convergence because distant rewards retain more weight.

Stop with an error bound

Let ${\mathrm{\Delta }}_k={\max }_s\mathrm{\mid }{V}_{k+1}(s)-V_k(s)\mathrm{\mid }$. For $0<\gamma <1$, the new array's maximum error is bounded by $\gamma {\mathrm{\Delta }}_k\mathrm{/}(1-\gamma )$. To ensure error below a chosen tolerance $\epsilon$, it is sufficient that

For $\gamma =0.9$ and tolerance 0.01, the threshold is about 0.00111. A change below 0.01 alone does not certify value error below 0.01. At $\gamma =0$, a single backup gives the optimal immediate rewards, so no division by the discount is needed.

Read out the policy

After stopping, compare action expectations using the final value array. This one-step lookahead gives a greedy policy. The policy can settle before the values: the robot's greedy policy from $V_1$ already says "Work when High, Charge when Low," but its values need 77 sweeps to come within 0.01 of the optimal pair $(31.50,28.35)$.

A stable-looking policy and accurate values are different checks. The backup must compare expected outcomes for each action; selecting the single most valuable possible successor leaves out both risk and immediate reward.

Policy iteration alternates two jobs: measure a policy, then improve its actions using that measurement. Start from any deterministic policy. A good initial guess can save work, but it is not required for correctness in a finite discounted MDP.

Separate evaluation from improvement

First compute $V^{{\pi }_i}$, the values of the current policy. Then, for every state, compare all actions using those same values:

Evaluation describes the old behavior. Improvement asks whether changing the first action would improve the return if the old policy were followed afterward. Changing all such actions gives a policy at least as good in every state. If the old policy is not optimal, an improvement is strict in at least one state.

Keep the current action whenever it ties for best. Otherwise, equally good actions can make a policy appear to keep changing even though there is no value improvement.

Improve the robot's policy

Start with "always Work." Exact evaluation gives High about 8.27 and Low about −3.48. In High, keeping Work gives 8.27; switching to Charge gives $0.9(8.27)\approx 7.45$. Keep Work. In Low, Work gives −3.48 and Charge gives about 7.45. Switch Low to Charge.

Now evaluate the new policy "Work when High, Charge when Low." Its values are about 31.50 and 28.35. Improve again:

No action changes, so policy iteration stops. The fixed-policy values also satisfy the optimality equations, establishing that this policy is optimal. The robot needed two full evaluations from this starting policy.

Explain why the process ends

A finite MDP has only finitely many deterministic policies. If every one of $\mathrm{\mid }S\mathrm{\mid }$ states has $\mathrm{\mid }A\mathrm{\mid }$ choices, there are $\mathrm{\mid }A{\mathrm{\mid }}^{\mathrm{\mid }S\mathrm{\mid }}$ such policies. The robot has two nonterminal states with two actions each, giving $2^2=4$ policies. With strict improvement whenever needed and consistent tie handling, the process cannot return to a worse policy and must finish.

Compare the planning methods

Full evaluations make policy-iteration rounds more expensive, but often fewer rounds are needed. The robot's 77 value-iteration sweeps and two policy evaluations are different units of work, so the counts alone do not establish which method is faster. Use values belonging to the current policy during each improvement; mixing them with values from a previous policy breaks that step's meaning.

In reinforcement learning, an agent learns from experience in a decision problem. It observes a state, chooses an available action, and receives a sample $(s,a,r,s^{\mathrm{\prime }})$: the previous state, action, reward, and next state. The objective remains high expected return, but transition probabilities and rewards must be learned.

Separate learning from planning

Planning uses an MDP model to calculate values or policies. It can happen before acting or while an agent replans during operation. Learning uses observed experience, either from ongoing interaction or from a previously collected data set. Offline reinforcement learning still learns from experience; it simply uses recorded experience.

In passive learning, a policy is fixed and the task is to estimate how well it performs. In active learning, the agent also chooses actions to discover better behavior. Those choices affect both collected reward and the information available for future updates.

Estimate transitions with counts

A model-based learner records how often each action is tried in each state. Let $N(s,a)$ count those trials and $N(s,a,s^{\mathrm{\prime }})$ count the trials ending in a particular successor. Then

The counts in the numerator partition the trials in the denominator, so their estimated probabilities sum to 1. An untried pair has denominator 0 and needs more experience or an explicit modeling choice; it has no empirical transition distribution yet.

For the robot, Work in High was tried 20 times: 13 transitions stayed High and 7 reached Low. The estimates are $13\mathrm{/}20=0.65$ and $7\mathrm{/}20=0.35$. Work in Low was tried 10 times: 7 survived and 3 reached Dead, giving 0.7 and 0.3. The second estimate understates the true death probability 0.4.

Record rewards for each transition too. The robot has fixed rewards for its outcomes. If repeated identical transitions have noisy rewards, estimate their conditional mean reward from the observed samples.

Plan with the learned model

Use the estimated transitions and rewards in value iteration or policy iteration. For these robot counts, with Charge transitions known and $\gamma =0.9$, the estimated optimal values are about $(30.42,27.38)$. The optimal action choices still match the true model: Work in High, Charge in Low. Similar policies can therefore arise from different value estimates.

Few samples can give inaccurate models. More representative experience improves the estimates, but collecting data only under one narrow policy can leave useful actions untried. A model-based learner still needs exploration.

Compare two learning routes

A learned model can reuse samples for many planning backups and support replanning when objectives change. It also takes storage and computation, and model errors can distort the plan. Model-free methods avoid building a transition table, but usually require substantial experience to make their value estimates reliable.

A fixed policy can be evaluated without knowing its transition model. Direct evaluation averages complete sampled returns. Temporal-difference learning, or TD learning, updates from a single reward and an estimated successor value. Both learn the policy's values from experience.

Average whole-episode returns

Follow "always Work" with $\gamma =0.9$. One robot episode is High → High (+4), High → Low (+4), Low → Dead (−10). The returns from its High visits are $4+0.9(4)+0.81(-10)=-0.5$ and $4+0.9(-10)=-5$. Its Low return is −10.

A second episode is High → Low (+4), Low → Low (+4), Low → Dead (−10). Its High return is −0.5; its Low returns are −5 and −10. The every-visit means are therefore $(-0.5-5-0.5)\mathrm{/}3=-2$ for High and $(-10-5-10)\mathrm{/}3\approx -8.33$ for Low. A first-visit method would count only the first visit to a state in each episode.

These estimates differ sharply from the true policy values $(8.27,-3.48)$ because both episodes ended quickly. Whole returns have sampling variation. With sufficient representative completed episodes, their averages approach the policy's expected returns. Direct evaluation waits until the required return is available at episode end and estimates states separately.

Update after one transition

TD uses the current estimate of what follows:

The target is $r+\gamma V(s^{\mathrm{\prime }})$. The TD error is target minus current estimate. The learning rate $\alpha$ controls the fraction of that error used in the update.

Suppose $V(H)=10$, $V(L)=8$, $\gamma =0.9$, and $\alpha =0.5$. After High → Low with reward 4, the target is $4+0.9(8)=11.2$. The error is $11.2-10=1.2$, so the new High estimate is $10+0.5(1.2)=10.6$. Low's stored value remains 8 on this update. A terminal next state contributes no future term.

TD bootstraps: it uses an estimate to improve another estimate. This passes information through connected states and permits updates in continuing tasks, but early targets can be biased by poor successor estimates.

Control how much new evidence counts

A large learning rate reacts strongly to each target. At $\alpha =1$ the old estimate is replaced by the latest target. A fixed positive rate generally keeps tracking sample noise. Suitably decreasing rates, with repeated visits and the usual finite discounted assumptions, support tabular TD convergence. A rate $1\mathrm{/}N(s)$ averages the sequence of observed TD targets; those targets themselves change as successor estimates improve.

State values alone do not reveal the best action without transition and reward information for a lookahead. Passive TD evaluates the behavior generating its samples. Learning action values gives an agent a direct way to compare actions without first learning a model.

Q-learning learns action values from observed transitions. Its target assumes the best next action, even while the agent chooses exploratory actions. This lets it learn how to act well without estimating a transition model.

Replace an expected backup with a sample

A model-based Q-backup averages over all possible successors:

Q-learning sees one successor at a time. After a sample $(s,a,r,s^{\mathrm{\prime }})$, it computes

and updates $Q(s,a)\leftarrow Q(s,a)+\alpha [y-Q(s,a)]$. A terminal successor makes $y=r$. The maximum is over actions available in the next state, not the state just left.

Initialize the Q-table, choose an action with an exploration rule, observe the result, update the selected entry, and continue from the next state. Restart after termination. To use the learned policy, select an action attaining the largest Q-value in the current row.

Work through two updates

Let $\gamma =0.9$ and $\alpha =0.5$. Initially $Q(L,\text{Work})=5$. The robot tries Work in Low and dies with reward −10. The target is −10, so the new value is $5+0.5(-10-5)=-2.5$. There is no future return after Dead.

Next suppose $Q(H,\text{Work})=6$ and the robot works High, earns 4, and reaches Low. At Low the estimates are Work at −2.5 and Charge at 3. The best next value is 3, making the target $4+0.9(3)=6.7$. The updated High–Work value is $6+0.5(6.7-6)=6.35$. This sample updates only that table entry.

Distinguish target behavior from actual behavior

Q-learning is off-policy: the continuation in its target is greedy, even if its action-selection rule explores. SARSA is on-policy: it uses $r+\gamma Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }})$ for the action actually chosen next.

Near a cliff, an exploring agent can take accidental dangerous steps. SARSA accounts for those future exploratory actions and can learn a more cautious route. Q-learning targets the greedy continuation and can favor a shorter edge route, even while exploration makes its training trips risky.

State the tabular guarantee precisely

In a finite stationary MDP with bounded rewards and $\gamma <1$, tabular Q-learning converges to $Q^{\ast }$ with probability 1 when every state–action pair receives infinitely many updates and its learning rates satisfy

A per-pair rate $1\mathrm{/}N(s,a)$ has this form. A rate $1\mathrm{/}N(s,a{)}^2$ decreases too quickly: its total sum is finite, so it can leave too little adjustment to remove an initial error. Infinite total adjustment prevents learning from stopping too early; finite squared adjustment controls accumulated noise. Constant rates generally retain fluctuations in stochastic tasks. These are limiting conditions, so a finite training run still needs evaluation.

Exploitation selects the action that currently looks best. Exploration gathers information that may reveal a better choice. If an early unlucky Work attempt makes the robot prefer Charge in High, pure exploitation can keep it charging forever and leave the Work estimate uncorrected.

Count the random branch correctly

An epsilon-greedy rule explores uniformly with probability $\epsilon$ and otherwise chooses a greedy action. Suppose there is one greedy action among four and $\epsilon =0.2$. Its selection probability is $0.8+0.2\mathrm{/}4=0.85$. Each other action has probability 0.05. The random branch includes the greedy action too.

Lower exploration early in training can leave useful actions untested; high exploration late in training keeps sacrificing reward. A schedule can become greedy in the limit while still trying every relevant pair infinitely often. This GLIE property is stronger than simply reducing epsilon, and reachability matters for whether all states are visited.

Favor actions with little evidence

An exploration function can add a bonus to a value estimate. With $f(u,n)=u+k\mathrm{/}n$ for a tried action, choose the action with the largest score. Give untried actions priority, such as score $+\mathrm{\infty }$. With $k=10$, a value 5 tried 20 times scores 5.5; a value 4 tried twice scores 9. The less-tried action is selected despite its lower current estimate.

The bonus can also enter a backup target: $r+\gamma {\max }_{a^{\mathrm{\prime }}}f(Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }}),N(s^{\mathrm{\prime }},a^{\mathrm{\prime }}))$. This propagates the attraction of unexplored actions to earlier states. Optimistic initial Q-values can also encourage trying actions whose estimates have not yet been corrected by experience.

Use a confidence bound for bandits

A multi-armed bandit has one decision state and several arms with unknown fixed mean rewards. Each pull teaches the agent about an arm's reward distribution. UCB1 assumes bounded independent reward draws with a fixed distribution per arm; rescale rewards to the range 0 to 1. Pull every arm once, then choose the largest score

Here ${\bar{x}}_j$ is arm $j$'s sample mean, $n_j$ its pull count, and $N$ the total count across arms. The bonus grows for poorly sampled arms. With means 0.6 and 0.5 after 10 and 2 pulls, $N=12$. The scores are about 1.30 and 2.08, so the second arm is selected. The score can exceed 1 even though observed rewards cannot: it is a decision index, not an observed reward.

Measure the cost of learning

Regret compares collected reward with what optimal choices would have earned. In a stationary bandit with a genuinely inferior arm, fixed positive epsilon keeps selecting that arm at a positive rate, producing linear expected regret. Under its stochastic bandit assumptions, UCB1 has logarithmic expected regret. A carefully tuned decreasing-epsilon schedule can also achieve that order; arbitrary decay cannot promise it.

Q-learning's off-policy target permits exploratory samples without redefining the optimal values it seeks. Exploration still affects the reward collected during training. For physical systems, use simulation, recorded experience, or permitted-action limits to keep exploration from causing harm.

A Q-table stores one number for every state–action pair. In a large problem, many pairs may never be visited. Separate entries also fail to share evidence between similar situations. Approximate Q-learning replaces the table with a function of features.

Represent values with a weighted sum

A feature $f_i(s,a)$ is a number describing an aspect of the state and action. For a delivery robot, features could describe battery level, distance to a charger, and waiting packages. A linear approximation writes

The weights $w_i$ describe how strongly each feature contributes. Features can depend on the action as well as the state, allowing different choices in the same state to have different values.

Update every weight from one error

Compute the current Q-value, then the target $y=r+\gamma {\max }_{a^{\mathrm{\prime }}}Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }})$. The difference $\delta =y-Q(s,a)$ drives each update:

All values used for the target and error come from the weights before the update. A zero feature produces no change to its weight. A nonzero feature scales the adjustment, including its sign.

For weights $(1,-0.5)$ and current features $(1,2)$, the estimate is $1(1)+(-0.5)(2)=0$. Suppose the reward is 4, the best next Q-value is 4, and $\gamma =0.9$. The target is $4+0.9(4)=7.6$, so $\delta =7.6$. With $\alpha =0.1$:

The new estimate for the same features becomes $1.76+1.02(2)=3.8$. A shared-weight update is not the same as replacing one independent table entry by the target.

Understand the reach and limits of sharing

One weight participates in many predictions. Updating it changes values for every pair with a nonzero value of that feature. This is generalization, and it can help the agent act sensibly in unseen states. It can also spread a mistaken update.

If two situations have identical feature vectors for every corresponding action, the model must give them identical action values. If they require different actions, no amount of weight tuning can represent both decisions correctly. Better features or a richer function are needed. Tabular learning is the special case with one indicator feature for each state–action pair, active only for that pair.

The convergence guarantee for tabular Q-learning does not extend to arbitrary function approximation. Off-policy bootstrapping with shared predictions can oscillate or diverge, so evaluate the learned policy on separate trials. Deep Q-networks learn features from inputs such as game-screen pixels; policy search instead adjusts a policy directly to increase return.