Learning to optimize via posterior sampling
From MaRDI portal
Abstract: This paper considers the use of a simple posterior sampling algorithm to balance between exploration and exploitation when learning to optimize actions such as in multi-armed bandit problems. The algorithm, also known as Thompson Sampling, offers significant advantages over the popular upper confidence bound (UCB) approach, and can be applied to problems with finite or infinite action spaces and complicated relationships among action rewards. We make two theoretical contributions. The first establishes a connection between posterior sampling and UCB algorithms. This result lets us convert regret bounds developed for UCB algorithms into Bayesian regret bounds for posterior sampling. Our second theoretical contribution is a Bayesian regret bound for posterior sampling that applies broadly and can be specialized to many model classes. This bound depends on a new notion we refer to as the eluder dimension, which measures the degree of dependence among action rewards. Compared to UCB algorithm Bayesian regret bounds for specific model classes, our general bound matches the best available for linear models and is stronger than the best available for generalized linear models. Further, our analysis provides insight into performance advantages of posterior sampling, which are highlighted through simulation results that demonstrate performance surpassing recently proposed UCB algorithms.
Recommendations
Cites work
- scientific article; zbMATH DE number 5485582 (Why is no real title available?)
- scientific article; zbMATH DE number 6276176 (Why is no real title available?)
- Adaptive treatment allocation and the multi-armed bandit problem
- Asymptotically efficient adaptive allocation rules
- Computationally Related Problems
- Finite-time analysis of the multiarmed bandit problem
- Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting
- Kullback-Leibler upper confidence bounds for optimal sequential allocation
- Linearly parameterized bandits
- Near-optimal regret bounds for Thompson sampling
- Regret analysis of stochastic and nonstochastic multi-armed bandit problems
- The knowledge gradient algorithm for a general class of online learning problems
- X-armed bandits
Cited in
(70)- Thompson sampling for zero-inflated count outcomes with an application to the drink less mobile health study
- Online learning and pricing for multiple products with reference price effects
- Optimal learning with local nonlinear parametric models over continuous designs
- On the convergence rates of expected improvement methods
- On the Prior Sensitivity of Thompson Sampling
- Reinforcement Learning, Bit by Bit
- Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning
- Online resource allocation with personalized learning
- A survey on online learning methods: Thompson sampling and others
- Finding the optimal exploration-exploitation trade-off online through Bayesian risk estimation and minimization
- Practical Bayesian support vector regression for financial time series prediction and market condition change detection
- Multiobjective optimization using the R2 utility
- Nonstationary bandits with habituation and recovery dynamics
- Technical note: Consistency analysis of sequential learning under approximate Bayesian inference
- Simple fixes that accommodate switching costs in multi-armed bandits
- Learning to optimize via information-directed sampling
- The local time method for targeting and selection
- Optimal information blending with measurements in the \(L^{2}\) sphere
- Decomposable Markov decision processes: A fluid optimization approach
- Optimal learning in linear regression with combinatorial feature selection
- On maximum a posteriori estimation with Plug \& Play priors and stochastic gradient descent
- Online decision making with high-dimensional covariates
- On Bayesian index policies for sequential resource allocation
- Bayesian exploration for approximate dynamic programming
- Satisficing in Time-Sensitive Bandit Learning
- Bayesian adversarial multi-node bandit for optimal smart grid protection against cyber attacks
- scientific article; zbMATH DE number 7307488 (Why is no real title available?)
- Bandit Theory: Applications to Learning Healthcare Systems and Clinical Trials
- Optimal learning policies for differential privacy in multi-armed bandits
- Game of thrones: fully distributed learning for multiplayer bandits
- Variance regularization in sequential Bayesian optimization
- scientific article; zbMATH DE number 7626733 (Why is no real title available?)
- Improved regret for zeroth-order adversarial bandit convex optimisation
- Optimal learning for sequential sampling with non-parametric beliefs
- Multi-armed bandit-based hyper-heuristics for combinatorial optimization problems
- ON THE IDENTIFICATION AND MITIGATION OF WEAKNESSES IN THE KNOWLEDGE GRADIENT POLICY FOR MULTI-ARMED BANDITS
- Bayesian optimization with partially specified queries
- Optimistic Posterior Sampling for Reinforcement Learning: Worst-Case Regret Bounds
- Factorial Designs for Online Experiments
- Sequential Model-Based Optimization for Continuous Inputs with Finite Decision Space
- Simple Bayesian algorithms for best-arm identification
- A model-free sampling method for basins of attraction using hybrid active learning (HAL)
- scientific article; zbMATH DE number 7307478 (Why is no real title available?)
- Best arm identification in generalized linear bandits
- Posterior exploration based sequential Monte Carlo for global optimization
- Thompson sampling: an asymptotically optimal finite-time analysis
- Infinite Arms Bandit: Optimality via Confidence Bounds
- Sequential Monte Carlo bandits
- Complete expected improvement converges to an optimal budget allocation
- Optimal learning for nonlinear parametric belief models over multidimensional continuous spaces
- Optimal online learning for nonlinear belief models using discrete priors
- IntelligentPooling: practical Thompson sampling for mHealth
- Near-optimal regret bounds for Thompson sampling
- Multi-armed bandit for species discovery: a Bayesian nonparametric approach
- Online learning of network bottlenecks via minimax paths
- Minimax approach to the Gaussian multi-armed bandit
- Online Network Revenue Management Using Thompson Sampling
- Online learning of energy consumption for navigation of electric vehicles
- Variable Selection Via Thompson Sampling
- Reward Maximization Through Discrete Active Inference
- Optimal sequential stochastic shortest path interdiction
- Multi-armed bandit with sub-exponential rewards
- Gaussian process bandits with adaptive discretization
- Multi-armed bandit experiments in the online service economy
- Multi-fidelity cost-aware Bayesian optimization
- Deep exploration via randomized value functions
- Efficient Simulation of High Dimensional Gaussian Vectors
- Sequential Bayesian replacement with unknown transition probabilities
- Statistical arbitrage under a fractal price model
- A unified framework for stochastic optimization
This page was built for publication: Learning to optimize via posterior sampling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5247618)
