Sequence prediction under a lying oracle

arXiv:2608.14102v1 Announce Type: new Abstract: We consider the problem of sequential prediction of an m-ary sequence, where at each epoch, (i) the environment selects an outcome from an m-ary alphabet, (ii) the learner selects a probability distribution over the same alphabet (unaware of the outcome generated by the environment), and finally, (iii) the learner incurs a cost that depends on the probability assigned to the outcome. The cost function we consider captures the complexity of predicting the outcome generated by the environment, in a scenario where the aforementioned prediction is performed via comparative queries to a lying oracle. We consider both stochastic and adversarial environments, propose algorithms for both settings, and establish logarithmic upper bounds on their regret.

Related

• Learning with Multiple Correct Answers -- Regret Bounds under Different Feedback Models
• An Efficient Near-Optimal Algorithm for Adversarial m-Set Bandits
• Efficient learning by implicit exploration in bandit problems with side observations

Source: arXiv cs.LG | 2026-08-17