Types of Learning: Supervised, Unsupervised, Reinforcement

A learning paradigm is defined by three things: what data the learner observes, what feedback (if any) it receives about correctness, and what object it is trying to produce at the end. These choices determine the entire mathematical formulation of the problem, independent of which specific algorithm is later used to solve it. In supervised learning, the learner is given a training set of input–output pairs

drawn from some unknown joint distribution $P(X, Y)$. The goal is to learn a function $f: X \to Y$ that predicts $y$ from $x$ accurately on new, unseen inputs — this is the generalization requirement. If $Y$ is a finite set of categories, the task is classification; if $Y$ is continuous, it is regression. The feedback signal is direct and complete: for every training example, the correct answer is known, and a loss function $L(f(x_i), y_i)$ measures how wrong the prediction was. In unsupervised learning, the learner observes only inputs $\{x_1, \dots, x_n\}$ drawn from $P(X)$, with no accompanying $y$. There is no "correct answer" to compare against. Instead, the learner seeks to uncover latent structure: groups of similar points (clustering), a compact representation that preserves information (dimensionality reduction), or an estimate of the probability density $P(X)$ itself (density estimation). Because there is no ground truth, success must be defined intrinsically — by how well the model compresses, reconstructs, or explains the data — rather than by matching known labels. In reinforcement learning (RL), the learner (called an agent) interacts with an environment over a sequence of time steps. At each step $t$, the agent observes a state $s_t$, chooses an action $a_t$ according to a policy $\pi(a_t \mid s_t)$, and receives a scalar reward $r_t$ along with a new state $s_{t+1}$. Crucially, the reward is evaluative, not instructive: it tells the agent how good the outcome was, not what the correct action would have been. Rewards may also be delayed — a good move in chess may not pay off for dozens of moves — creating the credit assignment problem: figuring out which past actions deserve credit for a later reward. The goal is to learn a policy that maximizes expected cumulative reward,

where $\gamma \in [0, 1]$ is a discount factor that weighs near-term reward more than distant reward. A fourth, hybrid category deserves mention because it appears throughout modern practice: self-supervised learning, in which labels are automatically manufactured from the unlabeled data itself (for example, predicting a masked word from surrounding context). It uses the mechanics of supervised learning — labeled pairs and a loss function — but the labels require no human annotation, blurring the line between the first two paradigms.

Rather than one algorithm, each paradigm defines a template that many specific algorithms instantiate. Below are the canonical templates, with pseudocode general enough to describe entire algorithm families (The Formal Learning Problem formalizes the supervised case with sample-complexity bounds).

Supervised learning template. Given labeled data, pick a hypothesis class $\mathcal{H}$ (e.g., linear functions, decision trees, neural networks), and search for the member of $\mathcal{H}$ that minimizes empirical loss, typically via gradient-based optimization. ``` function SUPERVISED_TRAIN(D = {(x_i, y_i)}, hypothesis_class H, loss L): initialize parameters θ for a model f_θ in H repeat until convergence or max_epochs: for each minibatch B ⊂ D: compute predictions: ŷ_i = f_θ(x_i) for (x_i, y_i) in B compute empirical loss: J(θ) = (1/|B|) Σ L(ŷ_i, y_i) compute gradient: g = ∇_θ J(θ) update: θ ← θ - η * g # η = learning rate return f_θ function SUPERVISED_PREDICT(f_θ, x_new): return f_θ(x_new) ```

Unsupervised learning template. Given unlabeled data, pick a structural objective (reconstruction error, cluster compactness, log-likelihood under a model), and optimize it without ever consulting a $y$. ``` function UNSUPERVISED_TRAIN(D = {x_i}, model class M, objective J): initialize parameters θ for model m_θ in M # e.g. k cluster centers, or an autoencoder repeat until convergence or max_epochs:

# example: k-means style alternation assign each x_i to nearest current structure (e.g. nearest centroid) update structure parameters θ to better fit assigned points (e.g. recompute centroids as means) evaluate objective J(θ) on D # e.g. within-cluster sum of squares if improvement in J is below tolerance: break return m_θ ```

Reinforcement learning template. The agent repeatedly acts, observes reward, and updates its policy or value estimates from the experience of interacting with the environment. ``` function RL_TRAIN(environment, policy π_θ, num_episodes): for episode in 1..num_episodes: s ← environment.reset() trajectory ← [] done ← false while not done: a ← sample_action(π_θ, s) # explore vs exploit (s_next, r, done) ← environment.step(a) trajectory.append((s, a, r)) s ← s_next G ← 0 for (s, a, r) in reverse(trajectory): # compute returns G ← r + γ G update θ to increase probability of a in s in proportion to G # policy-gradient style update return π_θ ``` The three loops look superficially similar — initialize, iterate, update — but the source of the error signal* differs fundamentally. In supervised learning the error is $L(\hat y, y)$, computable instantly and exactly for every example. In unsupervised learning there is no $y$; the "error" is an internally defined objective like reconstruction loss or cluster variance. In reinforcement learning the "error signal" is a reward that may arrive many steps after the responsible action, and the agent itself must decide which actions to try (exploration) versus which known-good actions to repeat (exploitation) — a tension absent from the other two paradigms entirely.

Complexity in this context is not one number but a set of distinct resource questions, since each paradigm poses a different learning problem.

Supervised learning. For a single gradient step over a minibatch of size $b$ with a model of $p$ parameters, the cost is $O(bp)$ for a forward and backward pass (dominant cost typically from matrix multiplications, which for a layer of size $p$ can be larger depending on architecture — for a fully connected layer with $p$ weights this is tight; for convolutions it scales with kernel size and feature-map size, not raw parameter count). Over $n$ training examples and $E$ epochs, total training cost is $O(E \cdot n \cdot p / b \cdot b) = O(E n p)$ ignoring constant factors from the specific architecture. Correctness here means generalization: minimizing training loss is only useful insofar as it controls loss on the true distribution $P(X,Y)$. This is formalized later via The Formal Learning Problem and PAC-learning bounds relating training error, hypothesis-class complexity, and sample size $n$; and via Maximum Likelihood Estimation for the probabilistic view of many loss functions (e.g., cross-entropy loss corresponds exactly to maximizing likelihood under a categorical model).

Unsupervised learning. Complexity depends heavily on the specific structural objective. $k$-means clustering, for instance, costs $O(n k d)$ per iteration for $n$ points in $d$ dimensions and $k$ clusters, and is only guaranteed to converge to a local optimum of the within-cluster sum of squares — a consequence of Lloyd's algorithm monotonically decreasing that objective at each reassignment-and-update step (each step is a coordinate descent on a non-convex objective, so global optimality is not guaranteed, only monotone improvement and eventual convergence to a fixed point). "Correctness" for unsupervised learning is inherently softer: there is no ground-truth label to check against, so success is judged by proxy criteria — reconstruction error, held-out log-likelihood, or downstream task performance after using the learned representation.

Reinforcement learning. Complexity is usually measured in sample complexity — how many environment interactions are needed before the policy is near-optimal — rather than pure compute. For tabular RL algorithms like $Q$-learning over $|S|$ states and $|A|$ actions, convergence to the optimal action-value function $Q^*$ is guaranteed under the Robbins–Monro step-size conditions (learning rate decaying appropriately, e.g. $\sum \alpha_t = \infty$, $\sum \alpha_t^2 < \infty$) provided every state–action pair is visited infinitely often — this is a consequence of the Bellman optimality equation being a contraction mapping under the max-norm, so repeated application of the Bellman backup converges to its unique fixed point $Q^*$. In practice with function approximation (deep RL), no such convergence guarantee generally holds, and sample complexity can be enormous — millions to billions of environment steps for complex tasks — because the reward signal is sparse and delayed relative to supervised learning's dense, instantaneous per-example feedback. The honest tradeoff across all three: supervised learning has the strongest theoretical guarantees but requires the most expensive resource — human-labeled data. Unsupervised learning needs only raw data (cheap) but offers the weakest guarantee of "correctness," since there is no external check on whether the discovered structure is meaningful. Reinforcement learning needs no labels at all and can in principle discover novel strategies beyond what any labeler could specify, but pays for this with severe sample inefficiency and the hard credit-assignment problem across long action sequences.

Consider a single dataset — customer purchase histories — analyzed under all three paradigms, to see how the same raw information yields three different problems. Raw data: 6 customers, each with `(age, monthly_spend, num_visits)` and, for four of them, a known label `churned` (yes/no) recorded from an actual cancellation event.

Supervised framing. Train on A–D (labeled), predict E and F. A logistic regression model learns weights on `(age, spend, visits)` to minimize cross-entropy against the four known labels. Because D and B (churned) both have low spend and low visits, while A and C (retained) have high spend and high visits, the model learns a decision boundary roughly along "low spend + low visits → churn." Applying $f_\theta$ to E `(45, 55, 10)` yields predicted "No" (matches the retained pattern); applying it to F `(28, 12, 2)` yields predicted "Yes." This is classic classification: exact labels exist for training, and the goal is accurate prediction on new points.

Unsupervised framing. Now discard all labels entirely — pretend they were never recorded. Run $k$-means with $k=2$ over all six customers using only `(age, spend, visits)`. The algorithm groups {A, C, E} (high spend, high visits) into one cluster and {B, D, F} (low spend, low visits) into another, purely by geometric proximity in feature space — with no notion of "churn" ever entering the computation. Strikingly the clusters happen to align with the true churn behavior, but the algorithm had no access to and made no claim about labels; it only claims these six points naturally separate into two groups by spending pattern. This distinction matters: an unsupervised clustering could equally have discovered a grouping by age instead, if age had been the dominant source of variance, and there is no mechanism in $k$-means to know which grouping is "right" — only which minimizes within-cluster distance.

Reinforcement framing. Reframe the problem entirely: an agent (a marketing system) chooses, for each customer at each month, an action — send a discount offer, send nothing, or send a loyalty email — and only observes a reward months later (whether the customer stayed subscribed, worth $+1$, or churned, worth $-1$, and the cost of the discount, worth $-0.1$). There is no table of "correct actions" anywhere; the agent must try different offers across many customers and months, observe delayed subscription outcomes, and gradually learn a policy $\pi(\text{action} \mid \text{customer state})$ that maximizes cumulative retained revenue. Notice the same underlying customers now sit inside a sequential decision problem with delayed, evaluative feedback — a completely different mathematical object from the labeled classification table above, even though the raw customer attributes are identical. The table below summarizes how the same six data points are used under each paradigm:

The taxonomy of learning paradigms crystallized gradually as statisticians, psychologists, and computer scientists converged from different directions on the same underlying question — how can a system improve its behavior from experience.

Supervised learning underlies most deployed predictive systems: spam filters, credit-scoring models, medical image diagnosis, speech recognition, and machine translation all rely on labeled training data mapping inputs to known correct outputs. Every large-scale image classifier and most fraud-detection pipelines are supervised systems at their core.

Unsupervised learning powers recommendation-system user segmentation, anomaly detection in network security (flagging traffic that doesn't fit learned normal patterns), topic modeling of text corpora, and the dimensionality reduction used to visualize high-dimensional embeddings. It is also the backbone of modern representation learning: large language models are pretrained with self-supervised objectives (predicting masked or next tokens) before any human-labeled fine-tuning occurs.

Reinforcement learning drives game-playing systems (from Samuel's checkers program to AlphaGo and beyond), robotic control (learning locomotion or manipulation policies through trial and error), resource allocation in data centers, autonomous vehicle decision-making, and the reinforcement-learning-from-human-feedback (RLHF) pipeline used to align large language models with human preferences — a striking case where all three paradigms combine in a single production system: self-supervised pretraining, supervised fine-tuning, and reinforcement learning from a learned reward model. Understanding which paradigm a real-world problem belongs to — or which combination of paradigms it requires — is the first and most consequential design decision in any applied machine learning system, well before any specific algorithm or architecture is chosen.

Ask the tutor: How does the reinforcement learning objective connect mathematically to the Bellman equation, and why does that guarantee convergence for tabular Q-learning?