Paper deep dive
Adaptive Incentive Design in Dynamic Principal-Agent Problem via Kernelized Bandits
Arghya Mallick, Anuj S. Vora, Sergio Grammatico, Peyman Mohajerin Esfahani
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/19/2026, 3:46:51 AM
Summary
This paper addresses the dynamic principal-agent problem under asymmetric information by introducing a stochastic utility model for the agent to resolve the discontinuity of the principal's expected utility found in deterministic models. The authors propose a Heteroscedastic GP-UCB algorithm using a Neural Network (Arcsin) kernel to solve the resulting structured multi-armed bandit problem. They prove a high-probability cumulative regret bound of O(sqrt(T)(log T)^(m+1)) and demonstrate the framework's efficacy in Vehicle-to-Grid (V2G) incentive design, showing superior economic performance for grid aggregators.
Entities (14)
Relation Signals (10)
Peyman Mohajerin Esfahani → affiliatedwith → University of Toronto
confidence 95% · Peyman Mohajerin Esfahani is with the University of Toronto, Toronto, Canada.
Arghya Mallick → affiliatedwith → Delft University of Technology
confidence 95% · Arghya Mallick, and Sergio Grammatico are with Delft Center for Systems and Control, Delft University of Technology
Sergio Grammatico → affiliatedwith → Delft University of Technology
confidence 95% · Arghya Mallick, and Sergio Grammatico are with Delft Center for Systems and Control, Delft University of Technology
Anuj S. Vora → affiliatedwith → Jio Institute
confidence 95% · Anuj S. Vora is with Jio Institute, Navi Mumbai, India.
Principal-Agent Problem → appliedto → Vehicle-to-Grid (V2G)
confidence 95% · demonstrate the practical efficacy of our theoretical framework by formulating the Vehicle-to-Grid (V2G) incentive design problem, proving its equivalence to a dynamic principal-agent problem
Heteroscedastic GP-UCB → solves → Principal-Agent Problem
confidence 95% · We propose a Heteroscedastic GP-UCB algorithm... to address this limitation... formulate the interaction as a structured multi-armed bandit problem
Heteroscedastic GP-UCB → uses → Arcsin Kernel
confidence 95% · We propose a Heteroscedastic GP-UCB algorithm that utilizes a Neural Network (Arcsin) kernel
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We consider the dynamic principal-agent problem under asymmetric information, wherein a principal sequentially designs contracts to incentivize an agent with unknown preferences and hidden actions. A fundamental bottleneck in the existing literature is the assumption of deterministic agent utility, which renders the principal's expected utility discontinuous and forces computationally intractable discretizations of the contract space. In this paper, we address this limitation by introducing a stochastic counterpart into the agent's utility model, capturing the inherent physical and behavioral variations in realistic subsystems. We formally prove that this stochastic formulation restores the continuity of the principal's expected utility. Leveraging this continuous geometric structure, we formulate the interaction as a structured multi-armed bandit problem subject to heteroscedastic noise. We propose a \texttt{Heteroscedastic GP-UCB} algorithm that utilizes a Neural Network (Arcsin) kernel, chosen to capture the non-stationary, sigmoidal geometry of the utility landscape. For an $m$-dimensional compact contract space, we establish a high-probability cumulative regret bound of $O\left(\sqrt{T}(\log T)^{m+1}\right)$. Finally, we demonstrate the practical efficacy of our theoretical framework by formulating the Vehicle-to-Grid (V2G) incentive design problem, proving its equivalence to a dynamic principal-agent problem, and showing superior economic performance for grid aggregators.
Tags
Links
- Source: https://arxiv.org/abs/2608.17614v1
- Canonical: https://arxiv.org/abs/2608.17614v1
Trouble viewing inline? Open PDF directly →
Full Text
87,316 characters extracted from source content.
Expand or collapse full text
Adaptive Incentive Design in Dynamic Principal-Agent Problem via Kernelized BanditsThanks: This work was partly funded by EU project DriVe2X (grant no. 101056934), and the ERC project TRUST (grant no. 949796). Arghya Mallick, and Sergio Grammatico are with Delft Center for Systems and Control, Delft University of Technology, Delft, The Netherlands. Email: A.Mallick, s.grammatico@tudelft.nl; Anuj S. Vora is with Jio Institute, Navi Mumbai, India. Email: anuj.vora@jioinstitute.edu.in; Peyman Mohajerin Esfahani is with the University of Toronto, Toronto, Canada. Email: P.MohajerinEsfahani@utoronto.ca Arghya Mallick, Anuj S. Vora, Sergio Grammatico, and Peyman Mohajerin Esfahani Abstract. We consider the dynamic principal-agent problem under asymmetric information, wherein a principal sequentially designs contracts to incentivize an agent with unknown preferences and hidden actions. A fundamental bottleneck in the existing literature is the assumption of deterministic agent utility, which renders the principal’s expected utility discontinuous and forces computationally intractable discretizations of the contract space. In this paper, we address this limitation by introducing a stochastic counterpart into the agent’s utility model, capturing the inherent physical and behavioral variations in realistic subsystems. We formally prove that this stochastic formulation restores the continuity of the principal’s expected utility. Leveraging this continuous geometric structure, we formulate the interaction as a structured multi-armed bandit problem subject to heteroscedastic noise. We propose a Heteroscedastic GP-UCB algorithm that utilizes a Neural Network (Arcsin) kernel, chosen to capture the non-stationary, sigmoidal geometry of the utility landscape. For an m-dimensional compact contract space, we establish a high-probability cumulative regret bound of (T(logT)m+1)O ( T( T)^m+1 ). Finally, we demonstrate the practical efficacy of our theoretical framework by formulating the Vehicle-to-Grid (V2G) incentive design problem, proving its equivalence to a dynamic principal-agent problem, and showing superior economic performance for grid aggregators. 1. Introduction We study the classical principal-agent problem [21] in a dynamic setting. The broader significance of this problem—underscored by the 2016 Nobel Memorial Prize in Economic Sciences [37]—lies in its ability to model asymmetric information. Specifically, a principal sequentially designs contracts to incentivize a strategic agent whose actions are hidden (unobservable to the principal) but stochastically govern the task outcome and, consequently, the principal’s payoff. Within the control community, such incentive design has historically been investigated through the lens of Stackelberg games [17, 16, 24], addressing applications ranging from demand response [40] to network congestion [5]. While recent works have made rich theoretical strides in adaptive incentive design [33, 29, 24], they frequently rely on restrictive assumptions that deviate from the classical setting. For instance, the approaches in [33] and [24] propose no-regret learning algorithms for dynamic Stackelberg games, but fundamentally assume that the leader (principal) can directly observe the follower’s (agent’s) actions at each round, or that the follower’s utility is linearly parameterized. In contrast to these idealized assumptions, we preserve the structural integrity of the original principal-agent problem, specifically the core challenge of the agent’s unobservable actions (known as moral hazard). To navigate this, we cast the dynamic contract design problem as a structured multi-armed bandit problem [31, 9]. Bandit frameworks naturally accommodate sequential decision-making under partial feedback among the principal, the agent, and the environment [2, 42, 39, 27]. Recently, bandit-based algorithms have made foundational contributions to automated contract design on modern crowdsourcing platforms, such as Amazon Mechanical Turk [15, 14]. Beyond digital markets, this adaptive framework holds immense potential for decentralized cyber-physical systems, most notably Vehicle-to-Grid (V2G) technology [26]. V2G enables electric vehicles (EVs) to act as distributed energy storage, providing critical balancing services to the power grid. However, while the physical infrastructure is increasingly mature [7], widespread adoption is severely bottlenecked by misaligned economic incentives and unobservable user costs [36]. Motivated by these research gaps, we focus on developing computationally efficient algorithms while modeling a principal-agent-compatible incentive framework for the end users of ‘V2G’ technology. Formally, in each round t, the principal posts a contract xt∈:=[0,1]mx_t :=[0,1]^m, that specifies an incentive payment (xt)i(x_t)_i for the i-th outcome of the task, with i∈[m]:=1,…mi∈[m]:=\1,… m\. An agent observes the contract, takes an action at⋆∈a _t , and the outcome of the task is realized. The uncoupled utility (or payoff) function of the principal is UP:×→ℝU^P:X×A and the utility function of the agent is UA:×→ℝU^A:X×A . We assume the agent is rational and always takes an action that maximizes its utility UAU^A. For simplicity, dropping the time t as a subscript, we compactly formulate the problem as (1a) a⋆(x) a (x) :=argmaxa∈UA(x,a), := _a U^A(x,a), (1b) x⋆ x :=argmaxx∈UPA(x):=UP(x,a⋆(x)), := _x \; \U^PA(x):=U^P\! (x,a (x) ) \, where a⋆(x)a (x) is the best response of the agent against the contract x, UPA:→ℝU^PA:X is the principal’s utility with embedded best response of the agent, and x⋆x denotes the optimal contract. The main technical challenge is that the principal does not explicitly know UPAU^PA because of the agent’s hidden action a⋆a . Our goal is to learn x⋆x via online random feedback from the principal’s utility UPAU^PA. To quantify the sub-optimality of the principal’s strategy in this sequential interaction, we use the traditional notion of cumulative regret as (2) RT:=T⋅UPA(x⋆)−∑t=1TUPA(xt), R_T:=T· U^PA(x )- _t=1^TU^PA(x_t), where x⋆x is as defined in (1b). We are interested in designing an algorithm to propose a sequence of xtt≤T\x_t\_t≤ T using the available feedback information from the environment so that we ensure the upper bound of RTR_T grows sub-linearly in T. 1.1. Related literature Computational Contract Design. While the principal-agent problem is rooted in economic theory [19], recent literature has focused on its computational aspects. Authors in [3] establish that computing optimal contracts in combinatorial settings is NP-hard in general. Hence, research shifted towards identifying robust, simple contract structures, such as linear contracts [11], which provide approximation guarantees in static environments. However, these works assume that the principal has full knowledge of the agent’s type and payoff function, an assumption that rarely holds in practice. Learning Contracts with Bandit Feedback. In the repeated principal-agent setting, the problem is modeled as a multi-armed bandit with a finite number of arms. Authors in [15] pioneer this direction with the Agnostic Zooming algorithm. Their approach relies on adaptively discretizing the contract space; however, the analysis necessitates strong regularity assumptions, specifically that contracts are monotone and outcomes satisfy first-order stochastic dominance. Authors in [41] relaxed these conditions, offering guarantees for general utility functions. More recently, authors in [4] proposed the Discover and Cover algorithm to address the problem with finite agent actions. While this approach avoids the geometric assumptions of earlier works, it suffers from the curse of dimensionality, as the complexity scales exponentially with the number of agent actions. Continuity of principal’s utility. The principal’s expected utility UPAU^PA is inherently discontinuous, formally characterized by [37] as a piecewise-affine function with sharp transitions. Prior dynamic algorithms [15, 41] treat this discontinuity as an obstacle that requires inefficient contract-space discretization. In contrast, our work introduces a stochastic utility framework that smooths out these discontinuities, enabling the application of kernelized bandits [8] directly in the continuous domain. Figure 1. Schematic of principal-agent feedback model (1). 1.2. Contributions (i) Modeling: Resolving discontinuity of UPAU^PA. We identify that the discontinuity of the principal’s utility UPAU^PA, a persistent barrier in dynamic contract design, stems from the idealized assumption of deterministic agent utilities. By incorporating a stochastic counterpart into the agent’s utility function (capturing unmodeled physical transients and behavioral fluctuations), we prove that the principal’s expected utility U~PA U^PA becomes continuous over its domain (Theorem 3.4). This modeling shift provides a more realistic representation of the problem and fundamentally resolves the need for the intractable discretization relied upon by existing state-of-the-art methods [4, 15, 41]. (i) Algorithm: Sub-linear regret via tailored kernel. Leveraging the continuity result of U~PA U^PA, we propose the Heteroscedastic GP-UCB algorithm paired with a Neural Network kernel, specifically chosen to capture the non-stationary, sigmoidal geometry of U~PA U^PA. By bounding the eigenvalue tail sum of this specific kernel (Proposition 4.4), we establish a formal high-probability regret bound of: ℙ[R~T≤(T(logT)m+1)]≥1−δP [ R_T ( T( T)^m+1 ) ]≥ 1-δ (Theorem 4.5), where m denotes the dimension of contract space X, and δ>0δ>0 is the confidence level. (i) Application: V2G incentive design. Finally, we demonstrate the practical relevance of our framework by addressing the Vehicle-to-Grid (V2G) incentive design problem. We formulate a smart-charging scheme where aggregators incentivize electric vehicle owners to provide ancillary services. We prove (Proposition 5.2) that this complex engineering problem, governed by stochastic battery dynamics and user preferences, formally reduces to a dynamic principal-agent formulation. It is noteworthy to mention that our proposed algorithm overcomes the best-known regret bound of the prior work [4] (i.e., RT≤(mnT4/5logT)R_T (m^nT^4/5 T)) by improving the original principal-agent problem formulation (i.e., from UPAU^PA to U~PA U^PA). We do not claim any improvement on RTR_T for the original (deterministic) problem formulation. Moreover, while RTR_T of [4] scales exponentially with the number of actions of the agent (i.e., mnm^n), the regret bound of our work (i.e., R~T R_T) entirely eliminates this exponential dependence on n, where n and m denote the number of actions of the agent and the number of outcomes, respectively. In a nutshell, our methodology establishes that adopting a more realistic system model enables a faster learning rate. 2. Principal-Agent Feedback Model Building on the introduction, we now discuss the principal-agent model’s formulation in detail. After the agent executes the best response following (1a), an outcome i∈[m]i∈[m] of the task is realized. The value for any outcome i∈[m]i∈[m] for the principal is denoted by (v)i∈[0,1](v)_i∈[0,1] and is known to the principal. Moreover, the outcome of a task is realized following a conditional probability distribution defined by the production function p:→Δmp:A→ _m, where Δm _m is the probability simplex over m outcomes. We define agents’ and principals’ utilities, respectively, (3a) UA(x,a)=∑i∈[m](x)ipi(a)−c(a), U^A(x,a)= _i∈[m](x)_i\;p_i(a)-c(a), (3b) UP(x,a)=∑i∈[m](v−x)ipi(a), U^P(x,a)= _i∈[m](v-x)_i\;p_i(a), where pi(a)p_i(a) is the probability of the i-th outcome conditional on action a, and c:→ℝc:A denotes the cost function of taking actions by the agent. As stated previously, a⋆(x)a (x) is not observable to the principal; however, the principal observes the following random reward conditioned on a⋆(x)a (x): (4) y=(v−x)i,with the random index’s lawi∼p(a⋆(x)). y=(v-x)_i,\;with the random index's law\;i p(a (x)). A schematic of the principal-agent model described in (1)-(4) is shown in Figure 1. We now discuss state-of-the-art methods for addressing the principal-agent problem. Furthermore, we analyze the key technical challenges faced by existing solution approaches. 2.1. State-of-the-art results Authors in [15] propose an adaptive algorithm called Agnostic Zooming for this problem. Their algorithm provides the following upper bound on regret: RT(Xcand)≤(αlogT)Tm+1m+2R_T(X_cand) (α T)T m+1m+2, where Xcand⊂[0,1]mX_cand⊂[0,1]^m represents the set of monotone contracts. In addition, they also assume first order stochastic dominance of contracts, which makes their regret bound to be less attractive. Authors in [41] recently proposed an algorithm where they lifted the monotonicity and first order stochastic dominance assumptions of [15]. They provide the upper bound of the regret in expectation as RT≤(mlog(T)T2m2m+1)R_T ( m (T)T 2m2m+1). However, their proposed algorithm cannot be implemented in reality. In fact, one of the steps in their algorithm requires X to be discretized using certain methods from spherical coding in information theory, which remains an open problem to date (Section 3.13.1 of [41]). Recently, Authors in [4] propose an algorithm considering A is finite. They provide a probabilistic regret bound ℙ[RT≤(mnℐlog(T)T4/5)]≥1−δ,P [R_T (m^nI (T)T^4/5) ]≥ 1-δ, where ℐI depends on m,nm,n polynomially, and n is the number of actions available to agent. Here, the constants deteriorate performance significantly as m and n increase. This algorithm requires the private parameter n. Apart from the main results above, the survey [10] presents other weaker results on the computational aspects of contracts. 2.2. Main technical challenges Assuming A is finite, the authors in [37] establish that the principal’s utility function UPAU^PA in (1b) is a piecewise affine function; it can be discontinuous on the boundary of linear pieces, and the global optimal contract is on the boundary of a linear piece. Let us first understand why UPAU^PA is discontinuous on its domain with the help of a simple example. Our understanding of the root cause of this technical challenge will eventually help us to resolve it in later sections. Assuming A is finite, the utility for an agent is UA(x,a)=⟨x,p(a)⟩−c(a),U^A(x,a)= x,p(a) -c(a), where a∈:=a1,a2,…,ana :=\a_1,a_2,…,a_n\. For a fixed contract x, the objective function UAU^A admits multiple optimizers only if x lies on an indifference hyperplane between distinct actions aia_i and aja_j, defined as Hi,j:=x∈∣UA(x,ai)=UA(x,aj).H_i,j:= \x U^A(x,a_i)=U^A(x,a_j) \. Consider a contract x∈Hi,jx∈ H_i,j such that the optimal action set is restricted to the pair ai,aj\a_i,a_j\, meaning UA(x,ai)=UA(x,aj)>UA(x,ak)U^A(x,a_i)=U^A(x,a_j)>U^A(x,a_k) for all k∉i,jk∉\i,j\. If p(ai)≠p(aj)p(a_i)≠ p(a_j), then the principal’s utility UPAU^PA exhibits a discontinuity across the hyperplane Hi,jH_i,j. Letting hi,j(x):=UA(x,ai)−UA(x,aj)h_i,j(x):=U^A(x,a_i)-U^A(x,a_j) denote the affine function defining the boundary, the function UPAU^PA takes the following piecewise form in the local neighborhood of x: (5) UPA(x) U^PA(x) =⟨(v−x),p(a⋆(x))⟩+⟨(v−x),p(aj)⟩,if hi,j(x)<0,⟨(v−x),p(ai)⟩,if hi,j(x)>0. = (v-x),p(a (x)) + cases (v-x),p(a_j) ,&if h_i,j(x)<0,\\[2.0pt] (v-x),p(a_i) ,&if h_i,j(x)>0. cases Note that X is partitioned by at most n(n−1)2 n(n-1)2 such discontinuous hyperplanes, corresponding to n actions of the agent. Let us now construct an instance of the so-called ‘High-low example’ [15] to empirically visualize the landscape of UPAU^PA. Example 2.1 (High-low case study). The principal posts a contract x∈[0,1]2x∈[0,1]^2 with two outcomes (low and high), and the agent takes action a∈al(low effort),a∈\a^l(low effort), ah(high effort)a^h(high effort)\ with corresponding private costs c(al),c(ah)c(a^l),c(a^h), respectively. Low and high outcomes bring respective values v=[vl,vh]⊤v=[v^l,v^h] to the principal. To empirically construct UPAU^PA, we consider p(al)=[0.9,0.1],p(ah)=[0.1,0.9],c(al)=0,c(ah)=0.3p(a^l)=[0.9,0.1],\>p(a^h)=[0.1,0.9],\>c(a^l)=0,\>c(a^h)=0.3, and v=[0.1,0.8]⊤v=[0.1,0.8] . Then we discretize [0,1]2[0,1]^2 with (1000×1000)(1000× 1000) data points and sample each data point 10001000 times to empirically approximate UPAU^PA. Figure 2(a) illustrates the geometry of the empirically constructed UPAU^PA. The x-axis represents contract (x)1(x)_1 for low outcome, and the y-axis denotes (x)2(x)_2 for high outcome. Unsurprisingly, we find it to be discontinuous between two affine pieces. (a) (b) (c) Figure 2. (High-low example 2.1) (a) Visualization of UPAU^PA. (b) Visualization of the variance of heteroscedastic noise σε2σ^2_ . (c) Geometry of U~PA U^PA under the Assumption 3.1. The second technical challenge is the decision-variable-dependent randomness in the principal’s reward structure. At round t, we can rewrite the principal’s reward in (4) in the following form: yt y_t =(v−xt)i,i∼p(a⋆(xt)), =(v-x_t)_i, i p(a (x_t)), (6) =∑j∈[m](v−xt)jpj(a⋆(xt))+ε(xt)=UPA(xt)+ε(xt), = _j∈[m](v-x_t)_jp_j(a (x_t))+ (x_t)=U^PA(x_t)+ (x_t), where ε(xt) (x_t) is the zero-mean heteroscedastic noise with variance ar[ε(xt)]=∑j∈[m]pj(a⋆(xt))[(v−xt)j−UPA(xt)]2Var[ (x_t)]= _j∈[m]p_j(a (x_t))[(v-x_t)_j-U^PA(x_t)]^2. Unlike homoscedastic models, the noise variance here depends on xtx_t and is unknown to the decision maker. Figure 2(b) illustrates this input-dependent variance, σε2σ^2_ , for Example 2.1. 3. Main Result I: Resolving Discontinuity of UPAU^PA Due to the aforementioned challenges, the authors in [4, 15, 41] prefer to discretize the contract space X and deal with a finite number of contracts. Instead, our approach is not to discretize X, but to design algorithms that can work in a continuous contract space, thereby freeing us from the technicality of upper-bounding the discretization error. In this regard, we first make the following improvement to the agent’s utility. Consider an embedding δ:→ℝnδ:A ^n, and an ℝnR^n-valued random variable w. We define the agent’s best response by adding a stochastic counterpart to the agent’s utility function, and update the optimal contract, respectively, (7a) a~⋆(x,w) a (x,w) =argmaxa∈U~A(x,a)=UA(x,a)+⟨w,δ(a)⟩, = _a \ U^A(x,a)=U^A(x,a)+ w,δ(a) \, (7b) x~⋆ x =argmaxx∈U~PA(x)=w[UP(x,a~⋆(x,w))], = _x \ U^PA(x)=E_w[U^P(x, a (x,w))] \, while the random feedback observed by the principal (8) y~ y =(v−x)i,i∼q(x), =(v-x)_i, i q(x), whereqi(x) q_i(x) =w[pi(a~⋆(x,w))]. =E_w [p_i( a (x,w)) ]. Note, the updated production function q(x)q(x) encodes the probability of any realization i∈[m]i∈[m] by marginalizing over randomness related to w. Moreover, the regret in (2) is updated as (9) R~T=TU~P∗−∑t=1TU~PA(xt), R_T=T U^P*- _t=1^T U^PA(x_t), where U~P∗=maxx∈U~PA(x) U^P*= _x \>\> U^PA(x). While the modification in (7a) serves to restore the continuity of the principal’s utility, it fundamentally reflects the inherent uncertainty of real-world agent behavior. In [4, 37], agent utilities are assumed to be static for a fixed x and a. However, in practical settings like a crowdsourcing market, a worker’s cost (effort) fluctuates due to unobserved latent factors such as fatigue, attention shifts, or external interruptions. Therefore, for the same contract and action pair (x,a)(x,a), the agent’s utility could take different values for different instances of time. By introducing stochasticity into the agent’s utility function, we effectively treat the principal’s problem as an optimization over the robust expected behavior of the agent, rather than overfitting to a deterministic model that inherently fails to capture such physical transients. Assumption 3.1 (Stochastic regularity). For the stochastic addition in the best response (7a), we assume the following: (i) One-to-one embedding: For all a1,a2∈a_1,a_2 , there exists a continuous embedding δ:→ℝnδ:A ^n such that δ(a1)≠δ(a2)δ(a_1)≠δ(a_2) if a1≠a2a_1≠ a_2. (i) Full-dimensional support: The random variable w∈ℝnw ^n admits a probability density distribution that is absolutely continuous with respect to Lebesgue measure. In particular, for all v1∈ℝn,v2∈ℝv_1 ^n,v_2 , the probability of any hyperplane is ℙ[w∈ℝn∣⟨v1,w⟩=v2]=0P [w ^n \; v_1,w =v_2 ]=0 (e.g., uniform distribution supported on [0,1]n[0,1]^n). Example 3.2 (Embedding). If A is finite, then it suffices to choose the embedding image (i.e., n=1n=1) as δ(ai)=(i−1)/||δ(a_i)=(i-1)/|A|. If A is a continuous set, a straightforward embedding is the identity map: δ(a)=aδ(a)=a. To visualize an example of the proposed modification, consider UA(x,a)=x−(a4−2a2)U^A(x,a)=x-(a^4-2a^2) for x=0x=0, and Figure 3 depicts how the optimizer a⋆a shifts to a~⋆ a as we add the identity embedding. a⋆a aaUA(x,a)U^A(x,a)a⋆a a~⋆ a aaU~A(x,a) U^A(x,a)w=0.3w=0.3 Figure 3. Left: The agent’s utility UA(x,a)U^A(x,a) with optimizer marked at a⋆a . Right: The modified utility U~A(x,a):=UA(x,a)+⟨w,a⟩ U^A(x,a):=U^A(x,a)+ w,a with a realization w=0.3w=0.3. Angled pointers clearly distinguish the original optimizer a⋆a from the newly shifted optimizer a~⋆ a . We also assume the following standard property for UAU^A and UPU^P. Assumption 3.3 (Compact and continuous domain). The agent’s utility UA:×→ℝU^A:X×A and the uncoupled principal’s utility UP:×→ℝU^P:X×A are continuous on their compact domains X and A. The above assumptions allows us to characterize the following property of the correspondence a~⋆(x,w) a (x,w) in (7a) and the principal’s utility U~PA U^PA. Theorem 3.4 (Continuous principal’s utility). Under Assumptions 3.1 and 3.3, the following holds: (i) The agent’s best response a~⋆(x,w) a (x,w) in (7a) is a singleton and continuous at any x∈x almost surely, i.e., for any x∈x , we have (10) ℙ[ [ w∈Ω∣a~⋆(x,w)issingletonand∀an∈a~⋆(xn,w),limn→∞an=a~⋆(x,w)]=1. w∈ \; a (x,w)\;is\;singleton\;and\;∀ a_n∈ a (x_n,w), _n→∞a_n= a (x,w) ]=1. (i) The principal’s utility U~PA U^PA defined in (7b) is continuous on its domain. Proof. The proof is decomposed into two parts: Part (i)(i). Define the value function V(x,w):=maxa∈UA(x,a)+⟨w,δ(a)⟩.V(x,w):= _a \U^A(x,a)+ w,δ(a) \. Since A is compact and UAU^A is continuous on its domain, V is finite everywhere. Moreover, for a fixed x, V is convex in w as it is the maximum of a family of affine functions. By an extension result from Danskin’s theorem [6], we have ∂wV(x,w)=coδ(a)∣a∈a~⋆(x,w), _wV(x,w)=co \δ(a) a∈ a (x,w) \, where ∂wV(x,w) _wV(x,w) denotes the convex subdifferential of V with respect to w, and co⋅co\·\ denotes the convex hull of its input. Consequently, we have V is differentiable at x and w⟺a~⋆(x,w) is a singleton.V is differentiable at x and w\;\; \;\; a (x,w) is a singleton. From Rademacher’s theorem [12, Section 3.13.1], we know that if the function V is a finite convex function on ℝnR^n, which is the case here, it is differentiable almost everywhere with respect to Lebesgue measure. Therefore, the set N:=w∈ℝn:a~⋆(x,w) is not a singletonN:=\w ^n: a (x,w) is not a singleton\ has Lebesgue measure zero. Because the distribution of w is absolutely continuous with respect to Lebesgue measure (following Assumption 3.1), then (11) ℙ[w∈N]=0⟺ℙ[a~⋆(x,w) is a singleton]=1 [w∈ N]=0 [ a (x,w) is a singleton ]=1 By Assumptions 3.3 and 3.1, (UA(x,a)+⟨w,δ(a)⟩)(U^A(x,a)+ w,δ(a) ) is jointly continuous in x and a, which leads us to apply the celebrated Berge’s maximum theorem [1, Theorem 17.3117.31] on (7a). And we say that the correspondence a~⋆(x,w) a (x,w) is upper-hemicontinuous at x. At the same time, we just proved in (11) that a~⋆(x,w) a (x,w) is unique. Thus, a~⋆(x,w) a (x,w) is continuous on x. Part (ii)(i). For any x∈x , and any convergent sequence of xn→x\x_n\→ x, we have limxn→xU~PA(xn)=limxn→xw[UP(xn,a~⋆(xn,w))] _x_n→ x U^PA(x_n)= _x_n→ xE_w[U^P(x_n, a (x_n,w))] =w[limxn→xUP(xn,a~⋆(xn,w))] =E_w [ _x_n→ xU^P(x_n, a (x_n,w)) ] =w[UP(x,a~⋆(x,w))]=U~PA(x) =E_w [U^P(x, a (x,w)) ]= U^PA(x) where the second equality follows from the Dominated Convergence Theorem [12, Theorem 1.191.19], as the function UPU^P is continuous (Assumption 3.3), and hence uniformly bounded over any compact set. The third equality holds true because of the continuity of a~⋆(x,w) a (x,w) in x as shown in the proof of part (i)(i). This concludes the proof. ∎ It is noteworthy to mention that Theorem 3.4 is built using the abstract formulation in (1), which implies that our result is also applicable to the class of repeated Stackelberg games [24]. Any other utility structure besides the principal-agent model in (3) will follow Theorem 3.4 as long as the necessary assumptions are met. To address the technical challenge of input-dependent randomness in (2.2), we propose a dedicated algorithm in Section 4.2. 4. Main Result I: Tailored Kernel and Sub-linear Regret In this section, we focus on designing an algorithm for the principal-agent model given by (3) and (4). Since the previous work [37] has already established geometric characterizations of the principal’s utility landscape with finite agent actions, we aim to exploit this to achieve a better regret rate. To this end, we restrict the complexity of our problem with the following assumption. Assumption 4.1 (Finite action space). The agent has a finite number of actions, i.e., ||<∞|A|<∞. By Assumption 4.1, a candidate embedding can be δ(aj)=(j−1)/||δ(a_j)=(j-1)/|A| for aj∈a_j , which leads to the agent’s best response a~⋆(x,w)=argmaxaj∈∑i∈[m](x)ipi(aj)−c(aj)+w(j−1)||, a (x,w)= _a_j \ _i∈[m](x)_i\;p_i(a_j)-c(a_j)+ w(j-1)|A| \, and the principal’s utility, U~PA(x)=w[∑i∈[m](v−x)ipi(a~⋆(x,w))] U^PA(x)=E_w [ _i∈[m](v-x)_i\;p_i( a (x,w)) ]. We now visualize U~PA U^PA using Example 2.1 where ||=2|A|=2. Assuming that w∼(0,σw2)w (0, _w^2), Figure 2(c) shows a continuous U~PA U^PA as stated in Theorem 3.4. In this regard, we identify two key observations: (1)(1) the surface of U~PA U^PA consists of flat plateaus and steep transitions (see Figure 2(c) ), and (2)(2) the variance around U~PA U^PA is still decision-variable-dependent as given in (2.2). To address both observations, we consider stochastic bandits [23] over a continuous domain. While parametric bandits [34] assume linear reward structures, akin to the simpler theory of linear contracts, we adopt a nonparametric approach using Gaussian Processes (GPs) to capture the complex structure of the principal’s utility. A GP over the feasibility set =[0,1]mX=[0,1]^m, denoted by GP(μt(⋅),k(⋅,⋅))GP_X( _t(·),k(·,·)), is a collection of random variables (U~PA(x))x∈( U^PA(x))_x , such that every finite sub-collection of random variables (U~PA(xi))i=1n( U^PA(x_i))_i=1^n is jointly Gaussian with mean μt(xi)=[U~PA(xi)] _t(x_i)=E[ U^PA(x_i)] and covariance k(xi,xj)=[(U~PA(xi)−μt(xi))(U~PA(xj)−μt(xj))]k(x_i,x_j)=E[( U^PA(x_i)- _t(x_i))( U^PA(x_j)- _t(x_j))], 1≤i,j≤n,n∈ℕ1≤ i,j≤ n,n . Algorithms use GP(0,k(⋅,⋅))GP_X(0,k(·,·)) as an initial prior distribution for the unknown function U~PA U^PA over X, where k(⋅,⋅)k(·,·) is the kernel associated with a suitable Reproducing Kernel Hilbert Space (RKHS) ℋkH_k. Algorithms such as GP-UCB [35], GP-PI [18], and IGP-UCB [8] leverage GPs by imposing regularity assumptions on the objective function U~PA U^PA: either (1) U~PA U^PA is a sample from a GP prior, or (2) U~PA U^PA resides in the RKHS ℋkH_k of a kernel k. Given the structured geometry of U~PA U^PA, the agnostic RKHS assumption is theoretically more robust than assuming the function is a random draw from a GP. Consequently, the focus is to identify a kernel k whose RKHS ℋkH_k naturally models flat plateaus and steep transitions. 4.1. Kernel design Standard stationary kernels, such as the Gaussian kernel, are ill-suited for this problem as their reliance on a single, global lengthscale fails to adapt to the heterogeneous geometry of U~PA U^PA. While the underlying deterministic utility (UPAU^PA) exhibits distinct affine segments, our stochastic smoothing transforms them into a non-stationary landscape characterized by flat plateaus and steep transitions (Figure 2(c)). To mimic this structure, we employ the Arcsin kernel (aka Neural Network kernel) [38, Section 33], which arises as the limit of a single-hidden-layer Bayesian Neural Network with error function (erf) activation. Unlike stationary kernels, this kernel induces a non-stationary prior inherently designed to model sigmoidal superpositions. This inductive bias allows it to represent the soft thresholding behavior and varying local smoothness of the principal’s expected utility. Consider the input-output mapping of a single-hidden-layer neural network fN:ℝn→ℝf_N:R^n with an activation function ϕ:ℝ→ℝφ:R , defined as (12a) ϕ(z) φ(z) =2π∫0zexp(−t2)t, = 2 π _0^z\; (-t^2)dt, (12b) fN(x) f_N(x) =∑i=1Nςiϕ(⟨ri,x⟩+bi), = _i=1^N _iφ( r_i,x +b_i), where the independent Gaussian priors ςi∼(0,σς2/N) _i (0, _ ^2/N), ri∼(0,σv2)r_i (0, _v^2I), and bi∼(0,σb2)b_i (0, _b^2). The kernel function k(x,y)k(x,y) is derived as the limiting covariance k(x,y) k(x,y) :=limN→∞[fN(x)fN(y)]=σς2zx,zy[ϕ(zx)ϕ(zy)], := _N→∞E[f_N(x)f_N(y)]= _ ^2E_z_x,z_y[φ(z_x)φ(z_y)], where the last equality follows by applying the central limit theorem, zx=⟨r,x⟩+bz_x= r,x +b and zy=⟨r,y⟩+bz_y= r,y +b are jointly Gaussian variables. The expectation in the above equation admits a closed-form solution known as the Neural Network (aka ‘arcsin’) kernel [38], described by (13) k(x,y)=2σς2πarcsin(σv2⟨x,y⟩+σb2(1+σv2⟨x,x⟩+σb2)(1+σv2⟨y,y⟩+σb2)), k(x,y)= 2 _ ^2π ( _v^2 x,y + _b^2 (1+ _v^2 x,x + _b^2)(1+ _v^2 y,y + _b^2) ), where σv2σ^2_v and σb2σ^2_b are treated as hyper-parameters. Apart from being symmetric, the positive definiteness of this kernel is guaranteed by its construction as an expectation of squares, ∑i,jcik(xi,xj)cj=σw2[(∑iciϕ(zxi))2]≥0 _i,jc_ik(x_i,x_j)c_j=σ^2_wE [ ( _ic_iφ(z_x_i) )^2 ]≥ 0. By the Moore-Aronszajn theorem, any symmetric and positive definite kernel on X induces a unique RKHS ℋkH_k defined as ℋk _k :=h∈ℝ∣∃αi∈ℝ,xi∈∀i∈ℕwithh(x)=∑i=1∞αik(xi,x)and∑i=1∞∑j=1∞αik(xi,xj)αj<∞. := \h ^X ∃ _i ,x_i \;∀ i \;with\;h(x)= _i=1^∞ _ik(x_i,x)\;and\; _i=1^∞ _j=1^∞ _ik(x_i,x_j) _j<∞ \. To empirically validate the correct hypothesis space of U~PA U^PA, we run a kernel regression on an instance of ‘High-low’ example (similar to Example 2.1) with k(x,y)k(x,y) in (13). We plot the learned function in Figure 4, which clearly shows the flat plateaus with sigmoidal transitions we were looking for. Therefore, the ℋkH_k induced by k(x,y)k(x,y) in (13) is a candidate hypothesis space for U~PA U^PA. Figure 4. Representative function of U~PA U^PA, which is built with Neural Network kernel using kernel regression where the empirical samples are generated from an instance of ‘High-low’ example 2.1. 4.2. Description of the algorithm First, we develop methods to address the heteroscedastic noise in the principal’s utility, which is denoted as a technical challenge in (2.2). In particular, we learn the unknown variance of this noise using feedback from repeated sampling of the principal’s utility at the same input. A good estimate of the variance helps us obtain a more accurate upper confidence bound for the unknown U~PA U^PA. Then we detail our main algorithm, based on a upper confidence bound-based acquisition function constructed using the Neural Network kernel in (13). To start with, similar to (2.2), we represent the feedback as a noisy version of U~PA U^PA, and write (14) y~t=U~PA(xt)+ε~(xt), y_t= U^PA(x_t)+ (x_t), where ε~(xt) (x_t) is assumed to be a zero-mean heteroscedastic noise with the variance ar(ε~(xt))=∑i∈[m]qi(xt)[(v−xt)i−U~PA(xt)]2Var( (x_t))= _i∈[m]q_i(x_t)[(v-x_t)_i- U^PA(x_t)]^2, and the production function q(xt)q(x_t) is defined in (8). It is straightforward to follow that ar(ε~(xt))Var( (x_t)) is continuous in xtx_t since the continuity of a~⋆(xt,w) a (x_t,w) in xtx_t (Theorem 3.4) makes qi(xt)q_i(x_t) to be continuous on its argument. Here, we first impose the following assumption on ε~(xt) (x_t) to restrict it within a well-defined function class. Assumption 4.2 (Noise function class). The noise variance ar(ε~(xt))Var( (x_t)) belongs to an RKHS induced by some kernel κvκ^v, i.e., ar(ε~(⋅))∈ℋκvVar( (·)) _κ^v with its RKHS norm is upper bounded with Bv>0B_v>0. Such assumptions are quite common when dealing with heteroscedastic noise [20, 30]. To learn ar(ε~(⋅))Var( (·)), we construct a repeated setting, where we collect ℓ>1 >1 samples for each xtx_t and form the feedback collection y~tii=1ℓ\ y_t^i\_i=1 . Then, we evaluate the sample mean and variance of ε~(xt) (x_t) as (15a) y^t y_t =1ℓ∑i=1ℓy~ti=1ℓ∑i=1ℓ(U~PA(xt)+ε~i(xt)), = 1 _i=1 y_t^i= 1 _i=1 ( U^PA(x_t)+ _i(x_t)), (15b) v^t v_t =1ℓ−1∑i=1ℓ(y~ti−y^t)2. = 1 -1 _i=1 ( y_t^i- y_t)^2. While we have random feedback samples of y~t y_t, we represent the randomness of sample variance using a zero-mean noise η(xt)η(x_t). Since (v)i,(x)i∈[0,1](v)_i,(x)_i∈[0,1], it is straightforward to check that the noise ε~(xt) (x_t) is uniformly bounded as |ε~(xt)|<χu| (x_t)|< _u, which leads to its variance function ar(ε~(xt))<χuVar( (x_t))< _u with χu>0 _u>0. And this allows us to further state v^t=ar(ε~(xt))+η(xt) v_t=Var( (x_t))+η(x_t). Moreover, the noise η(xt)η(x_t) adheres to the following standard assumption. Assumption 4.3 (Noise process regularity). The noise η(xt)η(x_t) is ρη(xt) _η(x_t)-sub-Gaussian with known ρη2(xt)ρ^2_η(x_t). Moreover, the process η(xt)t≥1\η(x_t)\_t≥ 1 is generated independently in time. The sub-Gaussianity assumption of η(xt)η(x_t) naturally follows from uniform boundedness of ε~(xt) (x_t). Following a brief introduction of GP models at the start of Section 4, the posterior GP mean (μt(⋅) _t(·)) and variance (σt2(⋅)σ^2_t(·)) of U~PA U^PA are respectively calculated based on the previous measurements y^1:t=[y^1,…y^t]⊤ y_1:t=[ y_1,… y_t] (16) μt(x) _t(x) =kt(x)⊤(Kt+λΣt)−1y^1:t, =k_t(x) (K_t+λ _t)^-1 y_1:t, σt2(x) σ^2_t(x) =1λ(k(x,x)−kt(x)⊤(Kt+λΣt)−1kt(x)), = 1λ(k(x,x)-k_t(x) (K_t+λ _t)^-1k_t(x)), where Σt:=diag(ar(ε~(x1)),…,ar(ε~(xt))) _t:=diag(Var( (x_1)),…,Var( (x_t))), (Kt)i,j=k(xi,xj)(K_t)_i,j=k(x_i,x_j) is an element of the covariance matrix KtK_t, λ>0λ>0 is a parameter trading off the magnitude of prior variance, and kt(x):=[k(x1,x),…,k(xt,x)]⊤k_t(x):=[k(x_1,x),…,k(x_t,x)] . Here, k(xi,xj)k(x_i,x_j) refers to our proposed Neural Network kernel in (13). As Σt _t depends on the unknown variance ar(ε~(xt))Var( (x_t)), we construct a separate GP model to learn it. Since we could not decode any specialized geometry for ε~(⋅) (·), we consider a universal kernel, such as a Gaussian kernel, to define the GP. The corresponding posterior mean μtvμ^v_t and variance σtvσ^v_t are calculated based on (16) by replacing Σt _t with Σtv:=diag[ρη2(x1),…,ρη2(xt)] ^v_t:=diag[ _η^2(x_1),…, _η^2(x_t)], y^1:t y_1:t with v^1:t=[v^1,…,v^t]⊤ v_1:t=[ v_1,…, v_t] , and using Gaussian kernel kv(⋅,⋅)k^v(·,·). Then, we build the upper confidence bound ucbt(⋅)ucb_t(·) as (17) ucbt(x):=μt−1v(x)+βtvσt−1v(x),ucb_t(x):=μ^v_t-1(x)+β^v_tσ^v_t-1(x), where the exploration-exploitation trade-off parameter βtv=2log(det(λΣtv+Ktv)0.5δdet(λΣtv)0.5)+λBvβ^v_t= 2 ( (λ ^v_t+K^v_t)^0.5δ (λ ^v_t)^0.5 )+ λB_v, taken from [20, Lemma 77]. We can approximate Σt _t with the upper confidence bound of ar(ε~(xt))Var( (x_t)) as (18) Σ^t=diag(minucbt(x1),χu,…,minucbt(xt),χu)/ℓ. _t=diag( \ucb_t(x_1), _u\,…, \ucb_t(x_t), _u\)/ . Now we are in a position to define the upper confidence bound-based acquisition function for U~PA U^PA using the current posterior mean μt−1 _t-1 and variance σt−12σ^2_t-1 as (19) xt=argmaxx∈μt−1(x)+βtσt−1(x)⏟Acquisitionfunction,x_t= _x \>\> _t-1(x)+ _t _t-1(x)_Acquisition\;function, where xtx_t is the action of the algorithm to maximize the acquisition function, and the exploitation-exploration trade-off parameter (20) βt=2log(det(λΣ^t+Kt)0.5δdet(λΣ^t)0.5)+λB, _t= 2 ( (λ _t+K_t)^0.5δ (λ _t)^0.5 )+ λB, which follows from [20, Lemma 77]. In (20), δ is the confidence interval, and B is the upper-bound of the RKHS-norm of its kernel. Intuitively, βt _t determines how much we trust the accuracy of the current posterior mean (μt−1 _t-1), which is an approximation of U~PA U^PA on the fly, by suitably adding the posterior variance (σt−1 _t-1), since the posterior variance quantifies the uncertainty of μt−1 _t-1 being the true unknown U~PA U^PA. Note, the role of Σ^t _t in (20) is to better estimate the unknown variance matrix (i.e., Σt _t), which essentially improves the exploitation-exploration trade-off. Needless to say, the posterior mean and variance of the acquisition function in (19) is built with our proposed Neural Network kernel in (13). In Algorithm 1, we explain the operation of our proposed methodology. Note that the initial dataset 0X_0 is created by sampling any fixed x0∈x_0 for ℓ times. 1 Initialization: B,BvB,B_v, λ, ℓ , Kernel functions k(⋅,⋅)k(·,·), kv(⋅,⋅)k^v(·,·), Confidence level δ, Initial dataset 0=(x0i,y~0i)i∈[l]X_0=\(x^i_0, y^i_0)_i∈[l]\, and Prior μ0=μ0v=0 _0=μ^v_0=0. 2 for t=1,2,…t=1,2,… do 3 Compute y^t y_t and v^t v_t following (15) (use 0X_0 if t=1t=1). Update ucbt(⋅)ucb_t(·) following (17). Update Σ^t _t following (18). Update the posterior μt(⋅) _t(·) and σt2(⋅)σ^2_t(·) following (16). Select xt=argmaxx∈μt−1(x)+βtσt−1(x)x_t= _x \>\> _t-1(x)+ _t _t-1(x) 4 for i∈1,…,ℓi∈\1,…, \ do 5 Collect y~ti\ y_t^i\, where y~ti=U~PA(xt)+ε~i(xt) y_t^i= U^PA(x_t)+ _i(x_t) end for 6 7 end for 8 Algorithm 1 Heteroscedastic GP-UCB 4.3. Regret bound The asymptotic performance of Heteroscedastic GP-UCB is based on the regret bound of [30, Theorem 11] where the authors provide (21) ℙ[R~T≤βTℓ2γ^TTlog(1+ℓχu2)]≥1−δ, [ R_T≤ _T 2 γ_TT (1+ _u^2) ]≥ 1-δ, where δ is the confidence level, βT _T is defined in (20), and γ^T γ_T denotes the maximum information gain [35]. At time T, γ^T γ_T is defined using mutual information I(y1:T,U~1:TPA)I(y_1:T, U^PA_1:T) [28, Equation 2.282.28] between the feedback y1:T=[y1,…yT]⊤y_1:T=[y_1,… y_T] and U~1:TPA=[U~PA(x1),…U~PA(xT)]⊤ U^PA_1:T=[ U^PA(x_1),… U^PA(x_T)] as (22) γ^T:=maxA⊂,|A|=TI(y1:T,U~1:TPA). γ_T:=\; _A ,|A|=T I(y_1:T, U^PA_1:T). In other words, maximum information gain is essentially the maximum uncertainty reduction of the unknown function U~PA U^PA for a set of T sampled data (say, A) in X. The main technical challenge in this setup is to find an upper bound for γ^T γ_T. γ^T γ_T is kernel-specific, and there exist standard upper bounds for γ^T γ_T where the kernel k is Gaussian, Matern, or Linear [35]. However, to our best knowledge, no such upper bound exists for our proposed neural-network kernel in (13). Following [35, Theorem 88], the upper bound of γ^T γ_T is a function of the eigenvalue tail sum Bk(T∗)B_k(T_*) of the respective kernel, where Bk(T∗):=∑s=T∗+1∞λsB_k(T_*):= _s=T_*+1^∞ _s, and λs _s is the eigenvalue corresponding to the integral operator of any kernel k(x,y)k(x,y). For our proposed neural network kernel in (13), the following result provides an upper bound for Bk(T∗)B_k(T_*). Proposition 4.4 (Bound on eigenvalue tail sum). Given the neural network kernel k(x,y)k(x,y) in (13), its eigenvalues λs _s, corresponding to the integral operator, decay exponentially. Consequently, the eigenvalue tail sum Bk(T∗)=∑s=T∗+1∞λsB_k(T_*)= _s=T_*+1^∞ _s is bounded as (23) Bk(T∗)≤(exp(−βT∗1/m)) B_k(T_*) ( (-β T^1/m_*) ) for some constant β>0β>0. The proof is given in Appendix A.2. The proof of the Proposition 4.4 hinges on the analytic property of any kernel. The analytic property refers to a certain level of smoothness of any kernel. It turns out that our proposed kernel enjoys this property (Lemma 1) which leads to its exponentially decaying eigenvalues. With the help of Proposition 4.4, we manage to derive an explicit upper bound for γ^T γ_T, which helps us establish the main regret bound of this study. Theorem 4.5 (Sub-linear regret). Consider U~PA∈ℋk U^PA _k with bounded RKHS-norm (i.e., ‖U~PA‖ℋk≤B\| U^PA\|_H_k≤ B) and sampling model in (14) with unknown variance ar(ε~(xt))Var( (x_t)) that satisfies Assumptions 4.2 and 4.3. Let xtt=1T\x_t\_t=1^T denote the set of actions chosen by Algorithm 1. Setting λ=1λ=1 in (20), the cumulative regret R~T R_T defined in (9) is bounded as (24) ℙ[R~T≤(T(logT)m+1)]≥1−δP [ R_T ( T( T)^m+1 ) ]≥ 1-δ for a chosen confidence level δ>0δ>0. Proof. The broad idea of the proof is to derive a kernel-specific upper bound of the information gain for an already existing regret bound in [30]. To bound the information gain, we follow key ideas from [35] to bound the eigenvalue tail sum of our proposed kernel in (13), and Proposition 4.4 does this job. To prove Proposition 4.4, we require the analytic property of our kernel, which is given by Lemma 1. The rest of the proof uses a few known algebraic manipulations to simplify the regret bound. We first write from Theorem 11 of [30] for the coefficient of risk α=0α=0 (25) ℙ[R~T≤βTℓ2γ^TTlog(1+ℓχu2)]≥1−δ, [ R_T≤ _T 2 γ_TT (1+ _u^2) ]≥ 1-δ, where δ is the confidence level, and the maximum information gain [30, Equation 4242] is defined as (26) γ^T=max∑t=1TA⊂D,|A|=T0.5log(1+σt−12(xt|diag(χu2/ℓ))χu2/ℓ). γ_T= _A⊂ D,|A|=T\>\> _t=1^T0.5 (1+ σ^2_t-1(x_t|diag( _u^2/ ))χ^2_u/ ). One could compare (26) with the information gain of homoscedastic noise (γT _T in [35, Lemma 5.35.3]) and state that γ^T γ_T is simply same as γT _T with a constant noise variance σ2=(χu2/ℓ)σ^2=( _u^2/ ). Therefore, making the required modification and replacing the upper bound of βT _T from equation (25)(25) in [30] (27) R~T≤ℓTlog(1+ℓχu2)(4γTlog(1/δ)+2γT2+B2λγT). R_T≤ T (1+ _u^2) ( 4 _T (1/δ)+2 _T^2+B 2λ _T ). Now, the key part is to upper bound γT _T for our proposed kernel k(x,y)k(x,y) in (13). For this, we use the result in [35, Theorem 88] as (28) γT≤0.51−e−1maxr≤T(T∗log(rnT/σ2)+C4σ−2(1−r/T)(logT)(Tτ+1Bk(T∗)+1))+(T1−τm) _T≤ 0.51-e^-1 _r≤ T\>\> (T_* (rn_T/σ^2)+C_4σ^-2(1-r/T)( T)(T^τ+1B_k(T_*)+1) )+O(T^1-τ m) for any T∗∈1,…,nTT_*∈\1,…,n_T\ and τ>0τ>0. Here Bk(T∗)=∑s>T∗λsB_k(T_*)= _s>T_* _s with λs\ _s\ being the operator spectrum of the kernel k(x,y)k(x,y) with respect to uniform distribution over D, nT=C4TτlogTn_T=C_4T^τ T with C4=2(D)(2τ+1)C_4=2V(D)(2τ+1), and (D)=∫x∈DxV(D)= _x∈ Ddx. Absorbing (28) inside ‘Big-O’ notation, we write γT _T ≤(maxr=1,…,T(T∗log(rnT))+(T−r)TτBk(T∗))+(T1−τ/m). ( _r=1,…,T\>(T_* (rn_T))+(T-r)T^τB_k(T_*) )+O(T^1-τ/m). Now setting τ=mτ=m converts (T1−m/m)=(1)O(T^1-m/m)=O(1). As T→∞T→∞, we can further compress the upper bound and write γT _T ≤(maxr=1,…,T(T∗log(rnT))+Tm+1Bk(T∗)), ( _r=1,…,T\>(T_* (rn_T))+T^m+1B_k(T_*) ), =(maxr=1,…,T(T∗log(rTm))+Tm+1Bk(T∗)),(by setting nT=(TmlogT)), =O ( _r=1,…,T\>(T_* (rT^m))+T^m+1B_k(T_*) ), (by setting $n_T=O(T^m T)$), =(T∗log(Tm+1)+Tm+1Bk(T∗)),(max is attained at r=T), =O (T_* (T^m+1)+T^m+1B_k(T_*) ), (max is attained at $r=T$), (29) =(T∗log(T)+Tm+1Bk(T∗)). =O (T_* (T)+T^m+1B_k(T_*) ). From Proposition 4.4, we know that Bk(T∗)≤(e−βT∗1/m)B_k(T_*) (e^-β T^1/m_*). Replacing it in the above equation γT _T ≤(T∗logT+Tm+1e−βT∗1/m), (T_* T+T^m+1e^-β T^1/m_* ), =((logT)mlogT),(by setting T∗=(m+1βlogT)m, the second term is (1)) =O (( T)^m T ),\>\>(by setting $T_*= ( m+1β T )^m$, the second term is $ O(1)$) (30) =((logT)m+1). =O (( T)^m+1 ). Now, simplifying (27) in terms of γT _T R~T R_T ≤(T(γT+γT2+γT)), ( T( _T+ _T^2+ _T) ), =(T(γT+γT))(as γT2 is dominant over γT), =O ( T( _T+ _T) )(as $ _T^2$ is dominant over $ _T$), =(T(γT))(as γT is dominant over γT), =O ( T( _T) )(as $ _T$ is dominant over $ _T$), (31) =(T(logT)m+1)(replacing equation (4.3)). =O ( T( T)^m+1 )\>\>(replacing equation gama_ub). Therefore, we have ℙ[R~T≤(T(logT)m+1)]≥1−δ,P [ R_T ( T( T)^m+1 ) ]≥ 1-δ, where δ>0δ>0 is the user-defined confidence level. This concludes the proof. ∎ 5. Application: V2G Incentive Design In a standard V2G ecosystem, an Aggregator coordinates a fleet of electric vehicle (EV) owners to trade energy with the Distribution System Operator (DSO). In particular, Aggregators provide ancillary services to local DSOs in response to time-varying tariffs (λgλ^g), while procuring them from EV users. One key conflict arises because discharging power to the grid accelerates battery degradation of the EVs. This degradation imposes a private, stochastic cost on the EV owner, driven by the unobservable decline of battery health. In addition, the EV users impose a subjective cost for “range anxiety” while participating in V2G. Because the Aggregator cannot directly observe these individual users’ costs or forcefully command the EVs to discharge, they must rely on incentives. 5.1. Mapping V2G to principal-agent model To model the interaction between the Aggregator and EV users, we first clarify the research goal to be addressed in this application. To this end, we ask the following research question. Figure 5. V2G incentive design schematic showing sequential interaction between aggregators and EV users. Problem. How can an aggregator dynamically learn an adaptive incentive scheme (contract) that elicits optimal EV participation to maximize the Aggregator’s revenue, despite the unobservable and stochastic nature of user costs? The solution approach is to map the V2G ecosystem into our dynamic principal-agent framework depicted in Figure 1. In particular, we want to mathematically model the interaction between the Aggregator and EV user in the form of (3), where the Aggregator is the principal and the EV user is the agent. As depicted in Figure 5, we model the incentive design problem as a sequential interaction between the Aggregator and an EV user, where at time t, the aggregator offers a contract xt:=[xl,xh]∈[0,1]2x_t:=[x^l,x^h]∈[0,1]^2, specifying monetary incentives for low (ll) and high (hh) V2G contribution outcome set l,h\l,h\. The EV user responds with a decision a(xt)∈:=0,1a(x_t) :=\0,1\, where 00 denotes participation and 11 denotes non-participation in the V2G program. Assume there exists a utility function UA(xt,at):=∑i∈[2](xt)ipi(at)−c(at)U^A(x_t,a_t):= _i∈[2](x_t)_i\;p_i(a_t)-c(a_t) for the EV user, where c:→ℝc:A denotes the user’s cost function, and p:0,1→Δ2p:\0,1\→ _2 is the production function. The EV user optimizes UAU^A to retrieve the best response a⋆(xt)a (x_t). Based on a⋆(xt)a (x_t), an outcome l,h∋it∼p(a⋆(xt))\l,h\ i_t p(a (x_t)) is realized. However, the process from the EV user’s optimal action (a⋆(xt))(a (x_t)) to the realization of an outcome (it)(i_t) includes several steps within the context of V2G operation. In particular, the non-trivial part is to characterize a production function p(⋅)p(·) that links EV users’ best response a⋆(xt)a (x_t) to a stochastic outcome (iti_t) for the Aggregator. 5.2. Characterization of p(⋅)p(·) To formalize the characterization, we split the V2G operation into two parts: (1)(1) smart charging, and (2)(2) value estimator. The smart charging problem, parameterized in a⋆(xt)a (x_t), provides a stochastic charging profile, which is passed through a deterministic value estimator to obtain the outcome and value for the aggregator. Smart charging: Consider the decision vector z=[Pc,Pd,δ,E]⊤z=[P^c,P^d,δ,E] where Pc∈ℝNP^c ^N is the charging power, Pd∈ℝNP^d ^N is the discharging power for N intervals, E∈ℝNE ^N is the EV battery energy profile, and δi∈0,1,∀i∈[N] _i∈\0,1\,∀ i∈[N] refers the charging (δi=1 _i=1) or the discharging (δi=0 _i=0) mode of the EV. Given the user action a⋆(xt)a (x_t), the smart charging problem is compactly given as (32) maxzJ(z,ζ)s.t.z∈(a⋆(xt),ζ), _zJ(z,ζ) .t. z (a (x_t),ζ), where J encodes net charging benefit for the EV user, Z encodes the operational constraints, and the uncertain vector is ζ=[N,ηc,ηd,Einitial,Edesired]ζ=[N,η^c,η^d,E_initial,E_desired]. A detailed formulation of smart charging is given in Appendix B, along with an explanation of each parameter in ζ. As the uncertain vector ζ is chosen by the user, we impose the following assumptions. Assumption 5.1 (Smart charging setting). Consider problem (32) where the uncertain vector ζ is defined on the probability space (Ω,ℱ,ℙ)( ,F,P) with support Ξ . (i) Measurability: For every a∈a , the correspondence ζ↦(a,ζ)ζ (a,ζ) has a measurable graph, while the map (z,ζ)↦J(z,ζ)(z,ζ) J(z,ζ) is Borel measurable in ζ. (i) Feasibility: We assume that the feasibility set (a,ζ)Z(a,ζ) in (32) is non-empty and compact for all ζ∈Ξζ∈ and a∈a . Assumption 5.1 helps construct a well-defined production function p(⋅)p(·), as we will show it later. The smart charging profile P^c(a⋆(xt),ζ),P^d(a⋆(xt),ζ)\ P^c(a (x_t),ζ), P^d(a (x_t),ζ)\ is used in the next step for the value estimator (see Figure 5) where P^c(a⋆(xt),ζ) P^c(a (x_t),ζ) and P^d(a⋆(xt),ζ) P^d(a (x_t),ζ) are part of the solution of (32) for a realization of the uncertain parameter ζ. Value estimator: To formalize the value estimator, we first define the net profit of the Aggregator (after transactions with DSO) stands as JP(a⋆(xt),ζ):=[J(z⋆(a⋆(xt)),ζ)+(P^d(a⋆(xt),ζ)−P^c(a⋆(xt),ζ))⊤λgΔt],J^P(a (x_t),ζ):= [J(z (a (x_t)),ζ)+( P^d(a (x_t),ζ)- P^c(a (x_t),ζ)) λ^g t ], where z⋆(a⋆(xt))z (a (x_t)) is the solution of (32). Then we define the value estimator function V:×Ξ→vl,vhV:A× →\v^l,v^h\ such that, vh≥vlv^h≥ v^l, and (33) V(a⋆(xt),ζ)=vhif,JtP(a⋆(xt),ζ)≥J′,vlotherwise,V(a (x_t),ζ)= cases&v^h ,\>J^P_t(a (x_t),ζ)≥ J ,\\ &v^l , cases where the threshold profit J′J and the values v=[vl,vh]⊤v=[v^l,v^h] are chosen by the aggregator. Since ζ is a well-defined random variable, we assume that vhv^h and vlv^l are realized with probabilities php^h and plp^l, respectively. Essentially, this translates to defining the production function p(a):=[pl,ph]⊤p(a):=[p^l,p^h] . To validate the mathematical correctness of p(a)p(a), we need to show that it is possible to define ph=ℙζ[JtP(a,ζ)≥J′]p^h=P_ζ[J^P_t(a,ζ)≥ J ] and pl=1−php^l=1-p^h for any a∈a . Thus, we provide the following Proposition. Proposition 5.2 (Equivalence to principal-agent). Under Assumption 5.1, the proposed V2G incentive scheme constitutes a Principal-Agent problem wherein the smart charging formulation in (32) and the value estimator in (33) induce a well-defined production function p:→Δ2p:A→ _2. The proof is given in Appendix A.3. Finally, the Aggregator aims to find the optimal contract x⋆=argmaxx∈[0,1]2UPA(x)=∑i∈[2](v−x)ipi(a⋆(x))x = _x∈[0,1]^2\U^PA(x)= _i∈[2](v-x)_ip_i(a (x))\ using the reward values (i.e., yt=(v−xt)i,i∼p(a⋆(xt))y_t=(v-x_t)_i,\;i p(a (x_t))) from the interaction with sequentially arriving EV users. To apply our proposed algorithm Heteroscedastic GP-UCB, we consider the stochastic modification in the EV user’s utility (i.e., from UAU^A to U~A U^A), in addition to the required Assumptions for the algorithm. 6. Numerical Experiments We present two numerical experiments evaluating the performance of our algorithm against state-of-the-art benchmarks. First, we simulate a complex variant of the ‘High-low’ example discussed in Section 2.2, where the agent’s action space is expanded to n=3n=3. Second, we validate the proposed V2G incentive scheme through a realistic case study. We benchmark our performance against Agnostic Zooming and Discover and Cover algorithms. Table 1. Performance comparison of different methods. Effort levels correspond to a1a_1 (low), a2a_2 (medium), and a3a_3 (high). Agent Low Med. High Cost c(ai)c(a_i) N(0, 0.05)(0,\,0.05) N(0.1, 0.05)(0.1,\,0.05) N(0.2, 0.05)(0.2,\,0.05) Production p(ai)p(a_i) [0.95,[0.95,0.05]0.05] [0.2,[0.2,0.8]0.8] [0.05,[0.05,0.95]0.95] Principal Outcome i Low (i=0i=0) High (i=1i=1) Value v v0=0.1v_0=0.1 v1=0.8v_1=0.8 6.1. Performance comparison in ‘High-low’ example We retain the contract dimension m=2m=2 while increasing the number of available actions to n=3n=3. The detailed parameters of the feedback environment are provided in Table 1. We compare the algorithms over a horizon of T=1000T=1000 rounds, averaging over 55 independent episodes per algorithm. Since the exact optimal contract is intractable to compute a priori in complex physical environments, we follow the convention established by [15] and evaluate empirical performance using the average utility reward, defined as UT=1T∑t=1TU~PA(xt)U_T= 1T _t=1^T U^PA(x_t). We explicitly note that this metric must be interpreted differently from cumulative regret. While cumulative regret ideally flattens to indicate sub-linear growth, a successful average utility curve converges upward to a positive horizontal asymptote, which represents the maximum achievable per-round yield. Consequently, an algorithm whose average utility converges to a higher, stable plateau demonstrates superior identification and exploitation of the optimal contract. As illustrated in Figure 6(a), our proposed algorithm outperforms the benchmarks. Additionally, we conduct an ablation study to highlight the impact of heteroscedastic noise modeling and kernel selection in Appendix C.2. Overall, the observed performance gap validates the efficacy of our two key contributions: (1) optimization within a continuous domain, and (2) utility geometry-aware kernel choice paired with heteroscedastic noise modeling. (a) (b) Figure 6. Performance comparison on the synthetic benchmark and V2G profit analysis: (a) Performance comparison of Heteroscedastic GP-UCB on the synthetic benchmark. The y-axis displays the Average Utility Reward (UTU_T), not cumulative regret. Therefore, the convergence of our proposed algorithm (green line) to a high, positive horizontal asymptote (≈0.45≈ 0.45) indicates successful exploitation of the optimal contract, outperforming the baselines, which fail to converge to this optimal yield. (b) Comparison of the net V2G profit (JnetJ_net) for two scenarios, highlighting the impact of V2G incentive schemes under the benchmarked algorithms. 6.2. Results on V2G incentive design We evaluate the economic impact of our proposed incentive scheme on the Aggregator’s net profit. To evaluate the aggregator’s net profit from V2G participation of consecutive T users, we define net V2G profit as Jnet:=ϑ∑t=1TU~PA(xt),J_net:= _t=1^T U^PA(x_t), where ϑ is the re-normalization constant for conversion to Euro (€) currency. Specifically, we compare the net profit under two conditions: (i) a baseline scenario without an incentive mechanism, and (i) a scenario where the V2G incentive mechanism is managed by the benchmarked algorithms. Experimental Setup: We construct a realistic simulation setup for this problem; detailed implementation specifics are provided in Appendix C. We simulate two distinct user types, θ1 _1 and θ2 _2. The θ1 _1 user incurs a low internal cost for V2G participation and is willing to participate without incentives. Conversely, the θ2 _2 user is averse to participation due to high internal costs. We investigate two scenarios: Scenario 1 (High Aversion) We sample θ2 _2 with probability 0.950.95. This dominance of reluctance creates an ideal testing ground for the impact of incentive design. Scenario 2 (Mixed Population): We uniformly sample θ1 _1 and θ2 _2. This presents a challenging setting where generating profit exceeding the baseline (no-incentive) case is difficult. We conduct the interaction with T=1000T=1000 sequential users, and gather results over 55 independent episodes. Discussion of Results: Figure 6(b) illustrates box plots of the key outcomes. In Scenario 1, we observe the substantial impact of the incentive design, with the baseline benchmark Agnostic Zooming achieving a minimum %43\% increase in JnetJ_net. Notably, our algorithm Heteroscedastic GP-UCB outperforms all benchmarks by a significant margin. Even in the challenging Scenario 2, our algorithm yields a %5\% higher profit compared to the absence of any V2G incentive scheme. This case study demonstrates that employing specialized learning-based algorithms can unlock diverse, economically viable business models for V2G technology. 7. Limitations and Future Work Numerical results demonstrate that our algorithm outperforms existing benchmarks. Furthermore, the V2G application confirms its robustness in complex, real-world settings. Nevertheless, we acknowledge the following limitations that suggest clear directions for future research. Computational Scalability. The kernel matrix inversion in (16) incurs a computational complexity of (T3)O(T^3). While feasible for our experimental horizon (T=1000T=1000), this limits long-term deployment. Future work could integrate sparse GP approximations or variational inference to reduce computational complexity, enhancing real-time applications. Finite Agent Action Space. While we eliminate exponential dependence on action count n, our second contribution still relies on a finite action set (Assumption 4.1). Extending this framework to continuous agent action spaces would further theoretically improve upon existing methods. Appendix A Technical Proofs A.1. Auxiliary Lemma We first present a preparatory lemma that will be used to establish the main results of this study. Lemma 1 (Analytic kernel). Let D=[0,1]mD=[0,1]^m be the compact domain in ℝmR^m. The kernel in (13) is an analytic function on the domain D×D× D. Proof. We observe that the kernel k(x,y)k(x,y) is a composition of some functions. The broad idea of our proof is that we will show each composition is an analytic function in the domain D×D× D. (i) The dot-product kernel kdot(x,y)=σv⟨x,y⟩+σbk_dot(x,y)= _v x,y + _b is a polynomial in x and y. Therefore, it is analytic in the domain. (i) Say g(x,y)=(1+kdot(x,x))(1+kdot(y,y))g(x,y)=(1+k_dot(x,x))(1+k_dot(y,y)). We find kdot(x,x)=σb2+σv2⟨x,x⟩>σb2>0k_dot(x,x)= _b^2+ _v^2 x,x > _b^2>0 that implies (1+kdot(x,x))>1(1+k_dot(x,x))>1. Therefore, g(x,y)>1g(x,y)>1 is an analytic function as it is the product of two analytic functions, and g g is also an analytic function for all g(x,y)>0g(x,y)>0. (i) Representing z(x,y)=kdot(x,y)(1+kdot(x,x))⋅(1+kdot(y,y))z(x,y)= k_dot(x,y) (1+k_dot(x,x))·(1+k_dot(y,y)), it is an analytic function as the ratio of two analytic functions (kdotk_dot and g g) remain analytic as long as the denominator is non-zero. (iv) Finally, it is well known that arcsin(z) (z) is analytic if z∈(−1,1)z∈(-1,1). Therefore, we just need to check the range of z(x,y)z(x,y). Assume a=kdot(x,y),b=kdot(x,x)a=k_dot(x,y),b=k_dot(x,x) and c=kdot(y,y)c=k_dot(y,y). One could show using Cauchy-Schwarz inequality, a2≤bca^2≤ bc, furthermore it is easy to see that a2(1+b)(1+c)<1 a^2(1+b)(1+c)<1. Hence |z(x,y)|<1|z(x,y)|<1 implies z∈[−h,h]z∈[-h,h] with h<1h<1. This completes the proof. ∎ A.2. Proof of Proposition 4.4 It is known from the spectral theory of integral operators that analytic kernels have eigenvalues λs _s which decay exponentially [25, 32]. Using Lemma 1, we can confirm the same for the eigenvalues of our proposed kernel k(x,y)k(x,y). Following the above argument, we bound the tail sum Bk(T∗)B_k(T_*) as Bk(T∗)≤∑s=T∗+1∞Ce−vs1/m≤C∫T∗∞e−vs1/ms B_k(T_*)≤ _s=T_*+1^∞Ce^-vs^1/m≤ C _T_*^∞e^-vs^1/mds for some constants C,C, and v. It can be shown with some calculation that the above integral transforms to Bk(T∗)≤C′Γ(m,vT∗1/m), B_k(T_*)≤ C (m,vT_*^1/m), where Γ is the upper incomplete gamma function and C′C is some constant. Using the formulae Γ(m,q)=(m−1)!e−q∑k=0m−1(qk/k!) (m,q)=(m-1)!e^-q _k=0^m-1(q^k/k!) [13], we can show for larger q=vT∗1/mq=vT_*^1/m, our bound behaves as (34) Bk(T∗)≤((vT∗1/m)m−1e−vT∗1/m).B_k(T_*) ((vT_*^1/m)^m-1e^-vT_*^1/m). One can see that the exponential decay of e−vT∗1/me^-vT_*^1/m is much stronger than the polynomial growth of (vT∗1/m)m−1(vT_*^1/m)^m-1 as T∗→∞T_*→∞. Therefore, for any small δ>0δ>0, we can find a constant CδC_δ such that (vT∗1/m)m−1≤Cδeδ(vT∗1/m)(vT_*^1/m)^m-1≤ C_δe^δ(vT_*^1/m). Substituting this into the above equation Bk(T∗) B_k(T_*) ≤(eδvT∗1/m⋅e−vT∗1/m)=(e−(1−δ)vT∗1/m). (e^δ vT_*^1/m· e^-vT_*^1/m )=O (e^-(1-δ)vT_*^1/m ). By choosing δ such that β=(1−δ)v>0β=(1-δ)v>0, we obtain Bk(T∗)≤(e−βT∗1/m). B_k(T_*) (e^-β T^1/m_*). This concludes the proof. □ A.3. Proof of Proposition 5.2 We first recall the setup of the principal-agent problem with respect to the Figure 5. The principal (aggregator) shows the contract xt∈[0,1]2x_t∈[0,1]^2 to the agent (EV user), and the agent takes a strategic action a⋆(xt)a (x_t) in hindsight. As a result, an outcome is realized following the condition in (33). The main focus here is to understand the existence of a production function p(⋅)p(·) as defined in (1). If we manage to show that JP(a⋆(xt),ζ)=[J(z⋆(a⋆(xt)),ζ)+(P^d(a⋆(xt),ζ)−P^c(a⋆(xt),ζ))⊤λgΔt],J^P(a (x_t),ζ)= [J(z (a (x_t)),ζ)+( P^d(a (x_t),ζ)- P^c(a (x_t),ζ)) λ^g t ], is a well-defined random variable in (33), we can confirm the existence of a production function. To establish that JP(a⋆(xt),ζ)J^P(a (x_t),ζ) is a random variable, we proceed by the following steps. (1) Since (35a) indicates that J is continuous in z, we apply Berge’s maximum theorem [1, Theorem 17.3117.31] to confirm that J(z⋆(a⋆(xt)),ζ)J(z (a (x_t)),ζ) is continuous in ζ. (2) Moreover, since J(z,ζ)J(z,ζ) is a Borel measurable function of ζ (Assumption 5.1), both the optimizer z⋆(a⋆(xt))z (a (x_t)) and optimal objective value J(z⋆(a⋆(xt),),ζ)J(z (a (x_t),),ζ) become Borel measurable in ζ, where the feasibility of the optimizer z⋆(a⋆(xt))z (a (x_t)) in (32) is ensured by Assumption 5.1. Finally, JP(a⋆(xt),ζ)J^P(a (x_t),ζ) is a linear combination of measurable functions, which makes it a measurable function of ζ. Hence, it is a well-defined random variable, which makes the definition php^h and plp^l consistent. This concludes the proof. □ Appendix B Detailed smart charging formulation Consider Pc∈ℝNP^c ^N is the charging profile, and Pd∈ℝNP^d ^N is the discharging profile for N intervals. The aggregator defines the buying price λib=cλig,∀i∈[N]λ^b_i=cλ^g_i,\>∀ i∈[N], and the selling price λis=c′λig,∀i∈[N]λ^s_i=c λ^g_i,\>∀ i∈[N], where c,c′c,c are the aggregator-defined constants resposible for profit margin such that c∈(0,1],c′≥1c∈(0,1],c ≥ 1. E∈ℝNE ^N is the EV battery energy profile with E¯ E and E¯ E being the limits of the energy level. Furthermore, we use δi∈0,1,∀i∈[N] _i∈\0,1\,∀ i∈[N] to refer to the charging (δi=1 _i=1) or the discharging (δi=0 _i=0) mode of the EV, and we use ηc/ηdη^c/η^d to refer to the charging/discharging coefficients embedding the efficiency and battery capacity of the EV, respectively. Based on the active load profile up to time t, we also have the bounds on the charging/discharging power as P¯t P_t and P¯t P_t, respectively. Given these terminologies, the smart charging algorithm solves the following optimization problem: maxPc,Pd,δ,E _P^c,P^d,δ,E J:=(Pc(λs)⊤−Pd(λb)⊤)Δt J:=(P^c(λ^s) -P^d(λ^b) ) t (35a) −α(∥Pc∥22+∥Pd∥22), -α( P^c _2^2+ P^d _2^2), (35b) s.t. Ei+1=Ei+ηcPcΔt−ηdPdΔt,∀i∈[N], E_i+1=E_i+η^cP^c t-η^dP^d t,∀ i∈[N], (35c) 0≤Pic≤δiP¯t,i,∀i∈[N], 0≤ P^c_i≤ _i P_t,i,\>∀ i∈[N], (35d) 0≤Pid≤(1−δi)P¯t,i,∀i∈[N], 0≤ P^d_i≤(1- _i) P_t,i,\>∀ i∈[N], (35e) E¯≤Ei≤E¯,∀i∈[N], E≤ E_i≤ E,\>∀ i∈[N], (35f) E1=Einitial,EN+1=Edesired, E_1=E_initial,\>E_N+1=E_desired, (35g) δj=1,∀j∈[N],ifa⋆(xt)=1, _j=1,\;∀ j∈[N],\;if\;a (x_t)=1, Figure 7. Assessing performance of Heteroscedastic GP-UCB (paired with Neural Network kernel) under two scenarios. In scenario 11, it outperforms GP-UCB [35] with a Neural Network kernel, validating the effect of considering heteroscedastic noise. In scenario 22, it also outperforms the radial basis function (RBF) kernel, validating our kernel choice. where the objective is to maximize the net profit J∈ℝJ for the EV user, the constraints include energy dynamics of the EV battery, limiting bounds for charging/discharging power and energy, α is a regularizer coefficient, Δt t is the time interval, and finally, N,Einitial,EdesiredN,E_initial,E_desired are the parameters given by the EV users. Appendix C Implementation details of numerical experiments and additional results Table 2. Details of uncertain and fixed parameters for numerical simulation. (a) Uncertain parameters Uncertain parameters Distribution N Uniform(20,2420,24) ηcη^c and ηdη^d Uniform(0.9,0.98) EinitialE_initial Uniform(10,15) EdesiredE_desired Uniform(20, NP¯tηcΔtN P_tη^c t) (b) Fixed parameters Fixed parameters Values E¯ E 55 kWh E¯ E 9090 kWh P¯t P_t and P¯t P_t 1111 kW c 0.70.7 c′c 1.21.2 J′J 8080 € Δ 1010 € vhv^h 0.90.9 vlv^l 00 Δt t 1515 minutes C.1. Implementation details We have used Assumption 5.1 to construct the random vector ζ in Table 2 such that its realized values appear realistic for the application, while maintaining the feasibility of the smart charging problem in (35). The values of the fixed parameters in (35) and (33) are given in Table 2. In addition, the tariff data from DSO (λgλ^g) is taken from Figure 77 of [22]. Given λgλ^g, one can easily construct λbλ^b and λsλ^s using the profit margin constants c and c′c from Table 2. C.2. Additional results We present an ablation study in Figure 7 to decouple the contributions of heteroscedastic variance modeling and kernel selection. First, to isolate the impact of the noise model, we compare our approach against standard homoscedastic GP-UCB [35] equipped with the Neural Network kernel. Second, to validate the kernel geometry, we substitute the N kernel with the standard Radial Basis Function (RBF) kernel within our framework. The results demonstrate that our proposed method outperforms both variations, confirming that both the heteroscedastic structure and the non-stationary kernel are essential for our problem setup. References [1] Charalambos D Aliprantis and Kim C Border. Infinite dimensional analysis: a hitchhiker’s guide. Springer, 2006. [2] Manjari Asawa and Demosthenis Teneketzis. Multi-armed bandits with switching penalties. IEEE Transactions on Automatic Control, 41(3):328–348, 2002. [3] Moshe Babaioff, Michal Feldman, and Noam Nisan. Combinatorial agency. In Proceedings of the 7th ACM Conference on Electronic Commerce, pages 18–28, 2006. [4] Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Learning optimal contracts: How to exploit small action spaces. In International Conference on Representation Learning, volume 2024, pages 11944–11970, 2024. [5] Jorge Barrera and Alfredo Garcia. Dynamic incentives for congestion control. IEEE Transactions on Automatic Control, 60(2):299–310, 2014. [6] Dimitri P Bertsekas. Control of uncertain systems with a set-membership description of the uncertainty. PhD thesis, Massachusetts Institute of Technology, 1971. [7] Alec N Brooks et al. Vehicle-to-grid demonstration project: Grid regulation ancillary service with a battery electric vehicle. 2002. [8] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference on Machine Learning, pages 844–853. PMLR, 2017. [9] Eric W Cope. Regret and convergence bounds for a class of continuum-armed bandit problems. IEEE Transactions on Automatic Control, 54(6):1243–1253, 2009. [10] Paul Dütting, Michal Feldman, and Inbal Talgam-Cohen. Algorithmic contract theory: A survey. Foundations and Trends® in Theoretical Computer Science, 16(3-4):211–411, 2024. [11] Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen. Simple versus optimal contracts. In Proceedings of the 2019 ACM Conference on Economics and Computation, pages 369–387, 2019. [12] Lawrence C Evans. Measure theory and fine properties of functions. Chapman and Hall/CRC, 2025. [13] Izrail Solomonovich Gradshteyn and Iosif Moiseevich Ryzhik. Table of integrals, series, and products. Academic press, 2014. [14] Christopher Harris. You’re hired! an examination of crowdsourcing incentive models in human resource tasks. In Proceedings of the Workshop on Crowdsourcing for Search and Data Mining (CSDM) at the Fourth ACM International Conference on Web Search and Data Mining (WSDM), pages 15–18. Hong Kong, China, 2011. [15] Chien-Ju Ho, Aleksandrs Slivkins, and Jennifer Wortman Vaughan. Adaptive contract design for crowdsourcing markets: Bandit algorithms for repeated principal-agent problems. In Proceedings of the fifteenth ACM conference on Economics and computation, pages 359–376, 2014. [16] Y Ho and D Teneketzis. On the interactions of incentive and information structures. IEEE Transactions on Automatic Control, 29(7):647–650, 1984. [17] Yu-Chi Ho, P Luh, and Ramal Muralidharan. Information structure, stackelberg games, and incentive controllability. IEEE Transactions on Automatic Control, 26(2):454–460, 1981. [18] Matthew Hoffman, Eric Brochu, Nando De Freitas, et al. Portfolio Allocation for Bayesian Optimization. In UAI, volume 11, pages 327–336, 2011. [19] Bengt Holmstrom et al. Moral hazard and observability. Bell journal of Economics, 10(1):74–91, 1979. [20] Johannes Kirschner and Andreas Krause. Information directed sampling and bandits with heteroscedastic noise. In Conference On Learning Theory, pages 358–384. PMLR, 2018. [21] Jean-Jacques Laffont and David Martimort. The theory of incentives: the principal-agent model. Princeton university press, 2002. [22] Shuying Lai, Jing Qiu, Yuechuan Tao, and Junhua Zhao. Pricing for electric vehicle charging stations based on the responsiveness of demand. IEEE Transactions on Smart Grid, 14(1):530–544, 2022. [23] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020. [24] Niklas Lauffer, Mahsa Ghasemi, Abolfazl Hashemi, Yagiz Savas, and Ufuk Topcu. No-regret learning in dynamic stackelberg games. IEEE Transactions on Automatic Control, 69(3):1418–1431, 2023. [25] G Little and JB Reade. Eigenvalues of analytic kernels. SIAM journal on mathematical analysis, 15(1):133–136, 1984. [26] Chunhua Liu, KT Chau, Diyun Wu, and Shuang Gao. Opportunities and challenges of vehicle-to-home, vehicle-to-vehicle, and vehicle-to-grid technologies. Proceedings of the IEEE, 101(11):2409–2427, 2013. [27] Wanchun Liu, Alex S Leong, and Daniel E Quevedo. Thompson sampling for networked control over unknown channels. Automatica, 165:111684, 2024. [28] Thomas M. Cover and Joy A. Thomas. Elements of information theory. John Wiley and Sons, 1999. [29] Chinmay Maheshwari, Kshitij Kulkarni, Manxi Wu, and Shankar Sastry. Adaptive incentive design with learning agents. IEEE Transactions on Automatic Control, 71(6):3619–3633, 2026. [30] Anastasia Makarova, Ilnura Usmanova, Ilija Bogunovic, and Andreas Krause. Risk-averse heteroscedastic bayesian optimization. Advances in Neural Information Processing Systems, 34:17235–17245, 2021. [31] Adam J Mersereau, Paat Rusmevichientong, and John N Tsitsiklis. A structured multiarmed bandit problem and the greedy policy. IEEE Transactions on Automatic Control, 54(12):2787–2802, 2009. [32] Albrecht Pietsch. Eigenvalues and s-numbers. Cambridge university press Cambridge, 1987. [33] Lillian J Ratliff and Tanner Fiez. Adaptive incentive design. IEEE Transactions on Automatic Control, 66(8):3871–3878, 2020. [34] Paat Rusmevichientong and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395–411, 2010. [35] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias W Seeger. Information-theoretic regret bounds for gaussian process optimization in the bandit setting. IEEE Transactions on Information Theory, 58(5):3250–3265, 2012. [36] Koen van Heuveln, Rishabh Ghotge, Jan Anne Annema, Esther van Bergen, Bert van Wee, and Udo Pesch. Factors influencing consumer acceptance of vehicle-to-grid by electric vehicle drivers in the Netherlands. Travel Behaviour and Society, 24:34–45, 2021. [37] Tonghan Wang, Paul Duetting, Dmitry Ivanov, Inbal Talgam-Cohen, and David C Parkes. Deep contract design via discontinuous networks. Advances in Neural Information Processing Systems, 36:65818–65836, 2023. [38] Christopher KI Williams. Computation with infinite neural networks. Neural Computation, 10(5):1203–1216, 1998. [39] Le Yang, Siyang Gao, Cheng Li, and Yi Wang. Stochastically constrained best arm identification with thompson sampling. Automatica, 176:112223, 2025. [40] Xinyang Zhou, Emiliano Dall’Anese, Lijun Chen, and Andrea Simonetto. An incentive-based online optimization framework for distribution grids. IEEE Transactions on Automatic Control, 63(7):2019–2031, 2017. [41] Banghua Zhu, Stephen Bates, Zhuoran Yang, Yixin Wang, Jiantao Jiao, and Michael I Jordan. The sample complexity of online contract design. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 1188–1188, 2023. [42] Jingxuan Zhu and Ji Liu. Distributed multiarmed bandits. IEEE Transactions on Automatic Control, 68(5):3025–3040, 2023.