Stuart Russell

TMLR Journal 2026 Journal Article

Active Teacher Selection for Reward Learning

• Rachel Freedman
• Justin Svegliato
• Kyle Hollins Wray
• Stuart Russell

Reward learning techniques enable machine learning systems to learn objectives from human feedback. A core limitation of these systems is their assumption that all feedback comes from a single human teacher, despite gathering feedback from large and heterogeneous populations. We propose the Hidden Utility Bandit (HUB) framework to model differences in teacher rationality, expertise, and costliness, formalizing the problem of learning from multiple teachers. We develop a variety of solution algorithms and apply them to two real-world domains: paper recommendation systems and COVID-19 vaccine testing. We find that Active Teacher Selection (ATS) algorithms outperform baselines by actively selecting when and which teacher to query. Our key contributions are 1) the HUB framework: a novel mathematical framework for modeling the teacher selection problem, 2) ATS: an active-learning based algorithmic approach that demonstrates the utility of modeling teacher heterogeneity, and 3) proof-of-concept application of the HUB framework and ATS approaches to model and solve multiple real-world problems with complex trade-offs between reward learning and optimization.

PRL Workshop 2025 Workshop Paper

Active Teacher Selection for Reinforcement Learning from Human Feedback

• Rachel Freedman
• Justin Svegliato
• Kyle Hollins Wray
• Stuart Russell

Reinforcement learning from human feedback (RLHF) enables machine learning systems to learn objectives from human feedback. A core limitation of these systems is their assumption that all feedback comes from a single human teacher, despite querying a range of distinct teachers. We propose the Hidden Utility Bandit (HUB) framework to model differences in teacher rationality, expertise, and costliness, formalizing the problem of learning from multiple teachers. We develop a variety of solution algorithms and apply them to two real-world domains: paper recommendation systems and COVID-19 vaccine testing. We find that the Active Teacher Selection (ATS) algorithm outperforms baseline algorithms by actively selecting when and which teacher to query. The HUB framework and ATS algorithm demonstrate the importance of leveraging differences between teachers to learn accurate reward models, facilitating future research on active teacher selection for robust reward modeling.

AAAI Conference 2025 Conference Paper

The Partially Observable Off-Switch Game

• Andrew Garber
• Rohan Subramani
• Linus Luu
• Mark Bedaywi
• Stuart Russell
• Scott Emmons

A wide variety of goals could cause an AI to disable its off switch because ``you can’t fetch the coffee if you’re dead.'' Prior theoretical work on this shutdown problem assumes that humans know everything that AIs do. In practice, however, humans have only limited information. Moreover, in many of the settings where the shutdown problem is most concerning, AIs might have vast amounts of private information. To capture these differences in knowledge, we introduce the Partially Observable Off-Switch Game (POSG), a game-theoretic model of the shutdown problem with asymmetric information. Unlike in the fully observable case, we find that in optimal play, even AI agents assisting perfectly rational humans sometimes avoid shutdown. As expected, increasing the amount of communication or information available always increases (or leaves unchanged) the agents' expected common payoff. But counterintuitively, introducing bounded communication can make the AI defer to the human less in optimal play even though communication mitigates information asymmetry. Thus, designing safe artificial agents in the presence of asymmetric information requires careful consideration of the tradeoffs between maximizing payoffs (potentially myopically) and maintaining AIs’ incentives to defer to humans.

NeurIPS Conference 2024 Conference Paper

Evidence of Learned Look-Ahead in a Chess-Playing Neural Network

• Erik Jenner
• Shreyas Kapur
• Vasil Georgiev
• Cameron Allen
• Scott Emmons
• Stuart Russell

Do neural networks learn to implement algorithms such as look-ahead or search "in the wild"? Or do they rely purely on collections of simple heuristics? We present evidence of learned look-ahead in the policy and value network of Leela Chess Zero, the currently strongest deep neural chess engine. We find that Leela internally represents future optimal moves and that these representations are crucial for its final output in certain board states. Concretely, we exploit the fact that Leela is a transformer that treats every chessboard square like a token in language models, and give three lines of evidence: (1) activations on certain squares of future moves are unusually important causally; (2) we find attention heads that move important information "forward and backward in time, " e. g. , from squares of future moves to squares of earlier ones; and (3) we train a simple probe that can predict the optimal move 2 turns ahead with 92% accuracy (in board states where Leela finds a single best line). These findings are clear evidence of learned look-ahead in neural networks and might be a step towards a better understanding of their capabilities.

NeurIPS Conference 2024 Conference Paper

Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamics

• Hanlin Zhu
• Baihe Huang
• Shaolun Zhang
• Michael Jordan
• Jiantao Jiao
• Yuandong Tian
• Stuart Russell

Auto-regressive large language models (LLMs) show impressive capacities to solve many complex reasoning tasks while struggling with some simple logical reasoning tasks such as inverse search: when trained on ''$A \to B$'' (e. g. , *Tom is the parent of John*), LLM fails to directly conclude ''$B \gets A$'' (e. g. , *John is the child of Tom*) during inference even if the two sentences are semantically identical, which is known as the ''reversal curse''. In this paper, we theoretically analyze the reversal curse via the training dynamics of (stochastic) gradient descent for two auto-regressive models: (1) a bilinear model that can be viewed as a simplification of a one-layer transformer; (2) one-layer transformers under certain assumptions. Our analysis reveals that for both models, the reversal curse is a consequence of the (effective) model weights *asymmetry*, i. e. , the increase of weights from a token $A$ to token $B$ during training does not necessarily cause the increase of the weights from $B$ to $A$, which is caused by the training dynamics under certain choice of loss function and the optimization space of model parameters. Moreover, our analysis can be naturally applied to other logical reasoning tasks such as chain-of-thought (COT), which provides a new perspective different from previous work that focuses on expressivity. Finally, we conduct experiments to validate our theory on multi-layer transformers under different settings. Our code is available at [https: //github. com/marlo-z/reversal_curse_analysis/](https: //github. com/marlo-z/reversal_curse_analysis/).

NeurIPS Conference 2024 Conference Paper

When Your AIs Deceive You: Challenges of Partial Observability in Reinforcement Learning from Human Feedback

• Leon Lang
• Davis Foote
• Stuart Russell
• Anca Dragan
• Erik Jenner
• Scott Emmons

Past analyses of reinforcement learning from human feedback (RLHF) assume that the human evaluators fully observe the environment. What happens when human feedback is based only on partial observations? We formally define two failure cases: deceptive inflation and overjustification. Modeling the human as Boltzmann-rational w. r. t. a belief over trajectories, we prove conditions under which RLHF is guaranteed to result in policies that deceptively inflate their performance, overjustify their behavior to make an impression, or both. Under the new assumption that the human's partial observability is known and accounted for, we then analyze how much information the feedback process provides about the return function. We show that sometimes, the human's feedback determines the return function uniquely up to an additive constant, but in other realistic cases, there is irreducible ambiguity. We propose exploratory research directions to help tackle these challenges and experimentally validate both the theoretical concerns and potential mitigations, and caution against blindly applying RLHF in partially observable settings.

PRL Workshop 2023 Workshop Paper

Learning to Plan with Tree Search via Deep RL

• Dylan Cope
• Justin Svegliato
• Stuart Russell

Tree search is an important component of many decision-making algorithms but often relies on an evaluation function that estimates the desirability of each node. In this paper, we propose to learn which nodes to expand based on a variety of object-level features. We introduce a reward function for this problem based on value of computation estimates with respect to improving the policy for the underlying problem. We apply deep reinforcement learning to this problem in an approach we call Reinforcement Learning for Tree Search (RLTS) and demonstrate that it can yield better performance than baselines in a procedurally generated environment.

AAMAS Conference 2021 Conference Paper

Accumulating Risk Capital Through Investing in Cooperation

• Charlotte Roman
• Michael Dennis
• Andrew Critch
• Stuart Russell

Recent work on promoting cooperation in multi-agent learning has resulted in many methods which successfully promote cooperation at the cost of becoming more vulnerable to exploitation by malicious actors. We show that this is an unavoidable trade-off and propose an objective which balances these concerns, promoting both safety and long-term cooperation. Moreover, the trade-off between safety and cooperation is not severe, and you can receive exponentially large returns through cooperation from a small amount of risk. We study both an exact solution method and propose a method for training policies that targets this objective, Accumulating Risk Capital Through Investing in Cooperation (ARCTIC), and evaluate them in iterated Prisoner’s Dilemma and Stag Hunt.

NeurIPS Conference 2021 Conference Paper

An Empirical Investigation of Representation Learning for Imitation

• Cynthia Chen
• Xin Chen
• Sam Toyer
• Cody Wild
• Scott Emmons
• Ian Fischer
• Kuang-Huei Lee
• Neel Alex

Imitation learning often needs a large demonstration set in order to handle the full range of situations that an agent might find itself in during deployment. However, collecting expert demonstrations can be expensive. Recent work in vision, reinforcement learning, and NLP has shown that auxiliary representation learning objectives can reduce the need for large amounts of expensive, task-specific data. Our Empirical Investigation of Representation Learning for Imitation (EIRLI) investigates whether similar benefits apply to imitation learning. We propose a modular framework for constructing representation learning algorithms, then use our framework to evaluate the utility of representation learning for imitation across several environment suites. In the settings we evaluate, we find that existing algorithms for image-based representation learning provide limited value relative to a well-tuned baseline with image augmentations. To explain this result, we investigate differences between imitation learning and other settings where representation learning has provided significant benefit, such as image classification. Finally, we release a well-documented codebase which both replicates our findings and provides a modular framework for creating new representation learning algorithms out of reusable components.

NeurIPS Conference 2021 Conference Paper

Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism

• Paria Rashidinejad
• Banghua Zhu
• Cong Ma
• Jiantao Jiao
• Stuart Russell

Offline (or batch) reinforcement learning (RL) algorithms seek to learn an optimal policy from a fixed dataset without active data collection. Based on the composition of the offline dataset, two main methods are used: imitation learning which is suitable for expert datasets, and vanilla offline RL which often requires uniform coverage datasets. From a practical standpoint, datasets often deviate from these two extremes and the exact data composition is usually unknown. To bridge this gap, we present a new offline RL framework that smoothly interpolates between the two extremes of data composition, hence unifying imitation learning and vanilla offline RL. The new framework is centered around a weak version of the concentrability coefficient that measures the deviation of the behavior policy from the expert policy alone. Under this new framework, we ask: can one develop an algorithm that achieves a minimax optimal rate adaptive to unknown data composition? To address this question, we consider a lower confidence bound (LCB) algorithm developed based on pessimism in the face of uncertainty in offline RL. We study finite-sample properties of LCB as well as information-theoretic limits in multi-armed bandits, contextual bandits, and Markov decision processes (MDPs). Our analysis reveals surprising facts about optimality rates. In particular, in both contextual bandits and RL, LCB achieves a faster rate of $1/N$ for nearly-expert datasets compared to the usual rate of $1/\sqrt{N}$ in offline RL, where $N$ is the batch dataset sample size. In contextual bandits with at least two contexts, we prove that LCB is adaptively optimal for the entire data composition range, achieving a smooth transition from imitation learning to offline RL. We further show that LCB is almost adaptively optimal in MDPs.

NeurIPS Conference 2021 Conference Paper

MADE: Exploration via Maximizing Deviation from Explored Regions

• Tianjun Zhang
• Paria Rashidinejad
• Jiantao Jiao
• Yuandong Tian
• Joseph E. Gonzalez
• Stuart Russell

In online reinforcement learning (RL), efficient exploration remains particularly challenging in high-dimensional environments with sparse rewards. In low-dimensional environments, where tabular parameterization is possible, count-based upper confidence bound (UCB) exploration methods achieve minimax near-optimal rates. However, it remains unclear how to efficiently implement UCB in realistic RL tasks that involve non-linear function approximation. To address this, we propose a new exploration approach via maximizing the deviation of the occupancy of the next policy from the explored regions. We add this term as an adaptive regularizer to the standard RL objective to balance exploration vs. exploitation. We pair the new objective with a provably convergent algorithm, giving rise to a new intrinsic reward that adjusts existing bonuses. The proposed intrinsic reward is easy to implement and combine with other existing RL algorithms to conduct exploration. As a proof of concept, we evaluate the new intrinsic reward on tabular examples across a variety of model-based and model-free algorithms, showing improvements over count-only exploration strategies. When tested on navigation and locomotion tasks from MiniGrid and DeepMind Control Suite benchmarks, our approach significantly improves sample efficiency over state-of-the-art methods.

NeurIPS Conference 2021 Conference Paper

Scalable Online Planning via Reinforcement Learning Fine-Tuning

• Arnaud Fickinger
• Hengyuan Hu
• Brandon Amos
• Stuart Russell
• Noam Brown

Lookahead search has been a critical component of recent AI successes, such as in the games of chess, go, and poker. However, the search methods used in these games, and in many other settings, are tabular. Tabular search methods do not scale well with the size of the search space, and this problem is exacerbated by stochasticity and partial observability. In this work we replace tabular search with online model-based fine-tuning of a policy neural network via reinforcement learning, and show that this approach outperforms state-of-the-art search algorithms in benchmark settings. In particular, we use our search algorithm to achieve a new state-of-the-art result in self-play Hanabi, and show the generality of our algorithm by also showing that it outperforms tabular search in the Atari game Ms. Pacman.

NeurIPS Conference 2021 Conference Paper

Uncertain Decisions Facilitate Better Preference Learning

• Cassidy Laidlaw
• Stuart Russell

Existing observational approaches for learning human preferences, such as inverse reinforcement learning, usually make strong assumptions about the observability of the human's environment. However, in reality, people make many important decisions under uncertainty. To better understand preference learning in these cases, we study the setting of inverse decision theory (IDT), a previously proposed framework where a human is observed making non-sequential binary decisions under uncertainty. In IDT, the human's preferences are conveyed through their loss function, which expresses a tradeoff between different types of mistakes. We give the first statistical analysis of IDT, providing conditions necessary to identify these preferences and characterizing the sample complexity—the number of decisions that must be observed to learn the tradeoff the human is making to a desired precision. Interestingly, we show that it is actually easier to identify preferences when the decision problem is more uncertain. Furthermore, uncertain decision problems allow us to relax the unrealistic assumption that the human is an optimal decision maker but still identify their exact preferences; we give sample complexities in this suboptimal case as well. Our analysis contradicts the intuition that partial observability should make preference learning more difficult. It also provides a first step towards understanding and improving preference learning methods for uncertain and suboptimal humans.

NeurIPS Conference 2020 Conference Paper

Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Design

• Michael Dennis
• Natasha Jaques
• Eugene Vinitsky
• Alexandre Bayen
• Stuart Russell
• Andrew Critch
• Sergey Levine

A wide range of reinforcement learning (RL) problems --- including robustness, transfer learning, unsupervised RL, and emergent complexity --- require specifying a distribution of tasks or environments in which a policy will be trained. However, creating a useful distribution of environments is error prone, and takes a significant amount of developer time and effort. We propose Unsupervised Environment Design (UED) as an alternative paradigm, where developers provide environments with unknown parameters, and these parameters are used to automatically produce a distribution over valid, solvable environments. Existing approaches to automatically generating environments suffer from common failure modes: domain randomization cannot generate structure or adapt the difficulty of the environment to the agent's learning progress, and minimax adversarial training leads to worst-case environments that are often unsolvable. To generate structured, solvable environments for our protagonist agent, we introduce a second, antagonist agent that is allied with the environment-generating adversary. The adversary is motivated to generate environments which maximize regret, defined as the difference between the protagonist and antagonist agent's return. We call our technique Protagonist Antagonist Induced Regret Environment Design (PAIRED). Our experiments demonstrate that PAIRED produces a natural curriculum of increasingly complex environments, and PAIRED agents achieve higher zero-shot transfer performance when tested in highly novel environments.

NeurIPS Conference 2020 Conference Paper

SLIP: Learning to predict in unknown dynamical systems with long-term memory

• Paria Rashidinejad
• Jiantao Jiao
• Stuart Russell

We present an efficient and practical (polynomial time) algorithm for online prediction in unknown and partially observed linear dynamical systems (LDS) under stochastic noise. When the system parameters are known, the optimal linear predictor is the Kalman filter. However, in unknown systems, the performance of existing predictive models is poor in important classes of LDS that are only marginally stable and exhibit long-term forecast memory. We tackle this problem by bounding the generalized Kolmogorov width of the Kalman filter coefficient set. This motivates the design of an algorithm, which we call spectral LDS improper predictor (SLIP), based on conducting a tight convex relaxation of the Kalman predictive model via spectral methods. We provide a finite-sample analysis, showing that our algorithm competes with the Kalman filter in hindsight with only logarithmic regret. Our regret analysis relies on Mendelson’s small-ball method, providing sharp error bounds without concentration, boundedness, or exponential forgetting assumptions. Empirical evaluations demonstrate that SLIP outperforms state-of-the-art methods in LDS prediction. Our theoretical and experimental results shed light on the conditions required for efficient probably approximately correct (PAC) learning of the Kalman filter from partially observed data.

NeurIPS Conference 2020 Conference Paper

The MAGICAL Benchmark for Robust Imitation

• Sam Toyer
• Rohin Shah
• Andrew Critch
• Stuart Russell

Imitation Learning (IL) algorithms are typically evaluated in the same environment that was used to create demonstrations. This rewards precise reproduction of demonstrations in one particular environment, but provides little information about how robustly an algorithm can generalise the demonstrator's intent to substantially different deployment settings. This paper presents the MAGICAL benchmark suite, which permits systematic evaluation of generalisation by quantifying robustness to different kinds of distribution shift that an IL algorithm is likely to encounter in practice. Using the MAGICAL suite, we confirm that existing IL algorithms overfit significantly to the context in which demonstrations are provided. We also show that standard methods for reducing overfitting are effective at creating narrow perceptual invariances, but are not sufficient to enable transfer to contexts that require substantially different behaviour, which suggests that new approaches will be needed in order to robustly generalise demonstrator intent. Code and data for the MAGICAL suite is available at https: //github. com/qxcv/magical/

AAAI Conference 2019 Conference Paper

Robust Multi-Agent Reinforcement Learning via Minimax Deep Deterministic Policy Gradient

• Shihui Li
• Yi Wu
• Xinyue Cui
• Honghua Dong
• Fei Fang
• Stuart Russell

Despite the recent advances of deep reinforcement learning (DRL), agents trained by DRL tend to be brittle and sensitive to the training environment, especially in the multi-agent scenarios. In the multi-agent setting, a DRL agent’s policy can easily get stuck in a poor local optima w.r.t. its training partners – the learned policy may be only locally optimal to other agents’ current policies. In this paper, we focus on the problem of training robust DRL agents with continuous actions in the multi-agent learning setting so that the trained agents can still generalize when its opponents’ policies alter. To tackle this problem, we proposed a new algorithm, MiniMax Multi-agent Deep Deterministic Policy Gradient (M3DDPG) with the following contributions: (1) we introduce a minimax extension of the popular multi-agent deep deterministic policy gradient algorithm (MADDPG), for robust policy learning; (2) since the continuous action space leads to computational intractability in our minimax learning objective, we propose Multi-Agent Adversarial Learning (MAAL) to efficiently solve our proposed formulation. We empirically evaluate our M3DDPG algorithm in four mixed cooperative and competitive multi-agent environments and the agents trained by our method significantly outperforms existing baselines.

NeurIPS Conference 2018 Conference Paper

Learning Plannable Representations with Causal InfoGAN

• Thanard Kurutach
• Aviv Tamar
• Ge Yang
• Stuart Russell
• Pieter Abbeel

In recent years, deep generative models have been shown to 'imagine' convincing high-dimensional observations such as images, audio, and even video, learning directly from raw data. In this work, we ask how to imagine goal-directed visual plans -- a plausible sequence of observations that transition a dynamical system from its current configuration to a desired goal state, which can later be used as a reference trajectory for control. We focus on systems with high-dimensional observations, such as images, and propose an approach that naturally combines representation learning and planning. Our framework learns a generative model of sequential observations, where the generative process is induced by a transition in a low-dimensional planning model, and an additional noise. By maximizing the mutual information between the generated observations and the transition in the planning model, we obtain a low-dimensional representation that best explains the causal nature of the data. We structure the planning model to be compatible with efficient planning algorithms, and we propose several such models based on either discrete or continuous states. Finally, to generate a visual plan, we project the current and goal observations onto their respective states in the planning model, plan a trajectory, and then use the generative model to transform the trajectory to a sequence of observations. We demonstrate our method on imagining plausible visual plans of rope manipulation.

NeurIPS Conference 2018 Conference Paper

Meta-Learning MCMC Proposals

• Tongzhou Wang
• Yi Wu
• Dave Moore
• Stuart Russell

Effective implementations of sampling-based probabilistic inference often require manually constructed, model-specific proposals. Inspired by recent progresses in meta-learning for training learning agents that can generalize to unseen environments, we propose a meta-learning approach to building effective and generalizable MCMC proposals. We parametrize the proposal as a neural network to provide fast approximations to block Gibbs conditionals. The learned neural proposals generalize to occurrences of common structural motifs across different models, allowing for the construction of a library of learned inference primitives that can accelerate inference on unseen models with no model-specific training required. We explore several applications including open-universe Gaussian mixture models, in which our learned proposals outperform a hand-tuned sampler, and a real-world named entity recognition task, in which our sampler yields higher final F1 scores than classical single-site Gibbs sampling.

NeurIPS Conference 2018 Conference Paper

Negotiable Reinforcement Learning for Pareto Optimal Sequential Decision-Making

• Nishant Desai
• Andrew Critch
• Stuart Russell

It is commonly believed that an agent making decisions on behalf of two or more principals who have different utility functions should adopt a Pareto optimal policy, i. e. a policy that cannot be improved upon for one principal without making sacrifices for another. Harsanyi's theorem shows that when the principals have a common prior on the outcome distributions of all policies, a Pareto optimal policy for the agent is one that maximizes a fixed, weighted linear combination of the principals’ utilities. In this paper, we derive a more precise generalization for the sequential decision setting in the case of principals with different priors on the dynamics of the environment. We refer to this generalization as the Negotiable Reinforcement Learning (NRL) framework. In this more general case, the relative weight given to each principal’s utility should evolve over time according to how well the agent’s observations conform with that principal’s prior. To gain insight into the dynamics of this new framework, we implement a simple NRL agent and empirically examine its behavior in a simple environment.

AAAI Conference 2017 Conference Paper

A Nearly-Black-Box Online Algorithm for Joint Parameter and State Estimation in Temporal Models

• Yusuf Erol
• Yi Wu
• Lei Li
• Stuart Russell

Online joint parameter and state estimation is a core problem for temporal models. Most existing methods are either restricted to a particular class of models (e. g. , the Storvik filter) or computationally expensive (e. g. , particle MCMC). We propose a novel nearly-black-box algorithm, the Assumed Parameter Filter (APF), a hybrid of particle filtering for state variables and assumed density filtering for parameter variables. It has the following advantages: (a) it is online and computationally efficient; (b) it is applicable to both discrete and continuous parameter spaces with arbitrary transition dynamics. On a variety of toy and real models, APF generates more accurate results within a fixed computation budget compared to several standard algorithms from the literature.

IJCAI Conference 2017 Conference Paper

Efficient Reinforcement Learning with Hierarchies of Machines by Leveraging Internal Transitions

• Aijun Bai
• Stuart Russell

In the context of hierarchical reinforcement learning, the idea of hierarchies of abstract machines (HAMs) is to write a partial policy as a set of hierarchical finite state machines with unspecified choice states, and use reinforcement learning to learn an optimal completion of this partial policy. Given a HAM with potentially deep hierarchical structure, there often exist many internal transitions where a machine calls another machine with the environment state unchanged. In this paper, we propose a new hierarchical reinforcement learning algorithm that discovers such internal transitions automatically, and shortcircuits them recursively in computation of Q values. The resulting HAMQ-INT algorithm outperforms the state of the art significantly on the benchmark Taxi domain and a much more complex RoboCup Keepaway domain.

NeurIPS Conference 2017 Conference Paper

Inverse Reward Design

• Dylan Hadfield-Menell
• Smitha Milli
• Pieter Abbeel
• Stuart Russell
• Anca Dragan

Autonomous agents optimize the reward function we give them. What they don't know is how hard it is for us to design a reward function that actually captures what we want. When designing the reward, we might think of some specific training scenarios, and make sure that the reward will lead to the right behavior in those scenarios. Inevitably, agents encounter new scenarios (e. g. , new types of terrain) where optimizing that same reward may lead to undesired behavior. Our insight is that reward functions are merely observations about what the designer actually wants, and that they should be interpreted in the context in which they were designed. We introduce inverse reward design (IRD) as the problem of inferring the true objective based on the designed reward and the training MDP. We introduce approximate methods for solving IRD problems, and use their solution to plan risk-averse behavior in test MDPs. Empirical results suggest that this approach can help alleviate negative side effects of misspecified reward functions and mitigate reward hacking.

IJCAI Conference 2017 Conference Paper

Should Robots be Obedient?

• Smitha Milli
• Dylan Hadfield-Menell
• Anca Dragan
• Stuart Russell

Intuitively, obedience -- following the order that a human gives -- seems like a good property for a robot to have. But, we humans are not perfect and we may give orders that are not best aligned to our preferences. We show that when a human is not perfectly rational then a robot that tries to infer and act according to the human's underlying preferences can always perform better than a robot that simply follows the human's literal order. Thus, there is a tradeoff between the obedience of a robot and the value it can attain for its owner. We investigate how this tradeoff is impacted by the way the robot infers the human's preferences, showing that some methods err more on the side of obedience than others. We then analyze how performance degrades when the robot has a misspecified model of the features that the human cares about or the level of rationality of the human. Finally, we study how robots can start detecting such model misspecification. Overall, our work suggests that there might be a middle ground in which robots intelligently decide when to obey human orders, but err on the side of obedience.

RLDM Conference 2017 Conference Abstract

Speeding Up HAM Learning with Internal Transitions

• Aijun Bai
• Stuart Russell

In the context of hierarchical reinforcement learning, the idea of hierarchies of abstract machines (HAMs) is to write a partial policy as a set of hierarchical finite state machines with unspecified choice states, and use reinforcement learning to learn an optimal completion of this partial policy. Given a HAM with potentially deep hierarchical structure, there often exist many internal transitions where a machine calls another machine with the environment state unchanged. In this paper, we propose a new hierarchical reinforcement learning algorithm that automatically discovers such internal transitions, and shortcircuits them recursively in the computation of Q values. We empirically confirm that the resulting HAMQ-INT algorithm outperforms the state of the art significantly on the benchmark Taxi domain and a much more complex RoboCup Keepaway domain.

IJCAI Conference 2017 Conference Paper

The Off-Switch Game

• Dylan Hadfield-Menell
• Anca Dragan
• Pieter Abbeel
• Stuart Russell

It is clear that one of the primary tools we can use to mitigate the potential risk from a misbehaving AI system is the ability to turn the system off. As the capabilities of AI systems improve, it is important to ensure that such systems do not adopt subgoals that prevent a human from switching the system off. This is a challenge because many formulations of rational agents create strong incentives for self-preservation. This is not caused by a built-in instinct, but because a rational agent will maximize expected utility and cannot achieve whatever objective it has been given if it is dead. Our goal is to study the incentives an agent has to allow itself to be switched off. We analyze a simple game between a human H and a robot R, where H can press R’s off switch but R can disable the off switch. A traditional agent takes its reward function for granted: we show that such agents have an incentive to disable the off switch, except in the special case where H is perfectly rational. Our key insight is that for R to want to preserve its off switch, it needs to be uncertain about the utility associated with the outcome, and to treat H’s actions as important observations about that utility. (R also has no incentive to switch itself off in this setting. ) We conclude that giving machines an appropriate level of uncertainty about their objectives leads to safer designs, and we argue that this setting is a useful generalization of the classical AI paradigm of rational agents.

NeurIPS Conference 2016 Conference Paper

Cooperative Inverse Reinforcement Learning

• Dylan Hadfield-Menell
• Stuart Russell
• Pieter Abbeel
• Anca Dragan

For an autonomous system to be helpful to humans and to pose no unwarranted risks, it needs to align its values with those of the humans in its environment in such a way that its actions contribute to the maximization of value for the humans. We propose a formal definition of the value alignment problem as cooperative inverse reinforcement learning (CIRL). A CIRL problem is a cooperative, partial- information game with two agents, human and robot; both are rewarded according to the human’s reward function, but the robot does not initially know what this is. In contrast to classical IRL, where the human is assumed to act optimally in isolation, optimal CIRL solutions produce behaviors such as active teaching, active learning, and communicative actions that are more effective in achieving value alignment. We show that computing optimal joint policies in CIRL games can be reduced to solving a POMDP, prove that optimality in isolation is suboptimal in CIRL, and derive an approximate CIRL algorithm.

IJCAI Conference 2016 Conference Paper

Markovian State and Action Abstractions for MDPs via Hierarchical MCTS

• Aijun Bai
• Siddharth Srivastava
• Stuart Russell

State abstraction is an important technique for scaling MD Palgorithms. As is well known, however, it introduces difficulties due to the non-Markovian nature of state-abstracted models. Whereas prior approaches rely upon ad hoc fixes for this issue, we propose instead to view the state-abstracted model as a POMDP and show that we can thereby take advantage of state abstraction without sacrificing the Markov property. We further exploit the hierarchical structure introduced by state abstraction by extending the theory of options to a POMDP setting. In this context we propose a hierarchical Monte Carlo tree search algorithm and show that it converges to a recursively optimal hierarchical policy. Both theoretical and empirical results suggest that abstracting an MDP into a POMDP yields a scalable solution approach.

AAAI Conference 2016 Conference Paper

Metaphysics of Planning Domain Descriptions

• Siddharth Srivastava
• Stuart Russell
• Alessandro Pinto

STRIPS-like languages (SLLs) have fostered immense advances in automated planning. In practice, SLLs are used to express highly abstract versions of real-world planning problems, leading to more concise models and faster solution times. Unfortunately, as we show in the paper, simple ways of abstracting solvable real-world problems may lead to SLL models that are unsolvable, SLL models whose solutions are incorrect with respect to the real-world problem, or models that are inexpressible in SLLs. There is some evidence that such limitations have restricted the applicability of AI planning technology in the real world, as is apparent in the case of task and motion planning in robotics. We show that the situation can be ameliorated by a combination of increased expressive power—for example, allowing angelic nondeterminism in action effects—and new kinds of algorithmic approaches designed to produce correct solutions from initially incorrect or non-Markovian abstract models.

IJCAI Conference 2016 Conference Paper

Swift: Compiled Inference for Probabilistic Programming Languages

• Yi Wu
• Lei Li
• Stuart Russell
• Rastislav Bodik

A probabilistic program defines a probability measure over its semantic structures. One common goal of probabilistic programming languages (PPLs) is to compute posterior probabilities for arbitrary models and queries, given observed evidence, using a generic inference engine. Most PPL inference engines - even the compiled ones - incur significant runtime interpretation overhead, especially for contingent and open-universe models. This paper describes Swift, a compiler for the BLOG PPL. Swift-generated code incorporates optimizations that eliminate interpretation overhead, maintain dynamic dependencies efficiently, and handle memory management for possible worlds of varying sizes. Experiments comparing Swift with other PPL engines on avariety of inference problems demonstrate speedups ranging from 12x to326x.

NeurIPS Conference 2015 Conference Paper

Gaussian Process Random Fields

• David Moore
• Stuart Russell

Gaussian processes have been successful in both supervised and unsupervised machine learning tasks, but their computational complexity has constrained practical applications. We introduce a new approximation for large-scale Gaussian processes, the Gaussian Process Random Field (GPRF), in which local GPs are coupled via pairwise potentials. The GPRF likelihood is a simple, tractable, and parallelizeable approximation to the full GP marginal likelihood, enabling latent variable modeling and hyperparameter selection on large datasets. We demonstrate its effectiveness on synthetic spatial data as well as a real-world application to seismic event location.

AAAI Conference 2015 Conference Paper

Tractability of Planning with Loops

• Siddharth Srivastava
• Shlomo Zilberstein
• Abhishek Gupta
• Pieter Abbeel
• Stuart Russell

We create a unified framework for analyzing and synthesizing plans with loops for solving problems with nondeterministic numeric effects and a limited form of partial observability. Three different action models—with deterministic, qualitative non-deterministic and Boolean nondeterministic semantics—are handled using a single abstract representation. We establish the conditions under which the correctness and termination of solutions, represented as abstract policies, can be verified. We also examine the feasibility of learning abstract policies from examples. We demonstrate our techniques on several planning problems and show that they apply to challenging real-world tasks such as doing the laundry with a PR2 robot. These results resolve a number of open questions about planning with loops and facilitate the development of new algorithms and applications.

NeurIPS Conference 2014 Conference Paper

Algorithm selection by rational metareasoning as a model of human strategy selection

• Falk Lieder
• Dillon Plunkett
• Jessica Hamrick
• Stuart Russell
• Nicholas Hay
• Tom Griffiths

Selecting the right algorithm is an important problem in computer science, because the algorithm often has to exploit the structure of the input to be efficient. The human mind faces the same challenge. Therefore, solutions to the algorithm selection problem can inspire models of human strategy selection and vice versa. Here, we view the algorithm selection problem as a special case of metareasoning and derive a solution that outperforms existing methods in sorting algorithm selection. We apply our theory to model how people choose between cognitive strategies and test its prediction in a behavioral experiment. We find that people quickly learn to adaptively choose between cognitive strategies. People's choices in our experiment are consistent with our model but inconsistent with previous theories of human strategy selection. Rational metareasoning appears to be a promising framework for reverse-engineering how people choose among cognitive strategies and translating the results into better solutions to the algorithm selection problem.

NeurIPS Conference 2013 Conference Paper

Multilinear Dynamical Systems for Tensor Time Series

• Mark Rogers
• Lei Li
• Stuart Russell

Many scientific data occur as sequences of multidimensional arrays called tensors. How can hidden, evolving trends in such data be extracted while preserving the tensor structure? The model that is traditionally used is the linear dynamical system (LDS), which treats the observation at each time slice as a vector. In this paper, we propose the multilinear dynamical system (MLDS) for modeling tensor time series and an expectation-maximization (EM) algorithm to estimate the parameters. The MLDS models each time slice of the tensor time series as the multilinear projection of a corresponding member of a sequence of latent, low-dimensional tensors. Compared to the LDS with an equal number of parameters, the MLDS achieves higher prediction accuracy and marginal likelihood for both simulated and real datasets.

IJCAI Conference 2011 Conference Paper

Bounded Intention Planning

• Jason Wolfe
• Stuart Russell

We propose a novel approach for solving unary SAS+ planning problems. This approach extends an SAS+ instance with new state variables representing intentions about how each original state variable will be used or changed next, and splits the original actions into several stages of intention followed by eventual execution. The result is a new SAS+ instance with the same basic solutions as the original. While the transformed problem is larger, it has additional structure that can be exploited to reduce the branching factor, leading to reachable state spaces that are many orders of magnitude smaller (and hence much faster planning) in several test domains with acyclic causal graphs.

AAAI Conference 2011 Conference Paper

Global Seismic Monitoring: A Bayesian Approach

• Nimar Arora
• Stuart Russell
• Paul Kidwell
• Erik Sudderth

The automated processing of multiple seismic signals to detect and localize seismic events is a central tool in both geophysics and nuclear treaty verification. This paper reports on a project, begun in 2009, to reformulate this problem in a Bayesian framework. A Bayesian seismic monitoring system, NET-VISA, has been built comprising a spatial event prior and generative models of event transmission and detection, as well as an inference algorithm. Applied in the context of the International Monitoring System (IMS), a global sensor network developed for the Comprehensive Nuclear- Test-Ban Treaty (CTBT), NET-VISA achieves a reduction of around 60% in the number of missed events compared to the currently deployed system. It also finds events that are missed even by the human analysts who post-process the IMS output.

NeurIPS Conference 2010 Conference Paper

Global seismic monitoring as probabilistic inference

• Nimar Arora
• Stuart Russell
• Paul Kidwell
• Erik Sudderth

The International Monitoring System (IMS) is a global network of sensors whose purpose is to identify potential violations of the Comprehensive Nuclear-Test-Ban Treaty (CTBT), primarily through detection and localization of seismic events. We report on the first stage of a project to improve on the current automated software system with a Bayesian inference system that computes the most likely global event history given the record of local sensor data. The new system, VISA (Vertically Integrated Seismological Analysis), is based on empirically calibrated, generative models of event occurrence, signal propagation, and signal detection. VISA exhibits significantly improved precision and recall compared to the current operational system and is able to detect events that are missed even by the human analysts who post-process the IMS output.

NeurIPS Conference 2008 Conference Paper

Probabilistic detection of short events, with application to critical care monitoring

• Norm Aleks
• Stuart Russell
• Michael Madden
• Diane Morabito
• Kristan Staudenmayer
• Mitchell Cohen
• Geoffrey Manley

We describe an application of probabilistic modeling and inference technology to the problem of analyzing sensor data in the setting of an intensive care unit (ICU). In particular, we consider the arterial-line blood pressure sensor, which is subject to frequent data artifacts that cause false alarms in the ICU and make the raw data almost useless for automated decision making. The problem is complicated by the fact that the sensor data are acquired at fixed intervals whereas the events causing data artifacts may occur at any time and have durations that may be significantly shorter than the data collection interval. We show that careful modeling of the sensor, combined with a general technique for detecting sub-interval events and estimating their duration, enables effective detection of artifacts and accurate estimation of the underlying blood pressure values.

IJCAI Conference 2005 Conference Paper

BLOG: Probabilistic Models with Unknown Objects

• Brian Milch
• Bhaskara Marthi
• Stuart Russell
• David Sontag
• Daniel L. Ong
• Andrey

This paper introduces and illustrates BLOG, a formal language for defining probability models over worlds with unknown objects and identity uncertainty. BLOG unifies and extends several existing approaches. Subject to certain acyclicity constraints, every BLOG model specifies a unique probability distribution over first-order model structures that can contain varying and unbounded numbers of objects. Furthermore, complete inference algorithms exist for a large fragment of the language. We also introduce a probabilistic form of Skolemization for handling evidence.

IJCAI Conference 2005 Conference Paper

Concurrent Hierarchical Reinforcement Learning

• Bhaskara Marthi
• Stuart Russell
• David Latham
• Carlos

We consider applying hierarchical reinforcement learning techniques to problems in which an agent has several effectors to control simultaneously. We argue that the kind of prior knowledge one typically has about such problems is best expressed using a multithreaded partial program, and present concurrent ALisp, a language for specifying such partial programs. We describe algorithms for learning and acting with concurrent ALisp that can be efficient even when there are exponentially many joint choices at each decision point. Finally, we show results of applying these methods to a complex computer game domain.

IJCAI Conference 2005 Conference Paper

Efficient belief-state AND–OR search, with application to Kriegspiel

• Stuart Russell
• Jason

The paper reports on new algorithms for solving partially observable games. Whereas existing algorithms apply AND-OR search to a tree of blackbox belief states, our “incremental” versions treat uncertainty as a new search dimension, examining the physical states within a belief state to construct solution trees incrementally. On a newly created database of checkmate problems for Kriegspiel (a partially observable form of chess), incrementalization yields speedups of two or more orders of magnitude on hard instances.

IJCAI Conference 2003 Conference Paper

Logical Filtering

• EyalAmir
• Stuart Russell

Filtering denotes any method whereby an agent updates its belief state—its knowledge of the state of the world—from a sequence of actions and observations. In logical filtering, the belief state is a logical formula describing possible world states and the agent has a (possibly nondeterministic) logical model of its environment and sensors. This paper presents efficient logical filtering algorithms that maintain a compact belief state representation indefinitely, for a broad range of environment classes including nondeterministic, partially observable STRIPS environments and environments in which actions permute the state space. Efficient filtering is also possible when the belief state is represented using prime implicates, or when it is approximated by a logically weaker formula.

NeurIPS Conference 2002 Conference Paper

A Hierarchical Bayesian Markovian Model for Motifs in Biopolymer Sequences

• Eric Xing
• Michael Jordan
• Richard Karp
• Stuart Russell

We propose a dynamic Bayesian model for motifs in biopolymer se- quences which captures rich biological prior knowledge and positional dependencies in motif structure in a principled way. Our model posits that the position-specific multinomial parameters for monomer distribu- tion are distributed as a latent Dirichlet-mixture random variable, and the position-specific Dirichlet component is determined by a hidden Markov process. Model parameters can be fit on training motifs using a vari- ational EM algorithm within an empirical Bayesian framework. Varia- tional inference is also used for detecting hidden motifs. Our model im- proves over previous models that ignore biological priors and positional dependence. It has much higher sensitivity to motifs during detection and a notable ability to distinguish genuine motifs from false recurring patterns.

NeurIPS Conference 2002 Conference Paper

Distance Metric Learning with Application to Clustering with Side-Information

• Eric Xing
• Michael Jordan
• Stuart Russell
• Andrew Ng

@cs. berkeley. edu Many algorithms rely critically on being given a good metric over their inputs. For instance, data can often be clustered in many “plausible” ways, and if a clustering algorithm such as K-means initially fails to find one that is meaningful to a user, the only recourse may be for the user to manually tweak the metric until sufficiently good clusters are found. For these and other applications requiring good metrics, it is desirable that we provide a more systematic way for users to indicate what they con- sider “similar. ” For instance, we may ask them to provide examples. In this paper, we present an algorithm that, given examples of similar (and, , learns a distance metric over if desired, dissimilar) pairs of points in that respects these relationships. Our method is based on posing met-  ric learning as a convex optimization problem, which allows us to give efficient, local-optima-free algorithms. We also demonstrate empirically that the learned metrics can be used to significantly improve clustering performance. 

NeurIPS Conference 2002 Conference Paper

Identity Uncertainty and Citation Matching

• Hanna Pasula
• Bhaskara Marthi
• Brian Milch
• Stuart Russell
• Ilya Shpitser

Identity uncertainty is a pervasive problem in real-world data analysis. It arises whenever objects are not labeled with unique identifiers or when those identifiers may not be perceived perfectly. In such cases, two ob- servations may or may not correspond to the same object. In this paper, we consider the problem in the context of citation matching—the prob- lem of deciding which citations correspond to the same publication. Our approach is based on the use of a relational probability model to define a generative model for the domain, including models of author and title corruption and a probabilistic citation grammar. Identity uncertainty is handled by extending standard models to incorporate probabilities over the possible mappings between terms in the language and objects in the domain. Inference is based on Markov chain Monte Carlo, augmented with specific methods for generating efficient proposals when the domain contains many objects. Results on several citation data sets show that the method outperforms current algorithms for citation matching. The declarative, relational nature of the model also means that our algorithm can determine object characteristics such as author names by combining multiple citations of multiple papers.

NeurIPS Conference 2000 Conference Paper

Programmable Reinforcement Learning Agents

• David Andre
• Stuart Russell

We present an expressive agent design language for reinforcement learn(cid: 173) ing that allows the user to constrain the policies considered by the learn(cid: 173) ing process. The language includes standard features such as parameter(cid: 173) ized subroutines, temporary interrupts, aborts, and memory variables, but also allows for unspecified choices in the agent program. For learning that which isn't specified, we present provably convergent learning algo(cid: 173) rithms. We demonstrate by example that agent programs written in the language are concise as well as modular. This facilitates state abstraction and the transferability of learned skills.

IJCAI Conference 1999 Conference Paper

Convergence of reinforcement learning with general -function approximators

• Vassilis A. Papavassiliou
• Stuart Russell

A key open problem in reinforcement learning is to assure convergence when using a compact hypothesis class to approximate the value function. Although the standard temporal-difference learning algorithm has been shown to converge when the hypothesis class is a linear combination of fixed basis functions, it may diverge with a general (nonlinear) hypothesis class. This paper describes the Bridge algorithm, a new method for reinforcement learning, and shows that it converges to an approximate global optimum for any agnostically learnable hypothesis class. Convergence is demonstrated on a simple example for which temporal-difference learning fails. Weak conditions are identified under which the Bridge algorithm converges for any hypothesis class. Finally, connections are made between the complexity of reinforcement learning and the PAC-learnability of the hypothesis class.

IJCAI Conference 1999 Conference Paper

Tracking many objects with many sensors

• Hanna Pasula
• Stuart Russell
• Michael Ostland
• YdacovRitov

Keeping track of multiple objects over time is a problem that arises in many real-world domains. The problem is often complicated by noisy sensors and unpredictable dynamics. Previous work by Huang and Russell, drawing on the data association literature, provided a probabilistic analysis and a threshold-based approximation algorithm for the case of multiple objects detected by two spatially separated sensors. This paper analyses the case in which large numbers of sensors are involved. We show that the approach taken by Huang and Russell, who used pairwise sensor-based appearance probabilities as the elementary probabilistic model, does not scale. When more than two observations are made, the objects' intrinsic properties must be estimated. These provide the necessary conditional independencies to allow a spatial decomposition of the global probability model. We also replace Huang and Russell's threshold algorithm for object identification with a polynomial-time approximation scheme based on Markov chain Monte Carlo simulation. Using sensor data from a freeway traffic simulation, we show that this allows accurate estimation of long-range origin/destination information even when the individual links in the sensor chain are highly unreliable.

AIJ Journal 1998 Journal Article

Object identification: a Bayesian analysis with application to traffic surveillance

• Timothy Huang
• Stuart Russell

Object identification—the task of deciding that two observed objects are in fact one and the same object—is a fundamental requirement for any situated agent that reasons about individuals. Object identity, as represented by the equality operator between two terms in predicate calculus, is essentially a first-order concept. Raw sensory observations, on the other hand, are essentially propositional—especially when formulated as evidence in standard probability theory. This paper describes patterns of reasoning that allow identity sentences to be grounded in sensory observations, thereby bridging the gap. We begin by defining a physical event space over which probabilities are defined. We then introduce an identity criterion, which selects those events that correspond to identity between observed objects. From this, we are able to compute the probability that any two objects are the same, given a stream of observations of many objects. We show that the appearance probability, which defines how an object can be expected to appear at subsequent observations given its current appearance, is a natural model for this type of reasoning. We apply the theory to the task of recognizing cars observed by cameras at widely separated sites in a freeway network, with new heuristics to handle the inevitable complexity of matching large numbers of objects and with online learning of appearance probability models. Despite extremely noisy observations, we are able to achieve high levels of performance.

IJCAI Conference 1997 Conference Paper

Challenge: What is the Impact of Bayesian Networks on Learning?

• Mr Friedman
• Moises Goldszmidt
• David Heckerman
• Stuart Russell

In recent years, there has been much interest in learning Bayesian networks from data. Learning such models is desirable simply because there is a wide array of off-the-shelf tools that can apply the learned models as expert systems, diagnosis engines, and decision support systems. Practitioners also claim that adaptive Bayesian networks have advantages in their own right as a non-parametric method for density estimation, data analysis, pattern classification, and modeling. Among the reasons cited we find: their semantic clarity and understandability by humans, the ease of acquisition and incorporation of prior knowledge, the ease of integration with optimal decision-making methods, the possibility of causal interpretation of learned models, and the automatic handling of noisy and missing data. In spite of these claims, and the initial success reported recently, methods that learn Bayesian networks have yet to make the impact that other techniques such as neural networks and hidden Markov models have made in applications such as pattern and speech recognition. In this paper, we challenge the research community to identify and characterize domains where induction of Bayesian networks makes the critical difference, and to quantify the factors that are responsible for that difference. In addition to formalizing the challenge, we identify research problems whose solution is, in our view, crucial for meeting this challenge.

IJCAI Conference 1997 Conference Paper

Object Identification in a Bayesian Context

• Timothy Huang
• Stuart Russell

Object identification—the task of deciding that two observed objects are in fact one and the same object—is a fundamental requirement for any situated agent that reasons about individuals. Object identity, as represented by the equality operator between two terms in predicate calculus, is essentially a first-order concept. Raw sensory observations, on the other hand, are essentially propositional— especially when formulated as evidence in standard probability theory. This paper describes patterns of reasoning that allow identity sentences to be grounded in sensory observations, thereby bridging the gap. We begin by defining a physical event space over which probabilities are defined. We then introduce an identity criterion, which selects those events that correspond to identity between observed objects. From this, we are able to compute the probability that any two objects are the same, given a stream of observations of many objects. We show that the appearance probability, which defines how an object can be expected to appear at subsequent observations given its current appearance, is a natural model for this type of reasoning. We apply the theory to the task of recognizing cars observed by cameras at widely separated sites in a freeway network, with new heuristics to handle the inevitable complexity of matching large numbers of objects and with online learning of appearance probability models. Despite extremely noisy observations, we are able to achieve high levels of performance.

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 1997 Conference Paper

Space-efficient inference in dynamic probabilistic networks

• John Binder
• Kevin Murphy
• Stuart Russell

AIJ Journal 1996 Journal Article

Optimal composition of real-time systems

• Shlomo Zilberstein
• Stuart Russell

Real-time systems are designed for environments in which the utility of actions is strongly time-dependent. Recent work by Dean, Horvitz and others has shown that anytime algorithms are a useful tool for real-time system design, since they allow computation time to be traded for decision quality. In order to construct complex systems, however, we need to be a ble to compose larger systems from smaller, reusable anytime modules. This paper addresses two basic problems associated with composition: how to ensure the interruptibility of the composed system; and how to allocate computation time optimally among the components. The first problem is solved by a simple and general construction that incurs only a small, constant penalty. The second is solved by an off-line compilation process. We show that the general compilation problem is NP-complete. However, efficient local compilation techniques, working on a single program structure at a time, yield glo bally optimal allocations for a large class of programs. We illustrate these results with two simple applications.

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 1995 Conference Paper

Rationality and Intelligence

• Stuart Russell
• University of California
• Berkeley

AIJ Journal 1991 Journal Article

Principles of metareasoning

• Stuart Russell
• Eric Wefald

In this paper we outline a general approach to the study of metareasoning, not in the sense of explicating the semantics of explicitly specified meta-level control policies, but in the sense of providing a basis for selecting and justifying computational actions. This research contributes to a developing attack on the problem of resource-bounded rationality, by providing a means for analyzing and generating optimal computational strategies. Because reasoning about a computation without doing it necessarily involves uncertainty as to its outcome, probability and decision theory will be our main tools. We develop a general formula for the utility of computations, this utility being derived directly from the ability of computations to affect an agent's external actions. We address some philosophical difficulties that arise in specifying this formula, given our assumption of limited rationality. We also describe a methodology for applying the theory to particular problem-solving systems, and provide a brief sketch of the resulting algorithms and their performance.

IJCAI Conference 1989 Conference Paper

On Optimal Game-Tree Search using Rational Meta-Reasoning

• Stuart Russell
• Eric Wefald

In this paper we outline a general approach to the study of problem-solving, in which search steps are considered decisions in the same sense as actions in the world. Unlike other metrics in the literature, the value of a search step is defined as a real utility rather than as a quasiutility, and can therefore be computed directly from a model of the base-level problem-solver. We develop a formula for the expected value of a search step in a game-playing context using the single-step assumption, namely that a computation step can be evaluated as it was the last to be taken. We prove some metalevel theorems that enable the development of a low-overhead algorithm, MGSS*, that chooses search steps in order of highest estimated utility. Although we show that the single-step assumption is untenable in general, a program implemented for the game of Othello soundly beats an alpha-beta search while expanding significantly fewer nodes, even though both programs use the same evaluation function.

AAAI Conference 1986 Conference Paper

Preliminary Steps Toward the Automation of Induction

• Stuart Russell

Rational inductive behaviour is strongly influenced by existing knowledge of the world. This paper begins to elucidate the formal relationship between the base-level induction to be attempted, the direct evidence for it (positive and negative instances) and the indirect evidence (higher-level regularities in the world). By constructing a program to search the space of forms of higher-level regularity WC discover some important new forms which have direct application to analogy, single-instance generalization and enumerative induction in general. We outline a theory which we hope is the first step towards the construction of powerful and robust learning systems.