On the possibility of learning in reactive environments with arbitrary dependence

DOI10.1016/J.TCS.2008.06.039zbMATH Open1158.68039arXiv0810.5636OpenAlexW1969028245WikidataQ58012401 ScholiaQ58012401MaRDI QIDQ950202FDOQ950202

Authors: Daniil Ryabko, Marcus Hutter 

Publication date: 22 October 2008

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

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.

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

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

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)

Cites Work

• Prediction, Learning, and Games
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Information Theory and Statistics: A Tutorial
• Nonparametric statistics for stochastic processes
• Universal artificial intelligence. Sequential decisions based on algorithmic probability.
• Self-Optimizing and Pareto-Optimal Policies in General Environments based on Bayes-Mixtures
• General Discounting Versus Average Reward
• 10.1162/1532443041827952
• Algorithmic Learning Theory
• Algorithmic Learning Theory
• Predicting non-stationary processes

Cited In (6)

• 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
• Asymptotic Learnability of Reinforcement Problems with Arbitrary Dependence

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)