Research map / Reinforcement learning / MDPs and planning
Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use myopic exploration with least-squares value iteration under a Bellman Eluder dimension and positive myopic exploration gap | Value-function-based RL in episodic MDPs · Episodic MDPs with bounded Bellman Eluder dimension | episodes selecting functions in F': O(\frac{\ln c(\cF', \cF)}{\alpha(\cF', \cF)^2} H^2 d \ln (\frac{\bar N_{\cF}(T^{-1})\ln T}{\delta})) | Helped |
| Use ε-greedy exploration | Value-function-based RL · Tabular MDPs | episodes selecting suboptimal functions: \Omega(\frac{S}{\alpha(\cF', \cF)^2}) | Hurt |
| Use ε-greedy exploration when the gap scales as (ε/A)^{h/2} times suboptimality | Value-function-based RL · Episodic MDPs | regret: \widetilde O(H^{\frac{h+3}{h+2}} T^{\frac{h+1}{h+2}} (h A^h d \ln \frac{\bar N_{\cF}(T^{-1})}{\delta})^{\frac{1}{h+2}}) | Helped |
| Use ε-greedy in a contextual bandit structure where actions do not affect transitions | ε-greedy RL · Contextual bandits | myopic exploration gap: \sqrt{\frac{\varepsilon}{A}} (V^{\star}_1(x_1) - V^{\pi^f}_1(x_1)) | Helped |
| Make transition distributions similar across actions | ε-greedy · MDPs with multiplicative action variation δ_P | myopic exploration gap: \sqrt{\frac{\varepsilon}{A \delta_P^H}} \cdot (V_1^{\star}(x_1) - V_1^{\pi^f}(x_1)) | Helped |
| Add intermediate rewards along the shortest route | ε-greedy · Grid-world navigation with breadcrumbs every B steps | myopic exploration gap: \frac{1}{2H} (\frac{\varepsilon}{A})^{B/2} | Helped |
| Add dense breadcrumbs that distract from the goal | ε-greedy · Grid-world navigation with distracting breadcrumbs | myopic exploration gap: \alpha(f, \cF) = \frac{1}{2} (\frac{\varepsilon}{A})^{H/2} if π^f reaches all breadcrumbs; otherwise ≥ \frac{1}{2H} (\fr | Mixed |
| Apply potential-based reward shaping while keeping policy returns unchanged | ε-greedy in tabular MDPs · Tabular MDPs | myopic exploration gap: identical | No clear effect |
Closest papers by meaning
- Improved Bounds for Reward-Agnostic and Reward-Free Exploration (ICML 2026 · similarity 0.89)
- Reward-Free Exploration for Reinforcement Learning (ICML 2020 · similarity 0.89)
- Towards Minimax Optimal Reward-free Reinforcement Learning in Linear MDPs (ICLR 2023 · similarity 0.89)
- Sample Efficient Myopic Exploration Through Multitask Reinforcement Learning with Diverse Tasks (ICLR 2024 · similarity 0.88)
- Beyond Optimism: Exploration With Partially Observable Rewards (NeurIPS 2024 · similarity 0.88)
- Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.