Challenges & Open Problems

One map of the whole course

At the root sits learning-based control, splitting into imitation learning (learning from demonstrations) and reinforcement learning (learning from rewards). Classic model-free RL divides into policy gradients and value-based methods; combine them and you get actor-critic — deep Q-learning on the value side, Q-function actor-critic like SAC in the middle, advanced policy gradients like TRPO and PPO on the policy side. Model-based control — planning methods like LQR — needs no learning at all, but paired with a learned model becomes model-based RL, either planning through the model directly or feeding it into policy gradients and value-based learning. Exploration strategies and unsupervised objectives like skill discovery cut across every algorithm choice, and tools from outside the framework — probabilistic and variational inference — give control as inference, which together with imitation learning yields inverse RL. The rest of the lecture asks what is still wrong with all of it.

Challenges with the core algorithms

RL solves “a significantly harder problem than supervised learning”: it collects its own data, gets no i.i.d. assumption, and optimizes an objective rather than being handed ground-truth actions. Each method class pays for that differently.

Value-based methods. Fitted value iteration with deep function approximation is generally not a contraction, so convergence is not guaranteed — the target-network delay, replay buffer size, and gradient clipping are “fixes to make it converge,” which is why they need such careful tuning. Bread-and-butter deep learning helps (large networks done right, normalization, data augmentation — see DrQ for Q-learning). But there is a deeper mystery: supervised deep learning should overfit catastrophically and doesn’t, so “there’s some kind of magic in a sense that makes deep learning work” — some regularizing effect of big networks under SGD. Value-based methods are not gradient descent, and whether the same magic applies to them is an open question at the frontier.

Policy gradients. These trade the nastiness of the other families for variance: unbiased in their purest form (until a learned critic reintroduces bias), hence better understood — but “the variance is no picnic.” In the worst case the sample requirement grows exponentially, and it is hard to predict for a new problem whether variance will be catastrophic. The load-bearing knobs: batch size, learning rate, baseline design.

Model-based RL. Fitting the model to a fixed batch is ordinary supervised learning, but the procedure is iterative and self-collecting, and “not all errors in the model are made equal” — a slightly wrong model of an airplane at 30,000 feet is harmless, the same error while landing is not, so a model that gets more accurate on average can still yield a worse policy. Optimizing through the model is nontrivial (backpropagation through time is ill-behaved; running model-free RL inside the model inherits model-free RL’s problems), and subtlest of all, “the policy can exploit the model” — it finds the one action where the model erroneously predicts something wonderful. Model-based RL is, in a sense, an adversarial process.

The efficiency ladder

Why prefer the less efficient rungs? Samples are not the only cost: policy gradients parallelize beautifully and can win on wall-clock time when simulation is cheap, while model-based methods are often the most compute-hungry, taking many gradient updates per simulation step. But sample complexity still decides whether real-world training is feasible at all, and whether you can afford high-fidelity simulators — finite-element analysis slower than real time is useless to an algorithm demanding hundreds of millions of trials.

Generalization, and the assumptions RL makes

State-of-the-art supervised learning is large-scale, emphasizes diversity, and is evaluated on generalization — nobody cares how well a language model memorizes its training text. RL research is mostly small-scale, emphasizes mastery, and is evaluated on performance in the very environment being optimized. Reasonable for studying optimization; but scaling up collides with a workflow problem: “actual reinforcement learning has an outer loop, and that outer loop is you.” Change your method and you rerun the whole interactive learning process — fine for a half-cheetah, quickly impractical at internet scale. A TRPO+GAE humanoid learns to run in about six days of equivalent real time (far less now) — but on an infinitely large flat plane, while the real world presents sand, cities, and obstacles. Offline RL suggests a better workflow — when unhappy, add data rather than recollect — and multitask training supplies diversity, though more MDPs exacerbate exactly the variance and sample-complexity challenges RL already has.

Then there are the assumptions. Where does supervision come from? A game has a score; “pour a glass of water” — something any child can do — requires a perception system just to tell whether the glass is full, and for internet chatbots, knowing whether users are satisfied is a major challenge where traditional reward specification fails. The alternatives each relax an assumption: inverse RL learns objectives from demonstrations, skill discovery generates tasks automatically, language and perception models can supply rewards by generalizing from internet-scale training, and learning from pairwise human preferences — pioneered for RL benchmarks by Christiano in 2017 — is now the preferred method for training language models. Underneath is a tension: should supervision tell the agent what to do or how? Demonstrations provide both; a sparse reward only the what; a well-shaped reward smuggles in some how. Supervise too closely and you forfeit RL’s power to discover novel solutions; too loosely (“make my company lots of money”) and learning is hopeless. Levine’s advice: “don’t assume that the basic RL problem is set in stone” — sometimes the right move is to invent a new formulation that fits your setting.

Perspective one: RL as an engineering tool

Forget the lofty ideals for a moment. Flying a rocket is traditionally solved by writing down the physics and inverting it by hand — calculus, linearization, control theory — to derive a feedback controller. A simulator is just a fancier version of those equations, numerically integrated; run RL inside it and you are using machine learning to invert your own understanding of physics. Before: characterize, simulate, derive the controller on paper. Now: characterize, simulate, run RL. The main role of RL here is “a more powerful inversion engine,” and the main weakness is that someone still has to characterize the system — viewed this way it is hardly even learning, more a really powerful optimization tool. But that tool already delivers quadrupeds walking rough terrain via extensive simulation, and in the long run any system we understand well enough to simulate — airplanes, vehicles, walking robots — may get its controller this way by default.

Perspective two: RL and the real world

When Deep Blue beat Kasparov, and again twenty years later when AlphaGo beat Lee Sedol, there was no robot at the board — a human moved the pieces, a computer teleoperating a person. Why could the computer out-think the champion but not out-move a child?

The real difficulty of hard universes is the unexpected. Plotting an oil tanker’s route across the ocean is easy for computers; going down to the engine room to fix whatever broke is why the ship carries a crew. Think of Robinson Crusoe: improvise with the resources at hand, minimal supervision, adapt to surprises, and stay alive long enough to discover the answers. Humans are extremely good at this; current AI systems — even ones that ingest billions of documents — are very bad at it. Levine’s claim: “in principle RL can actually do this, and more or less nothing else can — although mostly by definition,” since RL is the framework for learning from feedback in the moment. Yet RL research rarely studies that setting. Easy universes equate success with high reward in a closed, known, heavily simulated world and ask whether RL can optimize; hard universes equate success with survival in an open world where everything comes from data, and ask whether RL can generalize and adapt. The real-world questions — proximal supervision when there is no score, autonomy without episodic resets, robustness to a changing environment, exploration bootstrapped from prior experience — show up in work from Levine’s lab: preference learning in place of hand-written rewards, and behavioral priors, where experience of many past tasks yields a policy that explores a new environment by attempting plausibly useful tasks rather than flailing randomly. Real- world learning doesn’t mean no prior knowledge — it means prior knowledge “of an appropriate type,” acquired from experience rather than baked into a simulator.

Perspective three: RL as universal learning — and parting advice

The modern recipe pairs a little data that says what to do with a giant amount of “low-quality garbage data” — the internet. Classic unsupervised learning uses the garbage by density estimation: next-token prediction models $p_\theta(x)$, the distribution of buttons people pressed on keyboards. Perhaps that is why prompting is such an art — you are coaxing high-quality behavior from a model whose entire objective was to imitate a low-quality distribution. Levine’s alternative framing starts from the neuroscientist Daniel Wolpert: “we have a brain for one reason and one reason only, and that’s to produce adaptable and complex movements… movement is the only way we have of affecting the world around us.”

Two experiments make this concrete. Goal-conditioned offline RL — the task defined entirely by a goal image, no reward function — works as a pre-training objective for robots, with fast fine-tuning on task rewards afterward: “a little bit like BERT, but for robots.” And Joey Hong’s dialogue work inverts a language model instead of a simulator: an LLM is a good predictive model of humans, so prompt it to simulate plausible dialogues (the data “doesn’t have to be good, it just needs to be plausible”), then run value-based RL on that imagined corpus to find the policy that actually achieves the outcome — a teaching agent that asks short, targeted clarifying questions instead of GPT-4’s wall of text. RL plus LLMs is great for tasks that are easy for LLMs to simulate but hard to perform optimally — and some of ChatGPT’s success, Levine argues, is a primitive version of this pipeline already emerging.

So what is missing on the road to intelligence? Yann LeCun’s cake argues supervision bandwidth: a 1000-class label carries $\log_2 1000 \approx 10$ bits per datapoint, next-frame prediction millions, sparse reward almost none — so self-supervision should be the cake and RL the cherry. Others argue imitation and culture are central. But there is a defensible case that RL is enough: the reward may be one bit, yet it is modulated through complex dynamics, so the supervision reaching a value function is far richer than the raw signal — and multitask learning multiplies it. Nobody knows; the point is that the questions matter. The parting advice: pick problems where the upper bound on success is really high, then reduce the big picture to concrete, falsifiable hypotheses; “optimism in the face of uncertainty is a great strategy” for research, not just bandits; don’t be afraid to change the problem statement — many of these challenges will not be met by iterating on existing benchmarks; applications matter, because realistic domains reveal which problems are real (“RL has a long history of disregarding this fact — don’t fall into the same trap”); and “think big, but start small.”

Check yourself

Conceptual exercises on the lecture’s arguments — reason them through on paper.

Problem 23.1 stability across method classes

For each of the three method classes — value-based, policy gradient, model-based — name the core theoretical or structural reason it is hard to stabilize, and one hyperparameter whose sensitivity is a direct symptom of that reason. Then explain why the “magic” that makes supervised deep learning generalize might not transfer to value-based methods.

Show solution

Value-based: fitted value methods with deep function approximation are not contractions, so convergence is not guaranteed in general; the target-network delay (also replay buffer size, gradient clipping) is a patch whose setting is sensitive precisely because the underlying iteration may not converge. Policy gradient: the estimator is unbiased but high-variance — in the worst case the sample requirement grows exponentially — so batch size (also learning rate, baseline design) must be tuned carefully to keep the noise manageable. Model-based: although each model fit is supervised learning, the overall procedure is iterative and self-collecting, model errors are not equally costly across the state space, and the policy adversarially exploits model errors; the model class and fitting procedure are the correspondingly sensitive choices. Finally, the hypothesized regularizing effect behind supervised deep learning’s success is a property of large networks trained with stochastic gradient descent on a fixed objective — but value-based methods are not gradient descent on any fixed objective (they chase bootstrapped targets), so there is no reason the same implicit regularization must operate, and whether it does is an open research question.

Problem 23.2 efficiency ladder reasoning

Rank these methods by sample efficiency, worst to best: TRPO, evolutionary strategies, PILCO-style shallow model-based RL, SAC-style off-policy actor-critic, A3C-style fully online on-policy learning, deep model-based RL. Roughly how large is each gap? Then give two distinct reasons a practitioner with a fast, massively parallel simulator might rationally choose a method from the worst half of your ranking.

Show solution

Worst to best: evolutionary strategies, then A3C-style fully online methods (gradient-free is roughly $10\times$ worse), then batch on-policy policy gradients like TRPO, then off-policy replay-buffer methods like SAC, then deep model-based RL, then shallow model-based methods like PILCO — each step roughly an order of magnitude (illustratively: about 100M steps for fully online, about 10M for TRPO/PPO, about 1M for off-policy, less still for model-based, seconds for PILCO at the cost of non-scalable Gaussian-process models). Two reasons to pick a “worse” rung: (1) parallelism — on-policy policy gradient methods parallelize across simulators, so with cheap simulation they can minimize wall-clock time even while consuming more samples; (2) compute per sample — sample-efficient methods, especially model-based ones, spend many gradient updates per environment step, so when samples are cheap and compute is the binding cost, the sample-hungry but compute-light method is the economical choice.

Problem 23.3 what-versus-how supervision

Place these supervision signals on the spectrum from “specifies what you want” to “specifies how to do it”: a sparse game score, a dense shaped reward, expert demonstrations, pairwise human preferences over trajectories. Explain the failure mode at each extreme of the spectrum, and why demonstrations used as guidance rather than goal specification try to escape the tradeoff.

Show solution

Sparse score: pure “what” — it specifies the objective and nothing about the solution. Preferences: essentially “what” (which outcome is better), with only weak “how” leaking through whatever the comparisons reward stylistically. Shaped reward: a mixture — it still encodes the goal but its shaping steers the path taken, smuggling in “how.” Demonstrations: both at once — they show the goal implicitly and prescribe a particular way of achieving it. At the pure-”what” extreme the learning problem can become hopelessly hard (“make my company lots of money” is a well-specified objective and an intractable credit-assignment problem); at the pure-”how” extreme you supervise so closely that you forfeit RL’s central strength, discovering novel solutions the supervisor didn’t know. Using demonstrations as guidance — hints that ease learning (e.g., shaping exploration) without constraining the final solution — aims to keep the learning-acceleration benefit of the “how” while leaving the optimum defined only by the “what,” though how best to do this remains open research.

Problem 23.4 LeCun's cake, contested

Yann LeCun’s cake argues that RL provides the fewest bits of supervision per datapoint (a sparse scalar reward) and should therefore be only the “cherry” on a self-supervised cake. Reconstruct the bits-per-sample argument quantitatively for a 1000-class classifier versus next-frame video prediction versus sparse reward, then give the counterargument from the lecture for why RL’s effective supervision is richer than the raw count suggests.

Show solution

A 1000-way label carries $\log_2 1000 \approx 10$ bits per datapoint. Predicting the next video frame supervises every pixel, so each sample carries on the order of millions of bits. A sparse reward is a scalar arriving occasionally — often effectively a single bit (success or not) per episode. On raw bandwidth, self-supervised learning should be the foundation and RL the final adaptation layer. The counterargument: the reward signal is not consumed raw. It is propagated through the system dynamics — the supervision that actually reaches a value function is the reward modulated in complex ways by the dynamics across states and time, which is a far more elaborate target than predicting a one-or-zero outcome. Moreover, nothing restricts RL to one sparse signal: multitask learning and related constructions multiply the supervision available within the standard RL framework. So the bits-per-sample accounting understates RL’s signal, and “maybe RL is enough” remains a defensible position — the lecture’s honest conclusion being that the answer (cake, cherry, imitation, or a combination) is genuinely unknown.