On the possibility of learning in reactive environments with arbitrary dependence

DOI10.1016/J.TCS.2008.06.039MaRDI QIDQ950202zbMATH OpenOpenAlexWikidataFDO

Authors Daniil Ryabko, Marcus Hutter

Publication date 22 October 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0810.5636

zbMATH Keywords

Markov decision processesreinforcement learningasymptotic average valueself-optimizing policies

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Markov and semi-Markov decision processes (90C40)

Abstract: We address the problem of reinforcement learning in which observations may exhibit an arbitrary form of stochastic dependence on past observations and actions, i.e. environments more general than (PO)MDPs. The task for an agent is to attain the best possible asymptotic reward where the true generating environment is unknown but belongs to a known countable family of environments. We find some sufficient conditions on the class of environments under which an agent exists which attains the best asymptotic reward for any environment in the class. We analyze how tight these conditions are and how they relate to different probabilistic assumptions known in reinforcement learning and related fields, such as Markov Decision Processes and mixing conditions.

Recommendations

• Asymptotic Learnability of Reinforcement Problems with Arbitrary Dependence
• Markov decision processes with arbitrary reward processes
• 10.1162/153244303768966148
• Rationality, optimism and guarantees in general reinforcement learning
• Bayesian Reinforcement Learning with Exploration

Cites work

• scientific article; zbMATH DE number 4160608 (Why is no real title available?)
• scientific article; zbMATH DE number 783783 (Why is no real title available?)
• scientific article; zbMATH DE number 3085434 (Why is no real title available?)
• 10.1162/1532443041827952
• Algorithmic Learning Theory
• Algorithmic Learning Theory
• General Discounting Versus Average Reward
• Information Theory and Statistics: A Tutorial
• Nonparametric statistics for stochastic processes
• Predicting non-stationary processes
• Prediction, Learning, and Games
• Self-Optimizing and Pareto-Optimal Policies in General Environments based on Bayes-Mixtures
• Universal artificial intelligence. Sequential decisions based on algorithmic probability.

Cited in

(7)

• Rationality, optimism and guarantees in general reinforcement learning
• Predicting non-stationary processes
• Open problems in universal induction \& intelligence
• Regret bounds for restless Markov bandits
• 10.1162/153244303768966148
• Reinforcement learning in non-Markovian environments
• Asymptotic Learnability of Reinforcement Problems with Arbitrary Dependence

Describes a project that uses

Uses Software

• R-MAX

This page was built for publication: On the possibility of learning in reactive environments with arbitrary dependence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q950202)