# LITE: Efficiently Estimating Gaussian Probability of Maximality

arXiv: https://arxiv.org/abs/2501.13535 · HTML: https://mlsanity.com/paper/2501.13535/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 59 references that are in the map.
- First posted on arXiv 23 Jan 2025.

## Builds on (most cited first, 18 of 18)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Max-value Entropy Search for Efficient Bayesian Optimization](https://mlsanity.com/paper/1703.01968/) (2017)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Sample Efficiency Matters: A Benchmark for Practical Molecular Optimization](https://mlsanity.com/paper/2206.12411/) (2022)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Joint Entropy Search for Maximally-Informed Bayesian Optimization](https://mlsanity.com/paper/2206.04771/) (2022)
- [Optimal Regret Analysis of Thompson Sampling in Stochastic Multi-armed Bandit Problem with Multiple Plays](https://mlsanity.com/paper/1506.00779/) (2015)
- [Transductive Active Learning: Theory and Applications](https://mlsanity.com/paper/2402.15898/) (2024)
- [Preferential Bayesian optimisation with Skew Gaussian Processes](https://mlsanity.com/paper/2008.06677/) (2020)
- [Optimization as Estimation with Gaussian Processes in Bandit Settings](https://mlsanity.com/paper/1510.06423/) (2015)
- [Probabilistic Inference in Reinforcement Learning Done Right](https://mlsanity.com/paper/2311.13294/) (2023)
- [Variational Bayesian Optimistic Sampling](https://mlsanity.com/paper/2110.15688/) (2021)
- [Discovering Valuable Items from Massive Data](https://mlsanity.com/paper/1506.00935/) (2015)
- [The Iterates of the Frank-Wolfe Algorithm May Not Converge](https://mlsanity.com/paper/2202.08711/) (2022)

## Built on by (most cited first, 3 of 3)

- [Thompson Sampling via Fine-Tuning of LLMs](https://mlsanity.com/paper/2510.13328/) (2025)
- [A Theoretical Analysis of Test-Driven Code Generation](https://mlsanity.com/paper/2602.06098/) (2026)
- [POETS: Uncertainty-Aware LLM Optimization via Compute-Efficient Policy Ensembles](https://mlsanity.com/paper/2605.07775/) (2026)

## Abstract (arXiv)

We consider the problem of computing the probability of maximality (PoM) of a Gaussian random vector, i.e., the probability for each dimension to be maximal. This is a key challenge in applications ranging from Bayesian optimization to reinforcement learning, where the PoM not only helps with finding an optimal action, but yields a fine-grained analysis of the action domain, crucial in tasks such as drug discovery. Existing techniques are costly, scaling polynomially in computation and memory with the vector size. We introduce LITE, the first approach for estimating Gaussian PoM with almost-linear time and memory complexity. LITE achieves SOTA accuracy on a number of tasks, while being in practice several orders of magnitude faster than the baselines. This also translates to a better performance on downstream tasks such as entropy estimation and optimal control of bandits. Theoretically, we cast LITE as entropy-regularized UCB and connect it to prior PoM estimators.