The Computational Complexity of Probabilistic Planning

Aug 01, 1998

M. L. Littman, J. Goldsmith, M. Mundhenk

We examine the computational complexity of testing and finding small plans in probabilistic planning domains with both flat and propositional representations. The complexity of plan evaluation and existence varies with the plan type sought; we examine totally ordered plans, acyclic plans, and looping plans, and partially ordered plans under three natural definitions of plan value. We show that problems of interest are complete for a variety of complexity classes: PL, P, NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE. In the process of proving that certain planning problems are complete for NP^PP, we introduce a new basic NP^PP-complete problem, E-MAJSAT, which generalizes the standard Boolean satisfiability problem to computations involving probabilistic quantities; our results suggest that the development of good heuristics for E-MAJSAT could be important for the creation of efficient algorithms for a wide variety of problems.
Aug 01, 1998

M. L. Littman, J. Goldsmith, M. Mundhenk

* Journal of Artificial Intelligence Research, Vol 9, (1998), 1-36

* See http://www.jair.org/ for any accompanying files

**Click to Read Paper**

* Journal of Artificial Intelligence Research, Vol 4, (1996), 237-285

* See http://www.jair.org/ for any accompanying files

**Click to Read Paper**

ATTac-2000: An Adaptive Autonomous Bidding Agent

Jun 03, 2011

M. Kearns, M. L. Littman, S. Singh, P. Stone

The First Trading Agent Competition (TAC) was held from June 22nd to July 8th, 2000. TAC was designed to create a benchmark problem in the complex domain of e-marketplaces and to motivate researchers to apply unique approaches to a common task. This article describes ATTac-2000, the first-place finisher in TAC. ATTac-2000 uses a principled bidding strategy that includes several elements of adaptivity. In addition to the success at the competition, isolated empirical results are presented indicating the robustness and effectiveness of ATTac-2000's adaptive strategy.
Jun 03, 2011

M. Kearns, M. L. Littman, S. Singh, P. Stone

* Journal Of Artificial Intelligence Research, Volume 15, pages 189-206, 2001

**Click to Read Paper**

Decision-Theoretic Bidding Based on Learned Density Models in Simultaneous, Interacting Auctions

Jun 26, 2011

J. A. Csirik, M. L. Littman, D. McAllester, R. E. Schapire, P. Stone

Jun 26, 2011

J. A. Csirik, M. L. Littman, D. McAllester, R. E. Schapire, P. Stone

* Journal Of Artificial Intelligence Research, Volume 19, pages 209-242, 2003

**Click to Read Paper**

Successor Features Support Model-based and Model-free Reinforcement Learning

Jan 31, 2019

Lucas Lehnert, Michael L. Littman

Jan 31, 2019

Lucas Lehnert, Michael L. Littman

**Click to Read Paper**

Corpus-based Learning of Analogies and Semantic Relations

Aug 23, 2005

Peter D. Turney, Michael L. Littman

We present an algorithm for learning from unlabeled text, based on the Vector Space Model (VSM) of information retrieval, that can solve verbal analogy questions of the kind found in the SAT college entrance exam. A verbal analogy has the form A:B::C:D, meaning "A is to B as C is to D"; for example, mason:stone::carpenter:wood. SAT analogy questions provide a word pair, A:B, and the problem is to select the most analogous word pair, C:D, from a set of five choices. The VSM algorithm correctly answers 47% of a collection of 374 college-level analogy questions (random guessing would yield 20% correct; the average college-bound senior high school student answers about 57% correctly). We motivate this research by applying it to a difficult problem in natural language processing, determining semantic relations in noun-modifier pairs. The problem is to classify a noun-modifier pair, such as "laser printer", according to the semantic relation between the noun (printer) and the modifier (laser). We use a supervised nearest-neighbour algorithm that assigns a class to a given noun-modifier pair by finding the most analogous noun-modifier pair in the training data. With 30 classes of semantic relations, on a collection of 600 labeled noun-modifier pairs, the learning algorithm attains an F value of 26.5% (random guessing: 3.3%). With 5 classes of semantic relations, the F value is 43.2% (random: 20%). The performance is state-of-the-art for both verbal analogies and noun-modifier relations.
Aug 23, 2005

Peter D. Turney, Michael L. Littman

* Machine Learning, (2005), 60(1-3), 251-278

* related work available at http://purl.org/peter.turney/ and http://www.cs.rutgers.edu/~mlittman/

**Click to Read Paper**

On the Computational Complexity of Stochastic Controller Optimization in POMDPs

Oct 04, 2012

Nikos Vlassis, Michael L. Littman, David Barber

We show that the problem of finding an optimal stochastic 'blind' controller in a Markov decision process is an NP-hard problem. The corresponding decision problem is NP-hard, in PSPACE, and SQRT-SUM-hard, hence placing it in NP would imply breakthroughs in long-standing open problems in computer science. Our result establishes that the more general problem of stochastic controller optimization in POMDPs is also NP-hard. Nonetheless, we outline a special case that is convex and admits efficient global solutions.
Oct 04, 2012

Nikos Vlassis, Michael L. Littman, David Barber

* Corrected error in the proof of Theorem 2, and revised Section 5

**Click to Read Paper**

Interactive Learning from Policy-Dependent Human Feedback

Jan 21, 2017

James MacGlashan, Mark K Ho, Robert Loftin, Bei Peng, David Roberts, Matthew E. Taylor, Michael L. Littman

Jan 21, 2017

James MacGlashan, Mark K Ho, Robert Loftin, Bei Peng, David Roberts, Matthew E. Taylor, Michael L. Littman

* 7 pages, 2 figures

**Click to Read Paper**