Arrow Research search

Author name cluster

Christoph Dann

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

34 papers
2 author rows

Possible papers

34

ICML Conference 2025 Conference Paper

Can RLHF be More Efficient with Imperfect Reward Models? A Policy Coverage Perspective

  • Jiawei Huang
  • Bingcong Li
  • Christoph Dann
  • Niao He

Sample efficiency is critical for online Reinforcement Learning from Human Feedback (RLHF). While existing works investigate sample-efficient online exploration strategies, the potential of utilizing misspecified yet relevant reward models to accelerate learning remains underexplored. This paper studies how to transfer knowledge from those imperfect reward models in online RLHF. We start by identifying a novel property due to KL-regularization in the RLHF objective: a policy’s coverability of the optimal policy is captured by its sub-optimality. Building on this insight, we propose novel transfer learning principles and a theoretical algorithm— T ransfer P olicy O ptimization ( TPO )—with provable benefits compared to standard online learning. Empirically, inspired by our theoretical findings, we develop a win-rate-based transfer policy selection strategy with improved computational efficiency. Moreover, our empirical transfer learning technique is modular and can be integrated with various policy optimization methods, such as DPO, IPO and XPO, to further enhance their performance. We validate the effectiveness of our method through experiments on summarization tasks.

Details

ICML Conference 2025 Conference Paper

Design Considerations in Offline Preference-based RL

  • Alekh Agarwal
  • Christoph Dann
  • Teodor V. Marinov

Offline algorithms for Reinforcement Learning from Human Preferences (RLHF), which use only a fixed dataset of sampled responses given an input, and preference feedback among these responses, have gained increasing prominence in the literature on aligning language models. In this paper, we study how the different design choices made in methods such as DPO, IPO, SLiC and many variants influence the quality of the learned policy, from a theoretical perspective. Our treatment yields insights into the choices of loss function, the policy which is used to normalize log-likelihoods, and also the role of the data sampling policy. Notably, our results do not rely on the standard reparameterization-style arguments used to motivate some of the algorithms in this family, which allows us to give a unified treatment to a broad class of methods. We also conduct a small empirical study to verify some of the theoretical findings on a standard summarization benchmark.

Details

TMLR Journal 2025 Journal Article

Preserving Expert-Level Privacy in Offline Reinforcement Learning

  • Navodita Sharma
  • Vishnu Vinod
  • Abhradeep Guha Thakurta
  • Alekh Agarwal
  • Borja Balle
  • Christoph Dann
  • Aravindan Raghuveer

The offline reinforcement learning (RL) problem aims to learn an optimal policy from historical data collected by one or more behavioural policies (experts) by interacting with an environment. However, the individual experts may be privacy-sensitive in that the learnt policy may retain information about their precise choices. In some domains like personalized retrieval, advertising and healthcare, the expert choices are considered sensitive data. To provably protect the privacy of such experts, we propose a novel consensus-based expert-level differentially private offline RL training approach compatible with any existing offline RL algorithm. We prove rigorous differential privacy guarantees, while maintaining strong empirical performance. Unlike existing work in differentially private RL, we supplement the theory with proof-of-concept experiments on classic RL environments featuring large continuous state spaces, demonstrating substantial improvements over a natural baseline across multiple tasks.

PDF Details

NeurIPS Conference 2025 Conference Paper

Principled Model Routing for Unknown Mixtures of Source Domains

  • Christoph Dann
  • Yishay Mansour
  • Teodor Vanislavov Marinov
  • Mehryar Mohri

The rapid proliferation of domain-specialized machine learning models presents a challenge: while individual models excel in specific domains, their performance varies significantly across diverse applications. This makes selecting the optimal model when faced with an unknown mixture of tasks, especially with limited or no data to estimate the mixture, a difficult problem. We address this challenge by formulating it as a multiple-source domain adaptation (MSA) problem. We introduce a novel, scalable algorithm that effectively routes each input to the best-suited model from a pool of available models. Our approach provides a strong performance guarantee: remarkably, for any mixture domain, the accuracy achieved by the best source model is maintained. This guarantee is established through a theoretical bound on the regret for new domains, expressed as a convex combination of the best regrets in the source domains, plus a concentration term that diminishes as the amount of source data increases. While our primary contributions are theoretical and algorithmic, we also present empirical results demonstrating the effectiveness of our approach.

PDF Details

ICML Conference 2024 Conference Paper

A Minimaximalist Approach to Reinforcement Learning from Human Feedback

  • Gokul Swamy 0001
  • Christoph Dann
  • Rahul Kidambi
  • Zhiwei Steven Wu
  • Alekh Agarwal

We present Self-Play Preference Optimization (SPO), an algorithm for reinforcement learning from human feedback. Our approach is minimalist in that it does not require training a reward model nor unstable adversarial training and is therefore rather simple to implement. Our approach is maximalist in that it provably handles non-Markovian, intransitive, and stochastic preferences while being robust to the compounding errors that plague offline approaches to sequential prediction. To achieve the preceding qualities, we build upon the concept of a Minimax Winner (MW), a notion of preference aggregation from the social choice theory literature that frames learning from preferences as a zero-sum game between two policies. By leveraging the symmetry of this game, we prove that rather than using the traditional technique of dueling two policies to compute the MW, we can simply have a single agent play against itself while maintaining strong convergence guarantees. Practically, this corresponds to sampling multiple trajectories from a policy, asking a preference or teacher model to compare them, and then using the proportion of wins as the reward for a particular trajectory. We demonstrate that on a suite of continuous control tasks, we are able to learn significantly more efficiently than reward-model based approaches while maintaining robustness to the intransitive and stochastic preferences that frequently occur in practice when aggregating human judgments.

Details

ICML Conference 2023 Conference Paper

Best of Both Worlds Policy Optimization

  • Christoph Dann
  • Chen-Yu Wei
  • Julian Zimmert

Policy optimization methods are popular reinforcement learning algorithms in practice and recent works have build theoretical foundation for them by proving $\sqrt{T}$ regret bounds even when the losses are adversarial. Such bounds are tight in the worst case but often overly pessimistic. In this work, we show that by carefully designing the regularizer, bonus terms, and learning rates, one can achieve a more favorable $\text{polylog}(T)$ regret bound when the losses are stochastic, without sacrificing the worst-case guarantee in the adversarial regime. Specifically, we show the first best of both worlds guarantee for policy optimization in tabular MDPs by leveraging either a Tsallis entropy or a Shannon entropy regularizer. Then we show that under known transitions, we can further obtain a first-order regret bound in the adversarial regime by leveraging the log barrier regularizer.

Details

ICML Conference 2023 Conference Paper

Learning in POMDPs is Sample-Efficient with Hindsight Observability

  • Jonathan Lee 0002
  • Alekh Agarwal
  • Christoph Dann
  • Tong Zhang 0001

POMDPs capture a broad class of decision making problems, but hardness results suggest that learning is intractable even in simple settings due to the inherent partial observability. However, in many realistic problems, more information is either revealed or can be computed during some point of the learning process. Motivated by diverse applications ranging from robotics to data center scheduling, we formulate a Hindsight Observable Markov Decision Process (HOMDP) as a POMDP where the latent states are revealed to the learner in hindsight and only during training. We introduce new algorithms for the tabular and function approximation settings that are provably sample-efficient with hindsight observability, even in POMDPs that would otherwise be statistically intractable. We give a lower bound showing that the tabular algorithm is optimal in its dependence on latent state and observation cardinalities.

Details

ICML Conference 2023 Conference Paper

Reinforcement Learning Can Be More Efficient with Multiple Rewards

  • Christoph Dann
  • Yishay Mansour
  • Mehryar Mohri

Reward design is one of the most critical and challenging aspects when formulating a task as a reinforcement learning (RL) problem. In practice, it often takes several attempts of reward specification and learning with it in order to find one that leads to sample-efficient learning of the desired behavior. Instead, in this work, we study whether directly incorporating multiple alternate reward formulations of the same task in a single agent can lead to faster learning. We analyze multi-reward extensions of action-elimination algorithms and prove more favorable instance-dependent regret bounds compared to their single-reward counterparts, both in multi-armed bandits and in tabular Markov decision processes. Our bounds scale for each state-action pair with the inverse of the largest gap among all reward functions. This suggests that learning with multiple rewards can indeed be more sample-efficient, as long as the rewards agree on an optimal policy. We further prove that when rewards do not agree, multi-reward action elimination in multi-armed bandits still learns a policy that is good across all reward functions.

Details

NeurIPS Conference 2022 Conference Paper

Best of Both Worlds Model Selection

  • Aldo Pacchiano
  • Christoph Dann
  • Claudio Gentile

We study the problem of model selection in bandit scenarios in the presence of nested policy classes, with the goal of obtaining simultaneous adversarial and stochastic (``best of both worlds") high-probability regret guarantees. Our approach requires that each base learner comes with a candidate regret bound that may or may not hold, while our meta algorithm plays each base learner according to a schedule that keeps the base learner's candidate regret bounds balanced until they are detected to violate their guarantees. We develop careful mis-specification tests specifically designed to blend the above model selection criterion with the ability to leverage the (potentially benign) nature of the environment. We recover the model selection guarantees of the CORRAL algorithm for adversarial environments, but with the additional benefit of achieving high probability regret bounds. More importantly, our model selection results also hold simultaneously in stochastic environments under gap assumptions. These are the first theoretical results that achieve best-of-both world (stochastic and adversarial) guarantees while performing model selection in contextual bandit scenarios.

PDF Details

ICML Conference 2022 Conference Paper

Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation

  • Christoph Dann
  • Yishay Mansour
  • Mehryar Mohri
  • Ayush Sekhari
  • Karthik Sridharan

Myopic exploration policies such as epsilon-greedy, softmax, or Gaussian noise fail to explore efficiently in some reinforcement learning tasks and yet, they perform well in many others. In fact, in practice, they are often selected as the top choices, due to their simplicity. But, for what tasks do such policies succeed? Can we give theoretical guarantees for their favorable performance? These crucial questions have been scarcely investigated, despite the prominent practical importance of these policies. This paper presents a theoretical analysis of such policies and provides the first regret and sample-complexity bounds for reinforcement learning with myopic exploration. Our results apply to value-function-based algorithms in episodic MDPs with bounded Bellman Eluder dimension. We propose a new complexity measure called myopic exploration gap, denoted by alpha, that captures a structural property of the MDP, the exploration policy and the given value function class. We show that the sample-complexity of myopic exploration scales quadratically with the inverse of this quantity, 1 / alpha^2. We further demonstrate through concrete examples that myopic exploration gap is indeed favorable in several tasks where myopic exploration succeeds, due to the corresponding dynamics and reward structure.

Details

CLeaR Conference 2022 Conference Paper

Same Cause; Different Effects in the Brain

  • Mariya Toneva
  • Jennifer Williams
  • Anand Bollu
  • Christoph Dann
  • Leila Wehbe

To study information processing in the brain, neuroscientists manipulate experimental stimuli while recording participant brain activity. They can then use encoding models to find out which brain "zone" (e. g. which region of interest, volume pixel or electrophysiology sensor) is predicted from the stimulus properties. Given the assumptions underlying this setup, when stimulus properties are predictive of the activity in a zone, these properties are understood to cause activity in that zone. In recent years, researchers have used neural networks to construct representations that capture the diverse properties of complex stimuli, such as natural language or natural images. Encoding models built using these high-dimensional representations are often able to significantly predict the activity in large swathes of cortex, suggesting that the activity in all these brain zones is caused by stimulus properties captured in the representation. It is then natural to ask: "Is the activity in these different brain zones caused by the stimulus properties in the same way? " In neuroscientific terms, this corresponds to asking if these different zones process the stimulus properties in the same way. Here, we propose a new framework that enables researchers to ask if the properties of a stimulus affect two brain zones in the same way. We use simulated data and two real fMRI datasets with complex naturalistic stimuli to show that our framework enables us to make such inferences. Our inferences are strikingly consistent between the two datasets, indicating that the proposed framework is a promising new tool for neuroscientists to understand how information is processed in the brain.

PDF Details

NeurIPS Conference 2021 Conference Paper

A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning

  • Christoph Dann
  • Mehryar Mohri
  • Tong Zhang
  • Julian Zimmert

Thompson Sampling is one of the most effective methods for contextual bandits and has been generalized to posterior sampling for certain MDP settings. However, existing posterior sampling methods for reinforcement learning are limited by being model-based or lack worst-case theoretical guarantees beyond linear MDPs. This paper proposes a new model-free formulation of posterior sampling that applies to more general episodic reinforcement learning problems with theoretical guarantees. We introduce novel proof techniques to show that under suitable conditions, the worst-case regret of our posterior sampling method matches the best known results of optimization based methods. In the linear MDP setting with dimension, the regret of our algorithm scales linearly with the dimension as compared to a quadratic dependence of the existing posterior sampling-based exploration algorithms.

PDF Details

NeurIPS Conference 2021 Conference Paper

Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations

  • Ayush Sekhari
  • Christoph Dann
  • Mehryar Mohri
  • Yishay Mansour
  • Karthik Sridharan

There have been many recent advances on provably efficient Reinforcement Learning (RL) in problems with rich observation spaces. However, all these works share a strong realizability assumption about the optimal value function of the true MDP. Such realizability assumptions are often too strong to hold in practice. In this work, we consider the more realistic setting of agnostic RL with rich observation spaces and a fixed class of policies $\Pi$ that may not contain any near-optimal policy. We provide an algorithm for this setting whose error is bounded in terms of the rank $d$ of the underlying MDP. Specifically, our algorithm enjoys a sample complexity bound of $\widetilde{O}\left((H^{4d} K^{3d} \log |\Pi|)/\epsilon^2\right)$ where $H$ is the length of episodes, $K$ is the number of actions and $\epsilon>0$ is the desired sub-optimality. We also provide a nearly matching lower bound for this agnostic setting that shows that the exponential dependence on rank is unavoidable, without further assumptions.

PDF Details

NeurIPS Conference 2021 Conference Paper

Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning

  • Christoph Dann
  • Teodor Vanislavov Marinov
  • Mehryar Mohri
  • Julian Zimmert

We provide improved gap-dependent regret bounds for reinforcement learning in finite episodic Markov decision processes. Compared to prior work, our bounds depend on alternative definitions of gaps. These definitions are based on the insight that, in order to achieve a favorable regret, an algorithm does not need to learn how to behave optimally in states that are not reached by an optimal policy. We prove tighter upper regret bounds for optimistic algorithms and accompany them with new information-theoretic lower bounds for a large class of MDPs. Our results show that optimistic algorithms can not achieve the information-theoretic lower bounds even in deterministic MDPs unless there is a unique optimal policy.

PDF Details

ICML Conference 2021 Conference Paper

Dynamic Balancing for Model Selection in Bandits and RL

  • Ashok Cutkosky
  • Christoph Dann
  • Abhimanyu Das
  • Claudio Gentile
  • Aldo Pacchiano
  • Manish Purohit

We propose a framework for model selection by combining base algorithms in stochastic bandits and reinforcement learning. We require a candidate regret bound for each base algorithm that may or may not hold. We select base algorithms to play in each round using a “balancing condition” on the candidate regret bounds. Our approach simultaneously recovers previous worst-case regret bounds, while also obtaining much smaller regret in natural scenarios when some base learners significantly exceed their candidate bounds. Our framework is relevant in many settings, including linear bandits and MDPs with nested function classes, linear bandits with unknown misspecification, and tuning confidence parameters of algorithms such as LinUCB. Moreover, unlike recent efforts in model selection for linear stochastic bandits, our approach can be extended to consider adversarial rather than stochastic contexts.

Details

NeurIPS Conference 2021 Conference Paper

Neural Active Learning with Performance Guarantees

  • Zhilei Wang
  • Pranjal Awasthi
  • Christoph Dann
  • Ayush Sekhari
  • Claudio Gentile

We investigate the problem of active learning in the streaming setting in non-parametric regimes, where the labels are stochastically generated from a class of functions on which we make no assumptions whatsoever. We rely on recently proposed Neural Tangent Kernel (NTK) approximation tools to construct a suitable neural embedding that determines the feature space the algorithm operates on and the learned model computed atop. Since the shape of the label requesting threshold is tightly related to the complexity of the function to be learned, which is a-priori unknown, we also derive a version of the algorithm which is agnostic to any prior knowledge. This algorithm relies on a regret balancing scheme to solve the resulting online model selection problem, and is computationally efficient. We prove joint guarantees on the cumulative regret and number of requested labels which depend on the complexity of the labeling function at hand. In the linear case, these guarantees recover known minimax results of the generalization error as a function of the label complexity in a standard statistical learning setting.

PDF Details

AAAI Conference 2020 Conference Paper

Being Optimistic to Be Conservative: Quickly Learning a CVaR Policy

  • Ramtin Keramati
  • Christoph Dann
  • Alex Tamkin
  • Emma Brunskill

While maximizing expected return is the goal in most reinforcement learning approaches, risk-sensitive objectives such as conditional value at risk (CVaR) are more suitable for many high-stakes applications. However, relatively little is known about how to explore to quickly learn policies with good CVaR. In this paper, we present the first algorithm for sample-efficient learning of CVaR-optimal policies in Markov decision processes based on the optimism in the face of uncertainty principle. This method relies on a novel optimistic version of the distributional Bellman operator that moves probability mass from the lower to the upper tail of the return distribution. We prove asymptotic convergence and optimism of this operator for the tabular policy evaluation case. We further demonstrate that our algorithm finds CVaRoptimal policies substantially faster than existing baselines in several simulated environments with discrete and continuous state spaces.

PDF Details

NeurIPS Conference 2020 Conference Paper

Reinforcement Learning with Feedback Graphs

  • Christoph Dann
  • Yishay Mansour
  • Mehryar Mohri
  • Ayush Sekhari
  • Karthik Sridharan

We study RL in the tabular MDP setting where the agent receives additional observations per step in the form of transitions samples. Such additional observations can be provided in many tasks by auxiliary sensors or by leveraging prior knowledge about the environment (e. g. , when certain actions yield similar outcome). We formalize this setting using a feedback graph over state-action pairs and show that model-based algorithms can incorporate additional observations for more sample-efficient learning. We give a regret bound that predominantly depends on the size of the maximum acyclic subgraph of the feedback graph, in contrast with a polynomial dependency on the number of states and actions in the absence of side observations. Finally, we highlight fundamental challenges for leveraging a small dominating set of the feedback graph, as compared to the well-studied bandit setting, and propose a new algorithm that can use such a dominating set to learn a near-optimal policy faster.

PDF Details

ICML Conference 2019 Conference Paper

Policy Certificates: Towards Accountable Reinforcement Learning

  • Christoph Dann
  • Lihong Li 0001
  • Wei Wei
  • Emma Brunskill

The performance of a reinforcement learning algorithm can vary drastically during learning because of exploration. Existing algorithms provide little information about the quality of their current policy before executing it, and thus have limited use in high-stakes applications like healthcare. We address this lack of accountability by proposing that algorithms output policy certificates. These certificates bound the sub-optimality and return of the policy in the next episode, allowing humans to intervene when the certified quality is not satisfactory. We further introduce two new algorithms with certificates and present a new framework for theoretical analysis that guarantees the quality of their policies and certificates. For tabular MDPs, we show that computing certificates can even improve the sample-efficiency of optimism-based exploration. As a result, one of our algorithms is the first to achieve minimax-optimal PAC bounds up to lower-order terms, and this algorithm also matches (and in some settings slightly improves upon) existing minimax regret bounds.

Details

ICML Conference 2018 Conference Paper

Decoupling Gradient-Like Learning Rules from Representations

  • Philip S. Thomas
  • Christoph Dann
  • Emma Brunskill

In machine learning, learning often corresponds to changing the parameters of a parameterized function. A learning rule is an algorithm or mathematical expression that specifies precisely how the parameters should be changed. When creating a machine learning system, we must make two decisions: what representation should be used (i. e. , what parameterized function should be used) and what learning rule should be used to search through the resulting set of representable functions. In this paper we focus on gradient-like learning rules, wherein these two decisions are coupled in a subtle (and often unintentional) way. Using most learning rules, these two decisions are coupled in a subtle (and often unintentional) way. That is, using the same learning rule with two different representations that can represent the same sets of functions can result in two different outcomes. After arguing that this coupling is undesirable, particularly when using neural networks, we present a method for partially decoupling these two decisions for a broad class of gradient-like learning rules that span unsupervised learning, reinforcement learning, and supervised learning.

Details

NeurIPS Conference 2018 Conference Paper

On Oracle-Efficient PAC RL with Rich Observations

  • Christoph Dann
  • Nan Jiang
  • Akshay Krishnamurthy
  • Alekh Agarwal
  • John Langford
  • Robert Schapire

We study the computational tractability of PAC reinforcement learning with rich observations. We present new provably sample-efficient algorithms for environments with deterministic hidden state dynamics and stochastic rich observations. These methods operate in an oracle model of computation -- accessing policy and value function classes exclusively through standard optimization primitives -- and therefore represent computationally efficient alternatives to prior algorithms that require enumeration. With stochastic hidden state dynamics, we prove that the only known sample-efficient algorithm, OLIVE, cannot be implemented in the oracle model. We also present several examples that illustrate fundamental challenges of tractable PAC reinforcement learning in such general settings.

PDF Details

RLDM Conference 2017 Conference Abstract

Sample Efficient Policy Search for Optimal Stopping Domains

  • Karan Goel
  • Christoph Dann
  • Rika Antonova
  • Emma Brunskill

Arising naturally in many fields, optimal stopping problems consider the question of deciding when to stop an observation-generating process. Classical examples include house-selling, the problem of deciding whether to sell a house given a bid and a history of past offers, and the secretary problem of deciding whether to hire an applicant or not, given that future applicants may be of higher quality. We examine the problem of simultaneously learning and planning in optimal stopping domains with unknown dynamics, when data is collected directly from the environment, as is common in real-world applications, rather than from a simulator. We propose Gather Full, Search and Execute, a simple and flexible model-free policy search method that leverages problem structure to improve efficiency of data reuse. Using a simple policy evaluation trick, GFSE evaluates every policy in an input policy class using all of the collected data and outputs a policy that has a near-optimal value in the policy class. To achieve this, we bound the sample complexity of GFSE to guarantee that policy value estimates are uniformly close to their true values with high probability. Our results tighten existing PAC bounds for general Partially Observable Markov Decision Processes (POMDPs) to achieve logarithmic dependence on horizon length for our setting, in contrast to the exponential horizon length dependence for learning in general POMDPs. We demonstrate the benefit of our method against prevalent model-based and model-free approaches on a simulated student tutoring domain, and a ticket purchase domain with real airline pricing data.

PDF Details

IJCAI Conference 2017 Conference Paper

Sample Efficient Policy Search for Optimal Stopping Domains

  • Karan Goel
  • Christoph Dann
  • Emma Brunskill

Optimal stopping problems consider the question of deciding when to stop an observation-generating process in order to maximize a return. We examine the problem of simultaneously learning and planning in such domains, when data is collected directly from the environment. We propose GFSE, a simple and flexible model-free policy search method that reuses data for sample efficiency by leveraging problem structure. We bound the sample complexity of our approach to guarantee uniform convergence of policy value estimates, tightening existing PAC bounds to achieve logarithmic dependence on horizon length for our setting. We also examine the benefit of our method against prevalent model-based and model-free approaches on 3 domains taken from diverse fields.

PDF Details

RLDM Conference 2017 Conference Abstract

UBEV - A More Practical Algorithm for Episodic RL with Near-Optimal PAC and Regret Guar- antees

  • Christoph Dann
  • Tor Lattimore
  • Emma Brunskill

We present UBEV, a simple and efficient reinforcement learning algorithm for fixed-horizon episodic Markov decision processes. The main contribution is a proof that UBEV enjoys a sample-complexity bound that holds for all accuracy levels simultaneously with high probability, and matches the lower bound except for logarithmic terms and one factor of the horizon. A consequence of the fact that our sample- complexity bound holds for all accuracy levels is that the new algorithm achieves a sub-linear regret of O(sqrt(SAT)), which is the first time the dependence on the size of the state space has provably appeared inside the square root. A brief empirical evaluation shows that UBEV is practically superior to existing algorithms with known sample-complexity guarantees.

PDF Details

NeurIPS Conference 2017 Conference Paper

Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning

  • Christoph Dann
  • Tor Lattimore
  • Emma Brunskill

Statistical performance bounds for reinforcement learning (RL) algorithms can be critical for high-stakes applications like healthcare. This paper introduces a new framework for theoretically measuring the performance of such algorithms called Uniform-PAC, which is a strengthening of the classical Probably Approximately Correct (PAC) framework. In contrast to the PAC framework, the uniform version may be used to derive high probability regret guarantees and so forms a bridge between the two setups that has been missing in the literature. We demonstrate the benefits of the new framework for finite-state episodic MDPs with a new algorithm that is Uniform-PAC and simultaneously achieves optimal regret and PAC guarantees except for a factor of the horizon.

PDF Details

ICML Conference 2016 Conference Paper

Energetic Natural Gradient Descent

  • Philip S. Thomas
  • Bruno Castro da Silva
  • Christoph Dann
  • Emma Brunskill

We propose a new class of algorithms for minimizing or maximizing functions of parametric probabilistic models. These new algorithms are natural gradient algorithms that leverage more information than prior methods by using a new metric tensor in place of the commonly used Fisher information matrix. This new metric tensor is derived by computing directions of steepest ascent where the distance between distributions is measured using an approximation of energy distance (as opposed to Kullback-Leibler divergence, which produces the Fisher information matrix), and so we refer to our new ascent direction as the energetic natural gradient.

Details

EWRL Workshop 2016 Workshop Paper

Memory Lens: How Much Memory Does an Agent Use?

  • Christoph Dann
  • Katja Hofmann
  • Sebastian Nowozin

We propose a new method to study the internal memory used by reinforcement learning policies. We estimate the amount of relevant past information by estimating mutual information between behavior histories and the current action of an agent. We perform this estimation in the passive setting, that is, we do not intervene but merely observe the natural behavior of the agent. Moreover, we provide a theoretical justi cation for our approach by showing that it yields an implementation-independent lower bound on the minimal memory capacity of any agent that implement the observed policy. We demonstrate our approach by estimating the use of memory of DQN policies on concatenated Atari frames, demonstrating sharply di erent use of memory across 49 games. The study of memory as information that ows from the past to the current action opens avenues to understand and improve successful reinforcement learning algorithms.

PDF Details

ICAPS Conference 2015 Conference Paper

Policy Evaluation with Temporal Differences: A Survey and Comparison (Extended Abstract)

  • Christoph Dann
  • Gerhard Neumann
  • Jan Peters 0001

Value functions are an essential tool for solving sequential decision making problems such as Markov decision processes (MDPs). Computing the value function for a given policy (policy evaluation) is not only important for determining the quality of the policy but also a key step in prominent policy-iteration-type algorithms. In common settings where a model of the Markov decision process is not available or too complex to handle directly, an approximation of the value function is usually estimated from samples of the process. Linearly parameterized estimates are often preferred due to their simplicity and strong stability guarantees. Since the late 1980s, research on policy evaluation in these scenarios has been dominated by temporal-difference (TD) methods because of their data-efficiency. However, several core issues have only been tackled recently, including stability guarantees for off-policy estimation where the samples are not generated by the policy to evaluate. Together with improving sample efficiency and probabilistic treatment of uncertainty in the value estimates, these efforts have lead to numerous new temporal-difference algorithms. These methods are scattered over the literature and usually only compared to most similar approaches. The article therefore aims at presenting the state of the art of policy evaluation with temporal differences and linearly parameterized value functions in discounted MDPs as well as a more comprehensive comparison of these approaches. We put the algorithms in a unified framework of function optimization, with focus on surrogate cost functions and optimization strategies, to identify similarities and differences between the methods. In addition, important extensions of the base methods such as off-policy estimation and eligibility traces for better bias-variance trade-off, as well as regularization in high dimensional feature spaces, are discussed.

Details

RLDM Conference 2015 Conference Abstract

RLPy: A Value-Function-Based Reinforcement Learning Framework for Education and Re- search

  • Alborz Geramifard
  • Christoph Dann
  • Robert Klein
  • William Dabney
  • Jonathan How

RLPy (http: //acl. mit. edu/rlpy ) is an open-source reinforcement learning (RL) package with the focus on linear function approximation for value-based techniques and planning problems with discrete actions. The aim of this package is to: a) boost the RL education process, and b) enable crisp and easy to debug experimentation with existing and new methods. RLPy achieves these goals by providing a rich library of fine-grained, easily exchangeable components for learning agents (e. g. , policies or representations of value functions). Developed in Python, RLPy allows fast prototyping, yet harnesses the power of state-of- the-art numerical libraries such as scipy and parallelization to scale to large problems. Furthermore, RLPy is self-contained. The package includes code profiling, domain visualizations, and data analysis. Finally RLPy is available under the Modified BSD License that allows integration with 3rd party softwares with little legal entanglement.

PDF Details

JMLR Journal 2015 Journal Article

RLPy: A Value-Function-Based Reinforcement Learning Framework for Education and Research

  • Alborz Geramifard
  • Christoph Dann
  • Robert H. Klein
  • William Dabney
  • Jonathan P. How

RLPy is an object-oriented reinforcement learning software package with a focus on value-function-based methods using linear function approximation and discrete actions. The framework was designed for both educational and research purposes. It provides a rich library of fine-grained, easily exchangeable components for learning agents (e.g., policies or representations of value functions), facilitating recently increased specialization in reinforcement learning. RLPy is written in Python to allow fast prototyping, but is also suitable for large-scale experiments through its built-in support for optimized numerical libraries and parallelization. Code profiling, domain visualizations, and data analysis are integrated in a self-contained package available under the Modified BSD License at github.com/rlpy/rlpy. All of these properties allow users to compare various reinforcement learning algorithms with little effort. [abs] [ pdf ][ bib ] [ code ] &copy JMLR 2015. ( edit, beta )

PDF Details

NeurIPS Conference 2015 Conference Paper

Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning

  • Christoph Dann
  • Emma Brunskill

Recently, there has been significant progress in understanding reinforcement learning in discounted infinite-horizon Markov decision processes (MDPs) by deriving tight sample complexity bounds. However, in many real-world applications, an interactive learning agent operates for a fixed or bounded period of time, for example tutoring students for exams or handling customer service requests. Such scenarios can often be better treated as episodic fixed-horizon MDPs, for which only looser bounds on the sample complexity exist. A natural notion of sample complexity in this setting is the number of episodes required to guarantee a certain performance with high probability (PAC guarantee). In this paper, we derive an upper PAC bound of order O(|S|²|A|H² log(1/δ)/ɛ²) and a lower PAC bound Ω(|S||A|H² log(1/(δ+c))/ɛ²) (ignoring log-terms) that match up to log-terms and an additional linear dependency on the number of states |S|. The lower bound is the first of its kind for this setting. Our upper bound leverages Bernstein's inequality to improve on previous bounds for episodic finite-horizon MDPs which have a time-horizon dependency of at least H³.

PDF Details

NeurIPS Conference 2015 Conference Paper

The Human Kernel

  • Andrew Wilson
  • Christoph Dann
  • Chris Lucas
  • Eric Xing

Bayesian nonparametric models, such as Gaussian processes, provide a compelling framework for automatic statistical modelling: these models have a high degree of flexibility, and automatically calibrated complexity. However, automating human expertise remains elusive; for example, Gaussian processes with standard kernels struggle on function extrapolation problems that are trivial for human learners. In this paper, we create function extrapolation problems and acquire human responses, and then design a kernel learning framework to reverse engineer the inductive biases of human learners across a set of behavioral experiments. We use the learned kernels to gain psychological insights and to extrapolate in human-like ways that go beyond traditional stationary and polynomial kernels. Finally, we investigate Occam's razor in human and Gaussian process based function learning.

PDF Details

JMLR Journal 2014 Journal Article

Policy Evaluation with Temporal Differences: A Survey and Comparison

  • Christoph Dann
  • Gerhard Neumann
  • Jan Peters

Policy evaluation is an essential step in most reinforcement learning approaches. It yields a value function, the quality assessment of states for a given policy, which can be used in a policy improvement step. Since the late 1980s, this research area has been dominated by temporal-difference (TD) methods due to their data-efficiency. However, core issues such as stability guarantees in the off-policy scenario, improved sample efficiency and probabilistic treatment of the uncertainty in the estimates have only been tackled recently, which has led to a large number of new approaches. This paper aims at making these new developments accessible in a concise overview, with foci on underlying cost functions, the off-policy scenario as well as on regularization in high dimensional feature spaces. By presenting the first extensive, systematic comparative evaluations comparing TD, LSTD, LSPE, FPKF, the residual- gradient algorithm, Bellman residual minimization, GTD, GTD2 and TDC, we shed light on the strengths and weaknesses of the methods. Moreover, we present alternative versions of LSTD and LSPE with drastically improved off-policy performance. [abs] [ pdf ][ bib ] &copy JMLR 2014. ( edit, beta )

PDF Details

RLDM Conference 2013 Conference Abstract

Off-Policy Learning Combined with Automatic Feature Expansion for Solving Large MDPs

  • Alborz Geramifard
  • Christoph Dann
  • Jonathan How

Reinforcement learning (RL) techniques with cheap computational complexity and minimal hand-tuning that scale to large problems are highly desired among RL practitioners. Linear function ap- proximation has scaled existing RL techniques to large problems [Lagoudakis and Parr, 2003; Silver et al. , 2012], however that technique has two major drawbacks: 1) conventional off-policy techniques such as Q- Learning can be unstable when combined with linear function approximation [Baird, 1995] and 2) finding the “right” set of features for approximation can be challenging. The first drawback has been recently addressed with the introduction of the Greedy-GQ algorithm, a con- vergent extension of Q-Learning [Maei et al. , 2010]. The second drawback led to representation expansion techniques that add new features along the learning process [Geramifard et al. , 2011; Keller et al. , 2006; Parr et al. , 2007]. Amongst these techniques, incremental Feature Dependency Discovery (iFDD) has shown great potential as it scaled to large problems while enjoying convergence results [Geramifard et al. , 2011]. Recently, iFDD+ [Geramifard et al. , 2013b] improved the performance of iFDD in the prediction problem while outperforming the previous state-of-the-art batch expansion technique OMP-TD [Painter-Wakefield and Parr, 2012]. This paper connects Greedy-GQ learning with iFDD+ and, for the first time, introduces an online off-policy learning with automatic feature expansion technique. Given sparse features, the new algorithm has per- time-step complexity independent of the total number of features, while for most existing techniques feature discovery is at least quadratic in the number features [Keller et al. , 2006; Parr et al. , 2007]. Empirical results across 3 domains with sizes up to 77 billion state-action pairs verify the scalability of our new approach.

PDF Details
v2026.09.13