CS Paper Radar

CFR without Unbiasedness: Debit-Budgeted Public Feedback

Jiaxing Guo, Lei Ye

cs.GT cs.LG ·submitted 2026-08-14 09:28 UTC · v2
theory

Abstract

At a finite public-chance cut, partial counterfactual regret minimization (CFR) can evaluate successive outcome batches at learner states changed by earlier batches. Balanced coverage then lacks the conditional unbiasedness used by Monte Carlo CFR analyses. We introduce \emph{target debit}, the one-sided cumulative underestimation needed to transfer regret on delivered feedback to the dense target game. Our central theorem bounds weighted exploitability by delivered-row regret, target debit, and a native alternating-update correction. This yields Debit-Budgeted CFR (DB-CFR), which selects a public plan from completed history, executes it once, and settles its debit afterward. Complete coverage has zero debit and supplies exact recovery. With at most $\ell$ unsettled blocks, hidden debit is bounded by the sum of the $\ell$ largest predictable block envelopes; for fixed $\ell$ and polynomial output weights, the resulting $O(T^{-1})$ term preserves the additive-RM/RM+ rate. A finite converse gives equal-metadata plans with charges $0$ and $11/8$, proving that a nontrivial strict-budget decision requires semantic information or bounded post-execution settlement. In two released heads-up no-limit hold'em turn endgames, all 42 registered shallow comparisons favor partial coverage before complete coverage overtakes it between 32 and 64 rounds. In public Leduc, a lagged rule fixed on four development orders beats the best matched-recurrence-work fixed width on all ten unseen orders (median NashConv gain $0.0456$) without future candidate replay.

Comment
35 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Planned Restlessness: Delayed Meta Bandits with Budgets

cs.LG cs.DS ·2026-10-28 ·Sudipto Guha
theory similarity 0.63
Abstract

We study episodic finite-horizon Bayesian bandits, or meta-bandits, with independent arms. Each episode draws fresh arm qualities from unknown recurring priors. Observations arrive after known delays, and plays obey hard per-episode caps and total budgets. A play earns reward and informs both the current quality and the recurring prior: the learner must explore, use, and generalize. We formulate a common planning optimization over learning trajectories. Its LP relaxation values experiments through current reward, resource consumption and continuation: the value of future decisions from the learning state produced. Dual prices separate the arms into local programs and certify every admissible policy, including hierarchical Thompson sampling. Execution enforces the hard constraints while preserving the promised learning transitions or accounting for their loss. The framework also represents risk-sensitive objectives and prices purchased observations and buyout options. Delayed reports create planned restlessness: an arm's information changes while it is not played, through reports of its own earlier plays arriving on a known calendar. For stationary priors, finite reward alphabets, bounded report lag and nonbinding budgets, posterior sampling over the recurring priors bounds the price of not knowing them by $O(\sqrt{N})$ over $N$ episodes, with other parameters fixed. For one undelayed $T$-step episode with arms capped at $T/X$ plays each, we obtain the LP-relative approximation factor $1+(2πX)^{-1/2}+O(X^{-1})$, improving previous factors, with a matching lower bound for the leading term.

0.13

Counterfactual Regret for Reflective Agents with Lean-Verified Guarantees

cs.AI ·2026-10-10 ·Zhongnian Li, Shi Xu, Mengting Xu, Peng Ying, Xinzheng Xu
similarity 0.62
Abstract

Reflective language agents reuse feedback and memory to adapt across tasks without updating model weights. However, existing guarantees for policy selection and action generation do not by themselves establish when local reflection yields long-term performance guarantees for the complete agent under resource constraints. In this paper, we address this gap by deriving sufficient conditions for sublinear counterfactual regret from local generation and deployment guarantees, while retaining the native controller. Specifically, we establish a resource-sensitive transfer that bounds full-state deployment discrepancies along actual execution paths and preserves the own-history laws of both learner and comparator. Besides, local generation reliability yields a cumulative generation opportunity bound, linking policy acquisition to long-term performance through an explicit quality, coverage, and hard-budget tradeoff. To verify these guarantees, we formalize the conditional proof chain for all thirteen numbered theoretical results in Lean, including a native instance with repeated policy growth and imperfect validation.

0.23

No-Regret Mixing of LRU and LFU with Optimal Switching Cost

cs.LG cs.NI ·2026-09-07 ·Younes Ben Mazziane, Xinying Zou
benchmark similarity 0.62
Abstract

Caching systems often rely on simple eviction policies such as Least Recently Used (LRU) and Least Frequently Used (LFU), which perform well in complementary request regimes. Recent policies such as LeCar and Cacheus combine LRU and LFU using ideas from the experts problem in online learning. Specifically, upon a miss, they randomize between the two eviction rules using probabilities derived from scores updated by tracking the history of past evictions. While these policies exhibit strong empirical performance, it remains unclear whether they are guaranteed, on every request sequence, to perform asymptotically as well as the better of LRU and LFU, i.e., whether they achieve sublinear regret with respect to this benchmark. We first show that LeCar suffers linear regret against an oblivious adversary, even with unbounded history. We then propose H-MC, a Hedge-based mixture of virtual LRU and LFU caches that preserves Hedge's selection probabilities, and hence its regret guarantees, while minimizing the switching cost among all joint selection rules with these marginals.

0.15

SHPRR: An Algorithm for Pure Exploration under Constrained Regret

cs.LG cs.AI ·2026-10-29 ·Georgina Nouli, Flore Sentenac, Maximilian Schiffer
similarity 0.62
Abstract

Best Arm Identification (BAI) conventionally measures the cost of experimentation by the number of samples collected. In many operational settings, however, the cost of exploration relative to a trusted baseline already in place is equally important. We study BAI under both a fixed sampling horizon and a regret budget. Unlike generic resources considered in constrained pure exploration, regret has a distinctive structure: sampling better arms is less costly relative to the baseline. We theoretically show that the regret cost of exploration decreases across the phases of Sequential Halving, a widely used pure-exploration algorithm. This observation yields improved guarantees on the probability of identifying the best arm and motivates a more effective allocation of the regret budget. We propose Sequential Halving with Proportional Regret Rationing (SHPRR), which front-loads the regret budget to allow more exploration when many arms remain. Experiments on synthetic and real-world instances show that SHPRR improves best-arm identification performance over uniform regret allocation and existing baselines.

0.07

Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairness

cs.LG ·2026-10-01 ·Junhyuk Huh, Seoungbin Bae, Dabeen Lee
similarity 0.61
Abstract

We study causal logistic bandits with counterfactual fairness constraints. The causal structure is given through known factual and counterfactual feature maps that share an unknown logistic reward parameter, but the learner observes only factual rewards. Consequently, the directions determining counterfactual feasibility need not be identifiable from the available feedback. The closest prior analyses either omit a coverage condition or impose a comparatively strong one, and do not establish matching lower bounds. We first show that some coverage condition is necessary: without a coverage-type restriction, factually indistinguishable environments with different optimal fair actions force $Ω(T)$ expected joint loss. Under a weaker full-rank condition on the factual covariance pooled across actions, we identify a target-specific information scale $V_\star$ that measures the difficulty of estimating rewards and counterfactual effects from factual feedback. We construct worst-case families satisfying this condition on which every policy incurs expected joint loss $Ω\left(\left[V_\star\min\{\log K,d\}\right]^{1/3}T^{2/3}\right)$. We also give an explore--then--exploit procedure tuned using $V_\star$ and an adaptive algorithm that does not require its value. Both algorithms achieve $\max\{R_T,V_T\}=\widetilde{O}\left(\left[V_\star\min\{\log K,d\}\right]^{1/3}T^{2/3}+κd/σ_0^2\right)$, where $R_T$ is regret relative to the best fair action and $V_T$ denotes the cumulative stage-wise positive violations. Thus the upper and lower bounds match in their leading dependence on $T$, $V_\star$, and $\min\{\log K,d\}$, up to logarithmic factors.

0.20

Pathwise-Budgeted LLM Routing: Online Allocation with K-Bit Tail-Cost Learning

cs.LG math.OC ·2026-11-04 ·Hanzhang Qin, Sophie H. Yu, Yuewei Zhang, Zhi-Hai Zhang
similarity 0.61
Abstract

Firms using large language models under fixed budgets must decide which model to call and whether to retry a failed task. Because a call's charge is revealed only after completion, one long response can exhaust the remaining budget and leave later tasks unserved. Our objective is to maximize the number of tasks solved before service stops. We develop a contextual bandit policy, ADP-HT, which learns each model's task-specific success probability and constructs conservative cost estimates from coarsened response-length labels on a quantile grid with $2^K$ intervals. The policy weighs predicted success against these costs, adjusting the cost penalty to realized spending and the budget available per remaining task. Under calibration, local regularity, and grid-coverage conditions, we bound the excess allowance in the policy's conservative cost estimates. At a fixed sample size, increasing $K$ reduces the discretization term but increases the estimation allowance. At the tightest tested budgets, ADP-HT solves more than twice as many MATH500 and GPQA tasks as the best implemented baseline. It achieves the highest mean cumulative score at ten of fourteen RouterBench budgets. On LiveCodeBench, it outperforms a deployed commercial router in both default and cost-saving modes at the three lowest test budgets.

0.16

Block Optimism for Nonstationary Bandits with Latent Linear Dynamics

cs.LG stat.ML ·2026-10-01 ·Taehyun Hwang, Hyunjun Choi, Heesang Ann, Min-hwan Oh
top venuebenchmarktheory similarity 0.61
Abstract · Accepted at NeurIPS 2026

We study an endogenous nonstationary stochastic bandit problem with latent linear dynamics, where actions affect both immediate rewards and the future evolution of an unobserved latent state. Rewards are bilinear in the current action and latent state, inducing history-dependent rewards and a nontrivial long-horizon planning problem. The existing explore-then-commit approach achieves $\tilde{O}(T^{2/3})$ regret by uniformly exploring to estimate the latent dynamics and then committing to an optimized open-loop action sequence. We show that this rate can be improved via adaptive block-level optimism. Our key step is a cyclic approximation: under stable dynamics, the infinite-memory reward process can be truncated, and the open-loop benchmark can be approximated by optimizing a finite-memory block-level proxy. Building on this reduction, we propose a UCB-based block algorithm that maintains confidence sets for the truncated dynamics parameters and selects blocks optimistically. We prove a regret bound of order $\tilde{O}(\sqrt T)$, significantly improving over the previous $\tilde{O}(T^{2/3})$ guarantee for the same model. To the best of our knowledge, this is the first $\tilde{O}(\sqrt T)$ regret guarantee for latent linear-dynamics bandits with bilinear reward observations and an open-loop action-sequence benchmark.

0.33

Optimal Regret for Online Storage Control via Cumulative Policies

eess.SY math.OC ·2026-09-18 ·Kamiar Asgari, Michael J. Neely
theory similarity 0.61
Abstract

We study online control of a scalar storage system with adversarial nonnegative arrivals, known retention coefficient, and convex costs depending on both state and action. Each action must respect current resource availability and is chosen before the current arrival and cost function are revealed. For the existing simplex disturbance-action policy class, we give an exact reparameterization by cumulative allocation fractions and a decay-weighted projected subgradient update. The resulting regret bound is independent of policy memory length. For fixed retention coefficient and cost constants, the controller achieves $O(\sqrt T)$ regret against the best fixed infinite-memory policy in this class, using $O(\log T)$ memory and arithmetic operations per round and one cost-subgradient query. A storage-specific block construction gives a matching lower bound against every causal feasible controller, including randomized controllers. Writing $τ=(1-α)^{-1}$, the minimax expected regret is $Θ(\sqrt T\min\{T,τ\}^{3/2})$ for every finite-memory simplex policy class and its infinite-memory extension, when $α\in[1/2,1)$, $T\ge4$, and the positive cost constants are fixed. This identifies the joint horizon and retention-time dependence for these policy benchmarks.

0.10