Sequential Decision Making

Real-world reinforcement learning often faces environment drift, but most existing methods rely on static entropy coefficients/target entropy, causing over-exploration during stable periods and under-exploration after drift, and leaving unanswered the principled question of how exploration intensity should scale with drift magnitude. We show that, under standard assumptions, entropy scheduling in non-stationary maximum-entropy RL can be cast as the dynamic-regret trade-off between tracking a drifting comparator and stabilizing updates, yielding a square-root scaling rule for the entropy weight in terms of a online non-stationarity proxy. Building on this, we propose AES--Adaptive Entropy Scheduling--which adaptively adjusts the entropy coefficient/temperature online using observable drift proxies during training, requiring almost no structural changes and incurring minimal overhead. Across 4 algorithm variants, 12 tasks, and 4 drift modes, AES significantly reduces the fraction of performance degradation caused by drift and accelerates recovery after abrupt changes.

This paper introduces a new problem-dependent regret measure for online convex optimization with smooth losses. The notion, which we call the $G^\star$ regret, depends on the cumulative squared gradient norm evaluated at the decision in hindsight. We show that the $G^\star$ regret strictly refines the existing $L^\star$ (small loss) regret, and that it can be arbitrarily sharper when the losses have vanishing curvature around the hindsight decision. We establish upper and lower bounds on the $G^\star$ regret and extend our results to dynamic regret and bandit settings. As a byproduct, we refine the existing convergence analysis of stochastic optimization algorithms in the interpolation regime. Some experiments validate our theoretical findings.

Organizations often have an incumbent predictive model in production when new data sources become available. Because historical training data lack the new features, a challenger model must be trained on a small but growing full-feature dataset. We study whether, and when, the organization should switch to the challenger. The decision is statistical and economic: the challenger's predictive performance improves as full-feature data accumulate, but repeated retraining is costly and delays benefits from deployment. We develop a framework linking learning-curve dynamics to model-switching economics. Under a standard power-law learning curve and finite data-collection horizon $T$, the optimal time to train and evaluate the challenger scales as $T^{1/(1+α)}$: learning-curve shape (through its learning speed $α$) is the primary theoretical determinant of when to stop experimenting; costs determine switching profitability. Even without knowing the learning curve, the operational problem is tractable: we show that any algorithm stopping on the $T^{2/3}$ scale and making reliable switch/discard decisions achieves $O(T^{2/3}\sqrt{\log T})$ regret relative to a full-foresight oracle. We propose a sequential evaluation algorithm that uses local learning-curve trends to anticipate improvement, and test it in a real-world credit-scoring study. Even with this local approximation, the algorithm theoretically and empirically achieves near-oracle performance. It is also more stable than greedy sequential evaluation algorithms, where noisy early estimates trigger premature discarding, or simple one-shot evaluation algorithms, which work only when their fixed evaluation time matches the (unknown in practice) theoretical timing scale. Our framework offers a step toward principled model governance when new data sources require costly collection, validation, and deployment.

Agricultural decision-making faces a dual challenge: sustaining high yields to meet global food security needs while reducing the environmental impacts of input use, including fertilizer losses and other agrochemical applications such as herbicides, insecticides, and fungicides. Nitrogen inputs are central to this tension. They are indispensable for crop growth yet major drivers of greenhouse gas emissions, nutrient runoff, and escalating production costs. Addressing these intertwined pressures requires adaptive decision-support tools that are statistically principled, economically sustainable and interpretable for practitioners. We develop nonlinear model-based bandit algorithms as a framework for adaptive fertilizer management under uncertainty. Building on classical mechanistic yield-response models, our approach links algorithmic exploration-exploitation strategies directly to interpretable biological processes such as maximum yield and nutrient efficiency. This grounding makes recommendations transparent for practitioners while supporting cost-effective and sustainable input use. Methodologically, we establish regret and sample complexity results for the well-specified nonlinear case, examine robustness under misspecification, and evaluate the proposed methods through profit-oriented simulations and an offline replay case study on publicly available multi-site corn nitrogen field trials from the U.S. Midwest. The results show that incorporating biologically meaningful mechanistic structure enables faster learning and higher profit as evidence accumulates, with flexible nonparametric baselines providing a competitive alternative in pooled and heterogeneous settings. Our findings illustrate how interpretable, uncertainty-aware sequential decision rules can support economically sustainable fertilizer recommendations and contribute to more efficient agricultural input use.

We study the problem of fair cohort selection under uncertainty, motivated by university admissions where applicant outcomes are only partially observed. We consider both a one-shot setting, where a fixed policy is applied to a population, and a sequential setting, where policies are updated over time using data from previous admission years. We propose a policy optimization framework that combines probabilistic modeling of outcomes with policy gradient methods, supporting both logistic and neural network policies. In the sequential setting, the approach jointly updates the policy and the underlying models to adapt to evolving applicant populations. Experiments on a simulator grounded in real admission data show that adaptive policies substantially outperform static baselines in term of expected utility, especially under higher admission costs. Neural policies consistently achieve higher utility and adapt more effectively than simpler models, while maintaining favorable fairness properties over time. Our results demonstrate the importance of adaptivity and model expressiveness for decision-making under uncertainty.

Time-Varying Bayesian Optimization (TVBO) is the go-to framework for optimizing a time-varying, expensive, noisy black-box function $f$. However, most of the asymptotic guarantees offered by TVBO algorithms rely on the assumption that observations are acquired at a constant frequency. As the GP inference complexity scales with the cube of its dataset size, this assumption is unrealistic in the long run. In this paper, we relax this assumption and derive the first upper regret bound that explicitly accounts for changes in the observations sampling frequency. Based on this analysis, we formulate practical recommendations about dataset sizes and stale data policies of TVBO algorithms. We illustrate how an algorithm (BOLT) that follows these recommendations performs better than the state-of-the-art of TVBO through experiments on synthetic and real-world problems.

Multi-agent path finding (MAPF) in large networks is computationally challenging. An approach for MAPF is prioritized planning (PP), in which agents plan sequentially according to their priority. Albeit a computationally efficient approach for MAPF, the solution quality strongly depends on the prioritization. Most prioritizations rely either on heuristics, which do not generalize well, or iterate to find adequate priorities, which costs computational effort. In this work, we show how agents can compute with multiple prioritizations simultaneously. Our approach is general as it does not rely on domain-specific knowledge. The context of this work is multi-agent motion planning (MAMP) with a receding horizon subject to computation time constraints. MAMP considers the system dynamics in more detail compared to MAPF. In numerical experiments on MAMP, we demonstrate that our approach achieves near-optimal prioritization and outperforms state-of-the-art methods with only a minor increase in computation time. We show real-time capability in an experiment on a road network with ten vehicles in our Cyber-Physical Mobility Lab.

Online linear programming (OLP) has gained significant attention from both researchers and practitioners due to its extensive applications such as online auctions, network revenue management, order fulfillment and advertising. Existing OLP algorithms fall into two categories: LP-based algorithms and LP-free algorithms. The former typically guarantees better performance but requires solving a large number of LPs, which could be computationally expensive. In contrast, LP-free algorithms only require first-order computations but induce a worse performance. In this work, we bridge the gap between these two extremes by proposing a well-performing algorithm that solves LPs at a few selected time points and conducts first-order computations at other time points. Specifically, for the case where the inputs are drawn from an unknown finite-support distribution, the proposed algorithm achieves a constant regret (even for the hard "degenerate" case) while solving LPs only $O(\log\log T)$ times over the time horizon $T$. Moreover, when we are allowed to solve LPs only $M$ times, we design the corresponding schedule such that the proposed algorithm can guarantee a nearly $O\left(T^{(1/2)^{M-1}}\right)$ regret. Our work highlights the value of resolving both at the beginning and the end of the selling horizon, and provides a novel framework to prove the performance guarantee of the proposed policy under different infrequent resolving schedules. Numerical experiments are conducted to demonstrate the efficiency of the proposed algorithms.

We study Online Linear Programming (OLP) with batching. The planning horizon is cut into $K$ batches, and decisions on orders can be delayed to the end of their associated batch. The ability to delay decisions improves operational performance, as measured by regret. We study two questions: (1) What is a lower bound on the regret as a function of $K$ and the length of the planning horizon? (2) Which algorithms can achieve this regret lower bound? This paper analyzes these questions when the distribution of the reward has a continuous support. We provide an $Ω(\log K)$ regret lower bound in the single-resource case, and we provide pricing algorithms having an $O(\log K)$ regret in the setting with Poisson arrivals and multiple types of resources. All the algorithms update the prices at most $K$ times and only delay orders of the first and the last batches. All the regret bounds are independent of the length of the planning horizon. Finally, we study a more realistic large support setting where the number of distinct order types is finite but scales with the total number of orders. We prove that our $Θ(\log K)$ bounds still hold for the batching operation of a multisecretary problem with discretized uniform rewards in this large support setting, provided the support grows fast enough. This suggests that the continuous support setting that is the paper's focus serves as a useful theoretical surrogate for the more realistic large finite support setting.

We consider online resource allocation under a typical non-profit setting, where limited or even scarce resources are administered by a not-for-profit organization like a government. We focus on the internal-equity by assuming that arriving requesters are homogeneous in terms of their external factors like demands but heterogeneous for their internal attributes like demographics. Specifically, we associate each arriving requester with one or several groups based on their demographics (i.e., race, gender, and age), and we aim to design an equitable distributing strategy such that every group of requesters can receive a fair share of resources proportional to a preset target ratio. We present two LP-based sampling algorithms and investigate them both theoretically (in terms of competitive-ratio analysis) and experimentally based on real COVID-19 vaccination data maintained by the Minnesota Department of Health. Both theoretical and numerical results show that our LP-based sampling strategies can effectively promote equity, especially when the arrival population is disproportionately represented, as observed in the early stage of the COVID-19 vaccine rollout.

We propose a generalization of the synthetic control methods to the setting with dynamic treatment effects, in which each unit receives multiple treatments sequentially, according to an adaptive policy that depends on a latent, endogenously time-varying confounding state. Under a low-rank latent factor model assumption, which admits linear time-varying and time-invariant dynamic triangular systems as special cases, we develop an identification strategy for any unit-specific mean outcome under any sequence of interventions. Our method, which we term synthetic blips, is a backward induction process in which the blip effect of a treatment at each period for a target unit is recursively expressed as a linear combination of the blip effects of other units that received the designated treatment, avoiding the combinatorial donor requirements of naive synthetic control extensions. We provide easy-to-implement estimation algorithms that yield consistent estimators. Using unique Korean firm-level panel data, we estimate individualized dynamic treatment effects and optimal allocation rules in the context of financial support for exporting firms.