Ronald Parr

NeurIPS Conference 2025 Conference Paper

A Unifying View of Linear Function Approximation in Off-Policy RL Through Matrix Splitting and Preconditioning

• Zechen Wu
• Amy Greenwald
• Ronald Parr

In off-policy policy evaluation (OPE) tasks within reinforcement learning, Temporal Difference Learning(TD) and Fitted Q-Iteration (FQI) have traditionally been viewed as differing in the number of updates toward the target value function: TD makes one update, FQI makes an infinite number, and Partial Fitted Q-Iteration (PFQI) performs a finite number. We show that this view is not accurate, and provide a new mathematical perspective under linear value function approximation that unifies these methods as a single iterative method solving same linear system, but using different matrix splitting schemes and preconditioners. We show that increasing the number of updates under the same target value function, i. e. , the target network technique, is a transition from using a constant preconditioner to using a data-feature adaptive preconditioner. This elucidates, for the first time, why TD convergence does not necessarily imply FQI convergence, and establishes tight convergence connections among TD, PFQI, and FQI. Our framework enables sharper theoretical results than previous work and characterization of the convergence conditions for each algorithm, without relying on assumptions about the features (e. g. , linear independence). We also provide an encoder-decoder perspective to better understand TD’s convergence conditions, and prove, for the first time, that when a large learning rate doesn’t work, trying a smaller one may help(for batch TD). Our framework also leads to the discovery of new crucial conditions on features for convergence, and shows how common assumptions about features influence convergence, e. g. , the assumption of linearly independent features can be dropped without compromising the convergence guarantees of stochastic TD in the on-policy setting. This paper is also the first to introduce matrix splitting into the convergence analysis of these algorithms.

RLC Conference 2024 Conference Paper

An Optimal Tightness Bound for the Simulation Lemma

• Sam Lobel
• Ronald Parr

We present a bound for value-prediction error with respect to model misspecification that is tight, including constant factors. This is a direct improvement of the ``simulation lemma, ’’ a foundational result in reinforcement learning. We demonstrate that existing bounds are quite loose, becoming vacuous for large discount factors, due to the suboptimal treatment of compounding probability errors. By carefully considering this quantity on its own, instead of as a subcomponent of value error, we derive a bound that is sub-linear with respect to transition function misspecification. We then demonstrate broader applicability of this technique, improving a similar bound in the related subfield of hierarchical abstraction.

RLJ Journal 2024 Journal Article

An Optimal Tightness Bound for the Simulation Lemma

• Sam Lobel
• Ronald Parr

We present a bound for value-prediction error with respect to model misspecification that is tight, including constant factors. This is a direct improvement of the ``simulation lemma,’’ a foundational result in reinforcement learning. We demonstrate that existing bounds are quite loose, becoming vacuous for large discount factors, due to the suboptimal treatment of compounding probability errors. By carefully considering this quantity on its own, instead of as a subcomponent of value error, we derive a bound that is sub-linear with respect to transition function misspecification. We then demonstrate broader applicability of this technique, improving a similar bound in the related subfield of hierarchical abstraction.

NeurIPS Conference 2024 Conference Paper

Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy

• Cameron Allen
• Aaron Kirtland
• Ruo Yu Tao
• Sam Lobel
• Daniel Scott
• Nicholas Petrocelli
• Omer Gottesman
• Ronald Parr

Reinforcement learning algorithms typically rely on the assumption that the environment dynamics and value function can be expressed in terms of a Markovian state representation. However, when state information is only partially observable, how can an agent learn such a state representation, and how can it detect when it has found one? We introduce a metric that can accomplish both objectives, without requiring access to---or knowledge of---an underlying, unobservable state space. Our metric, the λ-discrepancy, is the difference between two distinct temporal difference (TD) value estimates, each computed using TD(λ) with a different value of λ. Since TD(λ=0) makes an implicit Markov assumption and TD(λ=1) does not, a discrepancy between these estimates is a potential indicator of a non-Markovian state representation. Indeed, we prove that the λ-discrepancy is exactly zero for all Markov decision processes and almost always non-zero for a broad class of partially observable environments. We also demonstrate empirically that, once detected, minimizing the λ-discrepancy can help with learning a memory function to mitigate the corresponding partial observability. We then train a reinforcement learning agent that simultaneously constructs two recurrent value networks with different λ parameters and minimizes the difference between them as an auxiliary loss. The approach scales to challenging partially observable domains, where the resulting agent frequently performs significantly better (and never performs worse) than a baseline recurrent agent with only a single value network.

ICML Conference 2024 Conference Paper

Position: Amazing Things Come From Having Many Good Models

• Cynthia Rudin
• Chudi Zhong
• Lesia Semenova
• Margo I. Seltzer
• Ronald Parr
• Jiachang Liu 0001
• Srikar Katta
• Jon Donnelly

The Rashomon Effect, coined by Leo Breiman, describes the phenomenon that there exist many equally good predictive models for the same dataset. This phenomenon happens for many real datasets and when it does, it sparks both magic and consternation, but mostly magic. In light of the Rashomon Effect, this perspective piece proposes reshaping the way we think about machine learning, particularly for tabular data problems in the nondeterministic (noisy) setting. We address how the Rashomon Effect impacts (1) the existence of simple-yet-accurate models, (2) flexibility to address user preferences, such as fairness and monotonicity, without losing performance, (3) uncertainty in predictions, fairness, and explanations, (4) reliable variable importance, (5) algorithm choice, specifically, providing advanced knowledge of which algorithms might be suitable for a given problem, and (6) public policy. We also discuss a theory of when the Rashomon Effect occurs and why. Our goal is to illustrate how the Rashomon Effect can have a massive impact on the use of machine learning for complex problems in society.

NeurIPS Conference 2024 Conference Paper

Using Noise to Infer Aspects of Simplicity Without Learning

• Zachery Boner
• HARRY CHEN
• Lesia Semenova
• Ronald Parr
• Cynthia Rudin

Noise in data significantly influences decision-making in the data science process. In fact, it has been shown that noise in data generation processes leads practitioners to find simpler models. However, an open question still remains: what is the degree of model simplification we can expect under different noise levels? In this work, we address this question by investigating the relationship between the amount of noise and model simplicity across various hypothesis spaces, focusing on decision trees and linear models. We formally show that noise acts as an implicit regularizer for several different noise models. Furthermore, we prove that Rashomon sets (sets of near-optimal models) constructed with noisy data tend to contain simpler models than corresponding Rashomon sets with non-noisy data. Additionally, we show that noise expands the set of ``good'' features and consequently enlarges the set of models that use at least one good feature. Our work offers theoretical guarantees and practical insights for practitioners and policymakers on whether simple-yet-accurate machine learning models are likely to exist, based on knowledge of noise levels in the data generation process.

NeurIPS Conference 2023 Conference Paper

A Path to Simpler Models Starts With Noise

• Lesia Semenova
• HARRY CHEN
• Ronald Parr
• Cynthia Rudin

The Rashomon set is the set of models that perform approximately equally well on a given dataset, and the Rashomon ratio is the fraction of all models in a given hypothesis space that are in the Rashomon set. Rashomon ratios are often large for tabular datasets in criminal justice, healthcare, lending, education, and in other areas, which has practical implications about whether simpler models can attain the same level of accuracy as more complex models. An open question is why Rashomon ratios often tend to be large. In this work, we propose and study a mechanism of the data generation process, coupled with choices usually made by the analyst during the learning process, that determines the size of the Rashomon ratio. Specifically, we demonstrate that noisier datasets lead to larger Rashomon ratios through the way that practitioners train models. Additionally, we introduce a measure called pattern diversity, which captures the average difference in predictions between distinct classification patterns in the Rashomon set, and motivate why it tends to increase with label noise. Our results explain a key aspect of why simpler models often tend to perform as well as black box models on complex, noisier datasets.

ICML Conference 2019 Conference Paper

Revisiting the Softmax Bellman Operator: New Benefits and New Perspective

• Zhao Song 0001
• Ronald Parr
• Lawrence Carin

The impact of softmax on the value function itself in reinforcement learning (RL) is often viewed as problematic because it leads to sub-optimal value (or Q) functions and interferes with the contraction properties of the Bellman operator. Surprisingly, despite these concerns, and independent of its effect on exploration, the softmax Bellman operator when combined with Deep Q-learning, leads to Q-functions with superior policies in practice, even outperforming its double Q-learning counterpart. To better understand how and why this occurs, we revisit theoretical properties of the softmax Bellman operator, and prove that (i) it converges to the standard Bellman operator exponentially fast in the inverse temperature parameter, and (ii) the distance of its Q function from the optimal one can be bounded. These alone do not explain its superior performance, so we also show that the softmax operator can reduce the overestimation error, which may give some insight into why a sub-optimal operator leads to better performance in the presence of value function approximation. A comparison among different Bellman operators is then presented, showing the trade-offs when selecting them.

AAAI Conference 2016 Conference Paper

Distance Minimization for Reward Learning from Scored Trajectories

• Benjamin Burchfiel
• Carlo Tomasi
• Ronald Parr

Many planning methods rely on the use of an immediate reward function as a portable and succinct representation of desired behavior. Rewards are often inferred from demonstrated behavior that is assumed to be near-optimal. We examine a framework, Distance Minimization IRL (DM-IRL), for learning reward functions from scores an expert assigns to possibly suboptimal demonstrations. By changing the expert’s role from a demonstrator to a judge, DM-IRL relaxes some of the assumptions present in IRL, enabling learning from the scoring of arbitrary demonstration trajectories with unknown transition functions. DM-IRL complements existing IRL approaches by addressing different assumptions about the expert. We show that DM-IRL is robust to expert scoring error and prove that finding a policy that produces maximally informative trajectories for an expert to score is strongly NP-hard. Experimentally, we demonstrate that the reward function DM-IRL learns from an MDP with an unknown transition model can transfer to an agent with known characteristics in a novel environment, and we achieve successful learning with limited available training data.

AAAI Conference 2016 Conference Paper

Efficient PAC-Optimal Exploration in Concurrent, Continuous State MDPs with Delayed Updates

• Jason Pazis
• Ronald Parr

We present a new, efficient PAC optimal exploration algorithm that is able to explore in multiple, continuous or discrete state MDPs simultaneously. Our algorithm does not assume that value function updates can be completed instantaneously, and maintains PAC guarantees in realtime environments. Not only do we extend the applicability of PAC optimal exploration algorithms to new, realistic settings, but even when instant value function updates are possible, our bounds present a significant improvement over previous single MDP exploration bounds, and a drastic improvement over previous concurrent PAC bounds. We also present TCE, a new, fine grained metric for the cost of exploration.

NeurIPS Conference 2016 Conference Paper

Improving PAC Exploration Using the Median Of Means

• Jason Pazis
• Ronald Parr
• Jonathan How

We present the first application of the median of means in a PAC exploration algorithm for MDPs. Using the median of means allows us to significantly reduce the dependence of our bounds on the range of values that the value function can take, while introducing a dependence on the (potentially much smaller) variance of the Bellman operator. Additionally, our algorithm is the first algorithm with PAC bounds that can be applied to MDPs with unbounded rewards.

NeurIPS Conference 2016 Conference Paper

Linear Feature Encoding for Reinforcement Learning

• Zhao Song
• Ronald Parr
• Xuejun Liao
• Lawrence Carin

Feature construction is of vital importance in reinforcement learning, as the quality of a value function or policy is largely determined by the corresponding features. The recent successes of deep reinforcement learning (RL) only increase the importance of understanding feature construction. Typical deep RL approaches use a linear output layer, which means that deep RL can be interpreted as a feature construction/encoding network followed by linear value function approximation. This paper develops and evaluates a theory of linear feature encoding. We extend theoretical results on feature quality for linear value function approximation from the uncontrolled case to the controlled case. We then develop a supervised linear feature encoding method that is motivated by insights from linear value function approximation theory, as well as empirical successes from deep RL. The resulting encoder is a surprisingly effective method for linear value function approximation using raw images as inputs.

ICRA Conference 2014 Conference Paper

Unsupervised discovery of object classes with a mobile robot

• Julian Mason
• Bhaskara Marthi
• Ronald Parr

Object detection and recognition are fundamental capabilities for a mobile robot. Objects are a powerful representation for a variety of tasks including mobile manipulation and inventory tracking. As a result, object-based world representations have seen a great deal of research interest in the last several years. However, these systems usually assume that object recognition is well-solved: they require that accurate recognition be available for every object they might encounter. Despite steady advances, object recognition remains a difficult, open problem. Existing object recognition algorithms rely on high-resolution three-dimensional object models or on extensive hand-labeled training data. The sheer variety of objects that occur in natural environments makes manually training a recognizer for every possible object infeasible. In this work, we present a robotic system for unsupervised object and class discovery, in which objects are first discovered, and then grouped into classes in an unsupervised fashion. At each step, we approach the problem as one of robotics, not disembodied computer vision. On a very large robotic dataset, we discover object classes with 98. 7% precision while achieving 71. 8% recall. The scale and quality of these results demonstrate the merit of our approach, and prove the practicality of long-term large-scale object discovery. To our knowledge, no other authors have investigated robotic object discovery at this scale, making direct quantitative comparison impossible. We make our implementation and ground-truth labelings available, and evaluate our technique on a very large dataset. As a result, this work is a baseline against which future work can be compared.

AAAI Conference 2013 Conference Paper

PAC Optimal Exploration in Continuous Space Markov Decision Processes

• Jason Pazis
• Ronald Parr

Current exploration algorithms can be classified in two broad categories: Heuristic, and PAC optimal. While numerous researchers have used heuristic approaches such as -greedy exploration successfully, such approaches lack formal, finite sample guarantees and may need a significant amount of finetuning to produce good results. PAC optimal exploration algorithms, on the other hand, offer strong theoretical guarantees but are inapplicable in domains of realistic size. The goal of this paper is to bridge the gap between theory and practice, by introducing C-PACE, an algorithm which offers strong theoretical guarantees and can be applied to interesting, continuous space problems.

AAAI Conference 2013 Conference Paper

Sample Complexity and Performance Bounds for Non-Parametric Approximate Linear Programming

• Jason Pazis
• Ronald Parr

One of the most difficult tasks in value function approximation for Markov Decision Processes is finding an approximation architecture that is expressive enough to capture the important structure in the value function, while at the same time not overfitting the training samples. Recent results in nonparametric approximate linear programming (NP-ALP), have demonstrated that this can be done effectively using nothing more than a smoothness assumption on the value function. In this paper we extend these results to the case where samples come from real world transitions instead of the full Bellman equation, adding robustness to noise. In addition, we provide the first max-norm, finite sample performance guarantees for any form of ALP. NP-ALP is amenable to problems with large (multidimensional) or even infinite (continuous) action spaces, and does not require a model to select actions using the resulting approximate solution.

AAAI Conference 2012 Conference Paper

Computing Optimal Strategies to Commit to in Stochastic Games

• Joshua Letchford
• Liam MacDermed
• Vincent Conitzer
• Ronald Parr
• Charles Isbell

Significant progress has been made recently in the following two lines of research in the intersection of AI and game theory: (1) the computation of optimal strategies to commit to (Stackelberg strategies), and (2) the computation of correlated equilibria of stochastic games. In this paper, we unite these two lines of research by studying the computation of Stackelberg strategies in stochastic games. We provide theoretical results on the value of being able to commit and the value of being able to correlate, as well as complexity results about computing Stackelberg strategies in stochastic games. We then modify the QPACE algorithm (MacDermed et al. 2011) to compute Stackelberg strategies, and provide experimental results.

ICML Conference 2012 Conference Paper

Greedy Algorithms for Sparse Reinforcement Learning

• Christopher Painter-Wakefield
• Ronald Parr

IROS Conference 2012 Conference Paper

Object disappearance for object discovery

• Julian Mason
• Bhaskara Marthi
• Ronald Parr

A useful capability for a mobile robot is the ability to recognize the objects in its environment that move and change (as distinct from background objects, which are largely stationary). This ability can improve the accuracy and reliability of localization and mapping, enhance the ability of the robot to interact with its environment, and facilitate applications such as inventory management and theft detection. Rather than viewing this task as a difficult application of object recognition methods from computer vision, this work is in line with a recent trend in the community towards unsupervised object discovery and tracking that exploits the fundamentally temporal nature of the data acquired by a robot. Unlike earlier approaches, which relied heavily upon computationally intensive techniques from mapping and computer vision, our approach combines visual features and RGB-D data in a simple and effective way to segment objects from robot sensory data. We then use a Dirichlet process to cluster and recognize objects. The performance of our approach is demonstrated in several test domains.

UAI Conference 2012 Conference Paper

Value Function Approximation in Noisy Environments Using Locally Smoothed Regularized Approximate Linear Programs

• Gavin Taylor
• Ronald Parr

Recently, Petrik et al. demonstrated that L1- Regularized Approximate Linear Programming (RALP) could produce value functions and policies which compared favorably to established linear value function approximation techniques like LSPI. RALP’s success primarily stems from the ability to solve the feature selection and value function approximation steps simultaneously. RALP’s performance guarantees become looser if sampled next states are used. For very noisy domains, RALP requires an accurate model rather than samples, which can be unrealistic in some practical scenarios. In this paper, we demonstrate this weakness, and then introduce Locally Smoothed L1-Regularized Approximate Linear Programming (LS-RALP). We demonstrate that LS-RALP mitigates inaccuracies stemming from noise even without an accurate model. We show that, given some smoothness assumptions, as the number of samples increases, error from noise approaches zero, and provide experimental examples of LS-RALP’s success on common reinforcement learning benchmark problems.

ICML Conference 2011 Conference Paper

Generalized Value Functions for Large Action Sets

• Jason Pazis
• Ronald Parr

AAAI Conference 2011 Conference Paper

Non-Parametric Approximate Linear Programming for MDPs

• Jason Pazis
• Ronald Parr

The Approximate Linear Programming (ALP) approach to value function approximation for MDPs is a parametric value function approximation method, in that it represents the value function as a linear combination of features which are chosen a priori. Choosing these features can be a difficult challenge in itself. One recent effort, Regularized Approximate Linear Programming (RALP), uses L1 regularization to address this issue by combining a large initial set of features with a regularization penalty that favors a smooth value function with few non-zero weights. Rather than using smoothness as a backhanded way of addressing the feature selection problem, this paper starts with smoothness and develops a non-parametric approach to ALP that is consistent with the smoothness assumption. We show that this new approach has some favorable practical and analytical properties in comparison to (R)ALP.

IJCAI Conference 2011 Conference Paper

Security Games with Multiple Attacker Resources

• Dmytro Korzhyk
• Vincent Conitzer
• Ronald Parr

Algorithms for finding game-theoretic solutions are now used in several real-world security applications. This work has generally assumed a Stackelberg model where the defender commits to a mixed strategy first. In general two-player normal-form games, Stackelberg strategies are easier to compute than Nash equilibria, though it has recently been shown that in many security games, Stackelberg strategies are also Nash strategies for the defender. However, the work on security games so far assumes that the attacker attacks only a single target. In this paper, we generalize to the case where the attacker attacks multiple targets simultaneously. Here, Stackelberg and Nash strategies for the defender can be truly different. We provide a polynomial-time algorithm for finding a Nash equilibrium. The algorithm gradually increases the number of defender resources and maintains an equilibrium throughout this process. Moreover, we prove that Nash equilibria in security games with multiple attackers satisfy the interchange property, which resolves the problem of equilibrium selection in such games. On the other hand, we show that Stackelberg strategies are actually NP-hard to compute in this context. Finally, we provide experimental results.

AAMAS Conference 2011 Conference Paper

Solving Stackelberg Games with Uncertain Observability

• Dmytro Korzhyk
• Vincent Conitzer
• Ronald Parr

Recent applications of game theory in security domains use algorithms to solve a Stackelberg model, in which one player (the leader) first commits to a mixed strategy and then the other player (the follower) observes that strategy and best-responds to it. However, in real-world applications, it is hard to determine whether the follower is actually able to observe the leader's mixed strategy before acting. In this paper, we model the uncertainty about whether the follower is able to observe the leader's strategy as part of the game (as proposed in the extended version of Yin et al. [17]). We describe an iterative algorithm for solving these games. This algorithm alternates between calling a Nash equilibrium solver and a Stackelberg solver as subroutines. We prove that the algorithm finds a solution in a finite number of steps and show empirically that it runs fast on games of reasonable size. We also discuss other properties of this methodology based on the experiments.

ICRA Conference 2011 Conference Paper

Textured occupancy grids for monocular localization without features

• Julian Mason
• Susanna Ricco
• Ronald Parr

A textured occupancy grid map is an extremely versatile data structure. It can be used to render human readable views and for laser rangefinder localization algorithms. For camera-based localization, landmark or feature based maps tend to be favored in current research. This may be because of a tacit assumption that working with a textured occupancy grid with a camera would be impractical. We demonstrate that a textured occupancy grid can be combined with an extremely simple monocular localization algorithm to produce a viable localization solution. Our approach is simple, efficient, and produces localization results comparable to laser localization results. A consequence of this result is that a single map representation, the textured occupancy grid, can now be used for humans, robots with laser rangefinders, and robots with just a single camera.

AAAI Conference 2010 Conference Paper

Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games

• Dmytro Korzhyk
• Vincent Conitzer
• Ronald Parr

Recently, algorithms for computing game-theoretic solutions have been deployed in real-world security applications, such as the placement of checkpoints and canine units at Los Angeles International Airport. These algorithms assume that the defender (security personnel) can commit to a mixed strategy, a so-called Stackelberg model. As pointed out by Kiekintveld et al. (2009), in these applications, generally, multiple resources need to be assigned to multiple targets, resulting in an exponential number of pure strategies for the defender. In this paper, we study how to compute optimal Stackelberg strategies in such games, showing that this can be done in polynomial time in some cases, and is NP-hard in others.

ICML Conference 2010 Conference Paper

Feature Selection Using Regularization in Approximate Linear Programs for Markov Decision Processes

• Marek Petrik
• Gavin Taylor
• Ronald Parr
• Shlomo Zilberstein

NeurIPS Conference 2010 Conference Paper

Linear Complementarity for Regularized Policy Evaluation and Improvement

• Jeffrey Johns
• Christopher Painter-wakefield
• Ronald Parr

Recent work in reinforcement learning has emphasized the power of L1 regularization to perform feature selection and prevent overfitting. We propose formulating the L1 regularized linear fixed point problem as a linear complementarity problem (LCP). This formulation offers several advantages over the LARS-inspired formulation, LARS-TD. The LCP formulation allows the use of efficient off-the-shelf solvers, leads to a new uniqueness result, and can be initialized with starting points from similar problems (warm starts). We demonstrate that warm starts, as well as the efficiency of LCP solvers, can speed up policy iteration. Moreover, warm starts permit a form of modified policy iteration that can be used to approximate a greedy" homotopy path, a generalization of the LARS-TD homotopy path that combines policy evaluation and optimization. "

IJCAI Conference 2009 Conference Paper

• Erik Halvorson
• Vincent Conitzer
• Ronald Parr

We study a multi-step hider-seeker game where the hider is moving on a graph and, in each step, the seeker is able to search c subsets of the graph nodes. We model this game as a zero-sum Bayesian game, which can be solved in weakly polynomial time in the players’ action spaces. The seeker’s action space is exponential in c, and both players’ action spaces are exponential in the game horizon. To manage this intractability, we use a column/constraint generation approach for both players. This approach requires an oracle to determine best responses for each player. However, we show that computing a best response for the seeker is NPhard, even for a single-step game when c is part of the input, and that computing a best response is NPhard for both players for the multi-step game, even if c = 1. An integer programming formulation of the best response for the hider is practical for moderate horizons, but computing an exact seeker best response is impractical due to the exponential dependence on both c and the horizon. We therefore develop an approximate best response oracle with bounded suboptimality for the seeker. We prove performance bounds on the strategy that results when column/constraint generation with approximate best responses converges, and we measure the performance of our algorithm in simulations. In our experimental results, column/constraint generation converges to near-minimax strategies for both players fairly quickly.

ICML Conference 2009 Conference Paper

Kernelized value function approximation for reinforcement learning

• Gavin Taylor
• Ronald Parr

ICML Conference 2008 Conference Paper

An analysis of linear models, linear value-function approximation, and feature selection for reinforcement learning

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

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.

UAI Conference 2006 Conference Paper

Efficient Selection of Disambiguating Actions for Stereo Vision

• Monika Schaeffer
• Ronald Parr

NeurIPS Conference 2005 Conference Paper

Hierarchical Linear/Constant Time SLAM Using Particle Filters for Dense Maps

• Austin Eliazar
• Ronald Parr

We present an improvement to the DP-SLAM algorithm for simultane- ous localization and mapping (SLAM) that maintains multiple hypothe- ses about densely populated maps (one full map per particle in a par- ticle filter) in time that is linear in all significant algorithm parameters and takes constant (amortized) time per iteration. This means that the asymptotic complexity of the algorithm is no greater than that of a pure localization algorithm using a single map and the same number of parti- cles. We also present a hierarchical extension of DP-SLAM that uses a two level particle filter which models drift in the particle filtering process itself. The hierarchical approach enables recovery from the inevitable drift that results from using a finite number of particles in a particle filter and permits the use of DP-SLAM in more challenging domains, while maintaining linear time asymptotic complexity.

ICRA Conference 2004 Conference Paper

DP-SLAM 2. 0

• Austin I. Eliazar
• Ronald Parr

Probabilistic approaches have proved very successful at addressing the basic problems of robot localization and mapping and they have shown great promise on the combined problem of simultaneous localization and mapping (SLAM). One approach to SLAM assumes relatively sparse, relatively unambiguous landmarks and builds a Kalman filter over landmark positions. Other approaches assume dense sensor data which individually are not very distinctive, such as those available from a laser range finder. In earlier work, we presented an algorithm called DP-SLAM, which provided a very accurate solution to the latter case by efficiently maintaining a joint distribution over robot maps and poses. The approach assumed an extremely accurate laser range finder and a deterministic environment. In this work we demonstrate an improved map representation and laser penetration model, an improvement in the asymptotic efficiency of the algorithm, and empirical results of loop closing on a high resolution map of a very challenging domain.

ICML Conference 2004 Conference Paper

Learning probabilistic motion models for mobile robots

• Austin I. Eliazar
• Ronald Parr

IJCAI Conference 2003 Conference Paper

Approximate Policy Iteration using Large-Margin Classifiers

• Michail G. Lagoudakis
• Ronald Parr

We present an approximate policy iteration algorithm that uses rollouts to estimate the value of each action under a given policy in a subset of states and a classifier to generalize and learn the improved policy over the entire state space. Using a multiclass support vector machine as the classifier, we obtained successful results on the inverted pendulum and the bicycle balancing and riding domains.

IJCAI Conference 2003 Conference Paper

DP-SLAM: Fast, Robust Simultaneous Localization and Mapping Without Predetermined Landmarks

• Austin Eliazar
• Ronald Parr

We present a novel, laser range finder based algorithm for simultaneous localization and mapping (SLAM) for mobile robots. SLAM addresses the problem of constructing an accurate map in real time despite imperfect information about the robot's trajectory through the environment. Unlike other approaches that assume predetermined landmarks (and must deal with a resulting dataassociation problem) our algorithm is purely laser based. Our algorithm uses a particle filter to represent both robot poses and possible map configurations. By using a new map representation, which we call distributed particle (DP) mapping, we are able to maintain and update hundreds of candidate maps and robot poses efficiently. The worst-case complexity of our algorithm per laser sweep is log-quadratic in the number of particles we maintain and linear in the area swept out by the laser. However, in practice our run time is usually much less than that. Our technique contains essentially no assumptions about the environment yet it is accurate enough to close loops of 60m in length with crisp, perpendicular edges on corridors and minimal or no misalignment errors.

JMLR Journal 2003 Journal Article

Least-Squares Policy Iteration

• Michail G. Lagoudakis
• Ronald Parr

We propose a new approach to reinforcement learning for control problems which combines value-function approximation with linear architectures and approximate policy iteration. This new approach is motivated by the least-squares temporal-difference learning algorithm (LSTD) for prediction problems, which is known for its efficient use of sample experiences compared to pure temporal-difference algorithms. Heretofore, LSTD has not had a straightforward application to control problems mainly because LSTD learns the state value function of a fixed policy which cannot be used for action selection and control without a model of the underlying process. Our new algorithm, least-squares policy iteration (LSPI), learns the state-action value function which allows for action selection without a model and for incremental policy improvement within a policy-iteration framework. LSPI is a model-free, off-policy method which can use efficiently (and reuse in each iteration) sample experiences collected in any manner. By separating the sample collection method, the choice of the linear approximation architecture, and the solution method, LSPI allows for focused attention on the distinct elements that contribute to practical reinforcement learning. LSPI is tested on the simple task of balancing an inverted pendulum and the harder task of balancing and riding a bicycle to a target location. In both cases, LSPI learns to control the pendulum or the bicycle by merely observing a relatively small number of trials where actions are selected randomly. LSPI is also compared against Q -learning (both with and without experience replay) using the same value function architecture. While LSPI achieves good performance fairly consistently on the difficult bicycle task, Q -learning variants were rarely able to balance for more than a small fraction of the time needed to reach the target location. [abs] [ pdf ][ ps.gz ][ ps ]

ICML Conference 2003 Conference Paper

Reinforcement Learning as Classification: Leveraging Modern Classifiers

• Michail G. Lagoudakis
• Ronald Parr

ICML Conference 2002 Conference Paper

Coordinated Reinforcement Learning

• Carlos Guestrin
• Michail G. Lagoudakis
• Ronald Parr

NeurIPS Conference 2002 Conference Paper

Learning in Zero-Sum Team Markov Games Using Factored Value Functions

• Michail Lagoudakis
• Ronald Parr

We present a new method for learning good strategies in zero-sum Markov games in which each side is composed of multiple agents col- laborating against an opposing team of agents. Our method requires full observability and communication during learning, but the learned poli- cies can be executed in a distributed manner. The value function is rep- resented as a factored linear architecture and its structure determines the necessary computational resources and communication bandwidth. This approach permits a tradeoff between simple representations with little or no communication between agents and complex, computationally inten- sive representations with extensive coordination between agents. Thus, we provide a principled means of using approximation to combat the exponential blowup in the joint action space of the participants. The ap- proach is demonstrated with an example that shows the efficiency gains over naive enumeration.

UAI Conference 2002 Conference Paper

Value Function Approximation in Zero-Sum Markov Games

• Michail G. Lagoudakis
• Ronald Parr

UAI Conference 2001 Conference Paper

Inference in Hybrid Networks: Theoretical Limits and Practical Algorithms

• Uri Lerner
• Ronald Parr

An important subclass of hybrid Bayesian networks are those that represent Conditional Linear Gaussian (CLG) distributions --- a distribution with a multivariate Gaussian component for each instantiation of the discrete variables. In this paper we explore the problem of inference in CLGs. We show that inference in CLGs can be significantly harder than inference in Bayes Nets. In particular, we prove that even if the CLG is restricted to an extremely simple structure of a polytree in which every continuous node has at most one discrete ancestor, the inference task is NP-hard.To deal with the often prohibitive computational cost of the exact inference algorithm for CLGs, we explore several approximate inference algorithms. These algorithms try to find a small subset of Gaussians which are a good approximation to the full mixture distribution. We consider two Monte Carlo approaches and a novel approach that enumerates mixture components in order of prior probability. We compare these methods on a variety of problems and show that our novel algorithm is very promising for large, hybrid diagnosis problems.

NeurIPS Conference 2001 Conference Paper

Model-Free Least-Squares Policy Iteration

• Michail Lagoudakis
• Ronald Parr

We propose a new approach to reinforcement learning which combines least squares function approximation with policy iteration. Our method is model-free and completely off policy. We are motivated by the least squares temporal difference learning algorithm (LSTD), which is known for its efficient use of sample experiences compared to pure temporal difference algorithms. LSTD is ideal for prediction problems, however it heretofore has not had a straightforward application to control problems. Moreover, approximations learned by LSTD are strongly influenced by the visitation distribution over states. Our new algorithm, Least Squares Policy Iteration (LSPI) addresses these issues. The result is an off-policy method which can use (or reuse) data collected from any source. We have tested LSPI on several problems, including a bicycle simulator in which it learns to guide the bicycle to a goal efficiently by merely observing a relatively small number of completely random trials.

NeurIPS Conference 2001 Conference Paper

Multiagent Planning with Factored MDPs

• Carlos Guestrin
• Daphne Koller
• Ronald Parr

We present a principled and efficient planning algorithm for cooperative multia- gent dynamic systems. A striking feature of our method is that the coordination and communication between the agents is not imposed, but derived directly from the system dynamics and function approximation architecture. We view the en- tire multiagent system as a single, large Markov decision process (MDP), which we assume can be represented in a factored way using a dynamic Bayesian net- work (DBN). The action space of the resulting MDP is the joint action space of the entire set of agents. Our approach is based on the use of factored linear value functions as an approximation to the joint value function. This factorization of the value function allows the agents to coordinate their actions at runtime using a natural message passing scheme. We provide a simple and efficient method for computing such an approximate value function by solving a single linear pro- gram, whose size is determined by the interaction between the value function structure and the DBN. We thereby avoid the exponential blowup in the state and action space. We show that our approach compares favorably with approaches based on reward sharing. We also show that our algorithm is an efficient alterna- tive to more complicated algorithms even in the single agent case.

UAI Conference 2000 Conference Paper

Policy Iteration for Factored MDPs

• Daphne Koller
• Ronald Parr

Many large MDPs can be represented compactly using a dynamic Bayesian network. Although the structure of the value function does not retain the structure of the process, recent work has shown that value functions in factored MDPs can often be approximated well using a decomposed value function: a linear combination of restricted basis functions, each of which refers only to a small subset of variables. An approximate value function for a particular policy can be computed using approximate dynamic programming, but this approach (and others) can only produce an approximation relative to a distance metric which is weighted by the stationary distribution of the current policy. This type of weighted projection is ill-suited to policy improvement. We present a new approach to value determination, that uses a simple closed-form computation to directly compute a least-squares decomposed approximation to the value function for any weights . We then use this value determination algorithm as a subroutine in a policy iteration process. We show that, under reasonable restrictions, the policies induced by a factored value function are compactly represented, and can be manipulated efficiently in a policy iteration process. We also present a method for computing error bounds for decomposed value functions using a variable-elimination algorithm for function optimization. The complexity of all of our algorithms depends on the factorization of system dynamics and of the approximate value function.

IJCAI Conference 1999 Conference Paper

Computing factored value functions for policies in structured MDPs

• Daphne Koller
• Ronald Parr

Many large Markov decision processes (MDPs) can be represented compactly using a structured representation such as a dynamic Bayesian network. Unfortunately, the compact representation does not help standard MDP algorithms, because the value function for the MDP does not retain the structure of the process description. We argue that in many such MDPs, structure is approximately retained. That is, the value functions are nearly additive: closely approximated by a linear function over factors associated with small subsets of problem features. Based on this idea, we present a convergent, approximate value determination algorithm for structured MDPs. The algorithm maintains an additive value function, alternating dynamic programming steps with steps that project the result back into the restricted space of additive functions. We show that both the dynamic programming and the projection steps can be computed efficiently, despite the fact that the number of states is exponential in the number of state variables.

NeurIPS Conference 1999 Conference Paper

Policy Search via Density Estimation

• Andrew Ng
• Ronald Parr
• Daphne Koller

We propose a new approach to the problem of searching a space of stochastic controllers for a Markov decision process (MDP) or a partially observable Markov decision process (POMDP). Following several other authors, our approach is based on searching in parameterized families of policies (for example, via gradient descent) to optimize solution qual(cid: 173) ity. However, rather than trying to estimate the values and derivatives of a policy directly, we do so indirectly using estimates for the proba(cid: 173) bility densities that the policy induces on states at the different points in time. This enables our algorithms to exploit the many techniques for efficient and robust approximate density propagation in stochastic sys(cid: 173) tems. We show how our techniques can be applied both to deterministic propagation schemes (where the MDP's dynamics are given explicitly in compact form, ) and to stochastic propagation schemes (where we have access only to a generative model, or simulator, of the MDP). We present empirical results for both of these variants on complex problems.

NeurIPS Conference 1999 Conference Paper

Reinforcement Learning Using Approximate Belief States

• Andres Rodriguez
• Ronald Parr
• Daphne Koller

The problem of developing good policies for partially observable Markov decision problems (POMDPs) remains one of the most challenging ar(cid: 173) eas of research in stochastic planning. One line of research in this area involves the use of reinforcement learning with belief states, probabil(cid: 173) ity distributions over the underlying model states. This is a promis(cid: 173) ing method for small problems, but its application is limited by the in(cid: 173) tractability of computing or representing a full belief state for large prob(cid: 173) lems. Recent work shows that, in many settings, we can maintain an approximate belief state, which is fairly close to the true belief state. In particular, great success has been shown with approximate belief states that marginalize out correlations between state variables. In this paper, we investigate two methods of full belief state reinforcement learning and one novel method for reinforcement learning using factored approximate belief states. We compare the performance of these algorithms on several well-known problem from the literature. Our results demonstrate the im(cid: 173) portance of approximate belief state representations for large problems.

UAI Conference 1998 Conference Paper

Flexible Decomposition Algorithms for Weakly Coupled Markov Decision Problems

• Ronald Parr

This paper presents two new approaches to decomposing and solving large Markov decision problems (MDPs), a partial decoupling method and a complete decoupling method. In these approaches, a large, stochastic decision problem is divided into smaller pieces. The first approach builds a cache of policies for each part of the problem independently, and then combines the pieces in a separate, light-weight step. A second approach also divides the problem into smaller pieces, but information is communicated between the different problem pieces, allowing intelligent decisions to be made about which piece requires the most attention. Both approaches can be used to find optimal policies or approximately optimal policies with provable bounds. These algorithms also provide a framework for the efficient transfer of knowledge across problems that share similar structure.

NeurIPS Conference 1997 Conference Paper

Generalized Prioritized Sweeping

• David Andre
• Nir Friedman
• Ronald Parr

Prioritized sweeping is a model-based reinforcement learning method that attempts to focus an agent's limited computational resources to achieve a good estimate of the value of environment states. To choose ef(cid: 173) fectively where to spend a costly planning step, classic prioritized sweep(cid: 173) ing uses a simple heuristic to focus computation on the states that are likely to have the largest errors. In this paper, we introduce generalized prioritized sweeping, a principled method for generating such estimates in a representation-specific manner. This allows us to extend prioritized sweeping beyond an explicit, state-based representation to deal with com(cid: 173) pact representations that are necessary for dealing with large state spaces. We apply this method for generalized model approximators (such as Bayesian networks), and describe preliminary experiments that compare our approach with classical prioritized sweeping.

NeurIPS Conference 1997 Conference Paper

Reinforcement Learning with Hierarchies of Machines

• Ronald Parr
• Stuart Russell

We present a new approach to reinforcement learning in which the poli(cid: 173) cies considered by the learning process are constrained by hierarchies of partially specified machines. This allows for the use of prior knowledge to reduce the search space and provides a framework in which knowledge can be transferred across problems and in which component solutions can be recombined to solve larger and more complicated problems. Our approach can be seen as providing a link between reinforcement learn(cid: 173) ing and "behavior-based" or "teleo-reactive" approaches to control. We present provably convergent algorithms for problem-solving and learn(cid: 173) ing with hierarchical machines and demonstrate their effectiveness on a problem with several thousand states.

IJCAI Conference 1995 Conference Paper

Approximating Optimal Policies for Partially Observable Stochastic Domains

• Ronald Parr
• Stuart Russell

The problem of making optimaJ decisions in uncertain conditions is central to Artificial Intelligence If the state of the world is known at all times, the world can be modeled as a Markov Decision Pro cess (MDP) MDPs have been studied extensively and many methods are known for determining op timal courses of action or policies The more realistic case where state information is only partially observable Partially Observable Markov Decision Processes (POMDPs) have received much less attention The best exact algorithms for these problems can be very inefficient in both space and lime We introduce Smooth Partially Observable Value Approximation (SPOVA), a new approximation method that can quickly yield good approximations which can improve over time This mediod can be combined with reinforcement learning meth ods a combination that was very effective in our test cases

IJCAI Conference 1993 Conference Paper

Provably bounded optimal agents

• Stuart J. Russell
• Devika Subramanian
• Ronald Parr

A program is bounded optimal for a given computational device for a given environment, if the expected utility of the program running on the device in the environment is at least as high as that of all other programs for the device. Bounded optimality differs from the decision-theoretic notion of rationality in that it explicitly allows for the finite computational resources of real agents. It is thus a central issue in the foundations of artificial intelligence. In this paper we consider a restricted class of agent architectures, in which a program consists of a sequence of decision procedures generated by a learning program or given a prion. For this class of agents, we give an efficient construction algorithm that generates a bounded optimal program for any episodic environment, given a set of training examples. The algorithm includes solutions to a new class of optimization problems, namely scheduling computational processes for real-time environments. This class appears to contain significant practical applications.