Provably Efficient Reinforcement Learning via Surprise Bound

2023-02-22 · Hanlin Zhu, Ruosong Wang, Jason D. Lee

Value function approximation is important in modern reinforcement learning (RL) problems especially when the state space is (infinitely) large. Despite the importance and wide applicability of value function approximation, its theoretical understanding is still not as sophisticated as its empirical success, especially in the context of general function approximation. In this paper, we propose a provably efficient RL algorithm (both computationally and statistically) with general value function approximations. We show that if the value functions can be approximated by a function class that satisfies the Bellman-completeness assumption, our algorithm achieves an $\widetilde{O}(\text{poly}(\iota H)\sqrt{T})$ regret bound where $\iota$ is the product of the surprise bound and log-covering numbers, $H$ is the planning horizon, $K$ is the number of episodes and $T = HK$ is the total number of steps the agent interacts with the environment. Our algorithm achieves reasonable regret bounds when applied to both the linear setting and the sparse high-dimensional linear setting. Moreover, our algorithm only needs to solve $O(H\log K)$ empirical risk minimization (ERM) problems, which is far more efficient than previous algorithms that need to solve ERM problems for $\Omega(HK)$ times.

📄 PDF Abstract BibTeX arXiv:2302.11634

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

VASE: Variational Assorted Surprise Exploration for Reinforcement Learning

2019-10-31 · Haitao Xu, Brendan McCane, Lech Szymanski

Exploration in environments with continuous control and sparse rewards remains a key challenge in reinforcement learning (RL). Recently, surprise has been used as an intrinsic reward that encourages systematic and effici…

continuous-control Continuous Control Efficient Exploration reinforcement-learning+3

Beyond Surprise: Improving Exploration Through Surprise Novelty

2023-08-09 · Hung Le, Kien Do, Dung Nguyen, Svetha Venkatesh

We present a new computing model for intrinsic rewards in reinforcement learning that addresses the limitations of existing surprise-driven explorations. The reward is the novelty of the surprise rather than the surprise…

Atari Games Retrieval

A Mixture of Surprises for Unsupervised Reinforcement Learning

2022-10-13 · Andrew Zhao, Matthieu Gaetan Lin, Yangguang Li, Yong-Jin Liu 외

Unsupervised reinforcement learning aims at learning a generalist policy in a reward-free manner for fast adaptation to downstream tasks. Most of the existing methods propose to provide an intrinsic reward based on surpr…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Unsupervised Reinforcement Learning

Adapting Surprise Minimizing Reinforcement Learning Techniques for Transactive Control

2021-11-11 · William Arnold, Tarang Srivastava, Lucas Spangher, Utkarsha Agwan 외

Optimizing prices for energy demand response requires a flexible controller with ability to navigate complex environments. We propose a reinforcement learning controller with surprise minimizing modifications in its arch…

Navigate reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Graph Distance as Surprise: Free Energy Minimization in Knowledge Graph Reasoning

2025-12-01 · Gaganpreet Jhajj, Fuhua Lin arxiv

In this work, we propose that reasoning in knowledge graph (KG) networks can be guided by surprise minimization. Entities that are close in graph distance will have lower surprise than those farther apart. This connects …

Reinforcement Learning