CONQUER: Confusion Queried Online Bandit Learning
This work addresses a specific recommendation setting for online bandit learning, offering incremental improvements in algorithm design for item selection tasks.
The paper tackles the problem of selecting two items to recommend based on contextual input, where a user chooses one stochastically with bias towards higher value, by proposing a second-order algorithm framework with relative upper-confidence bounds for exploration-exploitation trade-off, achieving a regret bound of O(Q_T + sqrt(TQ_T log T) + sqrt(T) log T) in an adversarial setting with mild assumptions. Experiments on product reviews from 33 domains show the method outperforms related algorithms, with UCB-based ones being inferior to greedy or sampling-based approaches.
We present a new recommendation setting for picking out two items from a given set to be highlighted to a user, based on contextual input. These two items are presented to a user who chooses one of them, possibly stochastically, with a bias that favours the item with the higher value. We propose a second-order algorithm framework that members of it use uses relative upper-confidence bounds to trade off exploration and exploitation, and some explore via sampling. We analyze one algorithm in this framework in an adversarial setting with only mild assumption on the data, and prove a regret bound of $O(Q_T + \sqrt{TQ_T\log T} + \sqrt{T}\log T)$, where $T$ is the number of rounds and $Q_T$ is the cumulative approximation error of item values using a linear model. Experiments with product reviews from 33 domains show the advantage of our methods over algorithms designed for related settings, and that UCB based algorithms are inferior to greed or sampling based algorithms.