A Strongly Asymptotically Optimal Agent In General Environments

Abstract

Reinforcement Learning agents are expected to eventually perform well. Typically, this takes the form of a guarantee about the asymptotic behavior of an algorithm given some assumptions about the environment. We present an algorithm for a policy whose value approaches the optimal value with probability 1 in all computable probabilistic environments, provided the agent has a bounded horizon. This is known as strong asymptotic optimality, and it was previously unknown whether it was possible for a policy to be strongly asymptotically optimal in the class of all computable probabilistic environments. Our agent, Inquisitive Reinforcement Learner (Inq), is more likely to explore the more it expects an exploratory action to reduce its uncertainty about which environment it is in, hence the term inquisitive. Exploring inquisitively is a strategy that can be applied generally; for more manageable environment classes, inquisitiveness is tractable. We conducted experiments in "grid-worlds" to co

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keycohen2019a

Related papers

• Curiosity Killed Or Incapacitated The Cat And The Asymptotically Optimal Agent (2020)0.00
• Simple Agent, Complex Environment: Efficient Reinforcement Learning With Agent States (2021)0.00
• An Intrinsically-motivated Approach For Learning Highly Exploring And Fast Mixing Policies (2019)6.34
• On Information Asymmetry In Competitive Multi-agent Reinforcement Learning: Convergence And Optimality (2020)0.00
• An Agent Design With Goal Reaching Guarantees For Enhancement Of Learning (2024)0.00
• Minimax-optimal Reward-agnostic Exploration In Reinforcement Learning (2023)0.00
• Satisficing Exploration For Deep Reinforcement Learning (2024)0.00
• Exploration-exploitation In Multi-agent Competition: Convergence With Bounded Rationality (2021)0.00