Our results show that the existence of a short high-utility protocol already suffices for efficient communication. In particular, in a game with $n$ possible observations and $m$ actions: (1) For any achievable target utility $α$, we give an algorithm with $\mathrm{poly}(n, m, 1/ε)$ runtime that designs a protocol achieving utility at least $α-ε$ using only $2^{\mathcal O(CC_α(G))}/ε^2$ bits of communication.
arXiv:2609.22757v1 Announce Type: cross
Abstract: A (coarse) correlated equilibrium (CE) is information-value-free (IVF) if a player can match the payoff obtained from recommendations by committing t...
By Ioannis Anagnostides, Weiqiang Zheng
arXiv:2608. 07532v1 Announce Type: new Abstract: Modern agentic AI systems combine multiple large language model agents with heterogeneous skills, yet most architectures either fix communication in advance or allow full broadcast.
By Mojtaba Eslami
arXiv:2607. 14877v1 Announce Type: new Abstract: Reachability is the most fundamental logical objective, yet it is notoriously difficult to learn in reinforcement learning settings: even for Markov decision processes, PAC learning of reachability is impossible without additional assumptions.
By Ali Asadi, Krishnendu Chatterjee, Pavol Kebis
arXiv:2406. 13668v4 Announce Type: replace Abstract: A set of probabilistic forecasts is calibrated if each prediction of the forecaster closely approximates the empirical distribution of outcomes on the subset of timesteps where that prediction was made.
By Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, Noah Golowich, Robert Kleinberg, Princewill Okoroafor
arXiv:2606. 00703v1 Announce Type: cross Abstract: Low-precision pretraining (FP8, MXFP4, NVFP4) is now standard for frontier language models, yet the literature is almost entirely achievability -- algorithms and empirical scaling laws -- with no matching characterization of what is information-theoretically possible.
By Munsik Kim
arXiv:2602. 16965v2 Announce Type: replace Abstract: We study the decentralized multi-player stochastic bandit problem over a continuous, Lipschitz-structured action space where hard collisions yield zero reward.
By Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni, Lijun Chen
arXiv:2608. 12753v1 Announce Type: new Abstract: We study decentralized multi-player reinforcement learning in episodic tabular Markov decision processes (MDPs) under three forms of information asymmetry: (A) unobserved actions with common rewards, (B) observed actions with independent rewards, and (C) unobserved actions with independent rewards.
By Larissa Xu, King Bi, William Chang
arXiv:2605.15692v2 Announce Type: replace-cross
Abstract: We study episodic reinforcement learning with fixed reward and transition functions, but with episode-dependent admissible action sets that a...
By Zijun Chen, Zihan Zhang
arXiv:2608. 02533v1 Announce Type: cross Abstract: We construct unambiguous DNFs having width $O(n)$ but $0$-certificate complexity $\Omega(n^2)$.
By Chirag Pabbaraju
arXiv:2603. 13356v2 Announce Type: replace Abstract: Robust reinforcement learning typically assumes that feedback sources are either globally trustworthy or corrupted within a fixed global budget.
By Majid Ghasemi, Mark Crowley
arXiv:2609. 08564v1 Announce Type: cross Abstract: We study distributed one-dimensional mean estimation under a 1-bit communication constraint.
By Ivan Lau, Jonathan Scarlett