Beyond Binary: Continuous State Optimization with Graph-Structured Objectives

Large-scale learning systems often face the challenge of balancing multiple, potentially competing objectives, such as fairness, accuracy, and latency. While recent work has formalized this as an optimization problem over binary states, many real-world control parameters---such as fairness thresholds, diversity mixing rates, or resource budgets---are continuous. In this work, we extend the framework to continuous state spaces. We model the problem as minimizing a sum of linear objectives subject to movement costs that penalize system instability. We capture the local structure of the objectives using a dependency graph (or factor graph), where each objective is determined by a subset of the state attributes. To address the tension between exploration and stability, we propose Lazy Graph-LinUCB, an algorithm that performs lazy updates to minimize switching costs while maintaining near-optimal regret. Beyond stability, we introduce three advanced mechanisms to exploit the underlying graph structure: (1) an asynchronous update schedule that eliminates synchronization overhead in sparse graphs; (2) an adaptive algorithm that learns the graph structure from data; and (3) a joint estimator that leverages data sharing among correlated objectives to significantly tighten regret bounds. Empirically, we demonstrate that these structural exploitations reduce movement costs by more than a factor of three in heterogeneous systems while maintaining similar cumulative losses.

Modern learning systems must balance many competing objectives at once. For example, a recommendation engine should be accurate, efficient, fair, and diverse, yet improving one objective often hurts another. Previous approaches treated each objective as a simple on/off switch, but in practice the "knobs" engineers turn are continuous (e.g., how strict a fairness threshold should be). This paper introduces algorithms that tune such continuous knobs automatically, learning from user feedback which settings best navigate the trade-offs among competing objectives. A key challenge is stability: changing settings too often is costly and disruptive, but changing them too rarely means learning slowly. Our algorithms solve this by updating only when enough new information has been gathered to justify the disruption. They also exploit the fact that most objectives depend on only a few nearby knobs, not all of them, so different parts of the system can be tuned independently and at different speeds. We prove that these algorithms are near-optimal and show experimentally that they cut unnecessary system changes by more than a factor of three compared to naive approaches.