← All AI/ML open problems

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.

OpenEditorially scopedFramework needs definitionCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

Consider horizon-HH block MDPs with SS latent states, AA actions and high-dimensional observations emitted on disjoint latent-state supports. The unknown decoder belongs to a finite class F\mathcal F, rewards lie in [0,1][0,1], and resets are allowed only to the initial-state law. Determine conditions for V⋆−Vπ^≤εV^\star-V^{\hat\pi}\leq\varepsilon with interaction and runtime polynomial in S,A,H,log⁡∣F∣,1/εS,A,H,\log|\mathcal F|,1/\varepsilon, 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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.