Paper deep dive
Adaptive Incentive Design with Regret Minimization
Georgios Vasileiou, Lantian Zhang, Silun Zhang
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 92%
Last extracted: 4/10/2026, 1:59:29 AM
Summary
The paper introduces the Regret-Minimizing Adaptive Incentive Design (RAID) problem, which addresses information asymmetry in principal-agent games. It proposes the RAID algorithm, which uses a switching policy between exploration (probing) and exploitation (estimate-based incentivization) to achieve asymptotically minimal regret. The authors establish strong consistency for the type estimator under a relaxed excitation condition, eliminating the need for standard persistence-of-excitation assumptions.
Entities (4)
Relation Signals (2)
RAID algorithm → solves → Regret-Minimizing Adaptive Incentive Design
confidence 95% · we develop the RAID algorithm... which aims to synthesize incentive laws under information asymmetry
System Planner → implements → RAID algorithm
confidence 90% · The system planner must design and publicly commit to an incentive law... we develop the RAID algorithm
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Incentive design constitutes a foundational paradigm for influencing the behavior of strategic agents, wherein a system planner (principal) publicly commits to an incentive mechanism designed to align individual objectives with collective social welfare. This paper introduces the Regret-Minimizing Adaptive Incentive Design (RAID) problem, which aims to synthesize incentive laws under information asymmetry and achieve asymptotically minimal regret compared to an oracle with full information. To this end, we develop the RAID algorithm, which employs a switching policy alternating between probing (exploration) and estimate-based incentivization (exploitation). The associated type estimator relies only on a weaker excitation condition required for strong consistency in least squares estimation, substantially relaxing the persistence-of-excitation assumptions previously used in adaptive incentive design. In addition, we establish the strong consistency of the proposed type estimator and prove that the incentive obtained asymptotically minimizes the planner's average regret almost surely. Numerical experiments illustrate the convergence rate of the proposed methodology.
Tags
Links
- Source: https://arxiv.org/abs/2604.05977v1
- Canonical: https://arxiv.org/abs/2604.05977v1
Trouble viewing inline? Open PDF directly →
Full Text
48,421 characters extracted from source content.
Expand or collapse full text
Adaptive Incentive Design with Regret Minimization Georgios Vasileiou†, Lantian Zhang†, and Silun Zhang† This work has been partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP), funded by the Knut and Alice Wallenberg Foundation.† Georgios Vasileiou, Lantian Zhang and Silun Zhang are with the Dept. of Mathematics at the KTH Royal Institute of Technology, Stockholm, 10044, Sweden. geovas, lantian, silunz@kth.se Abstract Incentive design constitutes a foundational paradigm for influencing the behavior of strategic agents, wherein a system planner (principal) publicly commits to an incentive mechanism designed to align individual objectives with collective social welfare. This paper introduces the Regret-Minimizing Adaptive Incentive Design (RAID) problem, which aims to synthesize incentive laws under information asymmetry and achieve asymptotically minimal regret compared to an oracle with full information. To this end, we develop the RAID algorithm, which employs a switching policy alternating between probing (exploration) and estimate-based incentivization (exploitation). The associated type estimator relies only on a weaker excitation condition required for strong consistency in least squares estimation, substantially relaxing the persistence-of-excitation assumptions previously used in adaptive incentive design. In addition, we establish the strong consistency of the proposed type estimator and prove that the incentive obtained asymptotically minimizes the planner’s average regret almost surely. Numerical experiments illustrate the convergence rate of the proposed methodology. Keywords—Incentive schemes, adaptive systems, agents and autonomous systems, game theoretical methods. I Introduction Incentivization is a central topic in many economic and engineered systems, where a central planner seeks to coordinate the behavior of agents with unknown or misaligned objectives. Designing incentives that align individual interests with collective goals gives rise to the general class of Incentive Design problems, also known as principal–agent or reverse Stackelberg games [grootReverseStackelbergGames2012]. These problems describe sequential decision-makers coupled through interdependent costs, where a system planner (leader) aims to steer a population of self-interested agents (followers) toward a globally favorable outcome. Each agent, however, acts to minimize its private cost that depends on its own action and the principal’s posted incentive. The planner must design and publicly commit to an incentive law which maps agents’ actions to rewards or penalties, thereby shaping the agents’ strategic behavior. From a control-theoretic perspective [hoControltheoreticViewIncentives1980, basarAffineIncentiveSchemes1984, ratliffPerspectiveIncentiveDesign2019], such a commitment can be viewed as a feedback mechanism that prescribes a desired equilibrium solution among agents. Problems of this type often emerge in adaptive pricing of distributed energy resources in smart grids [liDistributedOnlinePricing, liSociallyOptimalEnergy2024, samadiDemandSideMagement2012], congestion-aware road tolling [povedaDistributedAdaptivePricing, barreraDynamicIncentives, grootSystemOptimalRoutingTraffic2015], and data-crowdsourcing in federated learning markets [hoAdaptiveContractDesignCrowdsourcing, dingContractDesignFederated2021]. In such applications, the planner must adapt incentives under uncertainty about agents’ preferences, making adaptive methods essential. A significant challenge in incentive design problems is adverse selection [picardDesignIncentiveSchemes1987], i.e., information asymmetry arising from the planner’s incomplete knowledge of the agents’ private cost functions or preferences. Historically, adverse selection has been addressed via the design of mechanisms that induce truthful participation [nisanAlgorithmicGameTheory2007, hartlineMechanismDesignApproximation2013], methods which are restricted to static, one-shot interactions and are strongly model-dependent. To overcome these limitations, recent adaptive incentive design [ratliffAdaptiveIncentiveDesign2021] approaches infer agents’ preferences through repeated principal-agent interactions and the information derived from the corresponding equilibrium outcomes. Relaxing the exactness of agent responses, Chen et al. [chenActiveInverseMethods2025] study Stackelberg settings where agents exhibit bounded rationality, and the leader actively designs informative actions for a maximum-likelihood estimator. Departing from estimation-based methods, Maheshwari et al. [maheshwariAdaptiveIncentiveDesign2024] study incentive design under a two-timescale framework, where agents are learning individuals that exponentially converge to a Nash equilibrium. The planner leverages agent externalities, the difference between social objective and the agent cost gradients, to design incentives on a slower timescale. For finite action spaces, [yorulmazSoftInducementFramework2025] examines equilibrium steering in Bayesian normal-form games with bimatrix payoffs, where the principal guides learning agents toward desired action profiles by imposing constant, lower-bounded incentives, which achieves sublinear regret in utility. In this work, we introduce the Regret-Minimizing Adaptive Incentive Design (RAID) problem, which integrates online type estimation together with incentive design to achieve asymptotically vanishing behavioral regret relative to an oracle. The paper makes two main contributions. First, we investigate the dual problem of type estimation and incentive commitment, examining how online parameter estimation affects the planner’s ability to regulate agent behavior. Motivated by literature on adaptive estimation and control [tzelaiExtendedLeastSquares1986], we formulate the planner’s regret of a given sequence of incentives as the cumulative tracking error up to iteration t. We propose an adaptive incentive policy (Algorithm 1) that switches between probing (exploratory) and estimate-based (exploitative) incentives, and prove that the resulting incentive policy achieves almost-surely O(tγlogt)O(t^γ t) regret, for γ∈[23,1)γ∈[ 23,1). The sublinear regret implies the policy is asymptotically optimal and balances the competing demands of learning and control in adaptive incentive design. Second, we relax the excitation required for the planner’s identification objective to a weak diminishing-excitation condition, known to guarantee the strong consistency of the least-squares estimator in stochastic approximation [laiLeastSquaresEstimates1982]. This result eliminates the standard persistence-of-excitation (PE) assumption made in adaptive incentive design, and provides strong consistency guarantees for the estimator with injection of diminishing excitation. Overall, our findings extend the adaptive-control perspective on adaptive incentive design by ensuring strongly consistent type estimation and providing almost-surely vanishing regret for an appropriate switching incentive policy. Notations. Given some n∈ℕn , let [n]=1,2,…,n[n]=\1,2,…,n\. For a vector-valued map f:ℝ→ℝnf:R ^n, denote derivatives ∇f=(∂f1∂x(x),…,∂fn∂x(x))⊤∇ f= ( ∂ f_1∂ x(x),…, ∂ f_n∂ x(x) ) and ∇2f=∇(∇f)∇^2f=∇(∇ f). The notation f(t)=O(g(t))f(t)=O(g(t)) denotes the existence of c>0c>0 and t0t_0 so that |f(t)|≤c|g(t)||f(t)|≤ c|g(t)| for all t≥t0t≥ t_0. Likewise, f(t)=Ω(g(t))f(t)= (g(t)) indicates |f(t)|≥c|g(t)||f(t)|≥ c|g(t)|. We write f(t)=Θ(g(t))f(t)= (g(t)) when both bounds hold, and f(t)=o(g(t))f(t)=o(g(t)) if f(t)/g(t)→0f(t)/g(t)→ 0. CkC^k denotes the class of k−k-smooth functions. I Problem Formulation Consider a noncooperative game between n agents and a single system planner. Each agent i∈[n]i∈[n] aims to minimize an individual cost function by choosing a strategy xi∈ix_i _i, where i⊂ℝX_i is a compact interval.111Agents’ strategies are scalar for clarity of exposition. Results extend directly to higher-dimensional strategies with notational changes only. Agent i seeks to minimize the individual cost ci(xi,pi)=ℓi(xi)+pixi,c_i(x_i,p_i)= _i(x_i)+p_ix_i, (1) where ℓi:ℝ→ℝ _i:R is the agent’s nominal cost, and pi∈ℝp_i is an external incentive rate imposed by the system planner. Here, the agent’s nominal cost corresponds to an inherent preference over their strategy, and pixip_ix_i is the planner’s intervention, imposed to modify the nominal behavior. Linear incentives, as the simplest incentive mappings available to the planner, have been extensively examined in recent work on incentive design [maheshwariAdaptiveIncentiveDesign2024, liSociallyOptimalEnergy2024] and are sufficient to influence agent behavior by modifying marginal costs. The system planner’s objective is to minimize a social cost Ψ:ℝn→ℝ :R^n that depends on the collective action x=(x1,…,xn)⊤x=(x_1,…,x_n) . When agents act in self-interest, aligning their behavior with the planner’s objective requires that the planner design and implement an appropriate incentive. Define the set of socially optimal outcomes by des=argminx∈Ψ(x),X_ des= *arg\,min_x (x), where =∏i∈[n]iX= _i∈[n]X_i. If Ψ(⋅) (·) is strongly convex then desX_ des is a singleton; otherwise, the planner may select any xdes∈desx_ des _ des as the desired agent profile. We restrict our attention to problems where xdesx_ des it interior to the feasible region. Assumption 1. There exists a profile xdes∈desx_ des _ des such that xdes∈∏i∈[n]intix_ des∈ _i∈[n] *intX_i. A fundamental challenge for the planner is the information asymmetry that arises when the agent’s nominal costs ℓi _i are unknown. This information asymmetry prevents the direct computation of optimal incentives and necessitates the use of type identification methods. The planner parameterizes agents’ nominal costs with ℓi(xi)=θi∗⊤Φ(xi), _i(x_i)= _i^* (x_i), (2) where Φ:ℝ→ℝd :R ^d is the monomial basis222For notational simplicity, we assume that all agent’s nominal costs are parametrized with the same d-dimensional basis Φ . Φ(x)=(x,x2,…,xd)⊤, (x)=(x,\,x^2,\,…,\,x^d) , and θi∗∈ℝd _i^* ^d is the private type parameter of agent i. The system planner must issue incentives that both facilitate the learning of agent types and regulate their behavior toward the intended profile xdesx_ des. Assumption 2. For every agent i∈[n]i∈[n], there exist positive constants mim_i and MiM_i, such that θi∗ _i^* belongs to a set of admissible types Θi _i that satisfies θi∗∈Θi≜θ∈ℝd:mi≤θ⊤∇2Φ(xi)≤Mi,∀xi∈i. _i^*∈ _i \θ ^d:m_i≤θ ∇^2 (x_i)≤ M_i,\,∀ x_i _i\. Under Assumption 2, each Θi _i is closed and convex, and the nominal cost ℓi _i of agent i∈[n]i∈[n] is mim_i-strongly convex and has an MiM_i-Lipschitz gradient on iX_i. When the planner issues an arbitrary incentive pi∈ℝp_i to agent i, the agent’s response is given by a best-response map xi∗:ℝ→ix_i^*:R _i, which satisfies xi∗(pi)∈argminx∈i(θi∗⊤Φ(x)+pix).x_i^*(p_i)∈ *arg\,min_x _i( _i^* (x)+p_ix). (3) Remark 1. Throughout this work, we assume that each agent immediately selects the best response according to (3) and do not consider the procedure by which the minimization problem is solved. This is a standard (idealized) best-response model, often utilized in incentive design [liSociallyOptimalEnergy2024, ratliffAdaptiveIncentiveDesign2021]. Remark 2. Due to the decoupled structure of ℓi _i in (1), agents’ strategies are independent of other agents, as is evident in the best-response (3). This setting is often encountered in applications of incentive design, including demand-side energy management [liDistributedOnlinePricing, samadiDemandSideMagement2012] and federated learning data markets [dingContractDesignFederated2021], where users’ energy-scheduling and participation cost overheads are locally determined. We will extend the framework introduced in this paper to include multi-agent interactions in a following journal work. The next result characterizes the agent’s best-response map under Assumption 2, and establishes a bijection between incentives pip_i and responses xi∗(pi)x_i^*(p_i), in an appropriate open subset of ℝR. This result is developed from the case of unconstrained strategies presented in [liDistributedOnlinePricing, Lemma 1]. Lemma 1. Under Assumption 2, for each agent i∈[n]i∈[n] and θi∗∈Θi _i^*∈ _i, there is a C1C^1 map h(p)h(p) such that the best-response map xi∗(p)=h(p)x_i^*(p)=h(p). Over the open set i=h−1(inti)P_i=h^-1( *intX_i), it holds that, for any p∈ip _i, θi∗⊤∇Φ(h(p))+p=0, and _i^* ∇ (h(p))+p=0, and (4) −1mi≤h′(p)≤−1Mi,- 1m_i≤ h (p)≤- 1M_i, (5) Proof. Consider xi∗(pi)x^*_i(p_i) to be a solution of (3) within inti *intX_i. Then xi∗(pi)x^*_i(p_i) satisfies the first-order optimality condition for ci(xi,pi)c_i(x_i,p_i), and therefore −θi∗⊤∇Φ(xi∗(pi))+pi=0.- _i^* ∇ (x^*_i(p_i))+p_i=0. (6) The mapping f:xi↦−θi∗⊤∇Φ(xi)f:x_i - _i^* ∇ (x_i) is 1C^1 with a nonzero derivative so, by the inverse function theorem, there exists a 1C^1 map f−1:−θi∗⊤∇Φ(xi)↦xif^-1:- _i^* ∇ (x_i) x_i. Due to (6), f−1f^-1 maps pi↦xi∗(pi)p_i x^*_i(p_i) and satisfies (f−1)′(pi)=1f′(xi∗(pi))=−1θi∗⊤∇2Φ(xi∗(pi)).(f^-1) (p_i)= 1f (x_i^*(p_i))= -1 _i^* ∇^2 (x_i^*(p_i)). Define the open set i=f(int)P_i=f( *intX). For any p∈ip _i it holds that θi∗⊤∇Φ(f−1(p))+p=−f(f−1(p))+p=0 _i^* ∇ (f^-1(p))+p=-f(f^-1(p))+p=0. ∎ The planner can only learn from agent responses that vary smoothly with incentives, so we introduce the notion of an informative region iP_i, defined in Lemma 1 for each agent i∈[n]i∈[n]. We refer to any p∈ip _i as an informative incentive. Remark 3. The set iP_i of each agent depends on θi∗ _i^*, as evidenced by (4), and is unknown to the system planner. However, the planner can identify whether an incentive is informative by the observation xi∗(p)∈intix^*_i(p)∈ *intX_i. If the agents’ preferences were known, the planner could elicit the desired response xdes=(x1,des,…,xn,des)⊤x_ des=(x_1, des,…,x_n, des) by issuing to i∈[n]i∈[n] the incentive pi,des=−θi∗⊤∇Φ(xi,des)p_i, des=- _i^* ∇ (x_i, des). In the absence of this information, the planner must construct an estimator θ^i(t) θ_i(t) of θi∗ _i^* from incentive-response trajectories. Given estimate θ^i(t) θ_i(t), consider the adaptive incentive scheme pi(t+1)=−θ^i(t)⊤∇Φ(xi,des),p_i(t+1)=- θ_i(t) ∇ (x_i, des), (7) which approximates the (unrealizable) regulator that assumes knowledge of θi∗ _i^*. Denote the trajectory of player i up to time t as i(t)=(pi(τ),xi(τ))τ≤tT_i(t)=\(p_i(τ),x_i(τ))\_τ≤ t, where xi(t)=xi∗(pi(t))x_i(t)=x_i^*(p_i(t)). Whenever xi(t)∈intix_i(t)∈ *intX_i, the observation pair (p^i(t),xi(t))( p_i(t),x_i(t)) satisfies the observation equation p^i(t)=−θi∗⊤∇Φ(xi(t))+ei(t), p_i(t)=- _i^* ∇ (x_i(t))+e_i(t), (8) where ei(t)e_i(t) is an unobservable noise. We make the following assumption on the incentive–response noise. Assumption 3. For each i∈[n]i∈[n], the process ei(t)t≥1\e_i(t)\_t≥ 1 in (8) is i.i.d., zero-mean and satisfies supt≥1[|ei(t)|a]<∞ _t≥ 1E[|e_i(t)|^a]<∞ for a>2a>2. Moreover, ei(t)e_i(t) is independent of xi(t)x_i(t). Remark 4. The assumption that ei(t)e_i(t) is independent of xi(t)x_i(t) is standard in adaptive incentive design [ratliffAdaptiveIncentiveDesign2021]. It reflects a setting in which type estimation and incentive design are performed by distinct entities, and only the noisy incentive signal is available for estimation. When independence does not hold, (8) becomes an Error-in-Variables (EIV) regression, whose analysis is deferred to a following journal version. We quantify the performance of a selected incentive sequence with respect to the cumulative tracking error from xdesx_ des. Formally, define the t-stage regret of a given incentive sequence p(τ)τ≤t\p(τ)\_τ≤ t to be Rt=∑τ=1t‖x(τ)−xdes‖22=∑τ=1t‖x∗(p(τ))−xdes‖22, R_t= _τ=1^t\|x(τ)-x_ des\|^2_2= _τ=1^t\|x^*(p(τ))-x_ des\|_2^2, (9) where p(t)p(t) and x(t)x(t) denote p(t)=(p1(t),…,pn(t))⊤p(t)=(p_1(t),\,…,\,p_n(t)) , and x(t)=(x1∗(p1(t)),…,xn∗(pn(t)))⊤x(t)=(x_1^*(p_1(t)),\,…,\,x_n^*(p_n(t))) , respectively. The planner’s objective is twofold: to ensure accurate type estimation through sufficient exploration of the parameter space, and to regulate the collective behavior toward the social optimum. We formalize this task in the Regret-minimizing Adaptive Incentive Design (RAID) problem. Problem (Regret–minimizing Adaptive Incentive Design – RAID). Given a social cost function Ψ(⋅) (·) and a desired agent profile xdes∈argminx∈Ψ(x)x_ des∈ *arg\,min_x (x), a system planner with no prior knowledge of the true type θ∗=(θ1∗⊤,…,θn∗⊤)⊤θ^*=( _1^* ,…, _n^* ) aims to design a type estimator θ^(t) θ(t) and an incentive sequence p(τ)τ≥1\p(τ)\_τ≥ 1 satisfying two goals: 1. Strong consistency of θ^(t) θ(t): For any initial estimation θ^(0)=θ0 θ(0)= _0, the estimator θ^(t) θ(t) converges to θ∗θ^* a.s., and 2. Sublinear regret accumulation: The t-stage average regret of the policy p(τ)τ≤t\p(τ)\_τ≤ t, defined as in (9), vanishes asymptotically a.s., that is, Rt=o(t) a.s. R_t=o(t) a.s. Incentive Design can be seen as a Stackelberg game, wherein the planner acts as a Stackelberg leader by committing to an incentive policy which affects followers’ cost functionals and induces their best responses. In this way, each pair (pdes,xdes)(p_ des,x_ des) chosen by the planner constitutes a Stackelberg equilibrium. Achieving vanishing average regret corresponds to driving the incentive-response pair (p(t),x(t))(p(t),x(t)) to the Stackelberg equilibrium (pdes,xdes)(p_ des,x_ des) in a mean-square sense. The construction of the type estimator to learn θ∗θ^* and the conditions required for its strong consistency are presented in the next section. I Strongly Consistent Type Estimation In this section, we construct a type estimator and analyze its convergence under different levels of excitation present in the agents’ trajectories i(t)T_i(t). Given a collection of incentive-response observations for each agent i up to time t, the estimator θ^i(t) θ_i(t) for θi∗ _i^* can be constructed by θ^i(t)=argminθi∈Θi∑τ≤t:pi(τ)∈i|θi⊤∇Φ(xi(τ))+p^i(τ)|2. θ_i(t)= *arg\,min_ _i∈ _i _ subarraycτ≤ t:\\ p_i(τ) _i subarray| _i ∇ (x_i(τ))+ p_i(τ)|^2. (10) Notice that agent response xi(t)x_i(t) satisfies (8) only when the corresponding incentive pi(t)p_i(t) is informative, i.e., when pi(t)∈ip_i(t) _i. Due to Lemma 1, the event pi(t)∈i\p_i(t) _i\ in (10) is equivalent to xi(t)∈inti\x_i(t)∈ *intX_i\, which can be verified by the planner without requiring knowledge of θ∗θ^*. Problem (10) can be recursively solved by θ^i(t) θ_i(t) =θ^i(t−1) = θ_i(t-1) (11a) −δi(t)Σi(t)ξi(t)(p^i(t)+ξi(t)⊤θ^i(t−1)), - _i(t) _i(t) _i(t) ( p_i(t)+ _i(t) θ_i(t-1) ), Σi(t) _i(t) =Σi(t−1) = _i(t-1) (11b) −δi(t)Σi(t−1)ξi(t)ξi(t)⊤Σi(t−1)1+δi(t)ξi(t)⊤Σi(t−1)ξi(t). - _i(t) _i(t-1) _i(t) _i(t) _i(t-1)1+ _i(t)\, _i(t) _i(t-1)\, _i(t). where we denote ξi(t)=∇Φ(xi(t)) _i(t)=∇ (x_i(t)), δi(t)=xi(t)∈inti _i(t)=1\x_i(t)∈ *intX_i\ and ⋅1\·\ is the indicator function. Denote θ^(t)=(θ^1(t)⊤,…,θ^n(t)⊤)⊤ θ(t)=( θ_1(t) ,…, θ_n(t) ) . Observe that (11b) represents a rank-one update on the information matrix Σi(t)−1 _i(t)^-1, that is, Σi(t)−1=Σi(t−1)−1+ξi(t)ξi(t)⊤δi(t). _i(t)^-1= _i(t-1)^-1+ _i(t) _i(t) _i(t). (11b’) To simplify notation, we will denote the regressor vectors as ξi(t)=∇Φ(xi(t)) _i(t)=∇ (x_i(t)) and define λi(t)=λmin(Σi(t)−1) _i(t)= _ ( _i(t)^-1). I-A Convergence of the Type Estimator In this subsection, we establish a sufficient condition for the strong consistency of (11) with respect to the spectrum of the information matrix Σi(t)−1 _i(t)^-1. Theorem 1. Suppose Assumptions 2 and 3 hold. For each i∈[n]i∈[n], the estimator θ^i(t) θ_i(t) given in (11) satisfies ‖θ^i(t)−θi∗‖22=O(λi(t)−1logt) a.s.,\| θ_i(t)- _i^*\|_2^2=O ( _i(t)^-1 t ) a.s., where θi∗ _i^* is the agent’s true type. Consequently, θ^i(t)→θi∗ θ_i(t)→ _i^* a.s. if logt=o(λi(t)) t=o( _i(t)) a.s. Proof. Let ℱi(t)=σ(ei(s):s≤t)F_i(t)=σ(e_i(s):s≤ t) denote the filtration generated by ei(t)e_i(t). Under Assumption 3, ei(t)e_i(t) is a martingale difference sequence and satisfies supt≥1[|ei(t)|a∣ℱi(t−1)]<∞, for a>2. _t≥ 1E[|e_i(t)|^a _i(t-1)]<∞, for a>2. By [laiLeastSquaresEstimates1982, Theorem 1] and the observation that ‖θ^i(t)−θi∗‖2=O(‖θ^i(t)−θi∗‖∞)\| θ_i(t)- _i^*\|_2=O(\| θ_i(t)- _i^*\|_∞), it holds that ‖θ^i(t)−θi∗‖2=O(log(λmax(t))λi(t)) a.s.,\| θ_i(t)- _i^*\|_2=O ( ( _ (t)) _i(t) ) a.s., where λmax(t) _ (t) denotes the maximum eigenvalue of Σi(t)−1 _i(t)^-1. Due to the compactness of iX_i, it also holds that λmax(t)≤tmaxx∈i‖∇Φ(x)‖22=O(t), _ (t)≤ t _x _i\|∇ (x)\|_2^2=O(t), and the result follows. ∎ The excitation required by [laiLeastSquaresEstimates1982] is a diminishing excitation condition that guarantees strong consistency in stochastic regression (see [laiLeastSquaresEstimates1982, Example 1]). Since the spectrum of Σi(t)−1 _i(t)^-1 depends on the responses xi(τ)τ≤t\x_i(τ)\_τ≤ t, the growth condition in Theorem 1 can be guaranteed indirectly by adding appropriate noise in incentives pi(t)p_i(t). The subsection that follows shows that independent, normally-distributed incentives satisfy this requirement. I-B Excitation under Normally Distributed Incentives In regression (8), the noise ei(t)e_i(t) does not affect the regressor sequence by Assumption 3, so the planner must explicitly inject excitation via pi(t)p_i(t). Theorem 2 proves that an i.i.d. Gaussian probing policy suffices to obtain linear growth in the spectrum of the information matrix. Theorem 2. Suppose Assumptions 2 and 3 hold. For each agent i∈[n]i∈[n], the i.i.d incentive policy pi(τ)τ≤t\p_i(τ)\_τ≤ t with each pi(τ)∼(0,σ2)p_i(τ) (0,σ^2) guarantees that λi(t)=Θ(t) a.s. _i(t)= (t) a.s. Proof. Presented in Section VI. ∎ An intermediate result of independent interest is that i.i.d. Gaussian incentives are persistently exciting for the kernel regression (8), despite the nonlinearity introduced by the mapping ∇Φ(⋅)∇ (·). Crucially, this excitation holds despite individual incentives not necessarily belonging to the informative region iP_i for any agent i∈[n]i∈[n]. Lemma 2. Under Assumptions 2 and 3, for each agent i∈[n]i∈[n] and i.i.d incentives pi(t)p_i(t) distributed according to (0,σ2)N(0,σ^2), there exists δ>0δ>0 such that [ξi(t)ξi(t)⊤δi(t)]⪰δ.E [ _i(t) _i(t) _i(t) ] . Proof. Presented in Section VI. ∎ Theorem 2 establishes that i.i.d Gaussian incentives provide sufficient excitation to the parameter estimator given in (11). This will be utilized in the next section to develop an adaptive incentive policy that guarantees strong consistency. IV An Algorithm for Regret-Minimizing Adaptive Incentive Design In this section, we leverage the convergence of the estimator in Section I to design an adaptive incentive policy that achieves both objectives of RAID. The proposed mechanism, given in Algorithm 1, alternates between exploration and exploitation phases to guarantee vanishing average regret. Parameters : γ∈[23,1)γ∈[ 23,1), σ2>0σ^2>0, t≥1t≥ 1. Output: Estimates θ^i(τ)τ≤t\ θ_i(τ)\_τ≤ t Define A(τ)=τγlogτA(τ)=τ^γ τ; Initialize Σi(0)≻0 _i(0) 0 and θ^i(0) θ_i(0), i∈[n]i∈[n]; for i∈[n]i∈[n] and τ=1,…,tτ=1,…,t do /* Exploration phase */ if tr(Σi(τ−1))>A(τ−1)−1 *tr( _i(τ-1))>A(τ-1)^-1 then Issue pi(τ)∼(0,σ2)p_i(τ) (0,σ^2); Observe xi(τ)=xi∗(pi(τ))x_i(τ)=x_i^*(p_i(τ)); Update Σi(τ) _i(τ) and θ^i(τ) θ_i(τ), according to (11); /* Exploitation phase */ else if tr(Σi(τ−1))≤A(τ−1)−1 *tr( _i(τ-1))≤ A(τ-1)^-1 then Issue pi(τ)←−θ^i(τ−1)⊤∇Φ(xi,des)p_i(τ)←- θ_i(τ-1) ∇ (x_i, des); Maintain Σi(τ)←Σi(τ−1) _i(τ)← _i(τ-1) and θ^i(τ)←θ^i(τ−1) θ_i(τ)← θ_i(τ-1) end for Algorithm 1 Regret–minimizing Adaptive Incentive Design (RAID) For each i∈[n]i∈[n], the equation pi,des=−θi∗⊤∇Φ(xi,des)p_i, des=- _i^* ∇ (x_i, des) defines the unique incentive that would elicit the desired response xi,desx_i, des. Without prior knowledge of types, it is natural for the system planner to substitute the estimate θ^i(t) θ_i(t) for θi∗ _i^*, which defines the adaptive policy (7). By Theorem 1, the algorithm must ensure that logt=o(λi(t)) t=o( _i(t)) a.s. to achieve strongly-consistent estimation of θi∗ _i^*. For this reason, the proposed algorithm uses a threshold-based switching rule to alternate between exploration and exploitation phases. Let pi(t)=−θ^i(t−1)⊤∇Φ(xi,des),τi(k)≤t<σi(k)ϵi(t),σi(k)≤t<τi(k+1)p_i(t)\!=\! cases- θ_i(t\!-\!1) ∇ (x_i, des),\!\!\!\!& _i(k)\!≤\!t\!<\! _i(k)\\ _i(t),& _i(k)\!≤\!t\!<\! _i(k\!+\!1) cases (12) where the probing sequence ϵi(t)t\ _i(t)\_t is i.i.d with each ϵi(t)∼(0,σ2) _i(t) (0,σ^2), and the switching schedule τi(k)k≥1\ _i(k)\_k≥ 1 and σi(k)k≥1\ _i(k)\_k≥ 1 is designed as follows. Let τi(1)=0 _i(1)=0, σi(k) _i(k) =inft:t≥τi(k),tr(Σi(t))>A(t)−1, = \t:t≥ _i(k),\ *tr( _i(t))>A(t)^-1\, (13) τi(k+1) _i(k+1) =inft:t≥σi(k),tr(Σi(t))≤A(t)−1, = \t:t≥ _i(k),\ *tr( _i(t))≤ A(t)^-1\, for k≥1k≥ 1, where A(t)A(t) is given in Algorithm 1. Due to the switching schedule (13), the exploitation phase takes place during iterations t∈[τi(k),σi(k))t∈[ _i(k), _i(k)) for all k≥1k≥ 1, and utilizes the current type estimate θ^i(t) θ_i(t) to regulate the agent’s behavior. During exploitation, the planner does not update the estimate θ^i(t) θ_i(t). On the other hand, exploration occurs when the information matrix Σi(t)−1 _i(t)^-1 needs to be excited. Notice that 1/λi(Σi(t)−1)≤tr(Σi(t))≤d/λi(Σi(t)−1)1/ _i( _i(t)^-1)≤ *tr( _i(t))≤ d/ _i( _i(t)^-1), and therefore, when λi(t)≤A(t) _i(t)≤ A(t), it follows that tr(Σi(t))≥A(t)−1 *tr( _i(t))≥ A(t)^-1. This condition defines the exploration iterations t∈[σi(k),τi(k+1))t∈[ _i(k), _i(k+1)) for all k≥1k≥ 1, during which the planner utilizes (11) to update the estimate θ^i(t) θ_i(t) to better approximate θi∗ _i^*. Applying Algorithm 1 with the incentive policy (12) and switching schedule (13), the planner can guarantee the a.s. convergence rate of θ^i(t) θ_i(t) to θi∗ _i^*, for each i∈[n]i∈[n], and that the t-stage average regret t−1Rtt^-1R_t a.s. vanishes. This constitutes the main result of this work, and is presented below. Theorem 3. Suppose Assumptions 1, 2, and 3 hold. For every i∈[n]i∈[n] and γ∈[23,1)γ∈[ 23,1), the type estimates θ^i(τ)τ≤t\ θ_i(τ)\_τ≤ t produced by Algorithm 1 satisfy ‖θ^i(t)−θi∗‖22=O(t−γ), a.s.\| θ_i(t)- _i^*\|_2^2=O(t^-γ), a.s. Moreover, the system planner’s regret RtR_t, as defined in (9), satisfies Rt=O(tγlogt), a.s.R_t=O(t^γ t), a.s. Proof. Presented in Section VI. ∎ The above regret bound is sublinear for every choice of γ∈[23,1)γ∈[ 23,1), hence the policy is asymptotically optimal. Among admissible choices, γ=23γ= 23 yields the fastest decay of t−1Rtt^-1R_t and thus represents the planner’s preferred parameter. V Numerical Examples We illustrate the performance of the proposed algorithm through numerical simulations. We first consider a game of n=3n=3 players with cubic cost functions according to (1) and the feasible response set =[−1,1]3X=[-1,1]^3. Player preferences are represented by the unknown types θ1∗=(1,0.5,0)⊤ _1^*=(1,0.5,0) , θ2∗=(0,3.5,1)⊤ _2^*=(0,3.5,1) , and θ3∗=(−1,3.5,−1)⊤ _3^*=(-1,3.5,-1) , and each agent model (8) is perturbed by the process ei(t)t≥1\e_i(t)\_t≥ 1 which is i.i.d. and normally-distributed with variance 0.10.1. The system planner has a desired response xdes=(0.5,0.5,0.5)⊤x_ des=(0.5,0.5,0.5) , and utilizes Algorithm 1 with parameters γ=23γ= 23 and σ2=2σ^2=2. Theorem 3 predicts that the parameter estimation error ‖θ^i(t)−θi∗‖2\| θ_i(t)- _i^*\|_2 decays as O(t−γ/2)O(t^-γ/2) a.s. and the average regret t−1Rtt^-1R_t decays as O(tγ−1logt)O(t^γ-1 t) a.s. Taking 100100 independent runs of Algorithm 1, Figure 1 depicts the planner’s empirical expectation of the estimation errors and accumulated regret, respectively. The results obtained are consistent with the predicted almost-sure decay rates of the agents’ type estimation error and the planner’s average regret. Figure 1: Mean (solid) and ±1± 1 standard deviation (shaded) of ‖θ^i(t)−θi∗‖2\| θ_i(t)- _i^*\|_2 and t−1Rtt^-1R_t over 100 independent realizations of Algorithm 1. Dashed lines indicate the a.s. convergence rates predicted in Theorem 3. Figure 2 illustrates that the convergence of the parameter estimator is dependent on the injected probing excitation rather than the model noise ei(t)e_i(t). In particular, the convergence rate in Theorem 3 is guaranteed even when ei(t)e_i(t) is of measure-zero support, such as a Rademacher-distributed random variable on ±0.1± 0.1 (Fig. 2, second row). This confirms that the weak excitation condition of Theorem 1 is satisfied by the probing policy of Algoritm 1. Figure 2: Estimation error ‖θ^i(t)−θi∗‖2\| θ_i(t)- _i^*\|_2 over a single realization of Algorithm 1 for a single agent. Dashed lines indicate the rate O(t−γ/2)O(t^-γ/2), γ=2/3γ=2/3. Columns vary the probing parameter σ2σ^2. (Top row) ei(t)∼nif[−0.5,0.5]e_i(t) [-0.5,0.5]. (Bottom row) ei(t)e_i(t) is a Rademacher-distributed random variable on ±0.1\± 0.1\. Figure 3 validates the regret bound in Theorem 3 across different choices of parameters in Algorithm 1. As predicted, γ=23γ= 23 yields the fastest decay of t−1Rtt^-1R_t among admissible values and is therefore the planner’s preferred choice. Observe further that the probing variance σ2σ^2 affects the onset of the asymptotic regime in Algorithm 1. When σ2σ^2 is small (e.g σ2=0.5σ^2=0.5), the information matrix grows slowly, resulting in near-constant average regret over a given simulation horizon. This suggests that the probing variance and parameter γ should be chosen relative to the problem horizon, and that a finite-time analysis of the algorithm is needed to characterize this tuning. This is left as an interesting direction for future work. Figure 3: Average regret t−1Rtt^-1R_t over a single realization of Algorithm 1 for a single agent. Model noise is ei(t)∼(0,0.1)e_i(t) (0,0.1). Dashed lines indicate the rate O(tγ−1logt)O(t^γ-1 t). Columns vary the probing parameter σ2σ^2 and rows vary the switching parameter γ. VI Proofs VI-A Proof of Lemma 2 Lemma 3. Let f:ℝ→ℝdf:R ^d be the vector-valued mapping f(x)=(1,x,…,xd−1)⊤f(x)=(1,x,…,x^d-1) , and let x∼(0,σ2)x (0,σ^2). For any nonempty, open interval A⊂ℝA , [f(x)f(x)⊤∣x∈A]≻0.E[f(x)f(x) x∈ A] 0. Proof. Let A=(a,b)A=(a,b) for a<ba<b. Then [f(x)f(x)⊤∣x∈A]=σ−1Φ(b)−Φ(a)∫abf(x)f(x)⊤ϕ(xσ)x, [f(x)f(x) \!\! \!x∈ A]= σ^-1 (b)\!-\! (a)\! _a^b\!\!f(x)f(x) \!φ( xσ)dx, where Φ and ϕφ represent the CDF and PDF of (0,1)N(0,1), respectively. For any z∈ℝdz ^d satisfying z⊤[f(x)f(x)⊤∣x∈A]z=0z E[f(x)f(x) x∈ A]z=0, it holds that ∫ab(f(x)⊤z)2ϕ(xσ)x=0. _a^b(f(x) z)^2φ ( xσ )dx=0. This further implies that the polynomial Tz(x)=∑k=0d−1zkxk=0 a.s. on the event x∈A, T_z(x)= _k=0^d-1z_kx^k=0 a.s. on the event x∈ A, where zkz_k is the k-th element of z. However, Tz(x)T_z(x) is a polynomial of degree d−1d-1, and is 0 on a set of non-zero measure if and only if z=0z=0. ∎ Proof of Lemma 2. Notice that, due to Lemma 1, [ξi(t)ξi(t)⊤δi(t)] [ _i(t) _i(t) _i(t)] = = ℙ(xi(t)∈inti)[ξi(t)ξi(t)⊤∣xi(t)∈inti] (x_i(t)∈ *intX_i)E[ _i(t) _i(t) x_i(t)∈ *intX_i] = = ℙ(pi(t)∈i)[ξi(t)ξi(t)⊤∣pi(t)∈i], (p_i(t) _i)E[ _i(t) _i(t) p_i(t) _i], so it is sufficient to prove [ξi(t)ξi(t)⊤∣pi(t)∈i]≻0E[ _i(t) _i(t) p_i(t) _i] 0. First, for the vector-valued map f(x)=(1,x,…,xd−1)⊤f(x)=(1,x,…,x^d-1) , it holds that ξi(t)=∇Φi(xi(t))=D1f(xi(t)) _i(t)=∇ _i(x_i(t))=D_1f(x_i(t)), where D1=diag(1,2,…,d)D_1=diag(1,2,…,d). Second, on the event that pi(t)∈ip_i(t) _i, Lemma 1 guarantees that xi(t)=hi(pi(t))x_i(t)=h_i(p_i(t)) for an hi∈1h_i ^1. By the mean value theorem, there exists wi∈(0,pi(t))w_i∈(0,p_i(t)) such that xi(t)=h(0)+hi′(wi)pi(t)x_i(t)=h(0)+h _i(w_i)p_i(t). By the binomial theorem on f(xi(t))f(x_i(t)), we have f(xi(t))f(xi(t))⊤ f(x_i(t))f(x_i(t)) = = Π(hi(0))f(hi′(wi)pi(t))f(hi′(wi)pi(t))⊤Π(hi(0))⊤ (h_i(0) )f (h _i(w_i)p_i(t) )f (h _i(w_i)p_i(t) ) (h_i(0) ) = = Π(hi(0))D2f(pi(t))f(pi(t))⊤D2Π(hi(0))⊤, (h_i(0) )D_2f (p_i(t) )f (p_i(t) ) D_2 (h_i(0) ) , where D2=diag(1,hi′(wi),…,hi′(wi)d−1)D_2=diag(1,h _i(w_i),…,h_i (w_i)^d-1), and Π(x)∈ℝd×d (x) ^d× d is a nonsingular lower-triangular matrix. Taking the expectation and using Lemma 3, the result follows. ∎ VI-B Proof of Theorem 2 Proof. By the compactness of iX_i, ‖ξi(t)‖2\| _i(t)\|_2 is bounded and ‖ξi(t)‖2<∞E\| _i(t)\|_2<∞. Define the matrix M=[ξi(t)ξi(t)⊤δi(t)]M=E[ _i(t) _i(t) _i(t)], where M≻0M 0 due to Lemma 2. By the strong law of large numbers t−1Σi(t)−1=t−1∑τ=1tξi(t)ξi(t)⊤δi(t)⟶a.s.M. t^-1 _i(t)^-1=t^-1 _τ=1^t _i(t) _i(t) _i(t) a.s. M. Applying Weyl’s inequality, it holds that |t−1λmin(Σi(t)−1)−λmin(M)|≤‖t−1Σi(t)−1−M‖2,|t^-1 _ ( _i(t)^-1)- _ (M)|≤\|t^-1 _i(t)^-1-M\|_2, which in turn implies t−1λmin(Σi(t)−1)⟶a.s.λmin(M)t^-1 _ ( _i(t)^-1) a.s. _min(M), and hence, λi(t)=Θ(t) _i(t)= (t) a.s. ∎ VI-C Proof of Theorem 3 For each i∈[n]i∈[n] and t, consider a schedule τi(k)k≥1\ _i(k)\_k≥ 1, σi(k)k≥1\ _i(k)\_k≥ 1 according to (13). Let Ki,t=supk:τi(k)≤tK_i,t= \k: _i(k)≤ t\. By definition, it holds that τi(Ki,t)≤t<τi(Ki,t+1) _i(K_i,t)≤ t< _i(K_i,t+1), for any t. Define #i(t)\#_i(t) to be the total number of exploration samples up to time t, that is, #i(t)=∑k=1Ki,t−1(τi(k+1)−σi(k))+max0,t−σi(Ki,t).\#_i(t)= _k=1^K_i,t-1( _i(k+1)- _i(k))+ \0,t- _i(K_i,t)\. Lemma 4. Suppose Assumptions 2 and 3 hold. For every i∈[n]i∈[n], Algorithm 1 guarantees that λi(t)=Θ(A(t)) _i(t)= (A(t)) a.s., and #i(t)=O(A(t))\#_i(t)=O(A(t)) a.s. Proof. We will denote λi(t)=λmin(Σi(t)−1) _i(t)= _ ( _i(t)^-1) and tri(t)=tr(Σi(t))tr_i(t)=tr( _i(t)). The proof holds for each i∈[n]i∈[n], so we omit the subscript i to ease notation. Notice that limt→∞#(t)=∞ _t→∞\#(t)=∞ a.s., otherwise, there would exist some t0t_0 such that tr(t0)≤A(t)−1tr(t_0)≤ A(t)^-1 for all t≥t0t≥ t_0, which contradicts the monotonicity of A(t)A(t). Denote by ℐ(t)I(t) the times up to t that belong to exploration phases, hence |ℐ(t)|=#(t)|I(t)|=\#(t). The subsequence of incentives satisfies that p(τ)τ∈ℐ(t)=ϵ(τ)τ∈ℐ(t)\p(τ)\_τ (t)=\ε(τ)\_τ (t), where ϵ(τ)τ∈ℐ(t)\ε(τ)\_τ (t) is an i.i.d. sequence of Gaussian noise. To see this, we can consider an auxiliary noise sequence μ(k)k≥1\μ(k)\_k≥ 1, where μ(k)μ(k) has the same distribution as ϵ(t)ε(t), i.e., μ(k)∼(0,σ2)μ(k) (0,σ^2). When τ∈ℐ(t)τ (t), sampling the probing noise ϵ(τ)ε(τ) is equivalent to sampling from the process μ(k)\μ(k)\ with ϵ(τ)=μ(#(τ))ε(τ)=μ(\#(τ)). Therefore, ϵ(τ)τ∈ℐ(t)=μ(k)k=1#(t)\ε(τ)\_τ (t)=\μ(k)\_k=1^\#(t) is an i.i.d. probing sequence. By Theorem 2, there exists some constant c>0c>0 such that limt→∞1#(t)λmin(∑τ∈ℐ(t)ξ(τ)ξ(τ)⊤δ(τ))=c, a.s. _t→∞ 1\#(t) _ ( _τ (t)ξ(τ)ξ(τ) δ(τ) )=c, a.s. Σi(τ)−1 _i(τ)^-1 is only updated in Algorithm 1 when τ∈ℐ(t)τ (t), so ∑τ∈ℐ(t)ξ(τ)ξ(τ)⊤δ(τ)=Σi(t)−1 _τ (t)ξ(τ)ξ(τ) δ(τ)= _i(t)^-1. Therefore, for any ϵ>0ε>0, there exists some tϵ>0t_ε>0 such that (c−ϵ)#(t)≤λ(t)≤(c+ϵ)#(t),∀t≥tϵ.(c-ε)\#(t)≤λ(t)≤(c+ε)\#(t), ∀ t≥ t_ε. (14) Denote c−=c−ϵc^-=c-ε, and c+=c+ϵc^+=c+ε. Moreover, denote B=maxx∈‖∇Φ(x)‖2B= _x \|∇ (x)\|^2, such that for all t λ(t+1) λ(t+1) ≤λ(t)+λmax(ξ(t)ξ(t)⊤)≤λ(t)+B. ≤λ(t)+ _max(ξ(t)ξ(t) )≤λ(t)+B. (15) Finally, by (13), there exists some t0>0t_0>0 such that λ(t)≥A(t), λ(t)≥ A(t), ∀t≥t0:τ(Kt)≤t<σ(Kt), ∀ t≥ t_0:\ τ(K_t)≤ t<σ(K_t), (16) λ(t)≤dA(t), λ(t)≤ dA(t), ∀t≥t0:σ(Kt)≤t<τ(Kt+1), ∀ t≥ t_0:\ σ(K_t)≤ t<τ(K_t+1), where d is the dimension of the codomain of Φ in (2). Observe that (15)-(16) ensure λ(t)=O(A(t))λ(t)=O(A(t)). Specifically, 1. when σ(Kt)≤t<τ(Kt+1)σ(K_t)≤ t<τ(K_t+1), it holds λ(t)≤dA(t)λ(t)≤ dA(t); 2. when t=τ(Kt)t=τ(K_t), by (15) and (16), λ(t)≤λ(t−1)+B≤dA(t−1)+B;λ(t)≤λ(t-1)+B≤ dA(t-1)+B; 3. when τ(Kt)<t<σ(Kt)τ(K_t)<t<σ(K_t), by (15), λ(t)=λ(τ(Kt)) λ(t)=λ(τ(K_t)) ≤dA(τ(Kt)−1)+B ≤ dA(τ(K_t)-1)+B ≤dA(t−1)+B. ≤ dA(t-1)+B. Moreover, (14)-(16) ensure λ(t)=Ω(A(t))λ(t)= (A(t)) a.s., because 1. when τ(Kt)≤t<σ(Kt)τ(K_t)≤ t<σ(K_t), λ(t)≥A(t)λ(t)≥ A(t) due to (16); 2. when σ(Kt)≤t<τ(Kt+1)σ(K_t)≤ t<τ(K_t+1), by (14) we have, with probability one, λ(t) λ(t) ≥c−(#(σ(Kt)−1)+t−σ(Kt)+1) ≥ c^- (\#(σ(K_t)-1)+t-σ(K_t)+1 ) ≥c−c+(λ(σ(Kt)−1)+c+(t−σ(Kt)+1)) ≥ c^-c^+ (λ(σ(K_t)-1)+c^+(t-σ(K_t)+1) ) ≥c−c+(A(σ(Kt)−1)+c+(t−σ(Kt)+1)). ≥ c^-c^+ (A(σ(K_t)-1)+c^+(t-σ(K_t)+1) ). Algorithm 1 selects A(t)=o(t)A(t)=o(t), so the second term grows strictly faster than A(t)A(t). Therefore, it holds that λ(t)≥minc−c+,c+⋅A(t)λ(t)≥ \ c^-c^+,c^+\· A(t), and λ(t)=Ω(A(t))λ(t)= (A(t)) a.s. We conclude that λ(t)=Θ(A(t))λ(t)= (A(t)) a.s., and the upper bound on the growth of #(t)\#(t) follows from (14). ∎ Proof of Theorem 3. By Lemma 4, λi(t)=Θ(A(t)) _i(t)= (A(t)) a.s. for each i∈[n]i∈[n]. Then, by Theorem 1, ‖θ^i(t)−θi∗‖22=O(logtλi(t))=O(logtA(t))=O(t−γ), a.s.\| θ_i(t)- _i^*\|_2^2=O ( t _i(t) )=O ( tA(t) )=O(t^-γ), a.s. The system planner’s regret is Rt=∑i∈[n]∑ℓ=1t|xi(ℓ)−xi,des|2.R_t= _i∈[n] _ =1^t|x_i( )-x_i, des|^2. For any i∈[n]i∈[n], observe that ∑ℓ=1t|xi(ℓ)−xi,des|2≤ _ =1^t|x_i( )-x_i, des|^2≤ ∑k=1Ki,t(∑ℓ=τi(k)σi(k)−1|xi(ℓ)−xi,des|2 _k=1^K_i,t ( _ = _i(k) _i(k)-1|x_i( )-x_i, des|^2 (i) +∑ℓ=σi(k)τi(k+1)−1|xi(ℓ)−xi,des|2). + _ = _i(k) _i(k+1)-1|x_i( )-x_i, des|^2 ). (ii) We consider each of the RHS terms above separately. First, term (ii)(i) satisfies (ii)≤C∑k=1Ki,t∑ℓ=σi(k)τi(k+1)−11=O(#i(t))=O(tγlogt) a.s., (i)≤ C _k=1^K_i,t _ = _i(k) _i(k+1)-1\!\!1=O(\#_i(t))=O(t^γ t) a.s., where C=maxx∈i|x−xi,des|2C= _x _i|x-x_i, des|^2, and the last step follows from Lemma 4. Second, term (i)(i) satisfies ∑k=1Ki,t∑ℓ=τi(k)σi(k)−1|xi(ℓ)−xi,des|2≤1mi2∑k=1Ki,t∑ℓ=τi(k)σi(k)−1|pi(ℓ)−pi,des|2 _k=1^K_i,t _ = _i(k) _i(k)-1\!\!|x_i( )-x_i, des|^2≤ 1m_i^2 _k=1^K_i,t _ = _i(k) _i(k)-1\!\!|p_i( )-p_i, des|^2 ≤‖∇Φ(xi,des)‖22mi2∑k=1Ki,t∑ℓ=τi(k)σi(k)−1‖θ^i(ℓ)−θi∗‖22. ≤ \|∇ (x_i, des)\|_2^2m_i^2 _k=1^K_i,t _ = _i(k) _i(k)-1\!\!\| θ_i( )- _i^*\|_2^2. We have established that ‖θ^i(ℓ)−θi∗‖22=O(ℓ−γ)\| θ_i( )- _i^*\|_2^2=O( ^-γ) a.s., hence ∑ℓ=1t‖θ^i(ℓ)−θi∗‖22=O(t1−γ) _ =1^t\| θ_i( )- _i^*\|_2^2=O(t^1-γ) a.s. For all γ∈[23,1)γ∈[ 23,1), observe that term (ii)(i) increases faster than term (i)(i), and it follows that Rt=O(tγlogt)R_t=O(t^γ t) a.s. ∎ VII Concluding Remarks This work introduces the Regret-Minimizing Adaptive Incentive Design (RAID) problem, a unified framework for type identification and control in adaptive incentive design. Our first contribution is the design of a switching incentive policy that alternates between probing (exploration) and estimate-based (exploitation) incentives. We prove that this policy asymptotically minimizes the planner’s average t-stage regret almost surely. Our second contribution is to establish the strong consistency of the type estimator under a weak excitation condition for least-squares estimation, thereby relaxing the standard persistence-of-excitation assumptions used in adaptive incentive design. Throughout this paper, we have also identified two directions for future extensions of the RAID framework. First, and most significant, is to relax the decoupled-costs assumption in the nominal cost structure of (1), and generalize RAID to settings with multi-agent interactions among participants. Second, we aim to pursue a formal treatment of the Error-in-Variables problem that arises in regression (8) when the observation noise is not independent of the agents’ responses. References