Lifting the Information Ratio: An Information-Theoretic Analysis of Thompson Sampling for Contextual Bandits
We study the Bayesian regret of the renowned Thompson Sampling algorithm in contextual bandits with binary losses and adversarially-selected contexts. We adapt the information-theoretic perspective of \cite{RvR16} to the contextual setting by considering a lifted version of the information ratio defined in terms of the unknown model parameter instead of the optimal action or optimal policy as done in previous works on the same setting. This allows us to bound the regret in terms of the entropy of the prior distribution through a remarkably simple proof, and with no structural assumptions on the likelihood or the prior. The extension to priors with infinite entropy only requires a Lipschitz assumption on the log-likelihood. An interesting special case is that of logistic bandits with $d$-dimensional parameters, $K$ actions, and Lipschitz logits, for which we provide a $\widetilde{O}(\sqrt{dKT})$ regret upper-bound that does not depend on the smallest slope of the sigmoid link function.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Armed BanditsThompson SamplingSimilar Papers 제목 키워드 기반
Learning-based safety lifting monitoring system for cranes on construction sites
Lifting on construction sites, as a frequent operation, works still with safety risks, especially for modular integrated construction (MiC) lifting due to its large weight and size, probably leading to accidents, causing…
Characterizing Tradeoffs in Language Model Decoding with Informational Interpretations
We propose a theoretical framework for formulating language model decoder algorithms with dynamic programming and information theory. With dynamic programming, we lift the design of decoder algorithms from the logit spac…
DecoderDiversityLanguage ModelingLanguage ModellingLifting Layers: Analysis and Applications
The great advances of learning-based approaches in image processing and computer vision are largely based on deeply nested networks that compose linear transfer functions with suitable non-linearities. Interestingly, the…
Denoisingimage-classificationImage ClassificationLifting-based variational multiclass segmentation algorithm: design, convergence analysis, and implementation with applications in medical imaging
We propose, analyze and realize a variational multiclass segmentation scheme that partitions a given image into multiple regions exhibiting specific properties. Our method determines multiple functions that encode the se…
Image SegmentationSegmentationSemantic SegmentationChained Generalisation Bounds
This work discusses how to derive upper bounds for the expected generalisation error of supervised learning algorithms by means of the chaining technique. By developing a general theoretical framework, we establish a dua…