Beyond Binary: Continuous State Optimization with Graph-Structured Objectives

This paper extends the framework of optimizing systems with competing objectives from binary state spaces to continuous state spaces. The authors model the problem as minimizing a sum of linear objectives subject to movement costs that penalize system instability, capturing local structure using a dependency graph where each objective is determined by a subset of state attributes. They propose Lazy Graph-LinUCB, an algorithm that performs lazy updates to minimize switching costs while maintaining near-optimal regret. The paper introduces three advanced mechanisms to exploit graph structure: an asynchronous update schedule that eliminates synchronization overhead in sparse graphs, an adaptive algorithm that learns the graph structure from data, and a joint estimator that leverages data sharing among correlated objectives to tighten regret bounds. Empirically, the structural exploitations reduce movement costs by more than a factor of three in heterogeneous systems while maintaining similar cumulative losses.

The paper's contributions are fourfold. First, it extends the feedback-driven competing objectives framework from binary system configurations to continuous state spaces, modeling the problem as a graph-structured linear bandit with movement costs. Second, it proposes LazyGraphLinUCB, a stochastic algorithm that uses a decomposed determinant trigger to minimize switching costs while maintaining optimal prediction regret. Third, it introduces three advanced mechanisms to exploit the underlying graph structure: an asynchronous update schedule that eliminates synchronization penalties in sparse graphs, an adaptive routine that learns dependencies from data, and a joint estimator based on a Factor Graph decomposition that tightens regret bounds in dense, correlated systems. Finally, it provides matching minimax lower bounds and empirically demonstrates that the structural exploitations reduce movement costs by more than a factor of three in heterogeneous graph systems, and up to a factor of five in real-world single-objective tasks.

The problem is formulated as an online optimization game over T rounds, where at each round the learner selects a continuous state vector st ∈ [0, 1]k. The loss is graph-structured, meaning the expected loss for criterion i depends only on the state of its local neighborhood N(i), with local feature maps ϕi and parameters θi such that µi(s) = ⟨ϕi(sN(i)), θi⟩. The total expected complaint loss is the sum of individual criteria losses. Movement costs penalize the distance between consecutive states via Cmove(st−1, st) = λ∥st − st−1∥1. The regret is defined as the difference between the learner's total cost (complaints plus movement) and the cost of the optimal static state s*.

LazyGraphLinUCB maintains separate linear estimators for each criterion but coordinates their updates to minimize global movement. The algorithm maintains an active state sactive and only re-solves the optimization problem when the determinant of the covariance matrix for any criterion has doubled significantly since the last update. The theoretical analysis establishes confidence ellipsoids, bounds the number of policy updates (epochs), and bounds the prediction error incurred during lazy frozen periods. The main regret guarantee is RegT ≤ Õ(√(T ∑ki=1 di) + λk2dmax log T), where di is the dimension of the feature map for criterion i and dmax = maxi di. The paper also provides a minimax lower bound of E[RegT] = Ω(√(T ∑ki=1 di)), demonstrating the tightness of the dependency on the sum of dimensions.

The paper introduces three advanced mechanisms to exploit graph structure. First, the asynchronous update schedule (Async-LazyGraphLinUCB) performs local policy updates, where each criterion maintains its own last-update time and triggers updates only when its own determinant doubles. This yields a regret bound of RegT ≤ Õ(√(T ∑ki=1 di) + λ∆dmaxk log T), where ∆ is the maximum degree of the dependency graph, significantly reducing movement costs in sparse graphs. Second, the adaptive graph learning mechanism recovers the true sparse graph structure under minimum signal strength and diverse context assumptions, with a regret bound of RegT ≤ Õ(dtotal 1.5/(κγ2) + √(T ∑ki=1 di) + d2total log T). Third, the joint estimator based on Factor Graph decomposition treats the problem as a single linear bandit with matrix-valued features, achieving a regret bound of RegT ≤ Õ(deff√(kT) + λk2dmax log T), where deff is the sum of clique dimensions, improving over the node-wise bound by a factor of √k in dense, highly correlated systems.

The paper also extends the framework to the adversarial full-information setting, where loss functions are arbitrary convex functions chosen by an adversary. The proposed Randomized Lazy OGD maintains a virtual OGD iterate but updates the deployed state st only with probability p = M/T, achieving E[RegT] ≤ λDM + O(DG√(T/M)) for a switching budget M. This quantifies the price of sparsity: regret degrades from √T to √(T/M) as the switching budget tightens. An extension for heterogeneous budgets is also provided, where different criteria can have different stability requirements.

Numerical experiments validate the theoretical findings. In a single-clique stability analysis, LazyGraphLinUCB freezes the action for stable epochs while standard LinUCB jitters constantly, reducing movement cost from linear to logarithmic while maintaining statistically indistinguishable prediction regret. In a heterogeneous graph with 10 independent criteria, the asynchronous strategy reduces total system-wide moves by a factor of 3.1× compared to the global lazy strategy, with stable cliques incurring up to 3.7× waste under the global strategy. In a real-world fairness threshold tuning task on the Adult Census dataset, the lazy strategy reduces average cumulative movement cost by a factor of 5.7× compared to standard LinUCB while successfully converging to the fair region.

Improvements to AI Systems:

1. Resource-Efficient Online Learning with Lazy Updates: AI systems can adopt the Lazy Graph-LinUCB trigger mechanism to drastically reduce computational and operational costs. Instead of updating model parameters or policies at every time step, the system only re-optimizes when the uncertainty (determinant of the covariance matrix) doubles. This enables continuous-state decision-making (e.g., robotic control, dynamic pricing, adaptive resource allocation) with near-optimal regret but exponentially fewer policy switches, reducing wear-and-tear, energy consumption, and communication overhead.

2. Graph-Structured Multi-Objective Optimization: The framework enables AI systems to handle multiple competing objectives (e.g., fairness, accuracy, latency) where each objective depends only on a subset of state variables. By modeling dependencies as a graph and using separate estimators per criterion, the system can coordinate updates to minimize global instability. The asynchronous update schedule allows independent components to update only when needed, cutting total movement costs by over 3× in heterogeneous systems—ideal for distributed AI, multi-agent coordination, or federated learning where synchronization is costly.

3. Adaptive Dependency Discovery: The adaptive graph-learning mechanism allows AI systems to automatically infer which state attributes influence which objectives from data, without prior knowledge. This is valuable for real-world tasks with unknown causal structures (e.g., medical treatment planning, supply chain optimization). The system can recover the true sparse dependency graph under mild assumptions, then exploit it to reduce switching costs and improve regret bounds—enabling more robust and interpretable decision-making in complex, partially understood environments.

4. Data-Sharing via Joint Estimation for Correlated Objectives: For systems with highly correlated objectives (e.g., multi-task learning, portfolio optimization), the Factor Graph joint estimator treats the problem as a single bandit with matrix-valued features. This tightens regret bounds by a factor of √k in dense, correlated settings, allowing the AI to share statistical strength across objectives. This leads to faster convergence and lower cumulative loss when objectives are not independent—improving sample efficiency in multi-task reinforcement learning or multi-output prediction.

5. Controlled Switching with Tunable Sparsity: The Randomized Lazy OGD extension provides a principled way to trade off decision frequency against regret. AI systems can now operate under explicit switching budgets (e.g., limited model updates per day, limited reconfiguration of infrastructure) while maintaining provable performance guarantees. The regret gracefully degrades from √T to √(T/M) as the budget tightens, allowing system designers to precisely calibrate stability vs. adaptivity—useful for edge devices with battery constraints, real-time bidding systems, or any deployment where frequent changes are costly.

6. Stability-Aware Fairness and Safety Systems: The empirical validation on fairness threshold tuning shows that the lazy strategy converges to a fair region with 5.7× less movement cost than standard methods. This directly improves AI systems that must maintain ethical or safety constraints (e.g., loan approval thresholds, autonomous vehicle safety margins) by preventing erratic, costly fluctuations while still learning optimal, stable policies—critical for regulatory compliance and user trust.

What the Improved AI System Can Do:

• Operate continuously in high-dimensional state spaces with multiple, possibly conflicting goals, while minimizing both prediction error and operational switching costs.

• Automatically discover and exploit underlying structure (which variables affect which outcomes) to reduce unnecessary updates and improve sample efficiency.

• Function effectively in sparse, distributed, or asynchronous environments without global synchronization bottlenecks.

• Provide provable performance guarantees (sublinear regret) even under tight constraints on how often the system can change its behavior.

• Maintain stable, reliable decisions in safety-critical or fairness-sensitive applications, reducing costly oscillations while still learning and adapting optimally.