Tianyi Lin

We study robust learning in creator markets under the ε-contamination model. Here, a platform sequentially allocates advertiser demand to creators, collects rewards, and incentivizes them through revenue sharing. For each advertiser, rewards follow an unknown fixed distribution on at least T − εT rounds of a horizon of length T , while on the remaining at most εT rounds they can take arbitrary values in [0, 1]. Our first contribution is to formalize this robust learning problem in creator markets and demonstrate its algorithmic challenges. We prove that any learning algorithm suffers a regret of Ω(εT + T 2/3), and that the vanilla UCB update rule underlying Zhu et al. (2023) admits a linear-regret failure mode in an oracle-aided recommendation-only sub- problem even when εT < T 2/3. We then develop a new algorithm based on adaptive elimination, for which we establish a high-probability regret bound of ˜O(εT + T 2/3), optimal up to logarithmic factors. The algorithm is transparent and clarifies the key explore-exploit trade-off under contamination. Numerical experiments provide a focused stress test under front-loaded adversarial contamination, showing that the proposed elim- ination rule is more stable than vanilla UCB and Thompson sampling in this setting. These experiments complement the theoretical robustness guarantee rather than serve as an exhaustive empirical comparison across contamination models and baseline families. Using the outcomes induced by our algorithm, we also analyze how the distribution of creator capabilities and contamination shape long-term market concentration and revenue sharing, uncovering new insights that complement prior economic models (Bhargava 2022).

Artificial intelligence (AI) changes social learning when aggregated outputs become training data for future predictions. To study this, we extend the DeGroot model by introducing an AI aggregator that trains on population beliefs and feeds synthesized signals back to agents. We define the learning gap as the deviation of long-run beliefs from the efficient benchmark, allowing us to capture how AI aggregation affects learning. Our main result identifies a threshold in the speed of updating: when the aggregator updates too quickly, there is no positive-measure set of training weights that robustly improves learning across a broad class of environments, whereas such weights exist when updating is sufficiently slow. We then compare global and local architectures. Local aggregators trained on proximate or topic-specific data robustly improve learning in all environments. Consequently, replacing specialized local aggregators with a single global aggregator worsens learning in at least one dimension of the state.Institutional subscribers to the NBER working paper series, and residents of developing countries may download this paper without additional charge at www.nber.org.

Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback Curious about how players can learn and adapt in unknown games without knowing the game’s dynamics? In “Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback,” Ba, Lin, Zhang, and Zhou present a novel bandit learning algorithm for no-regret learning in games where each player only observes its reward determined by all players’ current joint action, not its gradient. Focusing on smooth and strongly monotone games, they introduce a bandit learning algorithm using self-concordant barrier functions. This algorithm achieves optimal single-agent regret and optimal last-iterate convergence rate in multiagent learning to the Nash equilibrium. Their work significantly improves previous methods and demonstrates the algorithm’s effectiveness through numerical results in various applications.

Feasible Online Learning with Gradient Feedback Online gradient descent (OGD) is well-known to be doubly optimal under strong convexity or monotonicity assumptions: (1) in the single-agent setting, it achieves an optimal regret of [ ] for strongly convex cost functions, and (2) in the multiagent setting of strongly monotone games with each agent employing OGD we obtain last-iterate convergence of the joint action to a unique Nash equilibrium at an optimal rate of [ ]. Whereas these finite-time guarantees highlight its merits, OGD has the drawback that it requires knowing the strong convexity/monotonicity parameters. In “Adaptive, Doubly Optimal No-Regret Learning in Strongly Monotone and Exp-Concave Games with Gradient Feedback,” M. Jordan, T. Lin, and Z. Zhou design a fully adaptive OGD algorithm, AdaOGD, that does not require a priori knowledge of these parameters. In the single-agent setting, the algorithm achieves [ ] regret under strong convexity, which is optimal up to a log factor. Further, if each agent employs AdaOGD in strongly monotone games, the joint action converges in a last-iterate sense to a unique Nash equilibrium at a rate of [ ], again optimal up to log factors. The algorithms are illustrated in a learning version of the classic newsvendor problem, in which, because of lost sales, only (noisy) gradient feedback can be observed. The results immediately yield the first feasible and near-optimal algorithm for both the single-retailer and multiretailer settings.

We propose and analyze a new dynamical system with a closed-loop control law in a Hilbert space [ ], aiming to shed light on the acceleration phenomenon for monotone inclusion problems, which unifies a broad class of optimization, saddle point, and variational inequality (VI) problems under a single framework. Given an operator [ ] that is maximal monotone, we propose a closed-loop control system that is governed by the operator [ ], where a feedback law [ ] is tuned by the resolution of the algebraic equation [ ] for some [ ]. Our first contribution is to prove the existence and uniqueness of a global solution via the Cauchy–Lipschitz theorem. We present a simple Lyapunov function for establishing the weak convergence of trajectories via the Opial lemma and strong convergence results under additional conditions. We then prove a global ergodic convergence rate of [ ] in terms of a gap function and a global pointwise convergence rate of [ ] in terms of a residue function. Local linear convergence is established in terms of a distance function under an error bound condition. Further, we provide an algorithmic framework based on the implicit discretization of our system in a Euclidean setting, generalizing the large-step hybrid proximal extragradient framework. Even though the discrete-time analysis is a simplification and generalization of existing analyses for a bounded domain, it is largely motivated by the aforementioned continuous-time analysis, illustrating the fundamental role that the closed-loop control plays in acceleration in monotone inclusion. A highlight of our analysis is a new result concerning [ ]-order tensor algorithms for monotone inclusion problems, complementing the recent analysis for saddle point and VI problems. Funding: This work was supported in part by the Mathematical Data Science Program of the Office of Naval Research [Grant N00014-18-1-2764] and by the Vannevar Bush Faculty Fellowship Program [Grant N00014-21-1-2941].

Motivated by applications to online learning in sparse estimation and Bayesian optimization, we consider the problem of online unconstrained nonsubmodular minimization with delayed costs in both full information and bandit feedback settings. In contrast to previous works on online unconstrained submodular minimization, we focus on a class of nonsubmodular functions with special structure, and prove regret guarantees for several variants of the online and approximate online bandit gradient descent algorithms in static and delayed scenarios. We derive bounds for the agent's regret in the full information and bandit feedback setting, even if the delay between choosing a decision and receiving the incurred cost is unbounded. Key to our approach is the notion of $(\alpha, \beta)$-regret and the extension of the generic convex relaxation model from~\citet{El-2020-Optimal}, the analysis of which is of independent interest. We conduct and showcase several simulation studies to demonstrate the efficacy of our algorithms.