Morteza Ibrahimi

UAI Conference 2023 Conference Paper

Approximate Thompson Sampling via Epistemic Neural Networks

• Ian Osband
• Zheng Wen 0002
• Seyed Mohammad Asghari
• Vikranth Dwaracherla
• Morteza Ibrahimi
• Xiuyuan Lu
• Benjamin Van Roy

Thompson sampling (TS) is a popular heuristic for action selection, but it requires sampling from a posterior distribution. Unfortunately, this can become computationally intractable in complex environments, such as those modeled using neural networks. Approximate posterior samples can produce effective actions, but only if they reasonably approximate joint predictive distributions of outputs across inputs. Notably, accuracy of marginal predictive distributions does not suffice. Epistemic neural networks (ENNs) are designed to produce accurate joint predictive distributions. We compare a range of ENNs through computational experiments that assess their performance in approximating TS across bandit and reinforcement learning environments. The results indicate that ENNs serve this purpose well and illustrate how the quality of joint predictive distributions drives performance. Further, we demonstrate that the epinet – a small additive network that estimates uncertainty – matches the performance of large ensembles at orders of magnitude lower computational cost. This enables effective application of TS with computation that scales gracefully to complex environments.

NeurIPS Conference 2023 Conference Paper

Epistemic Neural Networks

• Ian Osband
• Zheng Wen
• Seyed Mohammad Asghari
• Vikranth Dwaracherla
• Morteza Ibrahimi
• Xiuyuan Lu
• Benjamin Van Roy

Intelligence relies on an agent's knowledge of what it does not know. This capability can be assessed based on the quality of joint predictions of labels across multiple inputs. In principle, ensemble-based approaches can produce effective joint predictions, but the computational costs of large ensembles become prohibitive. We introduce the epinet: an architecture that can supplement any conventional neural network, including large pretrained models, and can be trained with modest incremental computation to estimate uncertainty. With an epinet, conventional neural networks outperform very large ensembles, consisting of hundreds or more particles, with orders of magnitude less computation. The epinet does not fit the traditional framework of Bayesian neural networks. To accommodate development of approaches beyond BNNs, such as the epinet, we introduce the epistemic neural network (ENN) as a general interface for models that produce joint predictions.

NeurIPS Conference 2022 Conference Paper

The Neural Testbed: Evaluating Joint Predictions

• Ian Osband
• Zheng Wen
• Seyed Mohammad Asghari
• Vikranth Dwaracherla
• Xiuyuan Lu
• Morteza Ibrahimi
• Dieterich Lawson
• Botao Hao

Predictive distributions quantify uncertainties ignored by point estimates. This paper introduces The Neural Testbed: an open source benchmark for controlled and principled evaluation of agents that generate such predictions. Crucially, the testbed assesses agents not only on the quality of their marginal predictions per input, but also on their joint predictions across many inputs. We evaluate a range of agents using a simple neural network data generating process. Our results indicate that some popular Bayesian deep learning agents do not fare well with joint predictions, even when they can produce accurate marginal predictions. We also show that the quality of joint predictions drives performance in downstream decision tasks. We find these results are robust across choice a wide range of generative models, and highlight the practical importance of joint predictions to the community.

ICLR Conference 2020 Conference Paper

Hypermodels for Exploration

• Vikranth Dwaracherla
• Xiuyuan Lu
• Morteza Ibrahimi
• Ian Osband
• Zheng Wen 0002
• Benjamin Van Roy

We study the use of hypermodels to represent epistemic uncertainty and guide exploration. This generalizes and extends the use of ensembles to approximate Thompson sampling. The computational cost of training an ensemble grows with its size, and as such, prior work has typically been limited to ensembles with tens of elements. We show that alternative hypermodels can enjoy dramatic efficiency gains, enabling behavior that would otherwise require hundreds or thousands of elements, and even succeed in situations where ensemble methods fail to learn regardless of size. This allows more accurate approximation of Thompson sampling as well as use of more sophisticated exploration schemes. In particular, we consider an approximate form of information-directed sampling and demonstrate performance gains relative to Thompson sampling. As alternatives to ensembles, we consider linear and neural network hypermodels, also known as hypernetworks. We prove that, with neural network base models, a linear hypermodel can represent essentially any distribution over functions, and as such, hypernetworks do not extend what can be represented.

NeurIPS Conference 2020 Conference Paper

On Efficiency in Hierarchical Reinforcement Learning

• Zheng Wen
• Doina Precup
• Morteza Ibrahimi
• Andre Barreto
• Benjamin Van Roy
• Satinder Singh

Hierarchical Reinforcement Learning (HRL) approaches promise to provide more efficient solutions to sequential decision making problems, both in terms of statistical as well as computational efficiency. While this has been demonstrated empirically over time in a variety of tasks, theoretical results quantifying the benefits of such methods are still few and far between. In this paper, we discuss the kind of structure in a Markov decision process which gives rise to efficient HRL methods. Specifically, we formalize the intuition that HRL can exploit well repeating "subMDPs", with similar reward and transition structure. We show that, under reasonable assumptions, a model-based Thompson sampling-style HRL algorithm that exploits this structure is statistically efficient, as established through a finite-time regret bound. We also establish conditions under which planning with structure-induced options is near-optimal and computationally efficient.

RLDM Conference 2019 Conference Abstract

Posterior Sampling Networks

• Vikranth Reddy Dwaracherla
• Benjamin Van Roy
• Morteza Ibrahimi

In this article, we propose a new approach for efficiently generating approximate samples from a posterior over complex models such as neural networks, induced by a prior distribution over the model family and a set of input-output data pairs. While there are other applications, we are particularly motivated in this work by its application in Thompson sampling, a technique for efficient exploration in reinforcement learning. Thompson sampling requires sampling from a posterior distribution over models, which can be achieved in special cases under restrictive assumptions. Approximations are called for when this can not be done exactly. Ensemble sampling offers an approach that is viable in complex settings such as deep reinforcement learning. However, ensemble sampling requires fitting a substantial number of separate mod- els, which although tractable is far more computationally demanding than one would hope. We propose a new approach that is based on point estimation in an ‘elevated model space’. This elevated model space is made up of models that map the input space and a d-dimensional Euclidean index space to the output space. After learning the mapping, by sampling a random index, one effectively samples a random neural network that maps predictors to output. Our approach aims to learn a mapping so that this random model is approximately distributed according to the posterior over neural networks conditioned on observed data. As a sanity check, we prove that in the special case of linear models with Gaussian noise our approach can generate exact samples from the posterior. We also demonstrate empirically the efficacy of our approach in the context of bandit learning with linear and neural network models.

NeurIPS Conference 2012 Conference Paper

Efficient Reinforcement Learning for High Dimensional Linear Quadratic Systems

• Morteza Ibrahimi
• Adel Javanmard
• Benjamin Roy

We study the problem of adaptive control of a high dimensional linear quadratic (LQ) system. Previous work established the asymptotic convergence to an optimal controller for various adaptive control schemes. More recently, an asymptotic regret bound of $\tilde{O}(\sqrt{T})$ was shown for $T \gg p$ where $p$ is the dimension of the state space. In this work we consider the case where the matrices describing the dynamic of the LQ system are sparse and their dimensions are large. We present an adaptive control scheme that for $p \gg 1$ and $T \gg \polylog(p)$ achieves a regret bound of $\tilde{O}(p \sqrt{T})$. In particular, our algorithm has an average cost of $(1+\eps)$ times the optimum cost after $T = \polylog(p) O(1/\eps^2)$. This is in comparison to previous work on the dense dynamics where the algorithm needs $\Omega(p)$ samples before it can estimate the unknown dynamic with any significant accuracy. We believe our result has prominent applications in the emerging area of computational advertising, in particular targeted online advertising and advertising in social networks.

SODA Conference 2012 Conference Paper

The set of solutions of random XORSAT formulae

• Morteza Ibrahimi
• Yash Kanoria
• Matt Kraning
• Andrea Montanari

NeurIPS Conference 2010 Conference Paper

Learning Networks of Stochastic Differential Equations

• José Pereira
• Morteza Ibrahimi
• Andrea Montanari

We consider linear models for stochastic dynamics. Any such model can be associated a network (namely a directed graph) describing which degrees of freedom interact under the dynamics. We tackle the problem of learning such a network from observation of the system trajectory over a time interval T. We analyse the l1-regularized least squares algorithm and, in the setting in which the underlying network is sparse, we prove performance guarantees that are uniform in the sampling rate as long as this is sufficiently high. This result substantiates the notion of a well defined ‘time complexity’ for the network inference problem.