RL foundations · Embeddings & representations · Data-efficient learning / Open question
The Price of Exploration
An agent must discover useful actions before it has the representation needed to recognize them. Resolving that circularity is central to data-efficient RL and robotics. Efficiency payoff: Learn from interactions while charging representation discovery rather than relying on free human-data pretraining or optimization oracles.
Seed catalog · Showing the bundled record.
Problem statement
Consider horizon- block MDPs with latent states, actions and high-dimensional observations emitted on disjoint latent-state supports. The unknown decoder belongs to a finite class , rewards lie in , and resets are allowed only to the initial-state law. Determine conditions for with interaction and runtime polynomial in , explicitly charging decoder search rather than assuming a free optimization oracle. Characterize computational obstructions within this class.
Assumptions and scope
- Fix a finite-horizon latent or nonlinear MDP family, representation complexity, reward bounds and the accessible interaction/reset model.
- State realizability and any Bellman-closure or observability requirements separately; an accurate optimal-value representation alone need not make exploration easy.
- Charge representation learning, action search and oracle implementation as well as samples; distinguish simulator/generative-model access from online trajectories.
What would settle it?
A matched statistical/computational upper and lower characterization for a nontrivial unknown-representation family, with an implementable algorithm or an explicit computational obstruction.
Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.
Status and evidence
Linear/all-policy-realizable settings already have sample-and-oracle-efficient methods, and a linear-softmax foundation-model framework characterizes coverage-driven runtime and multi-turn benefits. The target removes free representation/oracle access under additional declared structure; unrestricted RL efficiency is not assumed. This is an editorial, source-motivated research target. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.
Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.
Sources and further reading
- Mhammedi — Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions ↗partial theory · source checked 2026-11-19
Publisher abstract checked: all-policy linear value realizability, polynomial episodes and cost-sensitive-classification oracle calls, with efficient implementation in constant feature dimension. Oracle efficiency and unrestricted computational efficiency differ.
- Foster, Mhammedi and Rohatgi — Is a Good Foundation Necessary for Efficient Reinforcement Learning? ↗partial theory · source checked 2026-11-19
Publisher abstract checked: linear-softmax sampling-oracle framework, runtime dependence on base coverage, SpannerSampling, proper-policy limitations and multi-turn benefits under extra representation assumptions.
- Manda and Diddigi — Generalisation in Multitask Fitted Q-Iteration and Offline Q-learning ↗partial theory · source checked 2026-11-19
Abstract checked: finite-sample guarantees with shared low-rank action-value structure and pooled 1/sqrt(nT) dependence under realizability and coverage. Separate world/structure/task axes and matching lower bounds are not claimed.
- Ineffable Intelligence — mission, beliefs and A Note from Dave ↗research agenda · source checked 2026-11-20
Primary site checked: experience-driven, continual learning without reliance on human data is the stated agenda. The site supplies no corresponding theorem; rewards, environment access and architectures are still inductive assumptions.
- Hafner et al. — Mastering Diverse Domains through World Models ↗related algorithm · source checked 2026-11-20
Primary abstract checked: DreamerV3 world-model learning from experience, including Minecraft without human data/curricula. This is an empirical baseline, not unrestricted efficient learnability.