Reinforcement learning basics

In short

Reinforcement learning (RL) is the branch of machine learning where an agent learns by acting in an environment and receiving numeric rewards, with no labelled dataset telling it the right action. The formal model is the Markov decision process, and the goal is a policy that maximises expected cumulative discounted reward. It is examined in GATE Data Science & AI (DA), the AI/DS papers of Anna University, VTU, SPPU, AKTU and the AICTE model curriculum, and appears constantly in placement interviews for recommender, pricing, logistics and robotics teams. Indian users include Flipkart and Myntra (ranking and pricing experiments), Swiggy and Zomato (delivery-partner allocation), Ola and Uber (surge and dispatch), Jio and Airtel (network and offer optimisation) and research groups at IISc, IITs, Microsoft Research India and Google DeepMind India.

Explained

What RL is, and how it differs from supervised and unsupervised learning

• Agent: the learner/decision maker. Environment: everything outside it. At each discrete step t the agent sees state Sₜ, takes action Aₜ, receives reward Rₜ₊₁ and moves to Sₜ₊₁.
• Learning signal is evaluative (how good was this action) not instructive (what the correct action was) - that is the core difference from supervised learning.
• Delayed reward / credit assignment: a reward now may be the consequence of an action many steps earlier; RL must apportion credit across time.
• Exploration-exploitation trade-off: the agent must try unknown actions to learn, yet use known-good actions to earn. Supervised learning has no such dilemma.
• Data is non-i.i.d. and agent-generated: the policy decides what data is collected, so a bad early policy can starve whole regions of the state space.

• Terminology: episodic tasks end in a terminal state (a game, a delivery trip); continuing tasks run forever (a server controller). Model-based RL learns or is given P and R; model-free RL learns only from samples.

The Markov decision process (MDP)

• An MDP is the tuple (S, A, P, R, γ): state set S, action set A, transition probability P(s′ given s, a), reward function R(s, a) and discount factor γ in [0, 1).
• Markov property: the next state and reward depend only on the current state and action, not on the earlier history. A state that satisfies this is a sufficient statistic of the past.
• Return Gₜ = Rₜ₊₁ + γRₜ₊₂ + γ²Rₜ₊₃ + … The discount γ makes an infinite sum finite, models uncertainty about the future, and encodes impatience. γ near 0 is myopic; γ near 1 is far-sighted.
• Policy π: deterministic π(s) = a, or stochastic π(a given s) = probability. State-value Vπ(s) = expected return starting from s; action-value Qπ(s, a) = expected return after taking a in s, then following π.
• Optimality: there is always at least one deterministic optimal policy π\* with V\*(s) = maxπ Vπ(s) for all s. Once Q\* is known, π\*(s) = argmaxₐ Q\*(s, a) - this is why most algorithms learn Q.
• POMDP: when the agent sees only an observation, not the full state (partially observable). Handled with belief states or recurrent networks - usually only defined, not solved, in UG exams.

Dynamic programming: solving a known MDP

• Needs the full model P and R. Based on the Bellman expectation and Bellman optimality equations (see formula boxes).
• Policy evaluation: repeatedly apply the Bellman expectation backup V(s) ← Σₐ π(a given s) Σ_{s′} P(s′ given s,a)[R + γV(s′)] until the change falls below a threshold θ. Converges because the backup is a γ-contraction mapping.
• Policy improvement: set π′(s) = argmaxₐ Q(s, a). The policy improvement theorem guarantees Vπ′ ≥ Vπ.
• Policy iteration: alternate evaluation and improvement until the policy stops changing. Few iterations, each expensive.
• Value iteration: one-step greedy backup V(s) ← maxₐ Σ P[R + γV(s′)] repeated to convergence, then extract the greedy policy. More sweeps, each cheap.
• Generalised policy iteration (GPI): the common pattern - partially evaluate, partially improve. Almost every RL algorithm is a form of GPI.
• Limitations: needs the model; cost per sweep is O(|S|²|A|), so it fails on large or continuous state spaces (curse of dimensionality).

Model-free prediction and control: MC, TD, SARSA, Q-learning

• Monte Carlo (MC): wait for the episode to end, then V(Sₜ) ← V(Sₜ) + α[Gₜ − V(Sₜ)]. Unbiased, high variance, episodic tasks only, no bootstrapping.
• Temporal difference TD(0): update after one step using the estimate of the next state - V(Sₜ) ← V(Sₜ) + α[Rₜ₊₁ + γV(Sₜ₊₁) − V(Sₜ)]. The bracket is the TD error δₜ. Online, works on continuing tasks, lower variance but biased (bootstrapping).
• n-step returns and TD(λ): interpolate between TD(0) (n = 1) and MC (n = ∞); eligibility traces implement TD(λ) incrementally. λ = 0 gives TD(0), λ = 1 gives MC.
• SARSA (on-policy control): Q(S,A) ← Q(S,A) + α[R + γQ(S′,A′) − Q(S,A)], where A′ is the action the behaviour policy actually takes. Learns the value of the policy it is following, so it is cautious (avoids the cliff edge).
• Q-learning (off-policy control): Q(S,A) ← Q(S,A) + α[R + γ maxₐ′ Q(S′,a′) − Q(S,A)]. The max makes the target independent of the behaviour policy, so it learns Q\* while exploring. Converges with probability 1 under Robbins-Monro step sizes and infinite visits to every state-action pair.
• Expected SARSA: replaces Q(S′,A′) with Σ π(a′ given S′)Q(S′,a′) - lower variance than SARSA; equals Q-learning when the target policy is greedy.
• Double Q-learning: two Q tables, one to select the argmax and one to evaluate it, fixing the maximisation bias of the single max operator.
• Exploration strategies: ε-greedy (random with probability ε, usually decayed), softmax/Boltzmann (probability proportional to exp(Q/τ)), optimistic initialisation, UCB (bandits). GLIE - greedy in the limit with infinite exploration - is the condition for ε-greedy MC/SARSA control to reach π\*.
• Multi-armed bandit is the one-state special case: no transitions, pure exploration-exploitation; the standard model for A/B testing and ad/offer selection.

Function approximation and deep RL

• Tables are impossible beyond small S, so represent Q(s, a; w) or V(s; w) with a linear model or a neural network and update w by semi-gradient descent on the squared TD error.
• Deep Q-Network (DQN) stabilisers: (1) experience replay - sample random mini-batches from a buffer to break correlation between consecutive samples; (2) a target network whose weights are copied periodically to keep the bootstrap target stationary; (3) reward clipping and frame stacking. DQN handles discrete action sets only.
• Variants: Double DQN (reduces overestimation), Dueling DQN (separate value and advantage streams), Prioritised replay (sample high-TD-error transitions more often), Rainbow (combination).
• Policy-gradient methods optimise π(a given s; θ) directly - they handle continuous actions and stochastic optimal policies. REINFORCE uses ∇θ J = E[Gₜ ∇θ ln π(Aₜ given Sₜ; θ)]; subtract a baseline b(s) (usually V(s)) to cut variance without adding bias.
• Actor-critic: the actor updates θ using the critic's TD error as the advantage estimate; A2C/A3C, DDPG and TD3 (continuous, deterministic, off-policy), PPO (clipped surrogate objective, the usual industrial default) and SAC (maximum-entropy, sample-efficient).
• RLHF (reinforcement learning from human feedback) trains a reward model on human preference comparisons, then fine-tunes a language model against it with PPO - the standard alignment step in modern LLMs.
• Practical issues: sample inefficiency (millions of steps), instability (the "deadly triad" of bootstrapping + off-policy + function approximation), sensitivity to hyperparameters and reward scale, and poor reproducibility across random seeds.

Reward design, evaluation and safety

• Reward hypothesis: every goal can be expressed as maximisation of expected cumulative reward. Reward hacking is the agent maximising the stated reward while defeating the intent (a cleaning robot that hides dirt).
• Sparse vs dense reward: sparse (win/lose) is honest but hard to learn; reward shaping adds intermediate rewards. Potential-based shaping F = γΦ(s′) − Φ(s) is the only form proven not to change the optimal policy.
• Evaluation: learning curve of episodic return against steps, mean ± standard deviation over several seeds, sample efficiency (return per environment step), and regret for bandits. Never report a single lucky seed.
• Offline (batch) RL learns from a fixed logged dataset with no interaction - important in Indian industry because live exploration on real customers costs money; needs conservative methods (CQL, BCQ) to avoid extrapolating beyond the data.
• Off-policy evaluation: importance sampling or doubly-robust estimators to judge a new policy from old logs before deploying it.
• Sim-to-real: train in a simulator (Gym/Gymnasium, MuJoCo, SUMO for traffic, CARLA for driving) and transfer with domain randomisation.
• Indian regulatory context: an RL system that decides prices, credit limits or offers for individuals processes personal data under the Digital Personal Data Protection Act, 2023 (purpose limitation, consent, notice) - note its rules were being notified in phases, so check the current status. RBI's guidance on digital lending and its framework for responsible/ethical use of AI in finance require explainability and human oversight of automated decisions, so pure black-box RL is rarely deployable in regulated pricing or lending without a human-in-the-loop and audit logs.

Key points

• Agent-environment loop - state, action, reward, next state at every discrete time step.
• MDP (S, A, P, R, γ) - the formal frame; the Markov property makes the current state sufficient.
• Return Gₜ - discounted sum of future rewards; γ < 1 keeps infinite-horizon returns finite.
• Policy π - the mapping from states to actions (or to action probabilities); the object being learnt.
• V(s) vs Q(s, a) - value of a state vs value of a state-action pair; Q supports greedy action choice without a model.
• Bellman equation - recursive consistency of values; its optimality form has the max over actions.
• DP (value/policy iteration) - exact, needs the model, cost grows with |S|²|A|.
• Monte Carlo - unbiased, high variance, needs complete episodes.
• TD learning - bootstraps from its own estimate; biased, low variance, works online.
• SARSA is on-policy, Q-learning is off-policy - SARSA learns the behaviour policy's value, Q-learning learns Q\* regardless of behaviour.
• ε-greedy / GLIE - exploration scheme and the condition (decaying ε, infinite visits) for convergence to optimality.
• Maximisation bias - the max operator overestimates Q; Double Q-learning fixes it.
• Function approximation - linear or neural Q/π for large or continuous state spaces; tables do not scale.
• DQN = replay buffer + target network - the two tricks that made deep value learning stable.
• Policy gradient / actor-critic - direct policy optimisation; handles continuous actions, needs a baseline to control variance.
• Deadly triad - bootstrapping + off-policy + function approximation can diverge.
• Reward shaping - potential-based shaping is policy-invariant; arbitrary bonuses can change the optimum.
• Bandit - single-state MDP; the practical model for A/B tests, ads and offer ranking.
• Offline RL / OPE - learn and evaluate from logged data when live exploration is costly or risky.

Formulas and examples

Example 1 - computing a discounted return. An ad-serving agent collects rewards (₹ profit per impression) of 2, 0, 3, 5 over four steps, γ = 0.9, then the episode ends.

• G = 2 + 0.9(0) + 0.9²(3) + 0.9³(5) = 2 + 0 + 0.81×3 + 0.729×5
• = 2 + 0 + 2.43 + 3.645 = ₹8.075
• With γ = 0.5: G = 2 + 0 + 0.25×3 + 0.125×5 = 2 + 0.75 + 0.625 = ₹3.375 - the same rewards are worth less to a myopic agent.

Example 2 - infinite-horizon value of a constant reward. A running machine yields R = ₹10 every step for ever, γ = 0.95.

• V = 10(1 + 0.95 + 0.95² + …) = 10 × 1/(1 − 0.95) = 10 × 20 = ₹200
• At γ = 0.99: V = 10 × 1/0.01 = ₹1,000. Effective horizon ≈ 1/(1 − γ) = 20 steps vs 100 steps.

Example 3 - one TD(0) and one Q-learning update. Given α = 0.1, γ = 0.9, V(s) = 5, V(s′) = 8, observed R = 2.

• δ = 2 + 0.9(8) − 5 = 2 + 7.2 − 5 = 4.2
• V(s) ← 5 + 0.1(4.2) = 5.42

Now Q-learning with Q(s, a₁) = 3, and next state s′ has Q(s′, up) = 6, Q(s′, down) = 9, R = 1, same α and γ.

• Target = 1 + 0.9 × max(6, 9) = 1 + 8.1 = 9.1; δ = 9.1 − 3 = 6.1
• Q(s, a₁) ← 3 + 0.1(6.1) = 3.61
• SARSA on the same transition, if the ε-greedy behaviour actually chose "up": target = 1 + 0.9(6) = 6.4, δ = 3.4, Q ← 3.34. Same data, different update - that is on-policy vs off-policy in one line.

Example 4 - value iteration on a two-state MDP. States A and B. In A: action *stay* gives R = 0 and returns to A; action *move* gives R = 1 and goes to B. B is terminal with V(B) = 0. γ = 0.9.

• Initialise V(A) = 0. Sweep 1: V(A) = max{0 + 0.9(0), 1 + 0.9(0)} = 1
• Sweep 2: V(A) = max{0 + 0.9(1), 1 + 0} = max{0.9, 1} = 1 - converged.
• Greedy policy: π\*(A) = *move*. If instead *stay* paid R = 0.5, the fixed point of staying would be 0.5/(1 − 0.9) = 5 > 1, so π\*(A) = *stay*: a small per-step reward collected for ever beats a one-off reward.

Example 5 - ε-greedy action probabilities and expected reward. Four actions, Q = (1.0, 4.0, 2.0, 3.0), ε = 0.2.

• Greedy action is a₂. P(a₂) = 1 − 0.2 + 0.2/4 = 0.8 + 0.05 = 0.85; each other action = 0.2/4 = 0.05.
• Expected Q per step = 0.85×4 + 0.05(1 + 2 + 3) = 3.4 + 0.30 = 3.70 against 4.0 for pure greedy - exploration costs 0.30 per step, the price of learning.

# Tabular Q-learning: the whole algorithm in a dozen lines
import numpy as np
Q = np.zeros((n_states, n_actions))
alpha, gamma, eps = 0.1, 0.9, 1.0
for ep in range(episodes):
    s, done = env.reset(), False
    while not done:
        a = env.action_space.sample() if np.random.rand() < eps else int(np.argmax(Q[s]))
        s2, r, done, _ = env.step(a)
        target = r + (0 if done else gamma * Q[s2].max())   # 0 at a terminal state
        Q[s, a] += alpha * (target - Q[s, a])
        s = s2
    eps = max(0.05, eps * 0.995)        # decay towards greedy (GLIE)
policy = Q.argmax(axis=1)

Where it is used

• E-commerce and OTT in India: Flipkart, Myntra, Amazon India, Hotstar and JioCinema use bandits and contextual bandits for ranking, thumbnail/creative selection and personalised offers, where every impression is a cheap experiment.
• Logistics and mobility: Swiggy, Zomato, Blinkit and Zepto for order batching and rider allocation; Ola, Uber, Rapido and Delhivery for dispatch, repositioning and route choice; Indian Railways and metro operators study RL for timetable and energy-efficient driving.
• Finance and telecom: trading execution and portfolio rebalancing at quant desks, collections prioritisation and credit-line decisions in NBFCs (subject to RBI expectations on explainability and human oversight), and Jio/Airtel self-optimising networks and churn-offer selection.
• Manufacturing, energy and robotics: process control and scheduling in steel and cement plants, HVAC and data-centre cooling, warehouse robots (GreyOrange, Addverb) and arm manipulation; smart-grid demand response.
• LLM products: RLHF/RLAIF alignment and tool-use training - a large share of current AI engineering jobs in Bengaluru and Hyderabad research labs.
• Job roles: ML engineer (personalisation / pricing), research scientist, decision-science analyst, robotics software engineer, optimisation / operations-research scientist.

Interview questions

• Q: How does reinforcement learning differ from supervised learning? A: RL gets a scalar, possibly delayed reward instead of correct labels, and the agent's own actions generate the data, so it must balance exploration and exploitation.
• Q: What are the five elements of an MDP? A: States, actions, transition probabilities, reward function and discount factor - plus the Markov property that the next state depends only on the current state and action.
• Q: Why do we discount future rewards? A: To keep infinite-horizon returns finite, to express uncertainty about the far future and to encode a preference for sooner reward; γ also sets the effective horizon, about 1/(1 − γ) steps.
• Q: Difference between V(s) and Q(s, a)? A: V is the expected return from a state under a policy; Q is the expected return from taking a specific action in that state and then following the policy - Q lets you act greedily without knowing the model.
• Q: Explain on-policy versus off-policy with an example. A: SARSA evaluates the policy it is actually following, so it learns a safe path away from a cliff; Q-learning's max target learns the optimal (cliff-edge) path while still exploring, which is off-policy.
• Q: Compare Monte Carlo and TD learning. A: MC waits for the episode's actual return - unbiased but high variance and episodic only; TD bootstraps from the next state's estimate - biased but low variance, online and usable in continuing tasks.
• Q: Why does DQN need a replay buffer and a target network? A: Replay breaks the correlation between consecutive samples and reuses data; the target network keeps the bootstrap target fixed for a while so the regression target does not chase the weights and diverge.
• Q: What is maximisation bias and how is it fixed? A: Taking a max over noisy Q estimates systematically overestimates value; Double Q-learning uses one estimator to pick the argmax and another to evaluate it.
• Q: When would you use policy gradients instead of Q-learning? A: When actions are continuous or high-dimensional, when the optimal policy is stochastic, or when you need smooth policy updates - Q-learning requires a max over actions, which is intractable in continuous spaces.
• Q: What is reward hacking, and how do you guard against it? A: The agent maximises the written reward while violating the intent; guard with careful reward design, potential-based shaping, constraints or penalties, and evaluation on the true business metric rather than the proxy.
• Q: Can you do RL without interacting with the environment? A: Yes - offline/batch RL learns from logged data, with conservative algorithms and off-policy evaluation (importance sampling, doubly robust) to avoid trusting actions the data never covers.
• Q: Your ε-greedy agent plateaus below optimum. What do you check? A: Whether ε decayed too fast (insufficient exploration), whether α is too large or constant, whether γ matches the task horizon, whether the state representation is actually Markov, and whether rewards are sparse enough to need shaping.

Common mistakes

• Writing the Q-learning target with Q(s′, a′) from the behaviour policy instead of max over a′ - that is SARSA, not Q-learning.
• Forgetting that the bootstrap term is zero at a terminal state, which inflates values near the end of an episode.
• Confusing the reward Rₜ₊₁ with the return Gₜ, or summing rewards without discounting when γ < 1 is specified.
• Using γ = 1 in a continuing task, so values diverge, or γ = 0.9 in a 1,000-step task, so the agent cannot see the goal.
• Treating RL as supervised learning on logged data without correcting for the fact that the logging policy chose the actions.
• Decaying ε to zero too quickly, breaking the GLIE condition and locking in a sub-optimal policy.
• Reporting a single seed's learning curve as the result, and comparing algorithms without the same number of environment steps.

Related topics

Machine learning workflow · Model evaluation metrics · Overfitting, bias-variance and regularisation · Deep learning and neural networks · Markov chains and stochastic processes · Operations research and dynamic programming