# Stochastic One-Sided Full-Information Bandit

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jun 2019.

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

- [BanditQ: Fair Bandits with Guaranteed Rewards](https://mlsanity.com/paper/2304.05219/) (2023)
- [Stochastic contextual bandits with graph feedback: from independence number to MAS number](https://mlsanity.com/paper/2402.18591/) (2024)
- [Leveraging Reviews: Learning to Price with Buyer and Seller Uncertainty](https://mlsanity.com/paper/2302.09700/) (2023)
- [Hybrid Feedback-Guided Optimal Learning for Wireless Interactive Panoramic Scene Delivery](https://mlsanity.com/paper/2602.07273/) (2026)
- [Privacy Preserving Reinforcement Learning with One-Sided Feedback](https://mlsanity.com/paper/2605.18246/) (2026)

## Abstract (arXiv)

In this paper, we study the stochastic version of the one-sided full information bandit problem, where we have K arms [K] = 1, 2, ldots, K, and playing arm i would gain reward from an unknown distribution for arm i while obtaining reward feedback for all arms j ≥ i. One-sided full information bandit can model the online repeated second-price auctions, where the auctioneer could select the reserved price in each round and the bidders only reveal their bids when their bids are higher than the reserved price. In this paper, we present an elimination-based algorithm to solve the problem. Our elimination based algorithm achieves distribution independent regret upper bound O(√T·log (TK)), and distribution dependent bound O((log T + log K)f(Delta)), where T is the time horizon, Delta is a vector of gaps between the mean reward of arms and the mean reward of the best arm, and f(Delta) is a formula depending on the gap vector that we will specify in detail. Our algorithm has the best theoretical regret upper bound so far. We also validate our algorithm empirically against other possible alternatives.