cs.AINov 15, 2026

Lossless First-Action Menus for Linear-Reward Planning

Authors: Yukun Yang

Organizations: School of Management, Beijing Institute of Technology

Abstract

We study sequential decision making where an agent reserves a minimum menu of initial actions before multi-objective trade-offs are revealed, followed by unrestricted continuation planning once linear reward weights arrive. We prove that a menu preserves the unrestricted optimal return across all linear scalarizations if and only if its reachable continuations cover all vertices of the full feature polytope. This geometric equivalence yields an output-sensitive algorithm that is fixed-parameter tractable in the vertex count, combining scalar backward induction with oracle-based facet identification. On explicitly layered graphs with unit feature increments, menu verification is coNP-complete and synthesis is complete for the second existential level of the polynomial hierarchy, even under additive loss strictly below one. In fixed dimensions two and higher, verification is polynomial whereas synthesis remains NP-complete, while one-dimensional instances admit polynomial-time solutions.

Figures & tables

Explore similar work

Sep 14, 2026

Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets

We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let dd be the dimension, KK be the menu size, and TT the time horizon. For 2≤K≤d2\le K\le d, we prove an upper bound O~(K1/4dT)\widetilde O(K^{1/4}\sqrt{dT}). When T≥d2T\ge d^2, we further prove a lower bound Ω(K1/4dT)Ω(K^{1/4}\sqrt{dT}). Thus, for T≥d2T\ge d^2 and 2≤K≤d2\le K\le d, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on KK is optimal. Compared with the previous O~(dKT)\widetilde O(\sqrt{dKT}) bound, our upper bound improves the dependence on KK by a factor of K1/4K^{1/4}. For K≥dK\ge d, we prove an upper bound O~d,T(dTmin⁡{d,(dlog⁡K)1/4})\widetilde O_{d,T}\left(\sqrt{dT}\min\{\sqrt d,(d\log K)^{1/4}\}\right) and a lower bound Ω(dTmin⁡{d,(dlog⁡Klog⁡(2d))1/4})Ω\left(\sqrt{dT}\min\left\{\sqrt d,\left(\frac{d\log K}{\log(2d)}\right)^{1/4}\right\}\right). Here, O~d,T\widetilde O_{d,T} omits logarithmic factors only in dd and TT. In particular, for polynomially large K≥dK\ge d, the upper and lower bounds both scale as d3/4Td^{3/4}\sqrt T up to logarithmic factors, improving the standard O~(dT)\widetilde O(d\sqrt T) rate by a factor of d1/4d^{1/4}. As KK grows further, the regret smoothly recovers the dTd\sqrt T scale once log⁡K\log K reaches order dd.
Sep 22, 2026

Tight Regret Bound for Online Inverse Linear Optimization via Multiscale Matrix Weights

We study online inverse linear optimization with a fixed unknown linear utility: in each round, an environment presents a compact action set, the learner recommends an action from it, and the environment returns an action that maximizes the utility over the same set. When the utility vector and the actions lie in the dd-dimensional Euclidean unit ball, we give a randomized algorithm whose regret---the cumulative utility shortfall relative to optimal actions---is O(d)O(\sqrt d) in expectation for every time horizon, without knowledge of the horizon. The dependence on dd is optimal up to a constant factor by the known Ω(d)Ω(\sqrt d) lower bound for horizons T≥dT\ge d. Our algorithm maintains matrix multiplicative weights on polynomial feature spaces at geometrically spaced scales. It selects a recommendation distribution by solving a linear program and updates its score matrices by comparing the available actions with the feedback action. With rational oracle outputs and feedback actions, an implementation computable relative to a linear-optimization oracle preserves the O(d)O(\sqrt d) regret bound. Whether the same rate is attainable with running time polynomial in the dimension, horizon, and input length remains open.
Aug 7, 2026

Multiscale Reward Hedging from Correct Demonstrations

Learning from correct demonstrations is harder than supervised learning when many answers are correct: after predicting, the learner sees one valid answer but not whether its own answer was valid, nor any reward. Existing reward-hedging guarantees consequently assume a finite reward class. We give the first horizon-free guarantee for continuous classes. The key is to hedge in one shared vote over tolerant optimality tests at every accuracy scale. A target reward has one surviving proxy per scale, and a prediction with gap above that scale doubles the proxy. This yields the simultaneous tail bound ∣{t:ℓt>2−j}∣≤log⁡2N(G,2−j−1)+j|\{t:\ell_t>2^{-j}\}|\leq \log_2\mathcal N(\mathcal G,2^{-j-1})+j, where G\mathcal G is the class of optimality-gap functions. Integrating the tails gives cumulative hidden gap bounded by a metric-entropy integral, independently of the number of rounds. Polynomial entropy (A/ε)d(A/ε)^d gives O(dlog⁡A)O(d\log A) total gap and a fast O(d/m)O(d/m) statistical rate. For bounded linear contextual recommendation, the result is O(d)O(d) regret for arbitrary compact menus. This is the first polynomial finite bound without structural restrictions on the menus, at the price of improper prediction. Although the general vote can be expensive, it is exactly polynomial-time for one-dimensional Lipschitz parameter curves. Fixed-radius rank-two recommendation takes O(KT2)O(KT^2) time for menus of size KK. We also prove an Ω(d)Ω(d) lower bound, low-rank and bounded ReLU-network corollaries, and a robust theorem that adds only the demonstrator's cumulative suboptimality. A reproducible adaptive stress test illustrates the predicted scale adaptation. After factorization, an exact MovieLens audit runs in 1.7 CPU seconds across ten users and improves mean latent gap over both a demonstrated-rating policy and a proper online baseline. The learner uses only action demonstrations and never observes a reward or a loss.