Factored Bandits

2018-07-04 · NeurIPS 2018 12 · Julian Zimmert, Yevgeny Seldin

We introduce the factored bandits model, which is a framework for learning with limited (bandit) feedback, where actions can be decomposed into a Cartesian product of atomic actions. Factored bandits incorporate rank-1 bandits as a special case, but significantly relax the assumptions on the form of the reward function. We provide an anytime algorithm for stochastic factored bandits and up to constants matching upper and lower regret bounds for the problem. Furthermore, we show that with a slight modification the proposed algorithm can be applied to utility based dueling bandits. We obtain an improvement in the additive terms of the regret bound compared to state of the art algorithms (the additive terms are dominating up to time horizons which are exponential in the number of arms).

📄 PDF Abstract BibTeX arXiv:1807.01488

Code (0)

등록된 구현이 없습니다.

Information-Theoretic Confidence Bounds for Reinforcement Learning

2019-11-21 · NeurIPS 2019 12 · Xiuyuan Lu, Benjamin Van Roy

We integrate information-theoretic concepts into the design and analysis of optimistic algorithms and Thompson sampling. By making a connection between information-theoretic quantities and confidence bounds, we obtain re…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Thompson Sampling

FactoredRL: Leveraging Factored Graphs for Deep Reinforcement Learning

2021-01-01 · Bharathan Balaji, Petros Christodoulou, Xiaoyu Lu, Byungsoo Jeon 외

We propose a simple class of deep reinforcement learning (RL) methods, called FactoredRL, that can leverage factored environment structures to improve the sample efficiency of existing model-based and model-free RL algor…

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

Temporal Inference with Finite Factored Sets

2021-09-23 · Scott Garrabrant

We propose a new approach to temporal inference, inspired by the Pearlian causal inference paradigm - though quite different from Pearl's approach formally. Rather than using directed acyclic graphs, we make use of facto…

Causal Inference

Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting

2020-02-06 · NeurIPS 2020 12 · Ziping Xu, Ambuj Tewari

We study reinforcement learning in non-episodic factored Markov decision processes (FMDPs). We propose two near-optimal and oracle-efficient algorithms for FMDPs. Assuming oracle access to an FMDP planner, they enjoy a B…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL

2020-08-31 · ICLR 2021 1 · Xiaoyu Chen, Jiachen Hu, Lihong Li, Li-Wei Wang

Reinforcement learning (RL) in episodic, factored Markov decision processes (FMDPs) is studied. We propose an algorithm called FMDP-BF, which leverages the factorization structure of FMDP. The regret of FMDP-BF is shown …

reinforcement-learning Reinforcement Learning (RL)