Research map / Reinforcement learning / Visual and representation RL

Sample Efficient Myopic Exploration Through Multitask Reinforcement Learning with Diverse Tasks

ICLR 2024 · Reinforcement learning › Visual and representation RL · approach: Hierarchical skills and priors · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that myopic epsilon-greedy exploration can be sample-efficient in multitask RL when the task set is sufficiently diverse, via a multitask myopic exploration gap and diversity condition, with theory for tabular, linear, and LQR cases plus BipedalWalker experiments.

Problem

Epsilon-greedy-style myopic exploration is known to be sample-inefficient in worst case for single-task RL, yet works well in practice; the question is whether it can be sample-efficient for multitask RL.

Approach

Exploring one task with epsilon-greedy policies derived from other tasks' greedy policies yields coverage; a multitask myopic exploration gap and a diversity condition on the task set formalize when this gives polynomial sample complexity.

Key results

• Theory: with a (alpha, c)-diverse task set, epsilon-greedy multitask RL achieves polynomial sample complexity, e.g. tabular bound |M|^2 S^3 H^5 A^2 / beta^3.
• Linear MDP case: sample complexity tilde-O(|M|^3 H^3 d^2 |A| / (beta^3 b_1^2)) under a diverse task set with |M| >= d.
• BipedalWalker: PPO agent fine-tuned on stump heights in [1.3, 1.6] masters 41.6 tasks versus 28.1 for [0.0, 0.3] and 11.5 for [2.6, 3.0].

Measured effects reported in the paper

Surprising findings

• Tasks with extremely high stumps (2.6-3.0) yield the worst subsequent mastery, not the hardest-is-best intuition.
• Eigenvalue spread of feature covariance depends mainly on stump height, and the automatic curriculum (ALP-GMM) preferentially samples mid-range heights.

Limitations

• Diversity condition is explicit only for tabular, linear MDP and LQR cases; general function classes remain open.
• Sample complexity bounds are likely suboptimal (gap versus |M|SA/beta^2 in tabular case).
• Experiments are synthetic and only loosely validate the theory; the algorithm is not shown to be practically competitive.

Experimental setup

Datasets: BipedalWalker tasks parameterized by stump height and spacing

Benchmarks: BipedalWalker

Metrics: number of mastered tasks log-scaled eigenvalues of feature covariance

Baselines: ALP-GMM

Builds on: Myopic Exploration Gap (Dann et al.) Bellman-Eluder dimension Linear MDP ALP-GMM

Closest papers by meaning

• Task-agnostic Exploration in Reinforcement Learning (NeurIPS 2020 · similarity 0.89)
• Exploration via Planning for Information about the Optimal Trajectory (NeurIPS 2022 · similarity 0.88)
• Understanding the Complexity Gains of Single-Task RL with a Curriculum (ICML 2023 · similarity 0.88)
• DUO: Diverse, Uncertain, On-Policy Query Generation and Selection for Reinforcement Learning from Human Feedback (AAAI 2025 · similarity 0.87)
• Learning Policy Committees for Effective Personalization in MDPs with Diverse Tasks (ICML 2025 · similarity 0.87)
• Efficient Model-Based Reinforcement Learning Through Optimistic Thompson Sampling (ICLR 2025 · similarity 0.87)