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
- X-armed bandits
- 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
- scientific article; zbMATH DE number 5485582 (Why is no real title available?)
- scientific article; zbMATH DE number 6276176 (Why is no real title available?)
- 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
Cited in
(72)- Posterior exploration based sequential Monte Carlo for global optimization
- Gaussian process bandits with adaptive discretization
- A unified framework for stochastic optimization
- On Bayesian index policies for sequential resource allocation
- Bayesian adversarial multi-node bandit for optimal smart grid protection against cyber attacks
- Improved regret for zeroth-order adversarial bandit convex optimisation
- Multi-armed bandit with sub-exponential rewards
- Best arm identification in generalized linear bandits
- IntelligentPooling: practical Thompson sampling for mHealth
- A model-free sampling method for basins of attraction using hybrid active learning (HAL)
- Bayesian optimization with partially specified queries
- Multi-fidelity cost-aware Bayesian optimization
- On the Prior Sensitivity of Thompson Sampling
- On the convergence rates of expected improvement methods
- Decomposable Markov decision processes: A fluid optimization approach
- Optimal learning in linear regression with combinatorial feature selection
- Thompson sampling: an asymptotically optimal finite-time analysis
- A survey on online learning methods: Thompson sampling and others
- Optimal learning with local nonlinear parametric models over continuous designs
- Variance regularization in sequential Bayesian optimization
- Optimal information blending with measurements in the \(L^{2}\) sphere
- Optimal learning for nonlinear parametric belief models over multidimensional continuous spaces
- Practical Bayesian support vector regression for financial time series prediction and market condition change detection
- Near-optimal regret bounds for Thompson sampling
- Multi-armed bandit for species discovery: a Bayesian nonparametric approach
- Learning to optimize via information-directed sampling
- The local time method for targeting and selection
- Bayesian exploration for approximate dynamic programming
- Game of thrones: fully distributed learning for multiplayer bandits
- Recurrent Neural-Linear Posterior Sampling for Nonstationary Contextual Bandits
- scientific article; zbMATH DE number 7626733 (Why is no real title available?)
- Bandit Theory: Applications to Learning Healthcare Systems and Clinical Trials
- Infinite Arms Bandit: Optimality via Confidence Bounds
- Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning
- Online resource allocation with personalized learning
- Online decision making with high-dimensional covariates
- Technical note: Consistency analysis of sequential learning under approximate Bayesian inference
- Online Network Revenue Management Using Thompson Sampling
- Nonstationary bandits with habituation and recovery dynamics
- Optimal online learning for nonlinear belief models using discrete priors
- Simple Bayesian algorithms for best-arm identification
- scientific article; zbMATH DE number 7307478 (Why is no real title available?)
- scientific article; zbMATH DE number 7307488 (Why is no real title available?)
- Complete expected improvement converges to an optimal budget allocation
- Deep exploration via randomized value functions
- Efficient Simulation of High Dimensional Gaussian Vectors
- ON THE IDENTIFICATION AND MITIGATION OF WEAKNESSES IN THE KNOWLEDGE GRADIENT POLICY FOR MULTI-ARMED BANDITS
- Satisficing in Time-Sensitive Bandit Learning
- Multi-armed bandit-based hyper-heuristics for combinatorial optimization problems
- Online learning of network bottlenecks via minimax paths
- Variable Selection Via Thompson Sampling
- Reward Maximization Through Discrete Active Inference
- Reinforcement Learning, Bit by Bit
- On maximum a posteriori estimation with Plug \& Play priors and stochastic gradient descent
- Online learning of energy consumption for navigation of electric vehicles
- Optimistic Posterior Sampling for Reinforcement Learning: Worst-Case Regret Bounds
- Statistical arbitrage under a fractal price model
- Finding the optimal exploration-exploitation trade-off online through Bayesian risk estimation and minimization
- Multi-armed bandit experiments in the online service economy
- Factorial Designs for Online Experiments
- Sequential Model-Based Optimization for Continuous Inputs with Finite Decision Space
- Sequential Monte Carlo bandits
- Optimal sequential stochastic shortest path interdiction
- Sequential Bayesian replacement with unknown transition probabilities
- 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
- Multiobjective optimization using the R2 utility
- Simple fixes that accommodate switching costs in multi-armed bandits
- Optimal learning policies for differential privacy in multi-armed bandits
- Minimax approach to the Gaussian multi-armed bandit
- Concentration of cumulative reward in Markov decision processes
- Optimal learning for sequential sampling with non-parametric beliefs
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)
