Arrow Research search

Author name cluster

Michael L. Littman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

76 papers
2 author rows

Possible papers

76

ICML Conference 2025 Conference Paper

Knowledge Retention in Continual Model-Based Reinforcement Learning

  • Haotian Fu
  • Yixiang Sun
  • Michael L. Littman
  • George Konidaris 0001

We propose DRAGO, a novel approach for continual model-based reinforcement learning aimed at improving the incremental development of world models across a sequence of tasks that differ in their reward functions but not the state space or dynamics. DRAGO comprises two key components: Synthetic Experience Rehearsal, which leverages generative models to create synthetic experiences from past tasks, allowing the agent to reinforce previously learned dynamics without storing data, and Regaining Memories Through Exploration, which introduces an intrinsic reward mechanism to guide the agent toward revisiting relevant states from prior tasks. Together, these components enable the agent to maintain a comprehensive and continually developing world model, facilitating more effective learning and adaptation across diverse environments. Empirical evaluations demonstrate that DRAGO is able to preserve knowledge across tasks, achieving superior performance in various continual learning scenarios.

Details

ICML Conference 2023 Conference Paper

Meta-learning Parameterized Skills

  • Haotian Fu
  • Shangqun Yu
  • Saket Tiwari
  • Michael L. Littman
  • George Konidaris 0001

We propose a novel parameterized skill-learning algorithm that aims to learn transferable parameterized skills and synthesize them into a new action space that supports efficient learning in long-horizon tasks. We propose to leverage off-policy Meta-RL combined with a trajectory-centric smoothness term to learn a set of parameterized skills. Our agent can use these learned skills to construct a three-level hierarchical framework that models a Temporally-extended Parameterized Action Markov Decision Process. We empirically demonstrate that the proposed algorithms enable an agent to solve a set of highly difficult long-horizon (obstacle-course and robot manipulation) tasks.

Details

IJCAI Conference 2022 Conference Paper

On the (In)Tractability of Reinforcement Learning for LTL Objectives

  • Cambridge Yang
  • Michael L. Littman
  • Michael Carbin

In recent years, researchers have made significant progress in devising reinforcement-learning algorithms for optimizing linear temporal logic (LTL) objectives and LTL-like objectives. Despite these advancements, there are fundamental limitations to how well this problem can be solved. Previous studies have alluded to this fact but have not examined it in depth. In this paper, we address the tractability of reinforcement learning for general LTL objectives from a theoretical perspective. We formalize the problem under the probably approximately correct learning in Markov decision processes (PAC-MDP) framework, a standard framework for measuring sample complexity in reinforcement learning. In this formalization, we prove that the optimal policy for any LTL formula is PAC-MDP-learnable if and only if the formula is in the most limited class in the LTL hierarchy, consisting of formulas that are decidable within a finite horizon. Practically, our result implies that it is impossible for a reinforcement-learning algorithm to obtain a PAC-MDP guarantee on the performance of its learned policy after finitely many interactions with an unconstrained environment for LTL objectives that are not decidable within a finite horizon.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

On the Expressivity of Markov Reward (Extended Abstract)

  • David Abel
  • Will Dabney
  • Anna Harutyunyan
  • Mark K. Ho
  • Michael L. Littman
  • Doina Precup
  • Satinder Singh

Reward is the driving force for reinforcement-learning agents. We here set out to understand the expressivity of Markov reward as a way to capture tasks that we would want an agent to perform. We frame this study around three new abstract notions of "task": (1) a set of acceptable behaviors, (2) a partial ordering over behaviors, or (3) a partial ordering over trajectories. Our main results prove that while reward can express many of these tasks, there exist instances of each task type that no Markov reward function can capture. We then provide a set of polynomial-time algorithms that construct a Markov reward function that allows an agent to perform each task type, and correctly determine when no such reward function exists.

PDF Details DOI

AAAI Conference 2021 Conference Paper

Deep Radial-Basis Value Functions for Continuous Control

  • Kavosh Asadi
  • Neev Parikh
  • Ronald E. Parr
  • George D. Konidaris
  • Michael L. Littman

A core operation in reinforcement learning (RL) is finding an action that is optimal with respect to a learned value function. This operation is often challenging when the learned value function takes continuous actions as input. We introduce deep radial-basis value functions (RBVFs): value functions learned using a deep network with a radial-basis function (RBF) output layer. We show that the maximum action-value with respect to a deep RBVF can be approximated easily and accurately. Moreover, deep RBVFs can represent any true value function owing to their support for universal function approximation. We extend the standard DQN algorithm to continuous control by endowing the agent with a deep RBVF. We show that the resultant agent, called RBF-DQN, significantly outperforms value-function-only baselines, and is competitive with state-of-the-art actor-critic algorithms.

PDF Details

AAAI Conference 2021 Conference Paper

Lipschitz Lifelong Reinforcement Learning

  • Erwan Lecarpentier
  • David Abel
  • Kavosh Asadi
  • Yuu Jinnai
  • Emmanuel Rachelson
  • Michael L. Littman

We consider the problem of knowledge transfer when an agent is facing a series of Reinforcement Learning (RL) tasks. We introduce a novel metric between Markov Decision Processes and establish that close MDPs have close optimal value functions. Formally, the optimal value functions are Lipschitz continuous with respect to the tasks space. These theoretical results lead us to a value-transfer method for Lifelong RL, which we use to build a PAC-MDP algorithm with improved convergence rate. Further, we show the method to experience no negative transfer with high probability. We illustrate the benefits of the method in Lifelong RL experiments.

PDF Details

AAAI Conference 2021 Short Paper

Towards Sample Efficient Agents through Algorithmic Alignment (Student Abstract)

  • Mingxuan Li
  • Michael L. Littman

In this work, we propose and explore Deep Graph Value Network (DeepGV) as a promising method to work around sample complexity in deep reinforcement-learning agents using a message-passing mechanism. The main idea is that the agent should be guided by structured non-neural-network algorithms like dynamic programming. According to recent advances in algorithmic alignment, neural networks with structured computation procedures can be trained efficiently. We demonstrate the potential of graph neural network in supporting sample efficient learning by showing that Deep Graph Value Network can outperform unstructured baselines by a large margin in solving Markov Decision Process (MDP). We believe this would open up a new avenue for structured agents design. See https: //github. com/drmeerkat/Deep- Graph-Value-Network for the code.

PDF Details

JMLR Journal 2020 Journal Article

Successor Features Combine Elements of Model-Free and Model-based Reinforcement Learning

  • Lucas Lehnert
  • Michael L. Littman

A key question in reinforcement learning is how an intelligent agent can generalize knowledge across different inputs. By generalizing across different inputs, information learned for one input can be immediately reused for improving predictions for another input. Reusing information allows an agent to compute an optimal decision-making strategy using less data. State representation is a key element of the generalization process, compressing a high-dimensional input space into a low-dimensional latent state space. This article analyzes properties of different latent state spaces, leading to new connections between model-based and model-free reinforcement learning. Successor features, which predict frequencies of future observations, form a link between model-based and model-free learning: Learning to predict future expected reward outcomes, a key characteristic of model-based agents, is equivalent to learning successor features. Learning successor features is a form of temporal difference learning and is equivalent to learning to predict a single policy's utility, which is a characteristic of model-free agents. Drawing on the connection between model-based reinforcement learning and successor features, we demonstrate that representations that are predictive of future reward outcomes generalize across variations in both transitions and rewards. This result extends previous work on successor features, which is constrained to fixed transitions and assumes re-learning of the transferred state representation. [abs] [ pdf ][ bib ] &copy JMLR 2020. ( edit, beta )

PDF Details

ICML Conference 2019 Conference Paper

Finding Options that Minimize Planning Time

  • Yuu Jinnai
  • David Abel
  • D. Ellis Hershkowitz
  • Michael L. Littman
  • George Konidaris 0001

We formalize the problem of selecting the optimal set of options for planning as that of computing the smallest set of options so that planning converges in less than a given maximum of value-iteration passes. We first show that the problem is $\NP$-hard, even if the task is constrained to be deterministic—the first such complexity result for option discovery. We then present the first polynomial-time boundedly suboptimal approximation algorithm for this setting, and empirically evaluate it against both the optimal options and a representative collection of heuristic approaches in simple grid-based domains.

Details

AAAI Conference 2019 Conference Paper

State Abstraction as Compression in Apprenticeship Learning

  • David Abel
  • Dilip Arumugam
  • Kavosh Asadi
  • Yuu Jinnai
  • Michael L. Littman
  • Lawson L.S. Wong

State abstraction can give rise to models of environments that are both compressed and useful, thereby enabling efficient sequential decision making. In this work, we offer the first formalism and analysis of the trade-off between compression and performance made in the context of state abstraction for Apprenticeship Learning. We build on Rate-Distortion theory, the classic Blahut-Arimoto algorithm, and the Information Bottleneck method to develop an algorithm for computing state abstractions that approximate the optimal tradeoff between compression and performance. We illustrate the power of this algorithmic structure to offer insights into effective abstraction, compression, and reinforcement learning through a mixture of analysis, visuals, and experimentation.

PDF Details

AAAI Conference 2019 Conference Paper

Theory of Minds: Understanding Behavior in Groups through Inverse Planning

  • Michael Shum
  • Max Kleiman-Weiner
  • Michael L. Littman
  • Joshua B. Tenenbaum

Human social behavior is structured by relationships. We form teams, groups, tribes, and alliances at all scales of human life. These structures guide multi-agent cooperation and competition, but when we observe others these underlying relationships are typically unobservable and hence must be inferred. Humans make these inferences intuitively and flexibly, often making rapid generalizations about the latent relationships that underlie behavior from just sparse and noisy observations. Rapid and accurate inferences are important for determining who to cooperate with, who to compete with, and how to cooperate in order to compete. Towards the goal of building machine-learning algorithms with human-like social intelligence, we develop a generative model of multiagent action understanding based on a novel representation for these latent relationships called Composable Team Hierarchies (CTH). This representation is grounded in the formalism of stochastic games and multi-agent reinforcement learning. We use CTH as a target for Bayesian inference yielding a new algorithm for understanding behavior in groups that can both infer hidden relationships as well as predict future actions for multiple agents interacting together. Our algorithm rapidly recovers an underlying causal model of how agents relate in spatial stochastic games from just a few observations. The patterns of inference made by this algorithm closely correspond with human judgments and the algorithm makes the same rapid generalizations that people do.

PDF Details

RLDM Conference 2019 Conference Abstract

Value Preserving State-Action Abstractions

  • David Abel
  • Nate Umbanhowar
  • Dilip Arumugam
  • Doina Precup
  • Michael L. Littman

We here introduce combinations of state abstractions and options that preserve representation of near-optimal policies. We define φ-relative options, a general formalism for analyzing the value loss of options paired with a state abstraction, and prove that there exist classes of φ-relative options that preserve near-optimal behavior in any MDP.

PDF Details

ICML Conference 2018 Conference Paper

Lipschitz Continuity in Model-based Reinforcement Learning

  • Kavosh Asadi
  • Dipendra Misra
  • Michael L. Littman

We examine the impact of learning Lipschitz continuous models in the context of model-based reinforcement learning. We provide a novel bound on multi-step prediction error of Lipschitz models where we quantify the error using the Wasserstein metric. We go on to prove an error bound for the value-function estimate arising from Lipschitz models and show that the estimated value function is itself Lipschitz. We conclude with empirical results that show the benefits of controlling the Lipschitz constant of neural-network models.

Details

ICML Conference 2018 Conference Paper

Policy and Value Transfer in Lifelong Reinforcement Learning

  • David Abel
  • Yuu Jinnai
  • Yue Guo 0003
  • George Konidaris 0001
  • Michael L. Littman

We consider the problem of how best to use prior experience to bootstrap lifelong learning, where an agent faces a series of task instances drawn from some task distribution. First, we identify the initial policy that optimizes expected performance over the distribution of tasks for increasingly complex classes of policy and task distributions. We empirically demonstrate the relative performance of each policy class’ optimal element in a variety of simple task distributions. We then consider value-function initialization methods that preserve PAC guarantees while simultaneously minimizing the learning required in two learning algorithms, yielding MaxQInit, a practical new method for value-function-based transfer. We show that MaxQInit performs well in simple lifelong RL experiments.

Details

ICML Conference 2018 Conference Paper

State Abstractions for Lifelong Reinforcement Learning

  • David Abel
  • Dilip Arumugam
  • Lucas Lehnert
  • Michael L. Littman

In lifelong reinforcement learning, agents must effectively transfer knowledge across tasks while simultaneously addressing exploration, credit assignment, and generalization. State abstraction can help overcome these hurdles by compressing the representation used by an agent, thereby reducing the computational and statistical burdens of learning. To this end, we here develop theory to compute and use state abstractions in lifelong reinforcement learning. We introduce two new classes of abstractions: (1) transitive state abstractions, whose optimal form can be computed efficiently, and (2) PAC state abstractions, which are guaranteed to hold with respect to a distribution of tasks. We show that the joint family of transitive PAC abstractions can be acquired efficiently, preserve near optimal-behavior, and experimentally reduce sample complexity in simple domains, thereby yielding a family of desirable abstractions for use in lifelong reinforcement learning. Along with these positive results, we show that there are pathological cases where state abstractions can negatively impact performance.

Details

ICML Conference 2017 Conference Paper

An Alternative Softmax Operator for Reinforcement Learning

  • Kavosh Asadi
  • Michael L. Littman

A softmax operator applied to a set of values acts somewhat like the maximization function and somewhat like an average. In sequential decision making, softmax is often used in settings where it is necessary to maximize utility but also to hedge against problems that arise from putting all of one’s weight behind a single maximum utility decision. The Boltzmann softmax operator is the most commonly used softmax operator in this setting, but we show that this operator is prone to misbehavior. In this work, we study a differentiable softmax operator that, among other properties, is a non-expansion ensuring a convergent behavior in learning and planning. We introduce a variant of SARSA algorithm that, by utilizing the new operator, computes a Boltzmann policy with a state-dependent temperature parameter. We show that the algorithm is convergent and that it performs favorably in practice.

Details

AAMAS Conference 2017 Conference Paper

Curriculum Design for Machine Learners in Sequential Decision Tasks

  • Bei Peng
  • James MacGlashan
  • Robert Loftin
  • Michael L. Littman
  • David L. Roberts
  • Matthew E. Taylor

Existing machine-learning work has shown that algorithms can benefit from curricula—learning first on simple examples before moving to more difficult examples. While most existing work on curriculum learning focuses on developing automatic methods to iteratively select training examples with increasing difficulty tailored to the current ability of the learner, relatively little attention has been paid to the ways in which humans design curricula. We argue that a better understanding of the human-designed curricula could give us insights into the development of new machinelearning algorithms and interfaces that can better accommodate machine- or human-created curricula. Our work addresses this emerging and vital area empirically, taking an important step to characterize the nature of human-designed curricula relative to the space of possible curricula and the performance benefits that may (or may not) occur.

PDF

ICML Conference 2017 Conference Paper

Interactive Learning from Policy-Dependent Human Feedback

  • James MacGlashan
  • Mark K. Ho
  • Robert Tyler Loftin
  • Bei Peng 0001
  • Guan Wang
  • David L. Roberts 0001
  • Matthew E. Taylor
  • Michael L. Littman

This paper investigates the problem of interactively learning behaviors communicated by a human teacher using positive and negative feedback. Much previous work on this problem has made the assumption that people provide feedback for decisions that is dependent on the behavior they are teaching and is independent from the learner’s current policy. We present empirical results that show this assumption to be false—whether human trainers give a positive or negative feedback for a decision is influenced by the learner’s current policy. Based on this insight, we introduce Convergent Actor-Critic by Humans (COACH), an algorithm for learning from policy-dependent feedback that converges to a local optimum. Finally, we demonstrate that COACH can successfully learn multiple behaviors on a physical robot.

Details

ICAPS Conference 2017 Conference Paper

Planning with Abstract Markov Decision Processes

  • Nakul Gopalan
  • Marie desJardins
  • Michael L. Littman
  • James MacGlashan
  • Shawn Squire
  • Stefanie Tellex
  • John Winder
  • Lawson L. S. Wong

Robots acting in human-scale environments must plan under uncertainty in large state–action spaces and face constantly changing reward functions as requirements and goals change. Planning under uncertainty in large state–action spaces requires hierarchical abstraction for efficient computation. We introduce a new hierarchical planning framework called Abstract Markov Decision Processes (AMDPs) that can plan in a fraction of the time needed for complex decision making in ordinary MDPs. AMDPs provide abstract states, actions, and transition dynamics in multiple layers above a base-level “flat” MDP. AMDPs decompose problems into a series of subtasks with both local reward and local transition functions used to create policies for subtasks. The resulting hierarchical planning method is independently optimal at each level of abstraction, and is recursively optimal when the local reward and transition functions are correct. We present empirical results showing significantly improved planning speed, while maintaining solution quality, in the Taxi domain and in a mobile-manipulation robotics problem. Furthermore, our approach allows specification of a decision-making model for a mobile-manipulation problem on a Turtlebot, spanning from low-level control actions operating on continuous variables all the way up through high-level object manipulation tasks.

Details

AAMAS Conference 2016 Conference Paper

A Need for Speed: Adapting Agent Action Speed to Improve Task Learning from Non-Expert Humans

  • Bei Peng
  • James MacGlashan
  • Robert Loftin
  • Michael L. Littman
  • David L. Roberts
  • Matthew E. Taylor

As robots become pervasive in human environments, it is important to enable users to effectively convey new skills without programming. Most existing work on Interactive Reinforcement Learning focuses on interpreting and incorporating non-expert human feedback to speed up learning; we aim to design a better representation of the learning agent that is able to elicit more natural and effective communication between the human trainer and the learner, while treating human feedback as discrete communication that depends probabilistically on the trainer’s target policy. This work entails a user study where participants train a virtual agent to accomplish tasks by giving reward and/or punishment in a variety of simulated environments. We present results from 60 participants to show how a learner can ground natural language commands and adapt its action execution speed to learn more efficiently from human trainers. The agent’s action execution speed can be successfully modulated to encourage more explicit feedback from a human trainer in areas of the state space where there is high uncertainty. Our results show that our novel adaptive speed agent dominates different fixed speed agents on several measures of performance. Additionally, we investigate the impact of instructions on user performance and user preference in training conditions.

PDF

ICML Conference 2016 Conference Paper

Near Optimal Behavior via Approximate State Abstraction

  • David Abel
  • D. Ellis Hershkowitz
  • Michael L. Littman

The combinatorial explosion that plagues planning and reinforcement learning (RL) algorithms can be moderated using state abstraction. Prohibitively large task representations can be condensed such that essential information is preserved, and consequently, solutions are tractably computable. However, exact abstractions, which treat only fully-identical situations as equivalent, fail to present opportunities for abstraction in environments where no two situations are exactly alike. In this work, we investigate approximate state abstractions, which treat nearly-identical situations as equivalent. We present theoretical guarantees of the quality of behaviors derived from four types of approximate abstractions. Additionally, we empirically demonstrate that approximate abstractions lead to reduction in task complexity and bounded loss of optimality of behavior in a variety of environments.

Details

IJCAI Conference 2015 Conference Paper

Between Imitation and Intention Learning

  • James MacGlashan
  • Michael L. Littman

Research in learning from demonstration can generally be grouped into either imitation learning or intention learning. In imitation learning, the goal is to imitate the observed behavior of an expert and is typically achieved using supervised learning techniques. In intention learning, the goal is to learn the intention that motivated the expert’s behavior and to use a planning algorithm to derive behavior. Imitation learning has the advantage of learning a direct mapping from states to actions, which bears a small computational cost. Intention learning has the advantage of behaving well in novel states, but may bear a large computational cost by relying on planning algorithms in complex tasks. In this work, we introduce receding horizon inverse reinforcement learning, in which the planning horizon induces a continuum between these two learning paradigms. We present empirical results on multiple domains that demonstrate that performing IRL with a small, but non-zero, receding planning horizon greatly decreases the computational cost of planning while maintaining superior generalization performance compared to imitation learning.

PDF Details

ICML Conference 2013 Conference Paper

Coco-Q: Learning in Stochastic Games with Side Payments

  • Eric Sodomka
  • Elizabeth Hilliard
  • Michael L. Littman
  • Amy Greenwald

Coco (""cooperative/competitive"") values are a solution concept for two-player normal-form games with transferable utility, when binding agreements and side payments between players are possible. In this paper, we show that coco values can also be defined for stochastic games and can be learned using a simple variant of Q-learning that is provably convergent. We provide a set of examples showing how the strategies learned by the Coco-Q algorithm relate to those learned by existing multiagent Q-learning algorithms.

Details

ICML Conference 2013 Conference Paper

The Cross-Entropy Method Optimizes for Quantiles

  • Sergiu Goschin
  • Ari Weinstein
  • Michael L. Littman

Cross-entropy optimization (CE) has proven to be a powerful tool for search in control environments. In the basic scheme, a distribution over proposed solutions is repeatedly adapted by evaluating a sample of solutions and refocusing the distribution on a percentage of those with the highest scores. We show that, in the kind of noisy evaluation environments that are common in decision-making domains, this percentage-based refocusing does not optimize the expected utility of solutions, but instead a quantile metric. We provide a variant of CE (Proportional CE) that effectively optimizes the expected value. We show using variants of established noisy environments that Proportional CE can be used in place of CE and can improve solution quality.

Details

ICAPS Conference 2012 Conference Paper

Bandit-Based Planning and Learning in Continuous-Action Markov Decision Processes

  • Ari Weinstein
  • Michael L. Littman

Recent research leverages results from the continuous-armed bandit literature to create a reinforcement-learning algorithm for continuous state and action spaces. Initially proposed in a theoretical setting, we provide the first examination of the empirical properties of the algorithm. Through experimentation, we demonstrate the effectiveness of this planning method when coupled with exploration and model learning and show that, in addition to its formal guarantees, the approach is very competitive with other continuous-action reinforcement learners.

Details

EWRL Workshop 2012 Conference Paper

Planning in Reward-Rich Domains via PAC Bandits

  • Sergiu Goschin
  • Ari Weinstein
  • Michael L. Littman
  • Erick Chastain

In some decision-making environments, successful solutions are common. If the evaluation of candidate solutions is noisy, however, the challenge is knowing when a “good enough” answer has been found. We formalize this problem as an infinite-armed bandit and provide upper and lower bounds on the number of evaluations or “pulls” needed to identify a solution whose evaluation exceeds a given threshold r0. We present several algorithms and use them to identify reliable strategies for solving screens from the video games \emphInfinite Mario and \emphPitfall! We show order of magnitude improvements in sample complexity over a natural approach that pulls each arm until a good estimate of its success probability is known.

Details

EWRL Workshop 2012 Conference Paper

Rollout-based Game-tree Search Outprunes Traditional Alpha-beta

  • Ari Weinstein
  • Michael L. Littman
  • Sergiu Goschin

Recently, rollout-based planning and search methods have emerged as an alternative to traditional tree-search methods. The fundamental operation in rollout-based tree search is the generation of trajectories in the search tree from root to leaf. Game-playing programs based on Monte-Carlo rollouts methods such as “UCT” have proven remarkably effective at using information from trajectories to make state-of-the-art decisions at the root. In this paper, we show that trajectories can be used to prune more aggressively than classical alpha-beta search. We modify a rollout-based method, FSSS, to allow for use in game-tree search and show it outprunes alpha-beta both empirically and formally.

Details

AIJ Journal 2011 Journal Article

Democratic approximation of lexicographic preference models

  • Fusun Yaman
  • Thomas J. Walsh
  • Michael L. Littman
  • Marie desJardins

Lexicographic preference models (LPMs) are an intuitive representation that corresponds to many real-world preferences exhibited by human decision makers. Previous algorithms for learning LPMs produce a “best guess” LPM that is consistent with the observations. Our approach is more democratic: we do not commit to a single LPM. Instead, we approximate the target using the votes of a collection of consistent LPMs. We present two variations of this method—variable voting and model voting—and empirically show that these democratic algorithms outperform the existing methods. Versions of these democratic algorithms are presented in both the case where the preferred values of attributes are known and the case where they are unknown. We also introduce an intuitive yet powerful form of background knowledge to prune some of the possible LPMs. We demonstrate how this background knowledge can be incorporated into variable and model voting and show that doing so improves performance significantly, especially when the number of observations is small.

Details DOI

UAI Conference 2011 Conference Paper

Learning is planning: near Bayes-optimal reinforcement learning via Monte-Carlo tree search

  • John Asmuth
  • Michael L. Littman

Bayes-optimal behavior, while well-defined, is often difficult to achieve. Recent advances in the use of Monte-Carlo tree search (MCTS) have shown that it is possible to act near-optimally in Markov Decision Processes (MDPs) with very large or infinite state spaces. Bayes-optimal behavior in an unknown MDP is equivalent to optimal behavior in the known belief-space MDP, although the size of this belief-space MDP grows exponentially with the amount of history retained, and is potentially infinite. We show how an agent can use one particular MCTS algorithm, Forward Search Sparse Sampling (FSSS), in an efficient way to act nearly Bayes-optimally for all but a polynomial number of steps, assuming that FSSS can be used to act efficiently in any possible underlying MDP.

Details

ICAPS Conference 2011 Conference Paper

Sample-Based Planning for Continuous Action Markov Decision Processes

  • Christopher R. Mansley
  • Ari Weinstein
  • Michael L. Littman

In this paper, we present a new algorithm that integrates recent advances in solving continuous bandit problems with sample-based rollout methods for planning in Markov Decision Processes (MDPs). Our algorithm, Hierarchical Optimistic Optimization applied to Trees (HOOT) addresses planning in continuous-action MDPs. Empirical results are given that show that the performance of our algorithm meets or exceeds that of a similar discrete action planner by eliminating the problem of manual discretization of the action space.

Details

UAI Conference 2009 Conference Paper

A Bayesian Sampling Approach to Exploration in Reinforcement Learning

  • John Asmuth
  • Lihong Li 0001
  • Michael L. Littman
  • Ali Nouri
  • David Wingate

We present a modular approach to reinforcement learning that uses a Bayesian representation of the uncertainty over models. The approach, BOSS (Best of Sampled Set), drives exploration by sampling multiple models from the posterior and selecting actions optimistically. It extends previous work by providing a rule for deciding when to resample and how to combine the models. We show that our algorithm achieves nearoptimal reward with high probability with a sample complexity that is low relative to the speed at which the posterior distribution converges during learning. We demonstrate that BOSS performs quite favorably compared to state-of-the-art reinforcement-learning approaches and illustrate its flexibility by pairing it with a non-parametric model that generalizes across states.

Details

UAI Conference 2009 Conference Paper

Exploring compact reinforcement-learning representations with linear regression

  • Thomas J. Walsh 0001
  • Istvan Szita
  • Carlos Diuk
  • Michael L. Littman

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.

Details

AAMAS Conference 2009 Conference Paper

Online Exploration in Least-Squares Policy Iteration

  • Lihong Li
  • Michael L. Littman
  • Christopher R. Mansley

One of the key problems in reinforcement learning is balancing exploration and exploitation. Another is learning and acting in large or even continuous Markov decision processes (MDPs), where compact function approximation has to be used. In this paper, we provide a practical solution to exploring large MDPs by integrating a powerful exploration technique, Rmax, into a state-of-the-art learning algorithm, least-squares policy iteration (LSPI). This approach combines the strengths of both methods, and has shown its effectiveness and superiority over LSPI with two other popular exploration rules in several benchmark problems.

PDF

JMLR Journal 2009 Journal Article

Provably Efficient Learning with Typed Parametric Models

  • Emma Brunskill
  • Bethany R. Leffler
  • Lihong Li
  • Michael L. Littman
  • Nicholas Roy

To quickly achieve good performance, reinforcement-learning algorithms for acting in large continuous-valued domains must use a representation that is both sufficiently powerful to capture important domain characteristics, and yet simultaneously allows generalization, or sharing, among experiences. Our algorithm balances this tradeoff by using a stochastic, switching, parametric dynamics representation. We argue that this model characterizes a number of significant, real-world domains, such as robot navigati on across varying terrain. We prove that this representational assumption allows our algorithm to be probably approximately correct with a sample complexity that scales polynomially with all problem-specific quantities including the state-space dimension. We also explicitly incorporate the error introduced by approximate planning in our sample complexity bounds, in contrast to prior Probably Approximately Correct (PAC) Markov Decision Processes (MDP) approaches, which typically assume the estimated MDP can be solved exactly. Our experimental results on constructing plans for driving to work using real car trajectory data, as well as a small robot experiment on navigating varying terrain, demonstrate that our dynamics representation enables us to capture real-world dynamics in a sufficient manner to produce good performance. [abs] [ pdf ][ bib ] &copy JMLR 2009. ( edit, beta )

PDF Details

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 )

PDF Details

UAI Conference 2008 Conference Paper

A Polynomial-time Nash Equilibrium Algorithm for Repeated Stochastic Games

  • Enrique Munoz de Cote
  • Michael L. Littman

We present a polynomial-time algorithm that always finds an (approximate) Nash equilibrium for repeated two-player stochastic games. The algorithm exploits the folk theorem to derive a strategy profile that forms an equilibrium by buttressing mutually beneficial behavior with threats, where possible. One component of our algorithm efficiently searches for an approximation of the egalitarian point, the fairest pareto-efficient solution. The paper concludes by applying the algorithm to a set of grid games to illustrate typical solutions the algorithm finds. These solutions compare very favorably to those found by competing algorithms, resulting in strategies with higher social welfare, as well as guaranteed computational efficiency.

Details

ICML Conference 2008 Conference Paper

An object-oriented representation for efficient reinforcement learning

  • Carlos Diuk
  • Andre Cohen
  • Michael L. Littman

Rich representations in reinforcement learning have been studied for the purpose of enabling generalization and making learning feasible in large state spaces. We introduce Object-Oriented MDPs (OO-MDPs), a representation based on objects and their interactions, which is a natural way of modeling environments and offers important generalization opportunities. We introduce a learning algorithm for deterministic OO-MDPs and prove a polynomial bound on its sample complexity. We illustrate the performance gains of our representation and algorithm in the well-known Taxi domain, plus a real-life videogame.

Details

UAI Conference 2008 Conference Paper

CORL: A Continuous-state Offset-dynamics Reinforcement Learner

  • Emma Brunskill
  • Bethany R. Leffler
  • Lihong Li 0001
  • Michael L. Littman
  • Nicholas Roy

Continuous state spaces and stochastic, switching dynamics characterize a number of rich, realworld domains, such as robot navigation across varying terrain. We describe a reinforcementlearning algorithm for learning in these domains and prove for certain environments the algorithm is probably approximately correct with a sample complexity that scales polynomially with the state-space dimension. Unfortunately, no optimal planning techniques exist in general for such problems; instead we use fitted value iteration to solve the learned MDP, and include the error due to approximate planning in our bounds. Finally, we report an experiment using a robotic car driving over varying terrain to demonstrate that these dynamics representations adequately capture real-world dynamics and that our algorithm can be used to efficiently solve such problems.

Details

JAAMAS Journal 2008 Journal Article

Learning and planning in environments with delayed feedback

  • Thomas J. Walsh
  • Ali Nouri
  • Michael L. Littman

Abstract This work considers the problems of learning and planning in Markovian environments with constant observation and reward delays. We provide a hardness result for the general planning problem and positive results for several special cases with deterministic or otherwise constrained dynamics. We present an algorithm, Model Based Simulation, for planning in such environments and use model-based reinforcement learning to extend this approach to the learning setting in both finite and continuous environments. Empirical comparisons show this algorithm holds significant advantages over others for decision making in delayed-observation environments.

Details DOI

AIJ Journal 2007 Journal Article

A hierarchy of prescriptive goals for multiagent learning

  • Martin Zinkevich
  • Amy Greenwald
  • Michael L. Littman

A great deal of theoretical effort in multiagent learning involves either embracing or avoiding the inherent symmetry between the problem and the solution. Regret minimization is an approach to the prescriptive, non-cooperative goal that explicitly breaks this symmetry, but, since it makes no assumptions about the adversary, it achieves only limited guarantees. In this paper, we consider a hierarchy of goals that begins with the basics of regret minimization and moves towards the utility guarantees achievable by agents that could also guarantee converging to a game-theoretic equilibrium.

Details DOI

ICML Conference 2007 Conference Paper

Analyzing feature generation for value-function approximation

  • Ronald Parr
  • Christopher Painter-Wakefield
  • Lihong Li 0001
  • Michael L. Littman

We analyze a simple, Bellman-error-based approach to generating basis functions for value-function approximation. We show that it generates orthogonal basis functions that provably tighten approximation error bounds. We also illustrate the use of this approach in the presence of noise on some sample problems.

Details

UAI Conference 2006 Conference Paper

An Efficient Optimal-Equilibrium Algorithm for Two-player Game Trees

  • Michael L. Littman
  • Nishkam Ravi
  • Arjun Talwar
  • Martin Zinkevich

Two-player complete-information game trees are perhaps the simplest possible setting for studying general-sum games and the computational problem of finding equilibria. These games admit a simple bottom-up algorithm for finding subgame perfect Nash equilibria efficiently. However, such an algorithm can fail to identify optimal equilibria, such as those that maximize social welfare. The reason is that, counterintuitively, probabilistic action choices are sometimes needed to achieve maximum payoffs. We provide a novel polynomial-time algorithm for this problem that explicitly reasons about stochastic decisions and demonstrate its use in an example card game.

Details

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.

Details

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.

Details

AAAI Conference 2004 Conference Paper

An Instance-Based State Representation for Network Repair

  • Michael L. Littman
  • Eitan Fenson

We describe a formal framework for diagnosis and repair problems that shares elements of the well known partially observable MDP and cost-sensitive classification models. Our cost-sensitive fault remediation model is amenable to implementation as a reinforcementlearning system, and we describe an instance-based state representation that is compatible with learning and planning in this framework. We demonstrate a system that uses these ideas to learn to efficiently restore network connectivity after a failure.

PDF Details

AIJ Journal 2003 Journal Article

Contingent planning under uncertainty via stochastic satisfiability

  • Stephen M. Majercik
  • Michael L. Littman

We describe a new planning technique that efficiently solves probabilistic propositional contingent planning problems by converting them into instances of stochastic satisfiability (SSat) and solving these problems instead. We make fundamental contributions in two areas: the solution of SSat problems and the solution of stochastic planning problems. This is the first work extending the planning-as-satisfiability paradigm to stochastic domains. Our planner, zander, can solve arbitrary, goal-oriented, finite-horizon partially observable Markov decision processes (pomdps). An empirical study comparing zander to seven other leading planners shows that its performance is competitive on a range of problems.

Details DOI

AIJ Journal 2002 Journal Article

A probabilistic approach to solving crossword puzzles

  • Michael L. Littman
  • Greg A. Keim
  • Noam Shazeer

We attacked the problem of solving crossword puzzles by computer: given a set of clues and a crossword grid, try to maximize the number of words correctly filled in. After an analysis of a large collection of puzzles, we decided to use an open architecture in which independent programs specialize in solving specific types of clues, drawing on ideas from information retrieval, database search, and machine learning. Each expert module generates a (possibly empty) candidate list for each clue, and the lists are merged together and placed into the grid by a centralized solver. We used a probabilistic representation as a common interchange language between subsystems and to drive the search for an optimal solution. Proverb, the complete system, averages 95. 3% words correct and 98. 1% letters correct in under 15 minutes per puzzle on a sample of 370 puzzles taken from the New York Times and several other puzzle sources. This corresponds to missing roughly 3 words or 4 letters on a daily 15×15 puzzle, making Proverb a better-than-average cruciverbalist (crossword solver).

Details DOI

UAI Conference 2001 Conference Paper

Graphical Models for Game Theory

  • Michael J. Kearns
  • Michael L. Littman
  • Satinder Singh 0001

In this work, we introduce graphical modelsfor multi-player game theory, and give powerful algorithms for computing their Nash equilibria in certain cases. An n-player game is given by an undirected graph on n nodes and a set of n local matrices. The interpretation is that the payoff to player i is determined entirely by the actions of player i and his neighbors in the graph, and thus the payoff matrix to player i is indexed only by these players. We thus view the global n-player game as being composed of interacting local games, each involving many fewer players. Each player's action may have global impact, but it occurs through the propagation of local influences.Our main technical result is an efficient algorithm for computing Nash equilibria when the underlying graph is a tree (or can be turned into a tree with few node mergings). The algorithm runs in time polynomial in the size of the representation (the graph and theassociated local game matrices), and comes in two related but distinct flavors. The first version involves an approximation step, and computes a representation of all approximate Nash equilibria (of which there may be an exponential number in general). The second version allows the exact computation of Nash equilibria at the expense of weakened complexity bounds. The algorithm requires only local message-passing between nodes (and thus can be implemented by the players themselves in a distributed manner). Despite an analogy to inference in Bayes nets that we develop, the analysis of our algorithm is more involved than that for the polytree algorithm in, owing partially to the fact that we must either compute, or select from, an exponential number of potential solutions. We discuss a number of extensions, such as the computation of equilibria with desirable global properties (e.g. maximizing global return), and directions for further research.

Details

AAAI Conference 1999 Conference Paper

Contingent Planning Under Uncertainty via Stochastic Satisfiability

  • Stephen M. Majercik
  • Michael L. Littman
  • Duke University

Wedescribe two newprobabilistic planning techniques--C-MAXPLAN and ZANDER--that generate contingent plans in probabilistic propositional domains. Both operate by transforming the planning problem into a stochastic satisfiability problem andsolving that problem instead. C-MAXPLAN encodes the problem as an E-MAJSAT instance, while ZANDER encodes the problemas an S-SATinstance. Although S-SATproblems are in a higher complexity class than E-MAJSAT problems, the problem encodings produced by ZANDER are substantially morecompactandappear to be easier to solve than the corresponding E-MAJSAT encodings. Preliminaryresults for ZANDER indicate that it is competitive with existing plannerson a variety of problems.

PDF Details

AAAI Conference 1999 Conference Paper

Initial Experiments in Stochastic Satisfiability

  • Michael L. Littman
  • Duke University

This paper looks at the rich intersection between satisfiability problems and probabilistic models, openingthe door for the use of satisfiability approaches in probabilistic domains. A generic stochastic satisfiability problemis examined, whichcan function for probabilistic domains as SAT does for deterministic domains. Thepaper defines a Davis-Putnam-Logemann-Loveland-style procedurefor solving stochastic satisfiability problems, and reports on a preliminary empirical exploration of the complexity of the algorithm for a collection of randomlygenerated probabilistic problems. Theresults exhibit the familiar easyhardest-hard pattern for the difficulty of random SAT formulae. Special cases of the stochastic satisfiability problem lie in different complexity classes, and onecounterintuitive result is that the computational complexity and the empirical complexity of the problems examineddo not track each other exactly--problems in the hardest complexityclass are not the hardest to solve.

PDF Details

AAAI Conference 1999 Conference Paper

Proverb: The Probabilistic Cruciverbalist

  • Greg A. Keim
  • Noam M. Shazeer
  • Michael L. Littman
  • Sushant Agarwal
  • Catherine M. Cheves
  • Joseph Fitzgerald
  • Jason Grosland
  • Fan Jiang

Weattacked the problemof solving crosswordpuzzles by computer: given a set of clues and a crossword grid, try to maximizethe numberof wordscorrectly filled in. In our system, "expert modules"specialize in solving specific types of clues, drawingon ideas from information retrieval, database search, and machine learning. Eachexpert modulegenerates a (possibly empty)candidate list for each clue, andthe lists are mergedtogether andplaced into the grid by a centralized solver. Weused a probabilistic representation throughout the system as a common interchange language betweensubsystemsand to drive the search for an optimal solution. PROVERB, the complete system, averages 95. 3%wordscorrect and 98. 1%letters correct in under 15 minutesper puzzle on a sampleof 370 puzzles taken from the New YorkTimesand several other puzzle sources. This corresponds to missing roughly 3 wordsor 4 letters on a daily 15 x 15 puzzle, making PROVERB a better-than-average cruciverbalist (crosswordsolver),

PDF Details

AAAI Conference 1999 Conference Paper

Solving Crossword Puzzles as Probabilistic Constraint Satisfaction

  • Noam M. Shazeer
  • Michael L. Littman
  • Greg A. Keim
  • Duke University

Crossword puzzle solving is a classic constraint satisfaction problem, but, whensolving a real puzzle, the mapping fromclues to variable domainsis not perfectly crisp. At best, clues inducea probability distribution over viable targets, whichmust somehow be respected along with the constraints of the puzzle. Motivated by this type of problem, wedescribe a formal model of constraint satisfaction with probabilistic preferences on variable values. Twonatural optimization problems are defined for this model: maximizingthe probability of a correct solution, and maximizingthe number of correct words(variable values) in the solution. the latter, weapplyan efficient iterative approximation equivalent to turbo decodingandpresent results on a collection of real andartificial crossword puzzles.

PDF Details

AAAI Conference 1999 Conference Paper

Solving Crosswords with Proverb

  • Michael L. Littman
  • Greg A. Keim
  • Noam M. Shazeer
  • Duke University

We attacked the problem of solving crossword puzzles by computer: Given a set of clues and a crossword grid, try to maximize the number of words correctly filled in. Proverb , the probabilistic cruciverbalist, separates the problem into two, more familiar subproblems: candidate generation and grid filling. In candidate generation, each clue is treated as a type of query to an information retrieval system, and relevant words of the correct length are returned along with confidence scores. In grid filling, the candidate words are fit into the puzzle grid to maximize an overall confidence score using a combination of ideas from belief network inference and constraint satisfaction. For our demonstration, we will have an interactive version of the candidate-generation process available via the web, and will also give people an opportunity to go head-to- head against Proverb in solving complete puzzles.

PDF Details

ICAPS Conference 1998 Conference Paper

MAXPLAN: A New Approach to Probabilistic Planning

  • Stephen M. Majercik
  • Michael L. Littman

Classical artificial intelligence planningtechniquescan operate in large domains but traditionally assume a deterministic universe. Operations research planning techniques can operate in probabilistic domains but breakwhenthedomains approach realistic sizes. MAXPLANis a newprobabilistic planning technique that aimsat combining thebestofthesetwo~rlds. MAXPLANconverts a planning instance intoan E-MAJSAT instance, andthendrawson techniques fromBoolean satisfiability anddynamic programming to solvethe E-MAJSA’r instance. E-MAJSAT is an NPPP-complete problem thatisessentially a probabilistic version of SAT. MAXPLAN performs as muchas an orderof magnitude better onsomestandard stochastic testproblemsthanBURIDAN--a state-of-the-art probabilistic planner--and scales better on onetestproblem than twoalgorithms basedon dynamic programming.

Details

AIJ Journal 1998 Journal Article

Planning and acting in partially observable stochastic domains

  • Leslie Pack Kaelbling
  • Michael L. Littman
  • Anthony R. Cassandra

In this paper, we bring techniques from operations research to bear on the problem of choosing optimal actions in partially observable stochastic domains. We begin by introducing the theory of Markov decision processes (mdps) and partially observable MDPs (pomdps). We then outline a novel algorithm for solving pomdps off line and show how, in some cases, a finite-memory controller can be extracted from the solution to a POMDP. We conclude with a discussion of how our approach relates to previous work, the complexity of finding exact solutions to pomdps, and of some possibilities for finding approximate solutions.

Details DOI

AAAI Conference 1997 Conference Paper

Probabilistic Propositional Planning: Representations and Complexity

  • Michael L. Littman

Many representations for probabilistic propositional planning problems have been studied. This paper reviews several such representations and shows that, in spite of superficial differences between the representations, they are “expressively equivalent, ” meaning that planning problems specified in one representation can be converted to equivalent planning problems in any of the other representations with at most a polynomial factor increase in the size of the resulting representation and the number of steps needed to reach the goal with sufficient probability. The paper proves that the computational complexity of determining whether a successful plan exists for planning problems expressed in any of these representations is EXPTIME-complete and PSPACE-complete when plans are restricted to take a polynomial number of steps.

PDF Details

UAI Conference 1997 Conference Paper

The Complexity of Plan Existence and Evaluation in Probabilistic Domains

  • Judy Goldsmith
  • Michael L. Littman
  • Martin Mundhenk

We examine the computational complexity of testing and finding small plans in probabilistic planning domains with succinct representations. We find that many problems of interest are complete for a variety of complexity classes: NP, co-NP, PP, NP^PP, co-NP^PP, and PSPACE. Of these, the probabilistic classes PP and NP^PP are likely to be of special interest in the field of uncertainty in artificial intelligence and are deserving of additional study. These results suggest a fruitful direction of future algorithmic development.

Details

UAI Conference 1995 Conference Paper

On the Complexity of Solving Markov Decision Problems

  • Michael L. Littman
  • Thomas L. Dean
  • Leslie Pack Kaelbling

Markov decision problems (MDPs) provide the foundations for a number of problems of interest to AI researchers studying automated planning and reinforcement learning. In this paper, we summarize results regarding the complexity of solving MDPs and the running time of MDP solution algorithms. We argue that, although MDPs can be solved efficiently in theory, more study is needed to reveal practical algorithms for solving large problems quickly. To encourage future research, we sketch some alternative methods of analysis that rely on the structure of MDPs.

Details
v2026.09.13