mlsanityData to 14 Oct 2026

Satisficing Exploration for Deep Reinforcement Learning

arXiv 2407.12185 ↗First posted 16 Jul 2024cs.LG cs.AI stat.MLcited by 4

On the map: Deep reinforcement learning methods → Deep RL algorithms and representations

Abstract (arXiv)

A default assumption in the design of reinforcement-learning algorithms is that a decision-making agent always explores to learn optimal behavior. In sufficiently complex environments that approach the vastness and scale of the real world, however, attaining optimal performance may in fact be an entirely intractable endeavor and an agent may seldom find itself in a position to complete the requisite exploration for identifying an optimal policy. Recent work has leveraged tools from information theory to design agents that deliberately forgo optimal solutions in favor of sufficiently-satisfying or satisficing solutions, obtained through lossy compression. Notably, such agents may employ fundamentally different exploratory decisions to learn satisficing behaviors more efficiently than optimal ones that are more data intensive. While supported by a rigorous corroborating theory, the underlying algorithm relies on model-based planning, drastically limiting the compatibility of these ideas with function approximation and high-dimensional observations. In this work, we remedy this issue by extending an agent that directly represents uncertainty over the optimal value function allowing it to both bypass the need for model-based planning and to learn satisficing policies. We provide simple yet illustrative experiments that demonstrate how our algorithm enables deep reinforcement-learning agents to achieve satisficing behaviors. In keeping with previous work on this setting for multi-armed bandits, we additionally find that our algorithm is capable of synthesizing optimal behaviors, when feasible, more efficiently than its non-information-theoretic counterpart.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Placed in Deep RL algorithms and representations, one of 15 directions in Deep reinforcement learning methods. Builds on 69 of its 193 references that are in the map. First posted on arXiv 16 Jul 2024.

Builds on

69 of 193 references.

References · 69

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  3. 2015Continuous control with deep reinforcement learningcited by 3,407
  4. 2020Learning to summarize from human feedbackcited by 2,588
  5. 2015High-Dimensional Continuous Control Using Generalized Advantage Estimationcited by 2,026
  6. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,353
  7. 2022WebShop: Towards Scalable Real-World Web Interaction with Grounded Language Agentscited by 1,251
  8. 2019Solving Rubik's Cube with a Robot Handcited by 734
  9. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 669
  10. 2016Deep Exploration via Bootstrapped DQNcited by 527
  11. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  12. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
38 more
  1. 2018Is Q-learning Provably Efficient?cited by 487
  2. 2018Reinforcement Learning and Control as Probabilistic Inference: Tutorial and Reviewcited by 482
  3. 2017A Tutorial on Thompson Samplingcited by 433
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  5. 2018Provably Efficient Maximum Entropy Explorationcited by 242
  6. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  7. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  8. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  9. 2018Randomized Prior Functions for Deep Reinforcement Learningcited by 219
  10. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  11. 2018Optimization of Molecules via Deep Reinforcement Learningcited by 200
  12. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  13. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  14. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  15. 2014Learning to Optimize via Information-Directed Samplingcited by 168
  16. 2019Benchmarking Model-Based Reinforcement Learningcited by 162
  17. 2017Deep Reinforcement Learning for De-Novo Drug Designcited by 161
  18. 2017Deep Exploration via Randomized Value Functionscited by 156
  19. 2015Variational Information Maximisation for Intrinsically Motivated Reinforcement Learningcited by 144
  20. 2015Taming the Noise in Reinforcement Learning via Soft Updatescited by 127
  21. 2021Epistemic Neural Networkscited by 120
  22. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 117
  23. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  24. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  25. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 106
  26. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 92
  27. 2017The Uncertainty Bellman Equation and Explorationcited by 82
  28. 2019InfoBot: Transfer and Exploration via the Information Bottleneckcited by 78
  29. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  30. 2018Reinforcement Learning of Theorem Provingcited by 69
  31. 2017Near Optimal Behavior via Approximate State Abstractioncited by 66
  32. 2021Reinforcement Learning, Bit by Bitcited by 59
  33. 2019Information asymmetry in KL-regularized RLcited by 53
  34. 2019Information-Theoretic Confidence Bounds for Reinforcement Learningcited by 51
  35. 2021People construct simplified mental representations to plancited by 47
  36. 2018Satisficing in Time-Sensitive Bandit Learningcited by 39
  37. 2020Hypermodels for Explorationcited by 37
  38. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 32

50 most cited of 69 All 69 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 2; 2026: 1.

4 papers.

  1. 2025Beyond Markovian: Reflective Exploration via Bayes-Adaptive RL for LLM Reasoningcited by 9
  2. 2026Human-like autonomy emerges from self-play and a pinch of human datacited by 4
  3. 2025Memory Allocation in Resource-Constrained Reinforcement Learningcited by 2
  4. 2024Reinforcement Learning with a Focus on Adjusting Policies to Reach Targetscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025On Efficient Bayesian Exploration in Model-Based Reinforcement Learning
  2. 2024Efficient Exploration in Deep Reinforcement Learning: A Novel Bayesian Actor-Critic Algorithm
  3. 2020Guided Exploration with Proximal Policy Optimization using a Single Demonstration
  4. 2026Learning to Explore: Scaling Agentic Reasoning via Exploration-Aware Policy Optimization
  5. 2025Is Exploration or Optimization the Problem for Deep Reinforcement Learning?
  6. 2026Solving Parameter-Robust Avoid Problems with Unknown Feasibility using Reinforcement Learning
  7. 2025Imitation Learning via Focused Satisficing
  8. 2024Reinforcement Learning with Lookahead Information