# Sequence prediction under a lying oracle

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 13 references that are in the map.
- First posted on arXiv 14 Aug 2026.

## Builds on (most cited first, 2 of 2)

- [The entropy of lies: playing twenty questions with a liar](https://mlsanity.com/paper/1811.02177/) (2018)
- [Mode Estimation with Partial Feedback](https://mlsanity.com/paper/2402.13079/) (2024)

## Abstract (arXiv)

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.