Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 56 min ago
PreprintCC BY 4.0arXiv

No-Regret Language Generation

  • Jiaxun Li
  • Vinod Raman
  • Ambuj Tewari
Open at sourcePDFDOICite

Abstract

We introduce no-regret generation, which requires a generator to make a sublinear number of mistakes uniformly over all demonstration sequences and compatible target languages. We also formulate an agnostic variant that allows arbitrary demonstrations that may not be compatible with any languages. For both settings, we introduce tree-based mistake-forcing dimensions that exactly characterize finite-horizon minimax complexity and establish necessary and sufficient conditions for no-regret generation. Our characterizations reveal a rich spectrum of generation rates: up to constant rescaling, every admissible nondecreasing profile is attainable in both the realizable and agnostic settings. Finally, we connect generation complexity to online prediction: for language classes of finite Littlestone dimension d, we obtain realizable mistake bounds of O(dlog(1+T/d)) and agnostic regret bounds of O(√(dTlog(1+T/d))). The realizable bound is optimal up to universal constants.

Related

  1. Steering sequence generation in protein language models through Iterative Lookback Monte Carlo Sampling
    Francesco Calvanese, Gianluca Lombardi, Martin Weigt +1
    Machine Learning : Science and TechnologyPeer-reviewedCC BY 4.0Full textBioinformatics & computational biologyStatisticsHAL
  2. Causally Fair Generation with Large Language Models
    Patrik Okanovic, Torsten Hoefler, Drago Plecko
    arXivPreprintCC BY 4.0Full textStatisticsarXiv
  3. Regret in the Newsvendor Model with Demand and Yield Randomness
    Zhi Chen, Weijun Xie
    Production and Operations ManagementPeer-reviewedLicence not stated50 citedOptimisation & controlHAL
  4. Online tensor learning: Computational and statistical trade-offs, adaptivity and optimal regret
    Jingyang Li, Jian‐Feng Cai, Yang Chen +1
    The Annals of StatisticsPeer-reviewedLicence not statedFull text16 citedNumerical analysis & scientific computingOpenAlex
  5. Multiplicative Optimism for Constant Regret in Games
    Ashkan Soleymani, Georgios Piliouras
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{li2026noregret,
  title = {{No-Regret Language Generation}},
  author = {Jiaxun Li and Vinod Raman and Ambuj Tewari},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.23641},
  eprint = {2610.23641},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.23641},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - No-Regret Language Generation
AU  - Jiaxun Li
AU  - Vinod Raman
AU  - Ambuj Tewari
PY  - 2026
DA  - 2026/10/16
PB  - arXiv
DO  - 10.48550/arxiv.2610.23641
UR  - https://arxiv.org/abs/2610.23641
AB  - We introduce no-regret generation, which requires a generator to make a sublinear number of mistakes uniformly over all demonstration sequences and compatible target languages. We also formulate an agnostic variant that allows arbitrary demonstrations that may not be compatible with any languages. For both settings, we introduce tree-based mistake-forcing dimensions that exactly characterize finite-horizon minimax complexity and establish necessary and sufficient conditions for no-regret generation. Our characterizations reveal a rich spectrum of generation rates: up to constant rescaling, every admissible nondecreasing profile is attainable in both the realizable and agnostic settings. Finally, we connect generation complexity to online prediction: for language classes of finite Littlestone dimension d, we obtain realizable mistake bounds of O(dlog(1+T/d)) and agnostic regret bounds of O(√(dTlog(1+T/d))). The realizable bound is optimal up to universal constants.
ER  -