Research · Written work

Publications

Papers and preprints in statistical learning, probability and information theory. One entry per work, with its conference, journal and preprint versions.

BibTeX collectionGoogle Scholar ↗

2026

On Minimum Divergence for Distribution Reconstruction

Justin Bec, Thomas Le Corre, Aurélien Garivier
Preprint · October 2026
Abstract

We study the possibility of generalizing maximum-entropy reconstruction, which approximately recovers a probability distribution from finitely many (generalized) moments by minimizing the Kullback--Leibler (KL) divergence to a reference measure. The reconstruction lies in an exponential family and is also the best KL approximation of the unknown distribution within that family: moment matching and information projection coincide. Replacing KL by a smooth f-divergence, the reconstruction still exists in an associated family, but the best approximation property does not. Specifically, a family is called entropy-adapted if the projection of any distribution matches its moments. We show that, up to equivalence, KL is the only C2 f-divergence that is entropy-adapted, whatever the choice of the generalized moments. We illustrate the consequences of this failure numerically.

Original publication details

submitted · Sep. 2026

The Exhaustive Peres Transform: Extraction and Universal Coding

Aurélien Garivier
Preprint · October 2026
Abstract

Run to exhaustion, Peres's iteration of von Neumann's procedure yields a bijection of the set of binary strings of length N that splits every string into fair bits and a residual. The residual is self-delimiting and determines the number of ones, so the fair bits are exactly uniform given the residual under every exchangeable law. Each residual one accounts for a power of two of the weight of the input, and the residual of every input of length N has fewer than sqrt(3) × N^0.793 ones. This sparsity gives a short proof, with an explicit remainder, that the fair bits per symbol tend almost surely to the entropy for Bernoulli sources and every finite alphabet. The Bernoulli likelihood factorises along the recursion, and code B, which codes the residual at plug-in biases, has the length of the two-part code. Code G gamma-codes the gaps of the residual, with no estimate and no arithmetic coder: on every string its length is at most the logarithm of the type class plus O(N^0.793 log N). What is more, a concatenation of J pieces costs its piecewise empirical entropy plus a term that is sublinear when J = o(N), without the cuts being sent. After a Burrows–Wheeler transform of the reversed string, both codes are universal for stationary ergodic sources: code B through a context tree of growing depth, with regret O(2^k log N) against Markov sources of order k, and code G with no tree, competing on every individual sequence with the empirical conditional entropy of every order. For laws invariant under permutations inside the pieces of a partition, the fair bits not mixed across the pieces are exactly uniform given everything else; after the BWT, the fair bits of every stationary source fall short of their length by o(N) bits of entropy, with an exponential tail for Markov sources. Experiments measure the finite-length price of these guarantees.

Randomness extraction; Universal coding; Peres algorithm; Rice codes; Context trees

Versions & publication history

Earlier title

Universal Coding with the Exhaustive Peres Transform

Original publication details

Oct. 2026

A Novel Approach to Distributional Reinforcement Learning via Moment Matching

Juliet Bringas Miranda, Aurélien Garivier, Olivier Cappé
Preprint · May 2026
Abstract

We introduce a novel class of Distributional Reinforcement Learning (DistRL) algorithms that leverage the exact computability of specific moments of the return distribution via generalized dynamic programming. This approach offers a principled and theoretically grounded alternative to existing DistRL policy evaluation and planning methods, with the key advantage to avoid the accumulation of approximations during the iterations. We study the accuracy of generic reconstruction methods of the full return distribution from its computed moments: we prove an error bound on the Wasserstein W1 distance that is independent of the horizon (or discount factor). Then, we focus on the use of the Maximum Entropy principle: under additional regularity assumptions, we prove a much stronger control of the error under the Kullback-Leibler divergence. Both of these theoretical guarantees are stronger than those available for state-of-the-art DistRL policy evaluation algorithms. Empirically, we obtain very accurate and robust results in prototypal reinforcement learning environments.

Reinforcement learning; Distributional reinforcement learning; Distributional Bellman equations; Moment matching; Maximum Entropy

Original publication details

submitted · Jan. 2026

2025

EVaR-Optimal Arm Identification in Bandits

Mehrasa Ahmadipour, Aurélien Garivier
Preprint · October 2025
Abstract

We study the fixed-confidence best arm identification (BAI) problem within the multi-armed bandit (MAB) framework under the Entropic Value-at-Risk (EVaR) criterion. Our analysis considers a nonparametric setting, allowing for general reward distributions bounded in [0,1]. This formulation addresses the critical need for risk-averse decision-making in high-stakes environments, such as finance, moving beyond simple expected value optimization. We propose a 𝛿-correct, Track-and-Stop based algorithm and derive a corresponding lower bound on the expected sample complexity, which we prove is asymptotically matched. The implementation of our algorithm and the characterization of the lower bound both require solving a complex convex optimization problem and a related, simpler non-convex one.

Best arm identification; Entropic Value at Risk; Bandit problems; Risk averse

Original publication details

Oct. 2025

Efficient Risk-sensitive Planning via Entropic Risk Measures

Alexandre Marthe, Samuel Bounan, Aurélien Garivier, Claire Vernade
Preprint · January 2025
Abstract

Risk-sensitive planning aims to identify policies maximizing some tail-focused metrics in Markov Decision Processes (MDPs). Such an optimization task can be very costly for the most widely used and interpretable metrics such as threshold probabilities or (Conditional) Values at Risk. Indeed, previous work showed that only Entropic Risk Measures (EntRM) can be efficiently optimized through dynamic programming, leaving a hard-to-interpret parameter to choose. We show that the computation of the full set of optimal policies for EntRM across parameter values leads to tight approximations for the metrics of interest. We prove that this optimality front can be computed effectively thanks to a novel structural analysis and smoothness properties of entropic risks. Empirical results demonstrate that our approach achieves strong performance in a variety of decision-making scenarios.

Markov decision Processes; Risk sensitive control; Entropic risk measure; Value at Risk; Threshold Probability

Original publication details

submitted · Feb. 2025

On Sparsity and Sub-Gaussianity in the Johnson-Lindenstrauss Lemma

Aurélien Garivier, Emmanuel Pilliat
Preprint · revised 2025 (HAL version: 2024)
Abstract

We provide a simple proof of the Johnson-Lindenstrauss lemma for sub-Gaussian variables. We extend the analysis to identify how sparse projections can be, and what the cost of sparsity is on the target dimension. The Johnson-Lindenstrauss lemma is the theoretical core of the dimensionality reduction methods based on random projections. While its original formulation involves matrices with Gaussian entries, the computational cost of random projections can be drastically reduced by the use of simpler variables, especially if they vanish with a high probability. In this paper, we propose a simple and elementary analysis of random projections under classical assumptions that emphasizes the key role of sub-Gaussianity. Furthermore, we show how to extend it to sparse projections, emphasizing the limits induced by the sparsity of the data itself.

Johnson lindenstrauss; Random projections; Sparsity

Original publication details

, Oct. 2025

Identifying the Best Transition Law

Mehrasa Ahmadipour, Elise Crépon, Aurélien Garivier
Preprint · February 2025
Abstract

Motivated by recursive learning in Markov Decision Processes, this paper studies best-arm identification in bandit problems where each arm's reward is drawn from a multinomial distribution with a known support. We compare the performance reached by strategies including notably LUCB without and with use of this knowledge. In the first case, we use classical non-parametric approaches for the confidence intervals. In the second case, where a probability distribution is to be estimated, we first use classical deviation bounds (Hoeffding and Bernstein) on each dimension independently, and then the Empirical Likelihood method (EL-LUCB) on the joint probability vector. The effectiveness of these methods is demonstrated through simulations on scenarios with varying levels of structural complexity.

2024

Sequential Learning of the Pareto Front for Multi-objective Bandits

Elise Crépon, Aurélien Garivier, Wouter M Koolen
AISTATS 2024 · Proceedings of Machine Learning Research 238, pp. 3583–3591
Abstract

We study the problem of sequential learning of the Pareto front in multi-objective multi-armed bandits. An agent is faced with K possible arms to pull. At each turn she picks one, and receives a vector-valued reward. When she thinks she has enough information to identify the Pareto front of the different arm means, she stops the game and gives an answer. We are interested in designing algorithms such that the answer given is correct with probability at least 1-δ. Our main contribution is an efficient implementation of an algorithm achieving the optimal sample complexity when the risk δ is small. With K arms in d dimensions p of which are in the Pareto set, the algorithm runs in time O(Kp^d) per round.

Pure exploration; Pareto front algorithm; Multiobjective Optimization; Bandits

Original publication details

27th International Conference on Artificial Intelligence and Statistics (AISTAT'24) · Apr. 2024

Stochastic Direct Search Method for Blind Resource Allocation

Juliette Achddou, Olivier Cappe, Aurélien Garivier
Transactions on Machine Learning Research, 2024
Abstract

Motivated by programmatic advertising optimization, we consider the task of sequentially allocating budget across a set of resources. At every time step, a feasible allocation is chosen and only a corresponding random return is observed. The goal is to maximize the cumulative expected sum of returns. This is a realistic model for budget allocation across subdivisions of marketing campaigns, with the objective of maximizing the number of conversions. We study direct search (also known as pattern search) methods for linearly constrained and derivative-free optimization in the presence of noise, which apply in particular to sequential budget allocation. These algorithms, which do not rely on hierarchical partitioning of the resource space, are easy to implement; they respect the operational constraints of resource allocation by avoiding evaluation outside of the feasible domain; and, they are also compatible with warm start by being (approximate) descent algorithms. However, they have not yet been analyzed from the perspective of cumulative regret. We show that direct search methods achieves finite regret in the deterministic and unconstrained case. In the presence of evaluation noise and linear constraints, we propose a simple extension of direct search that achieves a regret upper-bound of the order of T^(2/3). We also propose an accelerated version of the algorithm, relying on repeated sequential testing, that significantly improves the practical behavior of the approach.

Online learning; Regret minimization; Derivative-free optimization; Direct search

Versions & publication history

Earlier title

Stochastic Direct Search Methods for Blind Resource Allocation

Original publication details

Transactions on Machine Learning Research · Apr. 2024

2023

Beyond Average Return in Markov Decision Processes

Alexandre Marthe, Aurélien Garivier, Claire Vernade
NeurIPS 2023, Dec 2023, New Orleans, United States
Abstract

Abstract What are the functionals of the reward that can be computed and optimized exactly in Markov Decision Processes? In the finite-horizon, undiscounted setting, Dynamic Programming (DP) can only handle these operations efficiently for certain classes of statistics. We summarize the characterization of these classes for policy evaluation, and give a new answer for the planning problem. Interestingly, we prove that only generalized means can be optimized exactly, even in the more general framework of Distributional Reinforcement Learning (DistRL). DistRL permits, however, to evaluate other functionals approximately. We provide error bounds on the resulting estimators, and discuss the potential of this approach as well as its limitations. These results contribute to advancing the theory of Markov Decision Processes by examining overall characteristics of the return, and particularly risk-conscious strategies.

Markov Decision Process; Dynamic Programming; Statistical functionals; Distributional Reinforcement Learning; Policy Evaluation; Planning

Original publication details

Neural Information Processing Systems · 2023 · Aug. 2023

On Adaptivity in Quantum Testing

Transactions on Machine Learning Research, 2023, pp. 1–33
Abstract

Can adaptive strategies outperform non-adaptive ones for quantum hypothesis selection? We exhibit problems where adaptive strategies provably reduce the number of required samples by a factor four in the worst case, and possibly more when the actual difficulty of the problem makes it possible. In addition, we exhibit specific hypotheses classes for which there is a provable polynomial separation between adaptive and non-adaptive strategies -- a specificity of the quantum framework that does not appear in classical testing.

Original publication details

· Sep. 2023

About the Cost of Central Privacy in Density Estimation

Clément Lalanne, Aurélien Garivier, Rémi Gribonval
Transactions on Machine Learning Research, 2023
Abstract

We study non-parametric density estimation for densities in Lipschitz and Sobolev spaces, and under global privacy. In particular, we investigate regimes where the privacy budget is not supposed to be constant. We consider the classical definition of global differential privacy, but also the more recent notion of global concentrated differential privacy. We recover the result of Barber & Duchi (2014) stating that histogram estimators are optimal against Lipschitz distributions for the L2 risk, and under regular differential privacy, and we extend it to other norms and notions of privacy. Then, we investigate higher degrees of smoothness, drawing two conclusions: First, and contrary to what happens with constant privacy budget (Wasserman & Zhou, 2010), there are regimes where imposing privacy degrades the regular minimax risk of estimation on Sobolev densities. Second, so-called projection estimators are near-optimal against the same classes of densities in this new setup with pure differential privacy, but contrary to the constant privacy budget case, it comes at the cost of relaxation. With zero concentrated differential privacy, there is no need for relaxation, and we prove that the estimation is optimal.

Versions & publication history

Earlier title

About the Cost of Global Privacy in Density Estimation

Original publication details

· Aug. 2023

Private Statistical Estimation of Many Quantiles

Clément Lalanne, Aurélien Garivier, Rémi Gribonval
ICML 2023–40th International Conference on Machine Learning, Jul 2023, Honolulu, United States
Abstract

This work studies the estimation of many statistical quantiles under differential privacy. More precisely, given a distribution and access to i.i.d. samples from it, we study the estimation of the inverse of its cumulative distribution function (the quantile function) at specific points. For instance, this task is of key importance in private data generation. We present two different approaches. The first one consists in privately estimating the empirical quantiles of the samples and using this result as an estimator of the quantiles of the distribution. In particular, we study the statistical properties of the recently published algorithm introduced by Kaplan et al. 2022 that privately estimates the quantiles recursively. The second approach is to use techniques of density estimation in order to uniformly estimate the quantile function on an interval. In particular, we show that there is a tradeoff between the two methods. When we want to estimate many quantiles, it is better to estimate the density rather than estimating the quantile function at specific points.

Quantiles; Differential Privacy

Original publication details

Fortieth International Conference on Machine Learning · Jul. 2023

Quantum Channel Certification with Incoherent Strategies

Conference on Learning Theory (COLT 2023) · July 2023
Abstract

In the problem of quantum channel certification, we have black box access to a quantum process and would like to decide if this process matches some predefined specification or is ε-far from this specification. The objective is to achieve this task while minimizing the number of times the black box is used. Here, we focus on optimal incoherent strategies for two relevant extreme cases of channel certification. The first one is when the predefined specification is a unitary channel, e.g., a gate in a quantum circuit. In this case, we show that testing whether the black box is described by a fixed unitary operator in dimension d or ε-far from it in the trace norm requires Θ(d/ε^2) uses of the black box. The second setting we consider is when the predefined specification is a completely depolarizing channel with input dimension din and output dimension dout. In this case, we prove that, in the non-adaptive setting, Θ(d_in^2 d_out^1.5 / ε^2) uses of the channel are necessary and sufficient to verify whether it is equal to the depolarizing channel or ε-far from it in the diamond norm. Finally, we prove a lower bound of Ω(d_in^2d_out/ε^2) for this problem in the adaptive setting. Note that the special case d_in=1 corresponds to the well-studied quantum state certification problem.

Original publication details

Conference on Learning Theory, Bengalore · n° 36 · COLT · Jul. 2023

On the Statistical Complexity of Estimation and Testing under Privacy Constraints

Clément Lalanne, Aurélien Garivier, Rémi Gribonval
Transactions on Machine Learning Research, 2023
Abstract

Producing statistics that respect the privacy of the samples while still maintaining their accuracy is an important topic of research. We study minimax lower bounds when the class of estimators is restricted to the differentially private ones. In particular, we show that characterizing the power of a distributional test under differential privacy can be done by solving a transport problem. With specific coupling constructions, this observation allows us to derivate Le Cam-type and Fano-type inequalities for both regular definitions of differential privacy and for divergence-based ones (based on Renyi divergence). We then proceed to illustrate our results on three simple, fully worked out examples. In particular, we show that the problem class has a huge importance on the provable degradation of utility due to privacy. For some problems, privacy leads to a provable degradation only when the rate of the privacy parameters is small enough whereas for other problem, the degradation systematically occurs under much looser hypotheses on the privacy parametters. Finally, we show that the known privacy guarantees of DP-SGLD, a private convex solver, when used to perform maximum likelihood, leads to an algorithm that is near-minimax optimal in both the sample size and the privacy tuning parameters of the problem for a broad class of parametric estimation procedures that includes exponential families.

Lower Bounds; Minimax; Testing; Estimation; Privacy

Original publication details

Transactions on Machine Learning Research · Apr. 2023

Private Quantiles Estimation in the Presence of Atoms

Information and Inference, 2023
Abstract

We address the differentially private estimation of multiple quantiles (MQ) of a dataset, a key building block in modern data analysis. We apply the recent non-smoothed Inverse Sensitivity (IS) mechanism to this specific problem and establish that the resulting method is closely related to the current state-of-the-art, the JointExp algorithm, sharing in particular the same computational complexity and a similar efficiency. However, we demonstrate both theoretically and empirically that (non-smoothed) JointExp suffers from an important lack of performance in the case of peaked distributions, with a potentially catastrophic impact in the presence of atoms. While its smoothed version would allow to leverage the performance guarantees of IS, it remains an open challenge to implement. As a proxy to fix the problem we propose a simple and numerically efficient method called Heuristically Smoothed JointExp (HSJointExp), which is endowed with performance guarantees for a broad class of distributions and achieves results that are orders of magnitude better on problematic datasets.

Original publication details

accepted · Information and Inference · Jul. 2023

On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits

Antoine Barrier, Aurélien Garivier, Gilles Stoltz
ALT 2023 - The 34th International Conference on Algorithmic Learning Theory, Feb 2023, Singapour, Singapore
Abstract

We lay the foundations of a non-parametric theory of best-arm identification in multi-armed bandits with a fixed budget T. We consider general, possibly non-parametric, models D for distributions over the arms; an overarching example is the model D = P(0,1) of all probability distributions over [0,1]. We propose upper bounds on the average log-probability of misidentifying the optimal arm based on information-theoretic quantities that correspond to infima over Kullback-Leibler divergences between some distributions in D and a given distribution. This is made possible by a refined analysis of the successive-rejects strategy of Audibert, Bubeck, and Munos (2010). We finally provide lower bounds on the same average log-probability, also in terms of the same new information-theoretic quantities; these lower bounds are larger when the (natural) assumptions on the considered strategies are stronger. All these new upper and lower bounds generalize existing bounds based, e.g., on gaps between distributions.

Multi-armed bandits; Best-arm identification; Non-parametric models; Kullback-Leibler divergences; Information-theoretic bounds

Original publication details

The 34th International Conference on Algorithmic Learning Theory · Feb. 2023

2022

On the complexity of All ε-Best Arms Identification

Aymen Al Marjani, Tomáš Kocák, Aurélien Garivier
European Conference (ECML-PKDD), 2022
Abstract

We consider the problem introduced by [MJTN20] of identifying all the ε-optimal arms in a finite stochastic multi-armed bandit with Gaussian rewards. In the fixed confidence setting, we give a lower bound on the number of samples required by any algorithm that returns the set of ε-good arms with a failure probability less than some risk level δ. This bound writes as T * ε (µ) log(1/δ), where T * ε (µ) is a characteristic time that depends on the vector of mean rewards µ and the accuracy parameter ε. We also provide an efficient numerical method to solve the convex max-min program that defines the characteristic time. Our method is based on a complete characterization of the alternative bandit instances that the optimal sampling strategy needs to rule out, thus making our bound tighter than the one provided by [MJTN20]. Using this method, we propose a Track-and-Stop algorithm that identifies the set of ε-good arms w.h.p and enjoys asymptotic optimality (when δ goes to zero) in terms of the expected sample complexity. Finally, using numerical simulations, we demonstrate our algorithm's advantage over state-of-the-art methods, even for moderate values of the risk parameter.

Original publication details

European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML-PKDD'22) · Sep. 2022

Génération de traces cellulaires réalistes

CORES 2022–7ème Rencontres Francophones sur la Conception de Protocoles, l’Évaluation de Performance et l’Expérimentation des Réseaux de Communication, May 2022, Saint-Rémy-Lès-Chevreuse, France
Abstract

Du fait de la confidentialité des données que contiennent les traces cellulaires CDRs (Call Data Records), leur obtention est soumise à des lois strictes qui limitent leur accessibilité aux chercheurs, et leur utilisabilité même lorsqu’ils sont disponibles. Pour pallier à ce manque, dans cet article, nous nous intéressons à la production de traces CDRs réalistes sur la base d’un ensemble de caractérisations de CDRs réels obtenus auprès d’un opérateur.

Préservation de la vie privée; Simulation; Réseaux cellulaires; CDR réalistes

Original publication details

CORES 2022 – 7ème Rencontres Francophones sur la Conception de Protocoles, l’Évaluation de Performance et l’Expérimentation des Réseaux de Communication · May 2022

A Non-asymptotic Approach to Best-Arm Identification for Gaussian Bandits

Antoine Barrier, Aurélien Garivier, Tomáš Kocák
AISTATS 2022–25th International Conference on Artificial Intelligence and Statistics, Mar 2022, Virtual, Spain
Abstract

We propose a new strategy for best-arm identification with fixed confidence of Gaussian variables with bounded means and unit variance. This strategy called Exploration-Biased Sampling is not only asymptotically optimal: we also prove non-asymptotic bounds occurring with high probability. To the best of our knowledge, this is the first strategy with such guarantees. But the main advantage over other algorithms like Track-and-Stop is an improved behavior regarding exploration: Exploration-Biased Sampling is slightly biased in favor of exploration in a subtle but natural way that makes it more stable and interpretable. These improvements are allowed by a new analysis of the sample complexity optimization problem, which yields a faster numerical resolution scheme and several quantitative regularity results that we believe of high independent interest.

Best arm identification; Fixed confidence; Multi-armed bandits; Sequential Learning

Original publication details

25th International Conference on Artificial Intelligence and Statistics (AISTAT'22) · Mar. 2022

KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints

Aurélien Garivier, Hédi Hadiji, Pierre Ménard, Gilles Stoltz
Journal of Machine Learning Research, 2022, 23 (179), pp. 1–66
Abstract

In the context of K-armed stochastic bandits with distribution only assumed to be supported by [0,1], we introduce a new algorithm, KL-UCB-switch, and prove that is enjoys simultaneously a distribution-free regret bound of optimal order \sqrt{KT} and a distribution-dependent regret bound of optimal order as well, that is, matching the k ln(T) lower bound by Lai and Robbins and Burnetas and Katehakis.

K-armed stochastic bandits; Distribution-dependent regret bounds; Distribution-free regret bounds; Index policies

Original publication details

Journal of Machine Learning Research · · pp.1−66 · Aug. 2022

2021

A/B/n Testing with Control in the Presence of Subpopulations

NeurIPS 2021 - Thirty-fifth Conference on Neural Information Processing Systems, Dec 2021, Virtual, France
Abstract

Motivated by A/B/n testing applications, we consider a finite set of distributions (called \emph{arms}), one of which is treated as a \emph{control}. We assume that the population is stratified into homogeneous subpopulations. At every time step, a subpopulation is sampled and an arm is chosen: the resulting observation is an independent draw from the arm conditioned on the subpopulation. The quality of each arm is assessed through a weighted combination of its subpopulation means. We propose a strategy for sequentially choosing one arm per time step so as to discover as fast as possible which arms, if any, have higher weighted expectation than the control. This strategy is shown to be asymptotically optimal in the following sense: if is the first time when the strategy ensures that it is able to output the correct answer with probability at least , then grows linearly with at the exact optimal rate. This rate is identified in the paper in three different settings: (1) when the experimenter does not observe the subpopulation information, (2) when the subpopulation of each sample is observed but not chosen, and (3) when the experimenter can select the subpopulation from which each response is sampled. We illustrate the efficiency of the proposed strategy with numerical simulations on synthetic and real data collected from an A/B/n experiment.

Versions & publication history

Earlier title

A A/B/n Testing with Control in the Presence of Subpopulations

Original publication details

Neural Information Processing Systems · Dec. 2021

Navigating to the Best Policy in Markov Decision Processes

Aymen Al Marjani, Aurélien Garivier, Alexandre Proutiere
35th International Conference on Neural Information Processing Systems, Dec 2021, Online, France
Abstract

We investigate the classical active pure exploration problem in Markov Decision Processes, where the agent sequentially selects actions and, from the resulting system trajectory, aims at identifying the best policy as fast as possible. We propose an information-theoretic lower bound on the average number of steps required before a correct answer can be given with probability at least . This lower bound involves a non-convex optimization problem, for which we propose a convex relaxation. We further provide an algorithm whose sample complexity matches the relaxed lower bound up to a factor . This algorithm addresses general communicating MDPs; we propose a variant with reduced exploration rate (and hence faster convergence) under an additional ergodicity assumption. This work extends previous results relative to the \emph{generative setting}~\cite{marjani2020adaptive}, where the agent could at each step observe the random outcome of any (state, action) pair. In contrast, we show here how to deal with the \emph{navigation constraints} and comment on the gap between the generative and online settings. Our analysis relies on an ergodic theorem for non-homogeneous Markov chains which we consider of wide interest in the analysis of Markov Decision Processes.

Original publication details

Neural Information Processing Systems · Dec. 2021

Sequential Algorithms for Testing Closeness of Distributions

NeurIPS 2021, Dec 2021, Virtual, France
Abstract

What advantage do \emph{sequential} procedures provide over batch algorithms for testing properties of unknown distributions? Focusing on the problem of testing whether two distributions $\mathcal{D}_1$ and $\mathcal{D}_2$ on $\{1,\dots, n\}$ are equal or $\eps$-far, we give several answers to this question. We show that for a small alphabet size $n$, there is a sequential algorithm that outperforms any batch algorithm by a factor of at least $4$ in terms sample complexity. For a general alphabet size $n$, we give a sequential algorithm that uses no more samples than its batch counterpart, and possibly fewer if the actual distance $\TV(\mathcal{D}_1, \mathcal{D}_2)$ between $\mathcal{D}_1$ and $\mathcal{D}_2$ is larger than $\eps$. As a corollary, letting $\eps$ go to $0$, we obtain a sequential algorithm for testing closeness when no a priori bound on $\TV(\mathcal{D}_1, \mathcal{D}_2)$ is given that has a sample complexity $\tilde{\mathcal{O}}(\frac{n^{2/3}}{\TV(\mathcal{D}_1, \mathcal{D}_2)^{4/3}})$: this improves over the $\tilde{\mathcal{O}}(\frac{n/\log n}{\TV(\mathcal{D}_1, \mathcal{D}_2)^{2} })$ tester of~\citet{daskalakis2017optimal} and is optimal up to multiplicative constants. We also establish limitations of sequential algorithms for the problem of testing closeness: they can improve the worst case number of samples by at most a constant factor.

Original publication details

Neural Information Processing Systems · spotlight · Dec. 2021

Fast Rate Learning in Stochastic First Price Bidding

Juliette Achddou, Olivier Cappé, Aurélien Garivier
ACML 2021 - Proceedings of Machine Learning Research 157, 2021, Nov 2021, SIngapore, Singapore
Abstract

First-price auctions have largely replaced traditional bidding approaches based on Vickrey auctions in programmatic advertising. As far as learning is concerned, first-price auctions are more challenging because the optimal bidding strategy does not only depend on the value of the item but also requires some knowledge of the other bids. They have already given rise to several works in sequential learning, many of which consider models for which the value of the buyer or the opponents' maximal bid is chosen in an adversarial manner. Even in the simplest settings, this gives rise to algorithms whose regret grows as $\sqrt{T}$ with respect to the time horizon $T$. Focusing on the case where the buyer plays against a stationary stochastic environment, we show how to achieve significantly lower regret: when the opponents' maximal bid distribution is known we provide an algorithm whose regret can be as low as $\log^2(T)$; in the case where the distribution must be learnt sequentially, a generalization of this algorithm can achieve $T^{1/3+ \epsilon}$ regret, for any $\epsilon>0$. To obtain these results, we introduce two novel ideas that can be of interest in their own right. First, by tranposing results obtained in the posted price setting, we provide conditions under which the first-price biding utility is locally quadratic around its optimum. Second, we leverage the observation that, on small sub-intervals, the concentration of the variations of the empirical distribution function may be controlled more accurately than by using the classical Dvoretzky-Kiefer-Wolfowitz inequality. Numerical simulations confirm that our algorithms converge much faster than alternatives proposed in the literature for various bid distributions, including for bids collected on an actual programmatic advertising platform.

Original publication details

13th Asian Conference on Machine Learning (ACML) · n°13 · Nov. 2021

Epsilon Best Arm Identification in Spectral Bandits

Aurélien Garivier, Tomáš Kocák
Thirtieth International Joint Conference on Artificial Intelligence {IJCAI-21}, Aug 2021, Montreal, Canada. pp. 2636–2642
Abstract

We propose an analysis of PAC identification of an epsilon-best arm in graph bandit models with Gaussian distributions. We consider finite but potentially very large bandit models where the set of arms is endowed with a graph structure, and we assume that the arms' expectations $\bmu$ are smooth with respect to this graph. Our goal is to identify an arm whose expectation is at most $\epsilon$ below the largest of all means. We focus on the fixed-confidence setting: given a risk parameter $\delta$, we consider sequential strategies that yield an epsilon-optimal arm with probability at least 1-delta. All such strategies use at least T*_{R,epsilon}(mu)\log(1/delta) samples, where R is the smoothness parameter. We identify the complexity term T*_{R,epsilon}(mu) as the solution of a min-max problem for which we give a game-theoretic analysis and an approximation procedure. This procedure is the key element required by the asymptotically optimal Track-and-Stop strategy.

Original publication details

International Joint Conference on Artificial Intelligence (IJCAI) · · Aug. 2021

Efficient Algorithms for Stochastic Repeated Second-price Auctions

Juliette Achddou, Olivier Cappé, Aurélien Garivier
ALT 2021–32nd International Conference on Algorithmic Learning Theory, Mar 2021, Paris, France
Abstract

Developing efficient sequential bidding strategies for repeated auctions is an important practical challenge in various marketing tasks. In this setting, the bidding agent obtains information, on both the value of the item at sale and the behavior of the other bidders, only when she wins the auction. Standard bandit theory does not apply to this problem due to the presence of action-dependent censoring. In this work, we consider second-price auctions and propose novel, efficient UCB-like algorithms for this task. These algorithms are analyzed in the stochastic setting, assuming regularity of the distribution of the opponents' bids. We provide regret upper bounds that quantify the improvement over the baseline algorithm proposed in the literature. The improvement is particularly significant in cases when the value of the auctioned item is low, yielding a spectacular reduction in the order of the worst-case regret. We further provide the first parametric lower bound for this problem that applies to generic UCB-like strategies. As an alternative, we propose more explainable strategies which are reminiscent of the Explore Then Commit bandit algorithm. We provide a critical analysis of this class of strategies, showing both important advantages and limitations. In particular, we provide a minimax lower bound and propose a nearly minimax-optimal instance of this class.

Auctions; Online learning; Bandits

Original publication details

Algorithmic Learning Theory (ALT) · n°32 · Mar. 2021

Self-Concordant Analysis of Generalized Linear Bandits with Forgetting

Yoan Russac, Louis Faury, Olivier Cappé, Aurélien Garivier
AISTATS 2021 - International Conference on Artificial Intelligence and Statistics, Apr 2021, San Diego / Virtual, United States
Abstract

Contextual sequential decision problems with categorical or numerical observations are ubiquitous and Generalized Linear Bandits (GLB) offer a solid theoretical framework to address them. In contrast to the case of linear bandits, existing algorithms for GLB have two drawbacks undermining their applicability. First, they rely on excessively pessimistic concentration bounds due to the non-linear nature of the model. Second, they require either non-convex projection steps or burn-in phases to enforce boundedness of the estimators. Both of these issues are worsened when considering non-stationary models, in which the GLB parameter may vary with time. In this work, we focus on self-concordant GLB (which include logistic and Poisson regression) with forgetting achieved either by the use of a sliding window or exponential weights. We propose a novel confidence-based algorithm for the maximum-likehood estimator with forgetting and analyze its perfomance in abruptly changing environments. These results as well as the accompanying numerical simulations highlight the potential of the proposed approach to address non-stationarity in GLB.

Original publication details

24th International Conference on Artificial Intelligence and Statistics (AISTAT'21) · Apr. 2021

Non-Asymptotic Sequential Tests for Overlapping Hypotheses and application to near optimal arm identification in bandit models

Aurélien Garivier, Emilie Kaufmann
Sequential Analysis, 2021, 40 (1), pp. 61–96
Abstract

In this paper, we study sequential testing problems with overlapping hypotheses. We first focus on the simple problem of assessing if the mean µ of a Gaussian distribution is ≥ε−or≤ε; if µ∈(−ε,ε), both answers are considered to be correct. Then, we consider PAC-best arm identification in a bandit model: given K probability distributions on R with means µ1,...,µK , we derive the asymptotic complexity of identifying, with risk at most δ, an index I∈1,...,K such that µ_I≥max_i µ_i−ε. We provide non asymptotic bounds on the error of a parallel General Likelihood Ratio Test, which can also be used for more general testing problems. We further propose lower bound on the number of observation needed to identify a correct hypothesis. Those lower bounds rely on information-theoretic arguments, and specifically on two versions of a change of measure lemma (a high-level form, and a low-level form) whose relative merits are discussed.

Generalized Likelihood Ratio test; Multi-armed bandits; Sequential testing; Best arm identification; Tests; Bandit models; Sequential statistics

Original publication details

Sequential Analysis · vol. 40 · pp. 61-96, 18th Wald Prize · Mar. 2021

Best Arm Identification in Spectral Bandits

Tomáš Kocák, Aurélien Garivier
IJCAI, Jul 2020, Yokohama, Japan
Abstract

We study best-arm identification with fixed confidence in bandit models with graph smoothness constraint. We provide and analyze an efficient gradient ascent algorithm to compute the sample complexity of this problem as a solution of a non-smooth max-min problem (providing in passing a simplified analysis for the unconstrained case). Building on this algorithm, we propose an asymptotically optimal strategy. We furthermore illustrate by numerical experiments both the strategy's efficiency and the impact of the smoothness constraint on the sample complexity. Best Arm Identification (BAI) is an important challenge in many applications ranging from parameter tuning to clinical trials. It is now very well understood in vanilla bandit models, but real-world problems typically involve some dependency between arms that requires more involved models. Assuming a graph structure on the arms is an elegant practical way to encompass this phenomenon, but this had been done so far only for regret minimization. Addressing BAI with graph constraints involves delicate optimization problems for which the present paper offers a solution.

Original publication details

International Joint Conference on Artificial Intelligence (IJCAI) · · · Jul. 2020

2020

Hierarchical and Unsupervised Graph Representation Learning with Loukas’s Coarsening

Algorithms, 2020, 13 (9), pp. 206
Abstract

We propose a novel algorithm for unsupervised graph representation learning with attributed graphs. It combines three advantages addressing some current limitations of the literature: i) The model is inductive: it can embed new graphs without re-training in the presence of new data; ii) The method takes into account both micro-structures and macro-structures by looking at the attributed graphs at different scales; iii) The model is end-to-end differentiable: it is a building block that can be plugged into deep learning pipelines and allows for back-propagation. We show that combining a coarsening method having strong theoretical guarantees with mutual information maximization suffices to produce high quality embeddings. We evaluate them on classification tasks with common benchmarks of the literature. We show that our algorithm is competitive with state of the art among unsupervised graph representation learning methods.

Original publication details

Algorithms 13(9) · 206 (pp. 1-22) · Aug. 2020

Algorithms for Non-Stationary Generalized Linear Bandits

Yoan Russac, Olivier Cappé, Aurélien Garivier
Preprint · March 2020
Abstract

The statistical framework of Generalized Linear Models (GLM) can be applied to sequential problems involving categorical or ordinal rewards associated, for instance, with clicks, likes or ratings. In the example of binary rewards, logistic regression is well-known to be preferable to the use of standard linear modeling. Previous works have shown how to deal with GLMs in contextual online learning with bandit feedback when the environment is assumed to be stationary. In this paper, we relax this latter assumption and propose two upper confidence bound based algorithms that make use of either a sliding window or a discounted maximum-likelihood estimator. We provide theoretical guarantees on the behavior of these algorithms for general context sequences and in the presence of abrupt changes. These results take the form of high probability upper bounds for the dynamic regret that are of order d^2/3 G^1/3 T^2/3 , where d, T and G are respectively the dimension of the unknown parameter, the number of rounds and the number of breakpoints up to time T. The empirical performance of the algorithms is illustrated in simulated environments.

Original publication details

Jan. 2020

A note on perfect simulation for Exponential Random Graph Models

Andressa Cerqueira, Aurélien Garivier, Florencia Leonardi
ESAIM: Probability and Statistics, 2020, 24, pp. 138–147
Abstract

In this paper we propose a perfect simulation algorithm for the Exponential Random Graph Model, based on the Coupling From The Past method of Propp & Wilson (1996). We use a Glauber dynamics to construct the Markov Chain and we prove the monotonicity of the ERGM for a subset of the parametric space. We also obtain an upper bound on the running time of the algorithm that depends on the mixing time of the Markov chain.

Original publication details

ESAIM: Probability and Statistics · · · Mar. 2020

Thresholding Bandit for Dose-ranging: The Impact of Monotonicity

Aurélien Garivier, Pierre Ménard, Laurent Rossi
ICMA 2020 · August 2020
Abstract

We analyze the sample complexity of the thresholding bandit problem, with and without the assumption that the mean values of the arms are increasing. In each case, we provide a lower bound valid for any risk δ and any δ-correct algorithm; in addition, we propose an algorithm whose sample complexity is of the same order of magnitude for small risks. This work is motivated by phase 1 clinical trials, a practically important setting where the arm means are increasing by nature, and where no satisfactory solution is available so far.

Thresholding bandits; Multi-armed bandits; Best arm identification; Unimodal regression; Isotonic regression

A review on quantile regression for stochastic computer experiments

Reliability Engineering and System Safety, 2020, 201 (C)
Abstract

We report on an empirical study of the main strategies for conditional quantile estimation in the context of stochastic computer experiments. To ensure adequate diversity, six metamodels are presented, divided into three categories based on order statistics, functional approaches, and those of Bayesian inspiration. The metamodels are tested on several problems characterized by the size of the training set, the input dimension, the quantile order and the value of the probability density function in the neighborhood of the quantile. The metamodels studied reveal good contrasts in our set of 480 experiments, enabling several patterns to be extracted. Based on our results, guidelines are proposed to allow users to select the best method for a given problem.

Original publication details

Reliability Engineering and System Safety · 201(C) · 2020

2019

X-Armed Bandits: Optimizing Quantiles, CVaR and Other Risks

Léonard Torossian, Aurélien Garivier, Victor Picheny
Asian Conference on Machine Learning, Nov 2019, Nagoya, Japan. pp. 252–267
Abstract

We propose and analyze StoROO, an algorithm for risk optimization on stochastic black-box functions derived from StoOO. Motivated by risk-averse decision making fields like agriculture, medicine, biology or finance, we do not focus on the mean payoff but on generic functionals of the return distribution, like for example quantiles. We provide a generic regret analysis of StoROO. Inspired by the bandit literature and black-box mean optimizers, StoROO relies on the possibility to construct confidence intervals for the targeted functional based on random-size samples. We explain in detail how to construct them for quantiles, providing tight bounds based on Kullback-Leibler divergence. The interest of these tight bounds is highlighted by numerical experiments that show a dramatic improvement over standard approaches.

CVaR optimization; Quantile optimization; Risk-averse solutions; Optimistic optimization

Versions & publication history

Earlier title

X-Armed Bandits: Optimizing Quantiles and Other Risks

Original publication details

Asian Conference on Machine Learning · n°11 · · · · Nov. 2019

Conditional quantile sequential estimation for stochastic codes

Journal of Statistical Theory and Practice · Dec. 2019 (first version in Feb. 2016)
Abstract

This paper is devoted to the estimation of conditional quantile, more precisely the quantile of the output of a real stochastic code whose inputs are in R d. In this purpose, we introduce a stochastic algorithm based on Robbins-Monro algorithm and on k-nearest neighbors theory. We propose conditions on the code for that algorithm to be convergent and study the non-asymptotic rate of convergence of the means square error. Finally, we give optimal parameters of the algorithm to obtain the best rate of convergence.

Stochastic code; Quantile; Non-asymptotic inequality; K nearest neighbors; Stochastic algorithm

Explore First, Exploit Next: The True Shape of Regret in Bandit Problems

Aurélien Garivier, Pierre Ménard, Gilles Stoltz
Mathematics of Operations Research, 2019, 44 (2), pp. 377–399
Abstract

We revisit lower bounds on the regret in the case of multi-armed bandit problems. We obtain non-asymptotic, distribution-dependent bounds and provide simple proofs based only on well-known properties of Kullback-Leibler divergences. These bounds show in particular that in the initial phase the regret grows almost linearly, and that the well-known logarithmic growth of the regret only holds in a final phase. The proof techniques come to the essence of the information-theoretic arguments used and they involve no unnecessary complications. First version: Feb. 2016

Multi-armed bandits; Information-theoretic proof techniques; Non-asymptotic lower bounds; Cumulative regret

Original publication details

Mathematics of Operations Research vol 44(2), pp.377-399 · May 2019

2018

L'IA du Quotidien peut elle être Éthique ? : Loyauté des Algorithmes d'Apprentissage Automatique

Statistique et Société · 6(3), pp. 9–31 · December 2018
Abstract

Associant données massives (big data) et algorithmes d'apprentissage automatique (machine learning), la puissance des outils de décision automatique suscite autant d'espoir que de craintes. De nombreux textes législatifs européens (RGPD) et français récemment promulgués tentent d'encadrer les usages de ces outils. Laissant de côté les problèmes bien identifiés de confidentialité des données et ceux d'entrave à la concurrence, nous nous focalisons sur les risques de discrimination, les problèmes de transparence et ceux de qualité des décisions algorithmiques. La mise en perspective détaillée des textes juridiques, face à la complexité et l'opacité des algorithmes d'apprentissage, révèle la nécessité d'importantes disruptions technologiques que ce soit pour détecter ou réduire le risque de discrimination ou pour répondre au droit à l'explication. La confiance des développeurs et surtout des usagers (citoyens, justiciables, clients) étant indispensable, les algorithmes exploitant des données personnelles se doivent d'être déployés dans un cadre éthique strict. En conclusion nous listons, pour ré-pondre à cette nécessité, quelques possibilités de contrôle à développer : institutionnel, charte éthique, audit externe attaché à la délivrance d'un label. Mots clefs Intelligence artificielle, éthique, apprentissage automatique, discrimination, discrimination impact assessment, droit à l'explication, qualité d'une décision automatique.

Apprentissage automatique; Qualité d’une décision automatique; Droit à l’explication; Discrimination; Éthique; Intelligence artificielle

Sequential Test for the Lowest Mean: From Thompson to Murphy Sampling

Emilie Kaufmann, Wouter Koolen, Aurélien Garivier
Advances in Neural Information Processing Systems (NIPS), Dec 2018, Montréal, Canada
Abstract

(poster) Learning the minimum/maximum mean among a finite set of distributions is a fundamental sub-task in planning, game tree search and reinforcement learning. We formalize this learning task as the problem of sequentially testing how the minimum mean among a finite set of distributions compares to a given threshold. We develop refined non-asymptotic lower bounds, which show that optimality mandates very different sampling behavior for a low vs high true minimum. We show that Thompson Sampling and the intuitive Lower Confidence Bounds policy each nail only one of these cases. We develop a novel approach that we call Murphy Sampling. Even though it entertains exclusively low true minima, we prove that MS is optimal for both possibilities. We then design advanced self-normalized deviation inequalities, fueling more aggressive stopping rules. We complement our theoretical guarantees by experiments showing that MS works best in practice.

Multi-armed bandits; Sequential adaptive hypothesis testing

Original publication details

Neural Information Processing Systems · n°32 · Dec. 2018

Profitable Bandits

Mastane Achab, Stéphan Clémençon, Aurélien Garivier
Proceedings of Machine Learning Research, 2018, 95, pp. 694–709
Abstract

Originally motivated by default risk management applications, this paper
investigates a novel problem, referred to as the profitable bandit problem
here. At each step, an agent chooses a subset of the K possible actions. For
each action chosen, she then receives the sum of a random number of rewards.
Her objective is to maximize her cumulated earnings. We adapt and study three
well-known strategies in this purpose, that were proved to be most efficient in
other settings: kl-UCB, Bayes-UCB and Thompson Sampling. For each of them, we
prove a finite time regret bound which, together with a lower bound we obtain
as well, establishes asymptotic optimality. Our goal is also to compare these
three strategies from a theoretical and empirical perspective both at the same
time. We give simple, self-contained proofs that emphasize their similarities,
as well as their differences. While both Bayesian strategies are automatically
adapted to the geometry of information, the numerical experiments carried out
show a slight advantage for Thompson Sampling in practice.

in Proceedings of Machine Learning Research vol. 95 http://proceedings.mlr.press/v95/

Credit risk; Multi-armed bandits; Thresholding bandits; Bayesian policy

Original publication details

Asian Conference on Machine Learning · n°10 · Nov. 2018

Optimization of a SSP's Header Bidding Strategy using Thompson Sampling

The 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Aug 2018, London, United Kingdom
Abstract

In the last decade digital media: web or app publishers, generalised the use of real-time ad auctions to sell their ad-spaces. Multiple auction platforms, also called Supply Side Platforms (SSP) were created. Because of this multiplicity, publishers started to create competition between SSPs. In this setting, there are two successive auctions: a second price auction in each SSP and a secondary, first price auction, called header bidding auction, between SSPs.

In this paper, we consider an SSP competing with other SSPs for advertising spaces. The SSP acts as an intermediary between an advertiser wanting to buy advertising spaces and a web publisher wanting to sell its advertising spaces, and needs to define a bidding strategy to be able to deliver to the advertisers as many ads as possible while spending as little as possible to deliver them. The revenue optimization of this SSP can be written as a contextual bandit problem, where the context consists of the information available about the ad opportunity, such as properties of the internet user or of the ad placement.

Using traditional multi-armed bandit strategies (such as the original versions of UCB and EXP3) is inefficient in this setting and yields a low convergence speed, as the arms are very correlated. In this paper we design and experiment a version of the Thompson Sampling algorithm that easily takes this correlation into account. This bayesian algorithm, that we combine with a particle filter, enables us to sequentially estimate the distribution of the highest bid to beat in order to win auctions. We apply this methodology on two real auction datasets, and show that it significantly outperforms the classical UCB and EXP3 strategies.

Online Learning; Multi-armed Bandit; Thompson Sampling; Bayesian Inference; Particle Filter; Sequential Monte Carlo; Big-Data; Ad-tech; Real-time; Auctions

Original publication details

Special Interest Group on Knowledge Discovery and Data Mining · n°2 018 · Aug. 2018

2017

Learning the distribution with largest mean: two bandit frameworks

Emilie Kaufmann, Aurélien Garivier
ESAIM: Proceedings and Surveys, 2017, 60, pp. 114–131
Abstract

Over the past few years, the multi-armed bandit model has become increasingly popular in the machine learning community, partly because of applications including online content optimization. This paper reviews two different sequential learning tasks that have been considered in the bandit literature ; they can be formulated as (sequentially) learning which distribution has the highest mean among a set of distributions, with some constraints on the learning process. For both of them (regret minimization and best arm identification) we present recent, asymptotically optimal algorithms. We compare the behaviors of the sampling rule of each algorithm as well as the complexity terms associated to each problem. Le modèle stochastique dit de bandit à plusieurs bras soulève ces dernières années un grand intérêt dans la communauté de l’apprentissage automatique, du fait notamment de ses applications à l’optimisation de contenu sur le web. Cet article présente deux problèmes d’apprentissage séquentiel dans le cadre d’un modèle de bandit qui peuvent être formulés comme la découverte de la distribution ayant la moyenne la plus élevée dans un ensemble de distributions, avec certaines contraintes sur le processus d’apprentissage. Pour ces deux objectifs (minimisation du regret d’une part et identification du meilleur bras d’autre part), nous présentons des algorithmes optimaux, en un sens asymptotique. Nous comparons les stratégies d’échantillonnage employées par ces deux types d’algorithmes ainsi que les quantités caractérisant la complexité de chacun des problèmes. DOI: https://doi.org/10.1051/proc/201760114

Best arm identification; Regret minimization; Ucb; Bandit

Original publication details

ESAIM: Proceedings and Surveys · pp.114-131 · Dec. 2017

A minimax and asymptotically optimal algorithm for stochastic bandits

Pierre Ménard, Aurélien Garivier
Proceedings of Machine Learning Research, 2017, Conference on Algorithmic Learning Theory, 76, pp. 223–237
Abstract

We propose the kl-UCB ++ algorithm for regret minimization in stochastic bandit models with exponential families of distributions. We prove that it is simultaneously asymptotically optimal (in the sense of Lai and Robbins' lower bound) and minimax optimal. This is the first algorithm proved to enjoy these two properties at the same time. This work thus merges two different lines of research, with simple proofs involving no complexity overhead.

Asymptotic optimality; Minimax optimality; Upper confidence bound UCB; Regret analysis; Stochastic multi-armed bandits

Original publication details

Algorithmic Learning Theory · n°28 · pp.223-237 · Oct. 2017

Max K-Armed Bandit: On the ExtremeHunter Algorithm and Beyond

Machine Learning and Knowledge Discovery in Databases ECML PKDD 2017, 2017, pp. 389–404
Abstract

This paper is devoted to the study of the max K-armed bandit problem, which consists in sequentially allocating resources in order to detect extreme values. Our contribution is twofold.
We first significantly refine the analysis of the ExtremeHunter algorithm carried out in [Carpentier et al. 2014], and next propose an alternative approach, showing that, remarkably, Extreme Bandits can be reduced to a classical version of the bandit problem to a certain extent. Beyond the formal analysis, these two approaches are compared through numerical experiments.

Versions & publication history

Earlier title

Max K-armed bandits: On the ExtremeHunter algorithm and beyond

Original publication details

European Conference on Machine Learning · n°2 017 · Sep. 2017

Other version / record · 2017

Max K-armed Bandits: On EstremeHunter and an Alternative Approach

ECML , Sep 2017, Skopje, Macedonia

hal-02287481

Diversified Bandit: the k-diversified Multiple-Play Recommendation Algorithm

Mar. 2017
Abstract

Recommender systems (RS) aim at recommending either one or several items simultaneously : the former type of RS is named single play RS, while the latter is named multiple-play RS. The efficiency of multiple-play RS can be evaluated by two different criteria: the \emph{click-through rate}, which measures the proportion of recommendations that are followed by a click; and the emph{proportion of abandonment}, which measures how many sessions which are followed by no click at all. Minimizing abandonment is at least as important as maximizing the CTR. It requires to diversify the recommendations so as to meet as often as possible one of the various expectations of the users. This paper focuses on this issue. The most efficient models from the litterature rely on machine learning models to determine the items to recommend at each time. While standard machine-learning approaches separate the learning phase (where the best model is estimated from initial interactions) from the recommending phase (where this model is applied repeatedly), the framework of \emph{multi-armed bandits} inherently mixes the exploration of the user's preferences and the exploitation of the learnt preferences. Within the framework of multi-arm bandit algorithms, we propose two variants of a new approach to address the diversification issue. The first one, that we name 2-diversified bandit algorithm, uses the conditional probability that a user clicks on an item, given that the previous item in the list was not clicked. The second one, named k-diversified bandit algorithm, is the generalization of the previous one using the conditional probabilities of an item given that all items recommended at previous positions were not clicked. We show on two reference real-world data sets that our approaches are ten times faster to reach good performance and decrease from $1.5\%$ to $6\%$ the proportion of the abandonment.

Loyauté des Décisions Algorithmiques

Philippe Besse, Céline Castets-Renard, Aurélien Garivier
Preprint · June 2017
Abstract

L'éthique des algorithmes s'inscrit dans des débats plus larges : éthique et nouvelles technologies, éthique et technologie du numérique, éthique et déontologie. Les retracer rapidement permet de préciser la notion de loyauté appliquée à celle de décision algorithmique. Le cadre juridique de la « décision individuelle prise sur le fondement d'un traitement algorithmique » est alors précisé. Il apparaît que, dans ce contexte, les notions de précision, transparence ou explicabilité des décisions, biais des algorithmes, sont centrales pour aborder la « loyauté » de ces derniers et les questions éthiques qu'ils soulèvent. Après avoir explicitées puis illustrées ces questions par des exemples (justice prédictive, biologie et santé), leurs propriétés sont ensuite confrontées aux textes juridiques en cours et à venir pour montrer le peu d'adéquation de ces derniers à la grande complexité des algorithmes concernés. Sont finalement envisagées les actions possibles : évolution des textes juridiques, contrôle ou audit des algorithmes mais pourquoi et par qui ? L'acceptabilité de ces nouvelles technologies par les utilisateurs, citoyens et consommateurs, reste encore la principale motivation ou la rare contrainte des industriels du secteur pour moraliser leur pratique.

Apprentissage machine; Statistique; Droit; Ethique

2016

On Explore-Then-Commit Strategies

Aurélien Garivier, Emilie Kaufmann, Tor Lattimore
NIPS, Dec 2016, Barcelona, Spain
Abstract

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 exploration phase (up to a stopping time) followed by exploitation are necessarily suboptimal. The results hold regardless of whether or not the difference in means between the two arms is known. Besides the main message, we also refine existing deviation inequalities, which allow us to design fully sequential strategies with finite-time regret guarantees that are (a) asymptotically optimal as the horizon grows and (b) order-optimal in the minimax sense. Furthermore we provide empirical evidence that the theory also holds in practice and discuss extensions to non-gaussian and multiple-armed case.
NIPS trailer

Ucb; Sequential statistics; Bandit models

Original publication details

Neural Information Processing Systems · n°30 · Dec. 2016

Algorithme de bandit et obsolescence : un modèle pour la recommandation

Abstract

Un nombre croissant de systèmes numériques font appel à des algortihmes de bandits pour combiner efficacement exploration de l'environnement et exploitation de l'information accumulée. Les modèles de bandits classiques sont toutefois assez naïfs : ils se bornent à un nombre fixé de choix disponibles (appelés bras), et à des répones ne variant pas au cours du temps. Pour les moteurs de recommandation, par exemple, il s'agit de limitations sévèers : de novueaux items à recommander apparaissent régulièrement, et les ancines ont une tendance prévisible à perdre de l'attractivité. Pour faire face à ces problèmes, des stratégies capables de gérer l'évolution temporelle du gain moyen associé à chaque bras ont été proposées. Sic es stratégies sont assez générlaes, elles ne sont pas forcément les plus efficaces dnas le cas où la forme de cette évolution temporelle est largement connue a priori.

Dans cet article, nous proposons deux nouvelles stratégies capabes de prendre en compte d'une part l'obsolescence progressive de chaque bars, et d'autre part l'arrivée de nouveaux brase : Fading-UCB, pour laquelle nous fournissons une analyse détaillée de la borne supérieure de regret, et Trust-and-Abandon. Nous montrons expérimentalement que les deux stratégies proposées permettent d'obtenir de meilleures performances que celles obtenues par les stratégies de l'état de l'art.

Maximin Action Identification: A New Bandit Framework for Games

Aurélien Garivier, Emilie Kaufmann, Wouter M. Koolen
29th Annual Conference on Learning Theory (COLT), Jun 2016, New-York, United States
Abstract

We study an original problem of pure exploration in a strategic bandit model motivated by Monte Carlo Tree Search. It consists in identifying the best action in a game, when the player may sample random outcomes of sequentially chosen pairs of actions. We propose two strategies for the fixed-confidence setting: Maximin-LUCB, based on lower-and upper-confidence bounds; and Maximin-Racing, which operates by successively eliminating the sub-optimal actions. We discuss the sample complexity of both methods and compare their performance empirically. We sketch a lower bound analysis, and possible connections to an optimal algorithm.
Emilie's presentation at COLT on youtube

Best-arm identification; Games; Multi-armed bandit problems; LUCB; Racing

Original publication details

Conference On Learning Theory · n°29 · pp.1 028-1 050 · Jun. 2016

Optimal Best Arm Identification with Fixed Confidence

Aurélien Garivier, Emilie Kaufmann
29th Annual Conference on Learning Theory (COLT), Jun 2016, New York, United States
Abstract

Julia code of the simulations on github
We provide a complete characterization of the complexity of best-arm identification in one-parameter bandit problems. We prove a new, tight lower bound on the sample complexity. We propose the 'Track-and-Stop' strategy, which is proved to be asymptotically optimal. It consists in a new sampling rule (which tracks the optimal proportions of arm draws highlighted by the lower bound) and in a stopping rule named after Chernoff, for which we give a new analysis.
COLT presentation on youtube (with some unfortunate sound recording problems)

Multi-armed bandits; Best arm identification; MDL

Original publication details

Conference On Learning Theory · n°29 · pp.998-1 027 · Jun. 2016

Bregman superquantiles. Estimation methods and applications.

Dependence Modeling · 4(1), pp. 76–108 · 2016
Abstract

In this work, we extend some parameters built on a probability distribution introduced before to the case where the proximity between real numbers is measured by using a Bregman divergence. This leads to the definition of the Bregman superquantile (that we can connect with several works in economy). Axioms of a coherent measure of risk discussed previously are studied in the case of Bregman superquantile. Furthermore, we deal with asymptotic properties of a Monte Carlo estimator of the Bregman superquantile. Several numerical tests confirm the theoretical results and an application illustrates the potential interests of the Bregman superquantile. ISSN (Online) 2300-2298, DOI: 10.1515/demo-2016-0004

Original publication details

Dependence Modeling · (1) · pp.76-108 · Mar. 2016

On the Complexity of Best Arm Identification in Multi-Armed Bandit Models

Emilie Kaufmann, Olivier Cappé, Aurélien Garivier
Journal of Machine Learning Research, 2016, 17, pp. 1–42
Abstract

The stochastic multi-armed bandit model is a simple abstraction that has proven useful in many different contexts in statistics and machine learning. Whereas the achievable limit in terms of regret minimization is now well known, our aim is to contribute to a better understanding of the performance in terms of identifying the m-best arms. We introduce generic notions of complexity for the two dominant frameworks considered in the literature: fixed-budget and fixed-condence settings. In the fixed-confidence setting, we provide the first known distribution-dependent lower bound on the complexity that involves information-theoretic quantities and holds when m>=1 under general assumptions. In the specific case of two armed-bandits, we derive rened lower bounds in both the fixed-confidence and fixed-budget settings, along with matching algorithms for Gaussian and Bernoulli bandit models. These results show in particular that the complexity of the fixed-budget setting may be smaller than the complexity of the fixed-condence setting, contradicting the familiar behavior observed when testing fully specied alternatives. In addition, we also provide improved sequential stopping rules that have guaranteed error probabilities and shorter average running times. The proofs rely on two technical results that are of independent interest : a deviation lemma for self-normalized sums (Lemma 19) and a novel change of measure inequality for bandit models (Lemma 1).

Sequential testing; Information-theoretic divergences; Pure exploration; Best arm identification; Multi-armed bandit

Original publication details

Journal of Machine Learning Research · (1) · pp.1-42 · Jan. 2016

2015

Modélisation Aléatoire et Statistique - Journées MAS 2014 (éditeur)

Aurélien Garivier
ESAIM: Proceedings and Surveys · Oct. 2015 · vol. 51
Abstract

Depuis 1996, les Journées du groupe Modélisation Aléatoire et Statistique (MAS) de la SMAI réunissent tous les deux ans une large part des communautés probabilistes et statistiques françaises. L'édition toulousaine de 2014 était composée de neufs conférences, dont les trois récents titulaires du Prix de thèse Neveu (Adrien Kassel, Quentin Berger et Pierre Jacob), et de vingt-deux sessions thématiques. Elle mettait en avant les "phénomènes de grande dimension" qui, sous divers aspects, concentrent les efforts de nombreux travaux ces dernières années. Ainsi, Nathaël Gozlan a proposé une présentation pédagogique et moderne de la concentration de la mesure et de ses liens avec les inégalités fonctionnelles, tandis que Mylène Maïda montrait comment étudier une transition de phase dans le comportement du spectre des matrices aléatoires; les enjeux de l'étude de ce spectre était mis en avant dans une session dédiée, alors qu'une autre séance résumait plusieurs avancées récentes de la statistique bayésienne en grande dimension, etc. Au delà de la thématique avancée, les Journées MAS constituent avant tout un forum d'échange et de mélange entre spécialistes engagés dans des voies différentes, mais partageant une même culture scientifique et une large gamme d'outils communs. Souvent, les travaux présentés trouvent une part de leur inspiration dans d'autres disciplines, comme la biologie, la finance, ou différents aspects de la physique statistique. Ils se rattachent parfois aussi à d'autres champs des mathématiques, comme la théorie des jeux, la géométrie et/ou la combinatoire. Toutefois, ils constituent un continuum, et l'on voyage de la concentration de la mesure, en passant par l'étude en temps long des processus markoviens, par la sélection de modèles ou par la méthode de la vraisemblance empirique, à la statistique bayésienne, aux méthodes de Monte-Carlo séquentielles pour les chaînes de Markov cachées et aux probabilités numériques, sans solution de continuité. Pour prolonger le succès de ces journées, Arnaud Guillin et Djalil Chafaï ont suggéré d'en publier les actes. Nous avons ainsi proposé à chaque orateur plénier et à chaque session de rédiger un article de revue résumant les points saillants mis en avant pendant le colloque. Cet article constitue une trace de l'état des lieux de la recherche dans le monde de l'aléatoire, et fournit une porte d'entrée dans un domaine à un moment donné. Ce deuxième numéro (après celui des Journées MAS 2012, publié en janvier 2014 dans le volume 44 de ESAIM: Proceedings and Surveys) rassemble donc dix-sept contributions offrant une certaine variété de formes et de tons. Il nous semble aussi utile qu'à même d'attirer la curiosité : le lecteur pourra y butiner quelques articles résumant plaisamment et édagogiquement l'avancée des sujets qu'il connait et suit au quotidien. Il y trouvera également plusieurs présentations lui permettant de découvrir un domaine plus étranger en plein essor. Et d'une lecture plus systématique se dégagera un panorama sûrement pas exhaustif, mais cependant vaste et riche de la recherche actuelle en modélisation aléatoire et statistique. Le niveau scientifique des Journées doit beaucoup à la qualité de son pilotage par le comité scientifique des Journées MAS, et particulièrement son président Pascal Massart. Il était alimenté de nombreuses et toujours pertinentes suggestions par le groupe MAS de la SMAI, présidé par Arnaud Guillin. Mais malgré ces bonnes étoiles, l'édition toulousaine n'aurait pas pu se tenir sans Sébastien Gerchinovitz, Aldéric Joulin, Clément Pellegrini et Laurent Risser : grâce à leur excellente connaissance de la communauté et à leur engagement à son service, ils ont autant contribué à l'attractivité et à l'équilibre scientifique du programme qu'à l'organisation pratique du colloque. Groupe MAS et organisateurs locaux ont ensemble assuré l'essentiel du travail de relecture des articles présentés ici, contribuant parfois significativement à leur qualité. Enfin, ce numéro n'aurait pu exister sans la volonté et l'expertise de Djalil Chafaï, qui en a assure en outre la publication.

Systèmes de recommandations : algorithmes de bandits et évaluation expérimentale

47emes Journees de Statistique de la SFdS (JDS 2015), Jun 2015, Lille, France. pp. 1–8
Abstract

Les systèmes de recommandation à très grande échelle sont aujourd'hui omniprésents sur internet : ouvrages conseillés à l'achat dans les librairies en ligne, articles recommandés sur les sites d'information, sans parler des cadres publicitaires qui financent l'essentiel de très nombreux sites aujourd'hui...
Trouver la meilleure recommandation à faire à un visiteur peut être considéré comme un ``problème de bandits'' : il faut en même temps apprendre ses préférences, et utiliser les interactions déjà passées pour maximiser le nombre de recommandations suivies, tout en restant capable de gérer des flux de données très importants.

Nous présentons ici quelques-uns des algorithmes les plus célèbres pour résoudre ce type de problèmes, et notamment l'algorithme UCB (Upper Confidence Bound), l'{al\-go\-rithme} EXP3 (Exponential weights for Exploration and Exploitation) et le Thompson Sampling (du nom de l'inventeur, au début des années trente, de cette méthode d'inspiration bayésienne). Leurs mérites respectifs sont soulignés et discutés, avec la présentation des résultats théoriques les plus importants les concernant.
Nous montrons en outre, dans un notebook ipython associé, comment expérimenter l'efficacité de ces méthodes pour la recommandation : ceci pose une difficulté particulière, car des jeux de données statiques rendent peu aisée l'évaluation de méthodes vouées à interagir avec des utilisateurs. Nous montrerons en particulier comment mettre en place des expériences sur deux jeux de données célèbres : movielens et jester.

Recommender Systems; Bandit Algorithms; Evaluation on Real Data

Original publication details

Journées de statistiques · n°2 015 · Jun. 2015

A multiple-play bandit algorithm applied to recommender systems

28th International Florida Artificial Intelligence Research Society (FLAIRS 2015), May 2015, Hollywood, United States. pp. 67–72
Abstract

For several web tasks such as ad placement or e-commerce, recommender systems must recommend multiple items to their users---such problems can be modeled as bandits with multiple plays. State-of-the-art methods require running as many single-play bandit algorithms as there are items to recommend. On the contrary, some recent theoretical work in the machine learning literature designed new algorithms to address the multiple-play case directly. These algorithms were proved to have strong theoretical guarantees. In this paper we compare one such multiple-play algorithm with previous methods. We show on two real-world datasets that the multiple-play algorithm we use converges to equivalent values but learns about three times faster than state-of-the-art methods. We also show that carefully adapting these earlier methods can improve their performance.

Information retrieval; Reinforcement learning; Recommender systems; Bandit problems

Versions & publication history

Earlier title

A Multiple-play Bandit Algorithm Applies to Recommender Systems

Original publication details

Florida Artificial Intelligence Research Society Conference · n°28 · pp.67-72 · May. 2015

Algorithmes de bandit pour les systèmes de recommandation : le cas de multiples recommandations simultanées

Conference francophone en Recherche d'Information et Applications (CORIA 2015), Mar 2015, Paris, France. pp. 73–88
Abstract

The multiple-play recommender systems (RS) are RS which recommend several items to the users. RS are based on learning models in order to choose the items to recommend. Among these models, the bandit algorithms offer the advantage to learn and exploite the learnt elements at the same time. Current approaches require running as many instances of a bandit algorithm as there are items to recommend. As opposed to that, we handle all recommendations simultaneously, by a single instance of a bandit algorithm. We show on two benchmark datasets (Movielens and Jester) that our method, MPB (Multiple Play Bandit), obtains a learning rate about thirteen times faster while obtaining equivalent click-through rates. We also show that the choice of the bandit algorithm used impacts the level of improvement.

Problèmes de bandit; Systèmes de recommandation; Recherche d'information

Original publication details

Conférence en Recherche d’Information et Applications · n°12 · pp.73-88 · Mar. 2015

Perfect Simulation Of Processes With Long Memory: a 'Coupling Into And From The Past' Algorithm

Aurélien Garivier
Random Structures and Algorithms, 2015, 46 (2), pp. 300–319
Abstract

We describe a new algorithm for the perfect simulation of variable length Markov chains and random systems with perfect connections. This algorithm generalizes Propp and Wilson's simulation scheme, and is based on the idea of coupling into and from the past. It improves on existing algorithms by relaxing the conditions required on the kernel and by accelerating convergence, even in the simple case of finite order Markov chains. Chains of variable or infinite order are an old object of consideration that raised considerable interest recently because of its applications in applied probability, from information theory to bio-informatics and linguistics.

Coupling into and from the past CIAFTP; Coupling from the past CFTP; Markov chains of infinite order; Context trees; Perfect simulation

Original publication details

Random Structures and Algorithms · (2) · pp.300-319 · Mar. 2015

Algorithmes de bandits pour la recommandation à tirages multiples

Document numérique - Revue des sciences et technologies de l'information. Série Document numérique, 2015, 18 (2–3), pp. 59–79
Abstract

Les systèmes de recommandation (SR) à tirages multiples font référence aux SR recommandant plusieurs objets en même temps aux utilisateurs. La plupart des SR s'appuient sur des modèles d'apprentissage afin de décider les objets à recommander. Parmi ces modèles, les algorithmes de bandits offrent l'avantage d'apprendre tout en exploitant les éléments déjà appris. Les approches actuelles utilisent autant d'instances d'un algorithme de bandits que le nombre d'objets que doit recommander le SR. Nous proposons au contraire de gérer l'ensemble des recommandations par une seule instance d'un algorithme de bandits pour rendre l'apprentissage plus efficace. Nous montrons sur deux jeux de données de références (Movielens et Jester) que notre méthode, MPB (Multiple Plays Bandit), obtient des temps d'apprentissage jusqu'à treize fois plus rapides tout en obtenant des taux de clics équivalents. Nous montrons également que le choix de l'algorithme de bandits utilisé influence l'amélioration obtenue.

Algorithmes de bandits; Systèmes de recommandation; Recherche d'Information

Original publication details

Document numérique (Hermès) · pp.59-79 · Feb. 2015

2014

Poursuite d'étude après un IUT STID : l'exemple du Cursus de Master en Ingénierie Statistique et Informatique Décisionnelle de Toulouse

Cécile Chouquet, Aurélien Garivier
Journées de Statistiques de la SFDS, Jun 2014, Rennes, France
Abstract

Après obtention de leur DUT, de nombreux étudiants des IUT STID souhaitent poursuivre leurs études pour obtenir un Master qui leur donne la possibilité de travailler comme ingénieur-expert ou chef de projet.
Une spécificité forte de la science des données est son aspect bi-disciplinaire : elle nécessite la maîtrise de concepts et d'outils tant informatiques (bases de données et informatique décisionnelle) que mathématiques (statistique et modélisation stochastique).
La formation SID de l'Université Paul Sabatier offre, depuis une douzaine d'années, une filière de poursuite d'étude cohérente qui respecte cette double compétence. Anciennement Institut Universitaire Professionnalisé, elle est devenue cette année un Cursus de Master en Ingénierie. Tout en conservant une forte composante industrielle, elle s'ouvre ainsi à la formation par la recherche et continue à préparer aux métiers d'ingénieurs dans toutes leurs dimensions, en s'appuyant fortement sur les activités de mise en situation.

Nous présentons ici brièvement l'articulation entre l'IUT et le master pour l'{ensei\-gne\-ment} de la statistique, ainsi que son évolution passée et à venir.
Nous revenons sur les atouts que leur passage en IUT donne aux étudiants, ainsi que les difficultés spécifiques qu'ils rencontrent.

Master; Continued studies; Statistics; Master --- education; Poursuite d'étude; STID; IUT; Statistique; Enseignement

Original publication details

Journées de statistiques · n°2 014 · Jun. 2014

On the Complexity of A/B Testing

Emilie Kaufmann, Olivier Cappé, Aurélien Garivier
Conference on Learning Theory, Jun 2014, Barcelona, Spain. pp. 461–481
Abstract

A/B testing refers to the task of determining the best option among two alternatives that yield random outcomes. We provide distribution-dependent lower bounds for the performance of A/B testing that improve over the results currently available both in the fixed-confidence (or delta-PAC) and fixed-budget settings. When the distribution of the outcomes are Gaussian, we prove that the complexity of the fixed-confidence and fixed-budget settings are equivalent, and that uniform sampling of both alternatives is optimal only in the case of equal variances. In the common variance case, we also provide a stopping rule that terminates faster than existing fixed-confidence algorithms. In the case of Bernoulli distributions, we show that the complexity of fixed-budget setting is smaller than that of fixed-confidence setting and that uniform sampling of both alternatives - though not optimal - is advisable in practice when combined with an appropriate stopping criterion.

Sequential testing; Best arm identification; Bandit models; Sample complexity

Original publication details

Conference On Learning Theory · n°27 · pp.461-481 · Jun. 2014

Big Data Analytics - Retour vers le Futur 3; De Statisticien à Data Scientist

Philippe Besse, Aurélien Garivier, Jean-Michel Loubes
Ingénierie des Systèmes d’Information · 19(3), pp. 93–105 · 2014
Abstract

The rapid evolution of information systems managing more and more voluminous data has caused profound paradigm shifts in the job of statistician, becoming successively data miner, bioinformatician and now data scientist. Without the sake of completeness and after having illustrated these successive mutations, this article briefly introduced the new research issues that quickly rise in Statistics, and more generally in Mathematics, in order to integrate the characteristics: volume, variety and velocity, of big data.

Grandes Masses de Données; Apprentissage Statistique; Bioinformatique; Grande Dimension; Données Biologiques à Haut Débit; Fouille de Données; Statistique

Versions & publication history

Earlier title

Big Data - Retour vers le Futur 3; De Statisticien à Data Scientist

Original publication details

Ingénierie des Systèmes d'Information · (3) · pp.93-105 · Mar. 2014

2013

Informational Confidence Bounds for Self-Normalized Averages and Applications

Aurélien Garivier
IEEE Information Theory Workshop, Sep 2013, Seville, Spain. pp. 489–493
Abstract

We present deviation bounds for self-normalized averages and applications to estimation with a random number of observations.
The results rely on a peeling argument in exponential martingale techniques that represents an alternative to the method of mixture.
The motivating examples of bandit problems and context tree estimation are detailed.

Original publication details

IEEE Information Theory Workshop · pp.489-493 · Sep. 2013

Kullback-Leibler Upper Confidence Bounds for Optimal Sequential Allocation

Annals of Statistics, 2013, 41 (3), pp. 1516–1541
Abstract

We consider optimal sequential allocation in the context of the so-called stochastic multi-armed bandit model. We describe a generic index policy, in the sense of Gittins (1979), based on upper confidence bounds of the arm payoffs computed using the Kullback-Leibler divergence. We consider two classes of distributions for which instances of this general idea are analyzed: The kl-UCB algorithm is designed for one-parameter exponential families and the empirical KL-UCB algorithm for bounded and finitely supported distributions. Our main contribution is a unified finite-time analysis of the regret of these algorithms that asymptotically matches the lower bounds of Lai and Robbins (1985) and Burnetas and Katehakis (1996), respectively. We also investigate the behavior of these algorithms when used with general bounded rewards, showing in particular that they provide significant improvements over the state-of-the-art.

Multi-armed bandit problems; Upper confidence bound; Kullback-Leibler divergence; Sequential testing

Original publication details

Annals of Statistics · (3) · pp.1 516-1 541 · Jun. 2013

Joint Estimation of Intersecting Context Tree Models

Antonio Galves, Aurélien Garivier, Elisabeth Gassiat
Scandinavian Journal of Statistics · 40(2) · pp. 344–362 · Jun. 2013
Abstract

We study a problem of model selection for data produced by two different context tree sources. Motivated by linguistic questions, we consider the case where the probabilistic context trees corresponding to the two sources are finite and share many of their contexts. In order to understand the differences between the two sources, it is important to identify which contexts and which transition probabilities are specific to each source. We consider a class of probabilistic context tree models with three types of contexts: those which appear in one, the other, or both sources. We use a BIC penalized maximum likelihood procedure that jointly estimates the two sources. We propose a new algorithm which efficiently computes the estimated context trees. We prove that the procedure is strongly consistent. We also present a simulation study showing the practical advantage of our procedure over a procedure that works separately on each data set.

BIC; Context tree Models; Joint estimation; Penalized maximum likelihood; Variable length markov chains

Optimal Discovery with Probabilistic Expert Advice: Finite Time Analysis and Macroscopic Optimality

Sébastien Bubeck, Damien Ernst, Aurélien Garivier
Journal of Machine Learning Research, 2013, 14, pp. 601–623
Abstract

We consider an original problem that arises from the issue of security analysis of a power system and that we name optimal discovery with probabilistic expert advice. We address it with an algorithm based on the optimistic paradigm and on the Good-Turing missing mass estimator. We prove two different regret bounds on the performance of this algorithm under weak assumptions on the probabilistic experts. Under more restrictive hypotheses, we also prove a macroscopic optimality result, comparing the algorithm both with an oracle strategy and with uniform sampling. Finally, we provide numerical experiments illustrating these theoretical findings.

Optimal discovery; Probabilistic experts; Optimistic algorithm; Good-Turing estimator; UCB

Versions & publication history

Original publication details

Journal of Machine Learning Research · pp.601-623 · Feb. 2013

Conference version · 2012

Optimal Discovery with Probabilistic Expert Advice

Sébastien Bubeck, Damien Ernst, Aurélien Garivier
IEEE Conference on Decision and Control · n°51 · pp. 6808–6812 · Dec. 2012
Abstract

Motivated by issues of security analysis for power systems, we analyze a new problem, called optimal discovery with probabilistic expert advice. We address it with an algorithm based on the optimistic paradigm and the Good-Turing missing mass estimator. We show that this strategy attains the optimal discovery rate in a macroscopic limit sense, under some assumptions on the probabilistic experts. We also provide numerical experiments suggesting that this optimal behavior may still hold under weaker assumptions.

2012

On Bayesian Upper Confidence Bounds for Bandit Problems

Emilie Kaufmann, Olivier Cappé, Aurélien Garivier
International Conference on Artificial Intelligence and Statistics (AISTATS), Apr 2012, La Palma, Iles Canaries, Spain. pp. 592–600
Abstract

Stochastic bandit problems have been analyzed from two different perspectives: a frequentist view, where the parameter is a deterministic unknown quantity, and a Bayesian approach, where the parameter is drawn from a prior distribution. We show in this paper that methods derived from this second perspective prove optimal when evaluated using the frequentist cumulated regret as a measure of performance. We give a general formulation for a class of Bayesian index policies that rely on quantiles of the posterior distribution. For binary bandits, we prove that the corresponding algorithm, termed Bayes-UCB, satisfies finite-time regret bounds that imply its asymptotic optimality. More generally, Bayes-UCB appears as an unifying framework for several variants of the UCB algorithm addressing different bandit problems (parametric multi-armed bandits, Gaussian bandits with unknown mean and variance, linear bandits). But the generality of the Bayesian approach makes it possible to address more challenging models. In particular, we show how to handle linear bandits with sparsity constraints by resorting to Gibbs sampling.

Statistiques bayésiennes; Algorithmes de bandits

Original publication details

International Conference on Artificial Intelligence and Statistics · n°15 · pp.592-600 · Apr. 2012

2011

Sequential Monte Carlo smoothing for general state space hidden Markov models

Randal Douc, Aurélien Garivier, Eric Moulines, Jimmy Olsson
The Annals of Applied Probability, 2011, 21 (6), pp. 2109–2145
Abstract

Computing smoothing distributions, the distributions of one or more states conditional on past, present, and future observations is a recurring problem when operating on general hidden Markov models. The aim of this paper is to provide a foundation of particle-based approximation of such distributions and to analyze, in a common unifying framework, different schemes producing such approximations. In this setting, general convergence results, including exponential deviation inequalities and central limit theorems, are established. In particular, time uniform bounds on the marginal smoothing error are obtained under appropriate mixing conditions on the transition kernel of the latent chain. In addition, we propose an algorithm approximating the joint smoothing distribution at a cost that grows only linearly with the number of particles.

Sequential Monte Carlo methods; Particle filter; Smoothing; Hidden Markov models

Versions & publication history

Original publication details

Annals of Applied Probability · (6) · pp.2 109-2 145 · Dec. 2011

Preprint · 2009

On the Forward Filtering Backward Smoothing particle approximations of the smoothing distribution in general state spaces models

2009

hal-00370685

Other version / record · 2009

Approximation particulaire par FFBS de la loi de lissage pour des HMM dans des espaces d'états généraux

41èmes Journées de Statistique, SFdS, Bordeaux , 2009, Bordeaux, France, France

inria-00386750

Context Tree Selection: A Unifying View

Aurélien Garivier, Florencia Leonardi
Stochastic Processes and their Applications · 121(11) · pp. 2488–2506 · Nov. 2011
Abstract

Context tree models have been introduced by Rissanen as a parsimonious generalization of Markov models. Since then, they have been widely used in applied probability and statistics. The present paper investigates non-asymptotic properties of two popular procedures of context tree estimation: Rissanen’s algorithm Context and penalized maximum likelihood. First showing how they are related, we prove finite horizon bounds for the probability of over- and under-estimation. Concerning over-estimation, no boundedness or loss-of-memory conditions are required: the proof relies on new deviation inequalities for empirical probabilities of independent interest. The under-estimation properties rely on classical hypotheses for processes of infinite memory. These results improve on and generalize the bounds obtained in Duarte et al. (2006), Galves et al. (2008), Galves and Leonardi (2008), Leonardi (2010), refining asymptotic results of Bühlmann and Wyner (1999) and Csiszár and Talata (2006).

On Upper-Confidence Bound Policies for Non-stationary Bandit Problems

Aurélien Garivier, Eric Moulines
Algorithmic Learning Theory · n°22 · pp. 174–188 · Oct. 2011
Abstract

Many problems, such as cognitive radio, parameter control of a scanning tunnelling microscope or internet advertisement, can be modelled as non-stationary bandit problems where the distributions of rewards changes abruptly at unknown time instants. In this paper, we analyze two algorithms designed for solving this issue: discounted UCB (D-UCB) and sliding-window UCB (SW-UCB). We establish an upper-bound for the expected regret by upper-bounding the expectation of the number of times suboptimal arms are played. The proof relies on an interesting Hoeffding type inequality for self normalized deviations with a random number of summands. We establish a lower-bound for the regret in presence of abrupt changes in the arms reward distributions. We show that the discounted UCB and the sliding-window UCB both match the lower-bound up to a logarithmic factor. Numerical simulations show that D-UCB and SW-UCB perform significantly better than existing soft-max methods like EXP3.S.

Multi-armed bandit; Reinforcement learning; Deviation inequalities; Non-stationary environment

The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond

Aurélien Garivier, Olivier Cappé
Conference On Learning Theory · n°24 · pp. 359–376 · Jul. 2011
Abstract

This paper presents a finite-time analysis of the KL-UCB algorithm, an online, horizon-free index policy for stochastic bandit problems. We prove two distinct results: first, for arbitrary bounded rewards, the KL-UCB algorithm satisfies a uniformly better regret bound than UCB and its variants; second, in the special case of Bernoulli rewards, it reaches the lower bound of Lai and Robbins. Furthermore, we show that simple adaptations of the KL-UCB algorithm are also optimal for specific classes of (possibly unbounded) rewards, including those generated from exponential families of distributions. A large-scale numerical study comparing KL-UCB with its main competitors (UCB, MOSS, UCB-Tuned, UCB-V, DMED) shows that KL-UCB is remarkably efficient and stable, including for short time horizons. KL-UCB is also the only method that always performs better than the basic UCB policy. Our regret bounds rely on deviations results of independent interest which are stated and proved in the Appendix. As a by-product, we also obtain an improved regret bound for the standard UCB algorithm.
COLT presentation on videolectures

Optimally Sensing a Single Channel Without Prior Information: The Tiling Algorithm and Regret Bounds

Sarah Filippi, Olivier Cappé, Aurélien Garivier
IEEE Journal of Selected Topics in Signal Processing · 5(1) · pp. 68–76 · Feb. 2011
Abstract

We consider the task of optimally sensing a two-state Markovian channel with an observation cost and without any prior information regarding the channel's transition probabilities. This task is of interest in the field of cognitive radio as a model for opportunistic access to a communication network by a secondary user. The optimal sensing problem may be cast into the framework of model-based reinforcement learning in a specific class of partially observable Markov decision processes (POMDPs). We propose the Tiling Algorithm, an original method aimed at reaching an optimal tradeoff between the exploration (or estimation) and exploitation requirements. It is shown that this algorithm achieves finite horizon regret bounds that are as good as those recently obtained for multi-armed bandits and finite-state Markov decision processes (MDPs).

Restless Bandit; Cognitive Radio; Opportunistic Channel Access; POMDPs; Regret Bounds; Reinforcement learning

Oracle approach and slope heuristic in context tree estimation

Aurélien Garivier, Matthieu Lerasle
Preprint · November 2011
Abstract

We introduce a general approach to prove oracle properties in context tree selection. The results derive from a concentration condition that is verified, for example, by mixing processes. Moreover, we show the superiority of the oracle approach from a non-asymptotic point of view in simulations where the classical BIC estimator has nice oracle properties even when it does not recover the source. Our second objective is to extend the slope algorithm of \cite{AM08} to context tree estimation. The algorithm gives a practical way to evaluate the leading constant in front of the penalties. We study the slope heuristic underlying this algorithm and obtain the first results on the slope phenomenon in a discrete, non i.i.d framework. We illustrate in simulations the improvement of the oracle properties of BIC estimators by the slope algorithm.

Earlier title

Oracle approach in context tree estimation

2010

Parametric Bandits: The Generalized Linear Case

Abstract

We consider structured multi-armed bandit problems based on the Generalized Linear Model (GLM) framework of statistics. For these bandits, we propose a new algorithm, called GLM-UCB. We derive finite time, high probability bounds on the regret of the algorithm, extending previous analyses developed for the linear bandits to the non-linear case. The analysis highlights a key difficulty in generalizing linear bandit algorithms to the non-linear case, which is solved in GLM-UCB by focusing on the reward space rather than on the parameter space. Moreover, as the actual effectiveness of current parameterized bandit algorithms is often poor in practice, we provide a tuning method based on asymptotic arguments, which leads to significantly better practical performance. We present two numerical experi-
ments on real-world data that illustrate the potential of the GLM-UCB approach.

Optimism in Reinforcement Learning and Kullback-Leibler Divergence

Sarah Filippi, Olivier Cappé, Aurélien Garivier
Communication, Control, and Computing (Allerton), 2010 48th Annual Allerton Conference on, Sep 2010, Monticello (Illinois), United States. pp. 115–122
Abstract

We consider model-based reinforcement learning in finite Markov Decision Processes (MDPs), focussing on so-called optimistic strategies. In MDPs, optimism can be implemented by carrying out extended value iterations under a constraint of consistency with the estimated model transition probabilities. The UCRL2 algorithm by Auer, Jaksch and Ortner (2009), which follows this strategy, has recently been shown to guarantee near-optimal regret bounds. In this paper, we strongly argue in favor of using the Kullback-Leibler (KL) divergence for this purpose. By studying the linear maximization problem under KL constraints, we provide an efficient algorithm, termed KL-UCRL, for solving KL-optimistic extended value iteration. Using recent deviation bounds on the KL divergence, we prove that KL-UCRL provides the same guarantees as UCRL2 in terms of regret. However, numerical experiments on classical benchmarks show a significantly improved behavior, particularly when the MDP has reduced connectivity. To support this observation, we provide elements of comparison between the two algorithms based on geometric considerations.

Regret bounds; Kullback-Leibler divergence; Optimism; Model-based approaches; Markov decision processes; Reinforcement learning

Original publication details

Allerton Conference on Communication, Control, and Computing · n°48 · pp.115-122 · Sep. 2010

Bandits contextuels: apprentissage par renforcement dans les modèles linéaires généralisés

Abstract

Nous considérons des problèmes de bandits multibras structurés dans lesquels l’agent est guidé par une connaissance a priori sur la structure de la récompense qui peut être exploitée de manière à sélectionner efficacement un bras optimal dans des situations o`u le nombre de bras est tr`es grand voire infini. Nous proposons un nouvel algorithme optimiste pour des problèmes de bandit paramétriques non-linéaires en utilisant le cadre des modèles linéaires généralisés (GLM). Ce cadre permet en particulier de s’intéresser au cas de récompenses binaires, non considéré jusqu’à présent. Nous analysons le regret de l’algorithme proposé, nommé GLM-UCB, et obtenons des résultats similaires à ceux récemment prouvés dans la littérature pour le cas de la régression linéaire. L’analyse met également en évidence une difficultés clé dans le cas non-linéaire que nous résolvons en nous focalisant sur l’espace des récompenses plutôt que sur celui des paramètres. De plus, les performances des algorithmes actuels pour des problèmes de bandits contextuels étant souvent décevantes en pratique, nous présentons des arguments asymptotiques qui conduisent à un algorithme efficace. Nous illustrons la performance et la robustesse de l’algorithme à la fois sur des données simulées et réelles.

2009

On Approximate Maximum Likelihood Methods for Blind Identification: How to Cope with the Curse of Dimensionality

Steffen Barembruch, Aurélien Garivier, Eric Moulines
IEEE Transactions on Signal Processing · 57(11) · pp. 4247–4259 · Nov. 2009
Abstract

We discuss approximate maximum-likelihood methods for blind identification and deconvolution. These algorithms are based on particle approximation versions of the expectation-maximization (EM) algorithm. We consider three different methods which differ in the way the posterior distribution of the symbols is computed. The first algorithm is a particle approximation method of the fixed-interval smoothing. The two-filter smoothing and the novel joined-two-filter smoothing involve an additional backward-information filter. Because the state space is finite, it is furthermore possible at each step to consider all the offsprings of any given particle. It is then required to construct a novel particle swarm by selecting, among all these offsprings, particle positions and computing appropriate weights. We propose here a novel unbiased selection scheme, which minimizes the expected loss with respect to general distance functions. We compare these smoothing algorithms and selection schemes in a Monte Carlo experiment. We show a significant performance increase compared to the expectation maximization Viterbi algorithm (EMVA), a fixed-lag smoothing algorithm and the Block constant modulus algorithm (CMA).

Conference version · 2008

On Approximate Maximum Likelihood Methods for Blind Identification: How to Cope with the Curse of Dimensionality

Steffen Barembruch, Aurélien Garivier, Eric Moulines
Abstract

We discuss approximate maximum likelihood methods for blind identification and deconvolution. These algorithms are based on particle approximation versions of the EM algorithm. We consider two different methods which differ in the way the posterior distribution of the symbols is computed. The first algorithm is based on a novel particle approximation method of the fixed-interval smoothing whereas the second uses fixed lag smoothing. We compare the two algorithms in a Monte-Carlo experiment; these two methods perform significantly better than the EMVA algorithm, which is considered as the state of the art in this area.

A Lower-Bound for the Maximin Redundancy in Pattern Coding

Aurélien Garivier
Entropy, 2009, 11 (4), pp. 634–642
Abstract

We show that the maximin average redundancy in pattern coding is eventually larger than 1.84 (n/log n)1/3 for messages of length n. This improves recent results on pattern redundancy, although it does not fill the gap between known lower- and upper-bounds. The pattern of a string is obtained by replacing each symbol by the index of its first occurrence. The problem of pattern coding is of interest because strongly universal codes have been proved to exist for patterns while universal message coding is impossible for memoryless sources on an infinite alphabet. The proof uses fine combinatorial results on partitions with small summands.

Universal coding; Pattern; Minimax

Versions & publication history

Earlier title

A Lower-bound for the Maximin Redundancy in Pattern Processes

Original publication details

Entropy · (4) · pp.634-642 · Oct. 2009

Pseudo-regenerative block-bootstrap for hidden Markov chains

Stéphan Clémençon, Aurélien Garivier, Jessica Tressou
IEEE Statistical Signal Processing Workshop · pp. 465–468 · August 2009
Abstract

This paper is devoted to extend the regenerative block-bootstrap (RBB) proposed for regenerative Markov chains to Hidden Markov Models {(Xn, Yn)}. In the HMM setup, regeneration times of the underlying chain X (i.e. consecutive times at which it visits a given state), which are regeneration times for the bivariate chain (X, Y) as well, are not observable. The principle underlying the RBB extension consists in resampling the output by generating first a sequence of approximate regeneration times for X from data Y(n) = (Y1, ... , Yn), by splitting up next Y(n) into data blocks corresponding to the pseudo-renewal times obtained and, eventually, by resampling the blocks until the (random) length of the reconstructed series is a least n. Beyond the algorithmic description of the resampling procedure, which we call dasiahidden regenerative block-bootstrappsila (HRBB), its performance is evaluated on a simple simulation example.

Confidence interval; Resampling; Bootstrap; Regeneration; Hidden Markov chain

Versions & publication history

Earlier title

Pseudo Regenerative Block-Bootstrap for Hidden Markov Models

Original publication details

IEEE Statistical Signal Processing Workshop · n°15 · pp.465-468 · Aug. 2009

Other version / record · 2009

Pseudo-regenerative block-bootstrap for hidden Markov chains

IEEE, pp.465-468, 2009

hal-02107248

A minimum description length approach to hidden Markov models with Poisson and Gaussian emissions. Application to order identification

Antoine Chambaz, Aurélien Garivier, Elisabeth Gassiat
Journal of Statistical Planning and Inference, 2009, 139 (3), pp. 962–977
Abstract

We address the issue of order identification for hidden Markov models with Poisson and Gaussian emissions. We prove information-theoretic BIC-like mixture inequalities in the spirit of Finesso [1991. Consistent estimation of the order for Markov and hidden Markov chains. Ph.D. Thesis, University of Maryland]; Liu and Narayan [1994. Order estimation and sequential universal data compression of a hidden Markov source by the method of mixtures. Canad. J. Statist. 30(4), 573–589]; Gassiat and Boucheron [2003. Optimal error exponents in hidden Markov models order estimation. IEEE Trans. Inform. Theory 49(4), 964–980]. These inequalities lead to consistent penalized estimators that need no prior bound on the order. A simulation study and an application to postural analysis in humans are provided.

Versions & publication history

Earlier title

A MDL approach to HMM with Poisson and Gaussian emissions. Application to order identification

Original publication details

Journal of Statistical Planning and Inference · (3) · pp.962-977 · Mar. 2009

Coding on countably infinite alphabets

Stéphane Boucheron, Aurélien Garivier, Elisabeth Gassiat
IEEE Transactions on Information Theory, 2009, 55 (1), pp. 358–373
Abstract

This paper describes universal lossless coding strategies for compressing sources on countably infinite alphabets. Classes of memoryless sources defined by an envelope condition on the marginal distribution provide benchmarks for coding techniques originating from the theory of universal coding over finite alphabets. We prove general upper bounds on minimax regret and lower bounds on minimax redundancy for such source classes. The general upper bounds emphasize the role of the normalized maximum likelihood (NML) codes with respect to minimax regret in the infinite alphabet context. Lower bounds are derived by tailoring sharp bounds on the redundancy of Krichevsky-Trofimov coders for sources over finite alphabets. Up to logarithmic (resp., constant) factors the bounds are matching for source classes defined by algebraically declining (resp., exponentially vanishing) envelopes. Effective and (almost) adaptive coding techniques are described for the collection of source classes defined by algebraically vanishing envelopes. Those results extend our knowledge concerning universal coding to contexts where the key tools from parametric inference are known to fail.

Adaptive compression; Redundancy; Countable alphabets; Nml

Versions & publication history

Original publication details

IEEE Transactions on Information Theory · (1) · pp.358-373 · Jan. 2009

Other version / record · 2009

Coding over infinite alphabets

IEEE Transactions on Information Theory , 2009, 55 (1), pp.358-373

hal-00356674

2008

On Optimal Sampling for Particle Filtering in Digital Communication

Steffen Barembruch, Aurélien Garivier, Eric Moulines
Abstract

Particle filtering has been successfully used to approximate the fixed-lag or fixed-interval smoothing distributions in digital communication and to perform approximate maximum likelihood inference. Because the state-space is finite, it is possible at each step to consider all the offsprings (path) of any given particle. Because each particle has typically several possible offsprings, the population of offsprings is larger than the initial population; it is thus required to construct a novel particle swarm by selecting, among all these offsprings, particle positions and computing appropriate weights. We propose here a novel unbiased selection algorithm, which minimizes the expected loss with respect to general distance functions. In a blind deconvolution setting, the selection schemes associated to the Chi-Square distance and the Kullback-Leibler divergence are compared by simulations to the deterministic scheme that keep only the best weights.

2006

Redundancy of the Context-Tree Weighting Method on Renewal and Markov Renewal Processes

Aurélien Garivier
IEEE Transactions on Information Theory · 52(12) · pp. 5579–5586 · Dec. 2006
Abstract

The Context Tree Weighting method (CTW) is shown to be almost adaptive on the classes of renewal and Markov renewal processes. Up to logarithmic factor, ctw achieves the minimax pointwise redundancy described by I. Csiszaacuter and P. Shields in IEEE Trans. Inf. Theory, vol. 42, no. 6, pp. 2065-2072, Nov. 1996. This result not only complements previous results on the adaptivity of the Context-Tree Weighting method on the relatively small class of all finite context-tree sources (which encompasses the class of all finite order Markov sources), it shows that almost minimax redundancy can be achieved on massive classes of sources (classes that cannot be smoothly parameterized by subsets of finite-dimensional spaces). Moreover, it shows that (almost) adaptive compression can be achieved in a computationally efficient way on those massive classes. While previous adaptivity results for CTW could rely on the fact that any Markov source is a finite-context-tree source, this is no longer the case for renewal sources. In order to prove almost adaptivity of CTW over renewal sources, it is necessary to establish that CTW carefully balances estimation error and approximation error.

Consistency of the unlimited BIC Context Tree estimator

Aurélien Garivier
IEEE Transactions on Information Theory · 52(10) · pp. 4630–4635 · Oct. 2006
Abstract

The Bayesian information criterion (BIC) and Krichevsky- Trofimov (KT) version of minimum description length (MDL) principle are popular in the study of model selection. For order estimation of Markov chains, both are known to be strongly consistent when there is an upper-bound on the order. In the unbounded case, the BIC is also known to be consistent, but the KT estimator is consistent only with a bound o(log n) on the order. For context trees, a flexible generalization of Markov models widely used in data processing, the problem is more complicated both in theory and practice, given the substantially higher number of possible candidate models. Imre Csiszar and Zsolt Talata proved the consistency of BIC and KT when the hypothetical tree depths are allowed to grow as o(log n). This correspondence proves that such a restriction is not necessary for finite context sources: the BIC context tree estimator is strongly consistent even if there is no constraint at all on the size of the chosen tree. Moreover, an algorithm computing the tree minimizing the BIC criterion among all context trees in linear time is provided.

2003

2002

An event spacing experiment

Abstract

Events in self-timed rings can propagate evenly spaced or as bursts. By studying these phenomena, we obtain a better understanding of the underlying dynamics of self-timed pipelines, which is a necessary precursor to utilizing these dynamics to obtain higher performance. We show that standard bounded delay models are inadequate to discriminate between bursting and evenly spaced behaviours and show that an extension of the Charlie Diagrams provides a framework for understanding these phenomena. This paper describes our novel analytical approaches and the design and fabrication of a chip to test our theoretical models.