Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles
- URL: http://arxiv.org/abs/1703.01347v3
- Date: Tue, 21 Mar 2023 01:19:15 GMT
- Title: Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles
- Authors: Jung-hun Kim and Se-Young Yun and Minchan Jeong and Jun Hyun Nam and
Jinwoo Shin and Richard Combes
- Abstract summary: We study contextual linear bandit problems under feature uncertainty.
The optimal hypothesis can be far from the underlying realizability function, depending on the noise characteristics.
We propose an algorithm that aims at the Bayesian oracle from observed information.
- Score: 61.247089049339664
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study contextual linear bandit problems under feature uncertainty; they
are noisy with missing entries. To address the challenges of the noise, we
analyze Bayesian oracles given observed noisy features. Our Bayesian analysis
finds that the optimal hypothesis can be far from the underlying realizability
function, depending on the noise characteristics, which are highly
non-intuitive and do not occur for classical noiseless setups. This implies
that classical approaches cannot guarantee a non-trivial regret bound.
Therefore, we propose an algorithm that aims at the Bayesian oracle from
observed information under this model, achieving $\tilde{O}(d\sqrt{T})$ regret
bound when there is a large number of arms. We demonstrate the proposed
algorithm using synthetic and real-world datasets.
Related papers
- Information limits and Thouless-Anderson-Palmer equations for spiked matrix models with structured noise [19.496063739638924]
We consider a saturate problem of Bayesian inference for a structured spiked model.
We show how to predict the statistical limits using an efficient algorithm inspired by the theory of adaptive Thouless-Anderson-Palmer equations.
arXiv Detail & Related papers (2024-05-31T16:38:35Z) - Thompson Sampling for Stochastic Bandits with Noisy Contexts: An Information-Theoretic Regret Analysis [4.297070083645049]
We investigate a contextual linear bandit problem where the agent observes a noisy, corrupted version of the true context.
Our objective is to design an action policy that can approximate" that of an oracle.
arXiv Detail & Related papers (2024-01-21T18:57:38Z) - High-Order Qubit Dephasing at Sweet Spots by Non-Gaussian Fluctuators:
Symmetry Breaking and Floquet Protection [55.41644538483948]
We study the qubit dephasing caused by the non-Gaussian fluctuators.
We predict a symmetry-breaking effect that is unique to the non-Gaussian noise.
arXiv Detail & Related papers (2022-06-06T18:02:38Z) - The price of ignorance: how much does it cost to forget noise structure
in low-rank matrix estimation? [21.3083877172595]
We consider the problem of estimating a rank-1 signal corrupted by structured rotationally invariant noise.
We make a step towards understanding the effect of the strong source of mismatch which is the noise statistics.
We show that this performance gap is due to an incorrect estimation of the signal norm.
arXiv Detail & Related papers (2022-05-20T07:54:21Z) - The Optimal Noise in Noise-Contrastive Learning Is Not What You Think [80.07065346699005]
We show that deviating from this assumption can actually lead to better statistical estimators.
In particular, the optimal noise distribution is different from the data's and even from a different family.
arXiv Detail & Related papers (2022-03-02T13:59:20Z) - Analyzing and Improving the Optimization Landscape of Noise-Contrastive
Estimation [50.85788484752612]
Noise-contrastive estimation (NCE) is a statistically consistent method for learning unnormalized probabilistic models.
It has been empirically observed that the choice of the noise distribution is crucial for NCE's performance.
In this work, we formally pinpoint reasons for NCE's poor performance when an inappropriate noise distribution is used.
arXiv Detail & Related papers (2021-10-21T16:57:45Z) - Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix
Recovery [8.581512812219737]
We propose a new framework for low-rank matrix recovery from observations corrupted with noise and outliers.
Inspired by the square root Lasso, this new formulation does not require prior knowledge of the noise level.
We show that a single, universal choice of the regularization parameter suffices to achieve reconstruction error proportional to the (a priori unknown) noise level.
arXiv Detail & Related papers (2021-06-17T02:28:11Z) - Learning with Group Noise [106.56780716961732]
We propose a novel Max-Matching method for learning with group noise.
The performance on arange of real-world datasets in the area of several learning paradigms demonstrates the effectiveness of Max-Matching.
arXiv Detail & Related papers (2021-03-17T06:57:10Z) - Robust Learning under Strong Noise via SQs [5.9256596453465225]
We show that every SQ learnable class admits an efficient learning algorithm with OPT + $epsilon misilon misclassification error for a broad class of noise models.
This setting substantially generalizes the widely-studied problem classification under RCN with known noise probabilities.
arXiv Detail & Related papers (2020-10-18T21:02:26Z) - Shape Matters: Understanding the Implicit Bias of the Noise Covariance [76.54300276636982]
Noise in gradient descent provides a crucial implicit regularization effect for training over parameterized models.
We show that parameter-dependent noise -- induced by mini-batches or label perturbation -- is far more effective than Gaussian noise.
Our analysis reveals that parameter-dependent noise introduces a bias towards local minima with smaller noise variance, whereas spherical Gaussian noise does not.
arXiv Detail & Related papers (2020-06-15T18:31:02Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.