Alexander L. Strehl

UAI Conference 2009 Conference Paper

Conditional Probability Tree Estimation Analysis and Algorithms

• Alina Beygelzimer
• John Langford 0001
• Yury Lifshits
• Gregory B. Sorkin
• Alexander L. Strehl

We consider the problem of estimating the conditional probability of a label in time O(log n), where n is the number of possible labels. We analyze a natural reduction of this problem to a set of binary regression problems organized in a tree structure, proving a regret bound that scales with the depth of the tree. Motivated by this analysis, we propose the first online algorithm which provably constructs a logarithmic depth tree on the set of labels to solve this problem. We test the algorithm empirically, showing that it works succesfully on a dataset with roughly 106 labels.

JMLR Journal 2009 Journal Article

Reinforcement Learning in Finite MDPs: PAC Analysis

• Alexander L. Strehl
• Lihong Li
• Michael L. Littman

We study the problem of learning near-optimal behavior in finite Markov Decision Processes (MDPs) with a polynomial number of samples. These "PAC-MDP" algorithms include the well-known E 3 and R-MAX algorithms as well as the more recent Delayed Q-learning algorithm. We summarize the current state-of-the-art by presenting bounds for the problem in a unified theoretical framework. A more refined analysis for upper and lower bounds is presented to yield insight into the differences between the model-free Delayed Q-learning and the model-based R-MAX. [abs] [ pdf ][ bib ] &copy JMLR 2009. ( edit, beta )

ICML Conference 2008 Conference Paper

Exploration scavenging

• John Langford 0001
• Alexander L. Strehl
• Jennifer Wortman Vaughan

We examine the problem of evaluating a policy in the contextual bandit setting using only observations collected during the execution of another policy. We show that policy evaluation can be impossible if the exploration policy chooses actions based on the side information provided at each time step. We then propose and prove the correctness of a principled method for policy evaluation which works when this is not the case, even when the exploration policy is deterministic, as long as each action is explored sufficiently often. We apply this general technique to the problem of offline evaluation of internet advertising policies. Although our theoretical results hold only when the exploration policy chooses ads independent of side information, an assumption that is typically violated by commercial systems, we show how clever uses of the theory provide non-trivial and realistic applications. We also provide an empirical demonstration of the effectiveness of our techniques on real ad placement data.

AAAI Conference 2007 Conference Paper

Efficient Structure Learning in Factored-State MDPs

• Alexander L. Strehl

We consider the problem of reinforcement learning in factored-state MDPs in the setting in which learning is conducted in one long trial with no resets allowed. We show how to extend existing efficient algorithms that learn the conditional probability tables of dynamic Bayesian networks (DBNs) given their structure to the case in which DBN structure is not known in advance. Our method learns the DBN structures as part of the reinforcement-learning process and provably provides an efficient learning algorithm when combined with factored Rmax.

ICML Conference 2006 Conference Paper

Experience-efficient learning in associative bandit problems

• Alexander L. Strehl
• Chris Mesterharm
• Michael L. Littman
• Haym Hirsh

UAI Conference 2006 Conference Paper

Incremental Model-based Learners With Formal Learning-Time Guarantees

• Alexander L. Strehl
• Lihong Li 0001
• Michael L. Littman

Model-based learning algorithms have been shown to use experience efficiently when learning to solve Markov Decision Processes (MDPs) with finite state and action spaces. However, their high computational cost due to repeatedly solving an internal model inhibits their use in large-scale problems. We propose a method based on real-time dynamic programming (RTDP) to speed up two model-based algorithms, RMAX and MBIE (model-based interval estimation), resulting in computationally much faster algorithms with little loss compared to existing bounds. Specifically, our two new learning algorithms, RTDP-RMAX and RTDP-IE, have considerably smaller computational demands than RMAX and MBIE. We develop a general theoretical framework that allows us to prove that both are efficient learners in a PAC (probably approximately correct) sense. We also present an experimental evaluation of these new algorithms that helps quantify the tradeoff between computational and experience demands.

ICML Conference 2006 Conference Paper

PAC model-free reinforcement learning

• Alexander L. Strehl
• Lihong Li 0001
• Eric Wiewiora
• John Langford 0001
• Michael L. Littman

ICML Conference 2005 Conference Paper

A theoretical analysis of Model-Based Interval Estimation

• Alexander L. Strehl
• Michael L. Littman

Several algorithms for learning near-optimal policies in Markov Decision Processes have been analyzed and proven efficient. Empirical results have suggested that Model-based Interval Estimation (MBIE) learns efficiently in practice, effectively balancing exploration and exploitation. This paper presents the first theoretical analysis of MBIE, proving its efficiency even under worst-case conditions. The paper also introduces a new performance metric, average loss, and relates it to its less "online" cousins from the literature.