Exploring compact reinforcement-learning representations with linear regression

By Thomas J. Walsh, Istvan Szita, Carlos Diuk, Michael L. Littman. 2009

120 citations recorded by the source corpus.

This paper presents a new algorithm for online linear regression whose efficiency guarantees satisfy the requirements of the KWIK (Knows What It Knows) framework. The algorithm improves on the complexity bounds of the current state-of-the-art procedure in this setting. We explore several applications of this algorithm for learning compact reinforcement-learning representations. We show that KWIK linear regression can be used to learn the reward function of a factored MDP and the probabilities of action outcomes in Stochastic STRIPS and Object Oriented MDPs, none of which have been proven to be efficiently learnable in the RL setting before. We also combine KWIK linear regression with other KWIK learners to learn larger portions of these models, including experiments on learning factored MDP transition and reward functions together.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

A contextual-bandit approach to personalized news article recommendation (2010, neutral): “When components in ca are independent conditioned on corresponding rows in Da, it can be shown [27] that, with probability at least 1− δ, ̨̨̨ x t,aθ̂a −E[rt,a|xt,a] ̨̨̨ ≤ α q x t,a(D a Da + Id)−1xt,a (4)”
DORA The Explorer: Directed Outreaching Reinforcement Action-Selection (2018, background): “In fact, several exploration schemes relying on optimism in the face of uncertainty were proposed (Walsh et al., 2009).”
Sample Complexity Bounds of Exploration (2012, methodology): “A similar result is obtained by a simpler algorithm based on ridge regression (Walsh et al, 2009).”
Near-Optimal BRL using Optimistic Local Transitions (2012, background): “The full description of the problem can be found in Walsh et al. [2009]. Here,”
Interactive collaborative filtering (2013, background): “According to [37], with the item feature vectors known and fixed, the expectation of the reward by choosing item i is bounded in the interval Θi,t with probability at least 1−ζ”