Publications (78)
Optimal Resource Allocation with Semi-Bandit Feedback
Tor Lattimore, Koby Crammer, Csaba Szepesvári
We study a sequential resource allocation problem involving a fixed number of recurring jobs. At each time-step the manager should distribute available resources among the jobs in…
Information Directed Sampling for Sparse Linear Bandits
Botao Hao, Tor Lattimore, Wei Deng
Stochastic sparse linear bandits offer a practical model for high-dimensional online decision-making problems and have a rich information-regret structure. In this work we explore…
Free Lunch for Optimisation under the Universal Distribution
Tom Everitt, Tor Lattimore, Marcus Hutter
Function optimisation is a major challenge in computer science. The No Free Lunch theorems state that if all functions with the same histogram are assumed to be equally probable th…
Minimax Regret for Partial Monitoring: Infinite Outcomes and Rustichini's Regret
Tor Lattimore
We show that a version of the generalised information ratio of Lattimore and Gyorgy (2020) determines the asymptotic minimax regret for all finite-action partial monitoring games p…
Bounded Regret for Finite-Armed Structured Bandits
Tor Lattimore, Remi Munos
We study a new type of K-armed bandit problem where the expected return of one arm may depend on the returns of other arms. We present a new algorithm for this general class of pro…
A Diffusion Analysis of Policy Gradient for Stochastic Bandits
Tor Lattimore
We study a continuous-time diffusion approximation of policy gradient for -armed stochastic bandits. We prove that with a learning rate the regret is $O(k…
Iterative Budgeted Exponential Search
Malte Helmert, Tor Lattimore, Levi H. S. Lelis +2
We tackle two long-standing problems related to re-expansions in heuristic search algorithms. For graph search, A* can require expansions, where is the number of st…
Universal Prediction of Selected Bits
Tor Lattimore, Marcus Hutter, Vaibhav Gavane
Many learning tasks can be viewed as sequence prediction problems. For example, online classification can be converted to sequence prediction with the sequence being pairs of input…
Zooming Cautiously: Linear-Memory Heuristic Search With Node Expansion Guarantees
Laurent Orseau, Levi H. S. Lelis, Tor Lattimore
We introduce and analyze two parameter-free linear-memory tree search algorithms. Under mild assumptions we prove our algorithms are guaranteed to perform only a logarithmic factor…
Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities
Ruitong Huang, Tor Lattimore, András György +1
The follow the leader (FTL) algorithm, perhaps the simplest of all online learning algorithms, is known to perform well when the loss functions it is used on are convex and positiv…
Online Newton Method for Bandit Convex Optimisation
Hidde Fokkema, Dirk van der Hoeven, Tor Lattimore +1
We introduce a computationally efficient algorithm for zeroth-order bandit convex optimisation and prove that in the adversarial setting its regret is at most $d^{3.5} \sqrt{n} \ma…
A Second-Order Method for Stochastic Bandit Convex Optimisation
Tor Lattimore, András György
We introduce a simple and efficient algorithm for unconstrained zeroth-order stochastic convex bandits and prove its regret is at most $(1 + r/d)[d^{1.5} \sqrt{n} + d^3] polylog(n,…
Soft-Bayes: Prod for Mixtures of Experts with Log-Loss
Laurent Orseau, Tor Lattimore, Shane Legg
We consider prediction with expert advice under the log-loss with the goal of deriving efficient and robust algorithms. We argue that existing algorithms such as exponentiated grad…
Asymptotics of Continuous Bayes for Non-i.i.d. Sources
Tor Lattimore, Marcus Hutter
Clarke and Barron analysed the relative entropy between an i.i.d. source and a Bayesian mixture over a continuous class containing that source. In this paper a comparable result is…
Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost
Sanae Amani, Tor Lattimore, András György +1
We study distributed contextual linear bandits with stochastic contexts, where agents act cooperatively to solve a linear bandit-optimization problem with -dimensional featu…
The Sample-Complexity of General Reinforcement Learning
Tor Lattimore, Marcus Hutter, Peter Sunehag
We present a new algorithm for general reinforcement learning where the true environment is known to belong to a finite class of N arbitrary models. The algorithm is shown to be ne…
Information Directed Sampling for Linear Partial Monitoring
Johannes Kirschner, Tor Lattimore, Andreas Krause
Partial monitoring is a rich framework for sequential decision making under uncertainty that generalizes many well known bandit models, including linear, combinatorial and dueling…
Conservative Bandits
Yifan Wu, Roshan Shariff, Tor Lattimore +1
We study a novel multi-armed bandit problem that models the challenge faced by a company wishing to explore new strategies to maximize revenue whilst simultaneously maintaining the…
Linear Bandits with Stochastic Delayed Feedback
Claire Vernade, Alexandra Carpentier, Tor Lattimore +3
Stochastic linear bandits are a natural and well-studied model for structured exploration/exploitation problems and are widely used in applications such as online marketing and rec…
Variational Bayesian Optimistic Sampling
Brendan O'Donoghue, Tor Lattimore
We consider online sequential decision problems where an agent must balance exploration and exploitation. We derive a set of Bayesian `optimistic' policies which, in the stochastic…
Exploration by Optimisation in Partial Monitoring
Tor Lattimore, Csaba Szepesvari
We provide a simple and efficient algorithm for adversarial -action -outcome non-degenerate locally observable partial monitoring game for which the -round minimax regret…
Minimax Regret for Bandit Convex Optimisation of Ridge Functions
Tor Lattimore
We analyse adversarial bandit convex optimisation with an adversary that is restricted to playing functions of the form for convex $g_t : \math…
Improved Regret for Zeroth-Order Adversarial Bandit Convex Optimisation
Tor Lattimore
We prove that the information-theoretic upper bound on the minimax regret for zeroth-order adversarial bandit convex optimisation is at most , where $d…
Degenerate Feedback Loops in Recommender Systems
Ray Jiang, Silvia Chiappa, Tor Lattimore +2
Machine learning is used extensively in recommender systems deployed in products. The decisions made by these systems can influence user beliefs and preferences which in turn affec…
A Geometric Perspective on Optimal Representations for Reinforcement Learning
Marc G. Bellemare, Will Dabney, Robert Dadashi +6
We propose a new perspective on representation learning in reinforcement learning based on geometric properties of the space of value functions. We leverage this perspective to pro…
Regret Analysis of the Anytime Optimally Confident UCB Algorithm
Tor Lattimore
I introduce and analyse an anytime version of the Optimally Confident UCB (OCUCB) algorithm designed for minimising the cumulative regret in finite-armed stochastic bandits with su…
Bandit Phase Retrieval
Tor Lattimore, Botao Hao
We study a bandit version of phase retrieval where the learner chooses actions in the -dimensional unit ball and the expected reward is $\langle A_t, θ_\star\ra…
An Information-Theoretic Approach to Minimax Regret in Partial Monitoring
Tor Lattimore, Csaba Szepesvari
We prove a new minimax theorem connecting the worst-case Bayesian regret and minimax regret under partial monitoring with no assumptions on the space of signals or decisions of the…
A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosis
Tor Lattimore
Existing strategies for finite-armed stochastic bandits mostly depend on a parameter of scale that must be known in advance. Sometimes this is in the form of a bound on the payoffs…
Bandit Convex Optimisation
Tor Lattimore
Bandit convex optimisation is a fundamental framework for studying zeroth-order convex optimisation. This book covers the many tools used for this problem, including cutting plane…
Gated Linear Networks
Joel Veness, Tor Lattimore, David Budden +8
This paper presents a new family of backpropagation-free neural architectures, Gated Linear Networks (GLNs). What distinguishes GLNs from contemporary neural networks is the distri…
Connections Between Mirror Descent, Thompson Sampling and the Information Ratio
Julian Zimmert, Tor Lattimore
The information-theoretic analysis by Russo and Van Roy (2014) in combination with minimax duality has proved a powerful tool for the analysis of online learning algorithms in full…
Online Sparse Reinforcement Learning
Botao Hao, Tor Lattimore, Csaba Szepesvári +1
We investigate the hardness of online reinforcement learning in fixed horizon, sparse linear Markov decision process (MDP), with a special focus on the high-dimensional regime wher…
Optimally Confident UCB: Improved Regret for Finite-Armed Bandits
Tor Lattimore
I present the first algorithm for stochastic finite-armed bandits that simultaneously enjoys order-optimal problem-dependent regret and worst-case regret. Besides the theoretical r…
Regret Analysis of the Finite-Horizon Gittins Index Strategy for Multi-Armed Bandits
Tor Lattimore
I analyse the frequentist regret of the famous Gittins index strategy for multi-armed bandits with Gaussian noise and a finite horizon. Remarkably it turns out that this approach l…
Geometric Entropic Exploration
Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, Alaa Saade +7
Exploration is essential for solving complex Reinforcement Learning (RL) tasks. Maximum State-Visitation Entropy (MSVE) formulates the exploration problem as a well-defined policy…
Cleaning up the neighborhood: A full classification for adversarial partial monitoring
Tor Lattimore, Csaba Szepesvari
Partial monitoring is a generalization of the well-known multi-armed bandit framework where the loss is not directly observed by the learner. We complete the classification of fini…
Sparse Feature Selection Makes Batch Reinforcement Learning More Sample Efficient
Botao Hao, Yaqi Duan, Tor Lattimore +2
This paper provides a statistical analysis of high-dimensional batch Reinforcement Learning (RL) using sparse linear function approximation. When there is a large number of candida…
Behaviour Suite for Reinforcement Learning
Ian Osband, Yotam Doron, Matteo Hessel +11
This paper introduces the Behaviour Suite for Reinforcement Learning, or bsuite for short. bsuite is a collection of carefully-designed experiments that investigate core capabiliti…
Concentration and Confidence for Discrete Bayesian Sequence Predictors
Tor Lattimore, Marcus Hutter, Peter Sunehag
Bayesian sequence prediction is a simple technique for predicting future symbols sampled from an unknown measure on infinite sequences over a countable alphabet. While strong bound…
Single-Agent Policy Tree Search With Guarantees
Laurent Orseau, Levi H. S. Lelis, Tor Lattimore +1
We introduce two novel tree search algorithms that use a policy to guide search. The first algorithm is a best-first enumeration that uses a cost function that allows us to prove a…
Near-optimal inference in adaptive linear regression
Koulik Khamaru, Yash Deshpande, Tor Lattimore +2
When data is collected in an adaptive manner, even simple methods like ordinary least squares can exhibit non-normal asymptotic behavior. As an undesirable consequence, hypothesis…
Probabilistic Inference in Reinforcement Learning Done Right
Jean Tarbouriech, Tor Lattimore, Brendan O'Donoghue
A popular perspective in Reinforcement learning (RL) casts the problem as probabilistic inference on a graphical model of the Markov decision process (MDP). The core object of stud…
Asymptotically Optimal Information-Directed Sampling
Johannes Kirschner, Tor Lattimore, Claire Vernade +1
We introduce a simple and efficient algorithm for stochastic linear bandits with finitely many actions that is asymptotically optimal and (nearly) worst-case optimal in finite time…
Refined Detection for Gumbel Watermarking
Tor Lattimore
We propose a simple detection mechanism for the Gumbel watermarking scheme proposed by Aaronson (2022). The new mechanism is proven to be near-optimal in a problem-dependent sense…
Regret Bounds for Information-Directed Reinforcement Learning
Botao Hao, Tor Lattimore
Information-directed sampling (IDS) has revealed its potential as a data-efficient algorithm for reinforcement learning (RL). However, theoretical understanding of IDS for Markov D…
Context-lumpable stochastic bandits
Chung-Wei Lee, Qinghua Liu, Yasin Abbasi-Yadkori +3
We consider a contextual bandit problem with contexts and actions. In each round , the learner observes a random context and chooses an action based on its pas…
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 th…
Contextual Information-Directed Sampling
Botao Hao, Tor Lattimore, Chao Qin
Information-directed sampling (IDS) has recently demonstrated its potential as a data-efficient reinforcement learning algorithm. However, it is still unclear what is the right for…
Learning with Good Feature Representations in Bandits and in RL with a Generative Model
Tor Lattimore, Csaba Szepesvari, Gellert Weisz
The construction by Du et al. (2019) implies that even if a learner is given linear features in that approximate the rewards in a bandit with a uniform error of ,…
Matrix games with bandit feedback
Brendan O'Donoghue, Tor Lattimore, Ian Osband
We study a version of the classical zero-sum matrix game with unknown payoff matrix and bandit feedback, where the players only observe each others actions and a noisy payoff. This…
Gaussian Gated Linear Networks
David Budden, Adam Marblestone, Eren Sezener +3
We propose the Gaussian Gated Linear Network (G-GLN), an extension to the recently proposed GLN family of deep neural networks. Instead of using backpropagation to learn features,…
Causal Bandits: Learning Good Interventions via Causal Inference
Finnian Lattimore, Tor Lattimore, Mark D. Reid
We study the problem of using causal models to improve the rate at which good interventions can be learned online in a stochastic environment. Our formalism combines multi-arm band…
Leveraging Demonstrations to Improve Online Learning: Quality Matters
Botao Hao, Rahul Jain, Tor Lattimore +2
We investigate the extent to which offline demonstration data can improve online learning. It is natural to expect some improvement, but the question is how, and by how much? We sh…
Model Selection in Contextual Stochastic Bandit Problems
Aldo Pacchiano, My Phan, Yasin Abbasi-Yadkori +4
We study bandit model selection in stochastic environments. Our approach relies on a meta-algorithm that selects between candidate base algorithms. We develop a meta-algorithm-base…
Mirror Descent and the Information Ratio
Tor Lattimore, András György
We establish a connection between the stability of mirror descent and the information ratio by Russo and Van Roy [2014]. Our analysis shows that mirror descent with suitable loss e…
Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits
Branislav Kveton, Csaba Szepesvari, Sharan Vaswani +3
We propose a bandit algorithm that explores by randomizing its history of rewards. Specifically, it pulls the arm with the highest mean reward in a non-parametric bootstrap sample…
Time Consistent Discounting
Tor Lattimore, Marcus Hutter
A possibly immortal agent tries to maximise its summed discounted rewards over time, where discounting is used to avoid infinite utilities and encourage the agent to value current…
PAC Bounds for Discounted MDPs
Tor Lattimore, Marcus Hutter
We study upper and lower bounds on the sample-complexity of learning near-optimal behaviour in finite-state discounted Markov Decision Processes (MDPs). For the upper bound we make…
Online Learning with Gated Linear Networks
Joel Veness, Tor Lattimore, Avishkar Bhoopchand +3
This paper describes a family of probabilistic architectures designed for online learning under the logarithmic loss. Rather than relying on non-linear transfer functions, our meth…
On the Optimality of Batch Policy Optimization Algorithms
Chenjun Xiao, Yifan Wu, Tor Lattimore +5
Batch policy optimization considers leveraging existing data for policy construction before interacting with an environment. Although interest in this problem has grown significant…
TopRank: A practical algorithm for online stochastic ranking
Tor Lattimore, Branislav Kveton, Shuai Li +1
Online learning to rank is a sequential decision-making problem where in each round the learning agent chooses a list of items and receives feedback in the form of clicks from the…
Asymptotically Optimal Agents
Tor Lattimore, Marcus Hutter
Artificial general intelligence aims to create agents capable of learning to solve arbitrary interesting problems. We define two versions of asymptotic optimality and prove that no…
Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications
Johannes Kirschner, Tor Lattimore, Andreas Krause
Partial monitoring is an expressive framework for sequential decision-making with an abundance of applications, including graph-structured and dueling bandits, dynamic pricing and…
The Pareto Regret Frontier for Bandits
Tor Lattimore
Given a multi-armed bandit problem it may be desirable to achieve a smaller-than-usual worst-case regret for some special actions. I show that the price for such unbalanced worst-c…
No Free Lunch versus Occam's Razor in Supervised Learning
Tor Lattimore, Marcus Hutter
The No Free Lunch theorems are often used to argue that domain specific knowledge is required to design successful algorithms. We use algorithmic information theory to argue the ca…
The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits
Tor Lattimore, Csaba Szepesvari
Stochastic linear bandits are a natural and simple generalisation of finite-armed bandits with numerous practical applications. Current approaches focus on generalising existing te…
Beyond Statistical Learning: Exact Learning Is Essential for General Intelligence
András György, Tor Lattimore, Nevena LaziÄ +1
Sound deductive reasoning -- the ability to derive new knowledge from existing facts and rules -- is an indisputably desirable aspect of general intelligence. Despite the major adv…
High-Dimensional Sparse Linear Bandits
Botao Hao, Tor Lattimore, Mengdi Wang
Stochastic linear bandits with high-dimensional sparse features are a practical model for a variety of domains, including personalized medicine and online advertising. We derive a…
Adaptive Exploration in Linear Contextual Bandit
Botao Hao, Tor Lattimore, Csaba Szepesvari
Contextual bandits serve as a fundamental model for many sequential decision making tasks. The most popular theoretically justified approaches are based on the optimism principle.…
On Explore-Then-Commit Strategies
Aurélien Garivier, Emilie Kaufmann, Tor Lattimore
We study the problem of minimising regret in two-armed bandit problems with Gaussian rewards. Our objective is to use this simple setting to illustrate that strategies based on an…
Refined Lower Bounds for Adversarial Bandits
Sébastien Gerchinovitz, Tor Lattimore
We provide new lower bounds on the regret that must be suffered by adversarial bandit algorithms. The new results show that recent upper bounds that either (a) hold with high-proba…
Thompson Sampling is Asymptotically Optimal in General Environments
Jan Leike, Tor Lattimore, Laurent Orseau +1
We discuss a variant of Thompson sampling for nonparametric reinforcement learning in a countable classes of general stochastic environments. These environments can be non-Markov,…
On First-Order Bounds, Variance and Gap-Dependent Bounds for Adversarial Bandits
Roman Pogodin, Tor Lattimore
We make three contributions to the theory of k-armed adversarial bandits. First, we prove a first-order bound for a modified variant of the INF strategy by Audibert and Bubeck [200…
Sequential Best-Arm Identification with Application to Brain-Computer Interface
Xin Zhou, Botao Hao, Jian Kang +2
A brain-computer interface (BCI) is a technology that enables direct communication between the brain and an external device or computer system. It allows individuals to interact wi…
A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits
Tor Lattimore
We adapt the analysis of policy gradient for continuous time -armed stochastic bandits by Lattimore (2026) to the standard discrete time setup. As in continuous time, we prove t…
Online Learning to Rank with Features
Shuai Li, Tor Lattimore, Csaba Szepesvári
We introduce a new model for online ranking in which the click probability factors into an examination and attractiveness function and the attractiveness function is a linear funct…
BubbleRank: Safe Online Learning to Re-Rank via Implicit Click Feedback
Chang Li, Branislav Kveton, Tor Lattimore +4
In this paper, we study the problem of safe online learning to re-rank, where user feedback is used to improve the quality of displayed lists. Learning to rank has traditionally be…