Sequence prediction under a lying oracle
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
- Conformal Prediction for Time Series with Deep Sequence Models
- State-Matched Sequence Conformal Prediction
- Robustness against lying of the confidence interval for a fraction of population with a sensitive characteristic
- Low Lying Zeros of Dedekind Zeta Functions
- Obstructions to deforming space curves lying on a complete intersection of quadrics
BibTeX
@misc{samanta2026sequence,
title = {{Sequence prediction under a lying oracle}},
author = {Puspabeethi Samanta and Nikhil Karamchandani and Jayakrishnan Nair},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.14102},
eprint = {2608.14102},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.14102},
}
RIS
TY - UNPB
TI - Sequence prediction under a lying oracle
AU - Puspabeethi Samanta
AU - Nikhil Karamchandani
AU - Jayakrishnan Nair
PY - 2026
DA - 2026/09/09
PB - arXiv
DO - 10.48550/arxiv.2608.14102
UR - https://arxiv.org/abs/2608.14102
AB - 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.
ER -