Paper deep dive
Adaptive Agent Design
Raj Kiriti Velicheti, Subhonmesh Bose, Tamer Başar
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 9/16/2026, 8:54:05 AM
Summary
This paper addresses the adaptive agent design problem where an agent operates in a general non-Markovian environment. The agent maintains internal states defined by a parametric transition kernel $f_\theta$ and optimizes both the kernel parameters $\theta$ and the induced state-feedback policy $\pi$. The authors formulate this as a bi-level optimization problem and propose an iterative algorithm (Algorithm 1) that alternates between inner policy optimization via soft Q-learning and outer parameter adaptation. They prove that soft Q-learning converges almost surely to a fixed point of a soft Bellman equation defined by stationary averages. For the outer loop, they analyze two optimization strategies: Zeroth-Order Optimization (ZOO) and Bayesian Optimization (BO), providing convergence guarantees for both under specific assumptions, particularly when the environment is a Partially Observed Markov Decision Process (POMDP).
Entities (14)
Relation Signals (10)
Raj Kiriti Velicheti → affiliatedwith → University of Illinois
confidence 100% · All authors are affiliated with the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory at the University of Illinois
Subhonmesh Bose → affiliatedwith → University of Illinois
confidence 100% · All authors are affiliated with the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory at the University of Illinois
Tamer Başar → affiliatedwith → University of Illinois
confidence 100% · All authors are affiliated with the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory at the University of Illinois
Adaptive Agent Design → addresses → Non-Markovian Environment
confidence 95% · We consider an agent acting against a general non-Markovian environment.
Soft Q-learning → usedfor → Policy Optimization
confidence 95% · we show that a soft Q-learning algorithm converges almost surely to the fixed point of a soft Bellman equation
Zeroth-Order Optimization → usedfor → Kernel Parameter Adaptation
confidence 95% · analyze convergence properties of parametrized transition kernel design via zero-th order ... optimization techniques
Bayesian optimization → usedfor → Kernel Parameter Adaptation
confidence 95% · analyze convergence properties of parametrized transition kernel design via ... Bayesian optimization techniques
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We consider an agent acting against a general non-Markovian environment. The agent maintains its agent states, but is free to choose a transition kernel across those states and optimize its state-feedback control policies. We study the bi-level agent design problem that optimizes the transition kernel and the policy it induces, given said kernel with offline data of observations and actions obtained via a behavioral policy. For general environments, we show that a soft $Q$-learning algorithm converges almost surely to the fixed point of a soft Bellman equation defined by the stationary averages that the behavioral policy and the chosen kernel induce, and we delineate what separates the resulting policy from an optimal one. In partially observed Markov decision problems, we analyze convergence properties of parametrized transition kernel design via zero-th order and Bayesian optimization techniques.
Tags
Links
- Source: https://arxiv.org/abs/2609.12486v1
- Canonical: https://arxiv.org/abs/2609.12486v1
Trouble viewing inline? Open PDF directly →
Full Text
61,514 characters extracted from source content.
Expand or collapse full text
Adaptive Agent Design Raj Kiriti Velicheti Subhonmesh Bose Tamer Başar †thanks: All authors are affiliated with the Department of Electrical and Computer Engineering and the Coordinated Science Laboratory at the University of Illinois, Urbana-Champaign, Urbana, IL˜61801. Emails: rkv4, boses, basar1@illinois.edu. This work was partially supported by the U.S. National Science Foundation under grant number NSF-ECCS-2349418 and by the U.S. Army Research Office under grant number W911NF-24-1-0085. Abstract We consider an agent acting against a general non-Markovian environment. The agent maintains its agent states, but is free to choose a transition kernel across those states and optimize its state-feedback control policies. We study the bi-level agent design problem that optimizes the transition kernel and the policy it induces, given said kernel with offline data of observations and actions obtained via a behavioral policy. For general environments, we show that a soft Q-learning algorithm converges almost surely to the fixed point of a soft Bellman equation defined by the stationary averages that the behavioral policy and the chosen kernel induce, and we delineate what separates the resulting policy from an optimal one. In partially observed Markov decision problems, we analyze convergence properties of parametrized transition kernel design via zero-th order and Bayesian optimization techniques. 1 Introduction Intelligent decision-making systems are ubiquitous: from autonomous vehicles navigating complex traffic to language-model-based agents that invoke tools in open-ended software environments. Abstracting any such system as an agent that interacts with everything outside it—the environment—the agent must assimilate observations and produce actions that yield favorable outcomes. A classical approach is to model the environment as a Markov Decision Process (MDP), explicitly encoding all decision-relevant information into a state variable. MDPs have driven considerable progress in control and reinforcement learning. Their central challenge, however, is state design: the state must capture all information relevant to future decisions, which is rarely obvious in practice [23]. In traditional control theory this challenge is addressed through observability and filtering—from the Kalman filter to particle filters—but these require the practitioner to specify the state structure in advance. In richer domains such as language modeling or robotics, the “right” state representation is far less transparent. A more realistic stance is to acknowledge that the environment may be arbitrarily complex and non-Markovian, and to design agents that learn to summarize their interaction history into a compact internal state on the fly. One principled formulation of this idea is the simple agent, complex environment framework of [5], later cast as reinforcement learning in non-Markovian environments by [4]. Related work on partially observed Markov decision processes (POMDPs) [15, 1] provides sample-complexity bounds on the degradation of decision quality as available history shrinks. More broadly, these works are related to learning in partially observed environments where the agent is assumed to act without completely knowing the true underlying state. A long line of literature formalizes such settings as POMDPs [2]. For discrete spaces, [10] formalizes the complexity of finding solutions in these environments. In [14], a point based value iteration is proposed to approximately solve these problems in belief space. Another line of work in this direction is utilizing what is known as Approximate Information State [17] which proposes a theoretical approach on what a notion of a state should satisfy in partially observed environments that would make it sufficient for acting optimally. See [23] for further literature. While these works establish a theoretical basis for acting in general environments, they leave open the question of how an agent should adapt its state abstraction during interaction. In this paper, we address that question directly. We formulate the agent design problem as an optimization problem over a parametric family of state-transition kernels fθf_θ, derive an iterative procedure that alternates between inner policy optimization and outer adaptation of θ, and study two concrete instantiations of the outer step: zeroth-order optimization (ZOO) and Bayesian optimization (BO). We prove that (i) the outer objective VD(θ)V_D(θ) has a Lipschitz-continuous gradient, (i) the ZOO variant converges to a first-order stationary point at rate (1/K)O(1/ K), and (i) the BO variant with a convex-combination parametrization converges to a global optimum asymptotically. 2 A Simple Agent in a Non-Markovian Environment Let A and O denote finite action and observation spaces, respectively. The environment is characterized by a stochastic kernel ρ that generates the next observation ot+1∼ρ(⋅|ot,at), o_t+1\; \;ρ\! (·\; |\;o^t,a^t ), where ot=(ot,ot−1,…)o^t=(o_t,o_t-1,…) and at=(at,at−1…)a^t=(a_t,a_t-1…) denote the full histories of observations and actions up to time t. We assume that the observation process has been evolving for a long enough time i.e., t>−∞t>-∞. This formulation allows for arbitrary temporal dependence and does not require the environment to be Markovian. The agent maintains an internal state sts_t taking values in a finite set S. Rather than assuming the state-update rule to be given or fixed but unknown, we parametrize the update by θ∈Θ⊂ℝdθ∈ ^d and write st+1∼fθ(⋅|st,at,ot+1),s_t+1\; \;f_θ\! (·\; |\;s_t,\,a_t,\,o_t+1 ), (1) where fθ(⋅|s,a,o)∈Δ()f_θ(·|s,a,o)∈ (S) is a stochastic transition kernel. Equation (1) is the agent’s mechanism for compressing its full interaction history into a finite state; the quality of this compression depends entirely on the choice of θ. Given internal state sts_t, the agent selects actions according to a policy π:→Δ()π:S→ (A) and receives reward r(st,at,ot+1)r(s_t,a_t,o_t+1), where we write |r(⋅)|≤Rmax|r(·)|≤ R_ for some finite Rmax>0R_ >0. The agent’s goal is to maximize the expected discounted cumulative reward. Since this objective depends on both the transition parameter θ and the policy π, we write maxθ∈Θ,πV(fθ,π)=ρ,fθ,π[∑t=0∞γtr(st,at,ot+1)], _θ∈ ,\;π\;V(f_θ,π)\;=\;E_ρ,f_θ,π [ _t=0^∞γ^tr(s_t,a_t,o_t+1) ], (2) where γ∈(0,1)γ∈(0,1) is a discount factor. Problem (2) is a bilevel optimization problem: at optimality the policy must be optimal given θ. Denoting this best-response policy πθ⋆π _θ, substituting it back yields the outer objective VD(θ):=V(fθ,πθ⋆)=ρ,fθ,πθ⋆[∑t=0∞γtr(st,at,ot+1)]. V_D(θ)\;:=\;V\! (f_θ,\,π _θ )\;=\;E_ρ,\,f_θ,\,π _θ\! [ _t=0^∞γ^t\,r(s_t,a_t,o_t+1) ]. (3) Optimizing VD(θ)V_D(θ) over θ is the central problem of this paper. We address it in Section 3. 3 Generic Adaptive Agent Design Directly optimizing VD(θ)V_D(θ) faces two obstacles. First, obtaining πθ⋆π _θ for a given fθf_θ requires solving a reinforcement learning problem in a non-Markovian environment, for which there is no closed-form solution. Second, the gradient of VDV_D with respect to θ is not analytically accessible because the environment ρ is treated as a black box. Our approach resolves both difficulties as follows. Fix a behavioral policy πb:→Δ() _b:S→ (A) and collect a dataset D of observation-action-observation triples by rolling πb _b out in the environment long enough for the induced process to mix. For a candidate θ, we approximate πθ⋆π _θ by running soft Q-learning directly on the internal states generated by fθf_θ, using D as the replay source. Note that this might not result in the true optimal policy because of the non-Markovian environment but is motivated by the fact that the agent ignores the environment complexities and acts simple. The resulting policy π^θ π_θ is then deployed in the true environment to obtain a Monte Carlo estimate of VD(θ)V_D(θ). Finally, an outer optimization routine updates θ using only these function evaluations (no gradient of VDV_D with respect to θ is assumed available). This design is summarized in Algorithm 1. Before stating the algorithm precisely, we record the three assumptions that underlie the entire development. 1Compact and Convex. Θ⊂ℝd ^d is compact, convex and ΠΘ _ denotes Euclidean projection onto Θ . 2Smooth internal kernel. For all θ∈Θθ∈ : (i) fθ(s′|s,a,o)>0f_θ(s |s,a,o)>0 for all (s′,s,a,o)(s ,s,a,o); and (i) θ↦fθ f_θ is twice continuously differentiable with uniformly bounded first and second derivatives over Θ . 3Ergodicity and coverage. The behavioral policy πb _b, together with fθf_θ and the environment ρ, induces a stationary and ergodic process over (st,at,ot+1)(s_t,a_t,o_t+1) for every θ∈Θθ∈ . Moreover, every state-action pair is visited: π~(s,a)=P(st=s,at=a)>0 π(s,a)=P(s_t=s,a_t=a)>0 for all (s,a)∈×(s,a) ×A. Algorithm 1 Iterative Agent Design 1: Behavioral policy πb _b; parametric kernel family fθ∈Θ\f_θ\_θ∈ ; reward r; discount γ∈(0,1)γ\!∈\!(0,1); temperature τ>0τ\!>\!0; outer iterations K; evaluation budget M. 2: Parameter θK _K and policy π^θK π_ _K. 3: Collect data: Roll out πb _b in the environment (allowing sufficient mixing) to obtain D=(ot,i,at,i,ot+1,i)i,tD=\(o_t,i,a_t,i,o_t+1,i)\_i,t. 4: Initialize θ0∈Θ _0∈ . 5: for k=0,1,…,K−1k=0,1,…,K-1 do 6: Policy Computation πθk⋆π _ _k: Run soft Q-learning with temperature τ on the internal-state sequence generated by fθkf_ _k using dataset D, until convergence to Q^θk Q_ _k; set π^θk(a|s)∝exp(Q^θk(s,a)/τ) π_ _k(a|s) ( Q_ _k(s,a)/τ). 7: Policy Evaluation: Estimate VD(θk)V_D( _k) by rolling out (fθk,π^θk)(f_ _k, π_ _k) in the true environment for M episodes of horizon H. 8: Parameter Update: θk+1=StepOptimize(VD,θk,(θj,VD(θj))j≤k) _k+1= StepOptimize\! (V_D,\; _k,\; \( _j,\,V_D( _j)) \_j≤ k ) 9: end for 10: return θK _K and π^θK π_ _K. Two concrete implementations of StepOptimize are discussed below and detailed in Algorithms 2 and 3. 3.1 StepOptimize I: Zeroth-Order Optimization When the gradient ∇θVD(θ) _θV_D(θ) is unavailable, we estimate it via a two-point finite-difference scheme. At iteration k, draw a unit direction uk∼Uniform(d−1)u_k (S^d-1), evaluate VDV_D at θk±δkuk _k± _ku_k, and form the gradient estimate g^k=d2δk(V^D(θk+δkuk)−V^D(θk−δkuk))uk. g_k= d2 _k ( V_D( _k+ _ku_k)- V_D( _k- _ku_k) )u_k. (4) The iterate is updated as θk+1=ΠΘ(θk+ηkg^k) _k+1= _ ( _k+ _k g_k), where ΠΘ _ is Euclidean projection onto Θ and ηk,δk>0 _k, _k>0 are the step size and smoothing radius, respectively. Algorithm 2 StepOptimize via Zeroth-Order Optimization (ZOO) 1: Current iterate θk _k; objective oracle VDV_D; step size ηk _k; smoothing radius δk _k; evaluation budget M. 2: Updated parameter θk+1 _k+1. 3: Draw uk∼Uniform(d−1)u_k (S^d-1). 4: Estimate V^+ V_+ and V^− V_- by rolling out (fθk±δkuk,π^θk±δkuk)(f_ _k± _ku_k,\, π_ _k± _ku_k) for M episodes each. 5: g^k=d2δk(V^+−V^−)uk g_k= d2 _k ( V_+- V_- )u_k. 6: θk+1=ΠΘ(θk+ηkg^k) _k+1= _ \! ( _k+ _k\, g_k ). 7: return θk+1 _k+1. 3.2 StepOptimize I: Bayesian Optimization When each evaluation of VDV_D is expensive, Bayesian optimization (BO) is preferable: it maintains a Gaussian Process (GP) surrogate fitted to all past evaluations and selects the next query by maximizing an acquisition function, thus exploiting global smoothness with far fewer function evaluations. We place a GP prior on VDV_D with a Matérn-5/25/2 covariance in the Euclidean metric on Θ . Writing r=‖θ−θ′‖2r=\|θ-θ \|_2, κ(θ,θ′)=σf2(1+5rℓ+5r23ℓ2)exp(−5rℓ),κ(θ,θ )= _f^2\! (1+ 5\,r + 5\,r^23 ^2 ) \! (- 5\,r ), with signal variance σf2 _f^2 and length scale ℓ . Under the convex-combination parametrization fθ=∑i=1Nθifif_θ= _i=1^N _if_i of Lemma 7, the domain Θ is the (N−1)(N-1)-simplex, a compact convex subset of ℝNR^N on which κ is strictly positive definite. It is the smoothness this kernel encodes, through ν=5/2ν=5/2, that Theorem 8 exploits. At each iteration the next candidate is chosen by maximizing the Upper Confidence Bound (UCB) acquisition: θk+1=argmaxθ∈Θ(μk(θ)+βk+1σk(θ)) _k+1= argmax_θ∈ ( _k(θ)+ _k+1\, _k(θ) ). Algorithm 3 StepOptimize via Bayesian Optimization (BO) 1: History ℋk=(θj,V^D(θj))j≤kH_k=\( _j, V_D( _j))\_j≤ k; kernel κ; observation noise variance σξ2 _ξ^2; acquisition parameter βk+1 _k+1; evaluation budget M. 2: Updated parameter θk+1 _k+1. 3: Let k=[V^D(θj)]j≤ky_k=[ V_D( _j)]_j≤ k and [Kk]ij=κ(θi,θj)[K_k]_ij=κ( _i, _j). 4: Compute Wk=(Kk+σξ2I)−1W_k=(K_k+ _ξ^2I)^-1. 5: For each candidate θ, let k(θ)=[κ(θ,θj)]j≤kk_k(θ)=[κ(θ, _j)]_j≤ k and compute μk(θ) _k(θ) =k(θ)⊺Wkk, =k_k(θ) 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $W_k\,y_k, σk(θ) _k(θ) =κ(θ,θ)−k(θ)⊺Wkk(θ). = κ(θ,θ)-k_k(θ) 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $W_k\,k_k(θ)\,. 6: θk+1=argmaxθ∈Θ(μk(θ)+βk+1σk(θ)) _k+1= argmax_θ∈ ( _k(θ)+ _k+1\, _k(θ) ). 7: Estimate V^D(θk+1) V_D( _k+1) using M rollout episodes. 8: Append (θk+1,V^D(θk+1))( _k+1, V_D( _k+1)) to ℋk+1H_k+1. 9: return θk+1 _k+1. 4 Convergence of Inner Soft Q-Learning Before analyzing the outer loop, we establish that the inner step of Algorithm 1 is well-founded: soft Q-learning converges almost surely to a well-defined fixed point even though the internal state process is not Markovian (because ρ has arbitrary memory). The key insight, formalized below, is that the non-Markovian noise term vanishes in expectation under the stationary measure induced by πb _b, and thus the iteration effectively tracks a Markovian ODE. 1Almost-sure convergence of soft Q-learning. Let Assumption 3 hold and let the learning rates αn\ _n\ satisfy the Robbins–Monro conditions ∑nαn=∞ _n _n=∞ and ∑nαn2<∞ _n _n^2<∞. Define the stationary expected reward and transition induced by πb _b and fθf_θ: r¯θ(s,a) r_θ(s,a) =πb,fθ[r(s,a,o)], =E_ _b,f_θ\! [r(s,a,o) ], (5) P¯θ(s′|s,a) P_θ(s |s,a) =πb,fθ[fθ(s′|s,a,o)]. =E_ _b,f_θ\! [f_θ(s |s,a,o) ]. (6) Then, the soft Q-learning iterates Qn+1(s,a)=Qn(s,a)+αn 1Sn=s,An=a[rn+γτlog∑a′expQn(Sn+1,a′)τ−Qn(s,a)] splitQ_n+1(s,a)\;&=\;Q_n(s,a)+ _n\,1_\S_n=s,\,A_n=a\\! [r_n\\ &+γ\,τ \! _a \! Q_n(S_n+1,a )τ-Q_n(s,a) ] split (7) converge almost surely to the unique fixed point Qθ⋆Q _θ satisfying Qθ⋆(s,a)=r¯θ(s,a)+γ∑s′P¯θ(s′|s,a)τlog∑a′expQθ⋆(s′,a′)τ.Q _θ(s,a)= r_θ(s,a)+γ _s P_θ(s |s,a)\,τ \! _a \! Q _θ(s ,a )τ. (8) The induced soft-greedy policy is π^θ(a|s)∝exp(Qθ⋆(s,a)/τ) π_θ(a|s) (Q _θ(s,a)/τ). Proof. Decompose the update in (7) as Qn+1(s,a)=Qn(s,a)+αn[Fs,a(Qn)+ζns,a+Mn+1s,a],Q_n+1(s,a)=Q_n(s,a)+ _n\! [F^s,a(Q_n)+ζ^s,a_n+M^s,a_n+1 ], where Fs,a(Q)F^s,a(Q) is the expected soft Bellman residual under (r¯θ,P¯θ)( r_θ, P_θ): Fs,a(Q) F^s,a(Q) =Sn=s,An=a[r¯θ(s,a)+ =1_\S_n=s,A_n=a\\! [ r_θ(s,a)+ γ∑s′P¯θ(s′|s,a)τlog∑a′eQ(s′,a′)/τ−Q(s,a)]; γ _s P_θ(s |s,a)\,τ \! _a e^Q(s ,a )/τ-Q(s,a) ]; ζns,aζ^s,a_n captures the non-Markovian correction ζns,a ζ^s,a_n =Sn=s,An=a[[rn|on,an]− =1_\S_n=s,A_n=a\ [E[r_n|o^n,a^n]- r¯θ(s,a)+γ∑s′(P(Sn+1=s′|on,an)−CLOSE r_θ(s,a)+γ\! _s \! (P(S_n+1=s |o^n,a^n)- P¯θ(s′|s,a))τlog∑a′eQn(s′,a′)/τ]; P_θ(s |s,a) )τ \! _a e^Q_n(s ,a )/τ ]; and Mn+1s,aM^s,a_n+1 is a martingale difference sequence with bounded increments (since rewards are bounded by RmaxR_ ). Under the stationary measure π~(s,a)>0 π(s,a)>0 (Assumption 3), integrating ζns,aζ^s,a_n over the history y=(on,an)y=(o^n,a^n) gives zero: ∫π~(y)ζs,a(Q,y)=0∀(s,a), π(dy)\,ζ^s,a(Q,y)=0 ∀\,(s,a), because P¯θ(s′|s,a)=π~[P(Sn+1=s′|on,an)∣Sn=s,An=a] P_θ(s |s,a)=E_ π[P(S_n+1=s |o^n,a^n) S_n=s,A_n=a] by definition of the stationary averages in (6). Hence, the non-Markovian noise vanishes in expectation under the stationary measure. Standard stochastic approximation theory [3] then implies that Qn\Q_n\ almost surely tracks the ODE Q˙=∑s,aπ~(s,a)Fs,a(Q) Q= _s,a π(s,a)\,F^s,a(Q). The operator underlying Fs,aF^s,a is the soft Bellman operator with temperature τ>0τ>0, which is a γ-contraction in ℓ∞ _∞; see, e.g., [9]. Hence the ODE is globally asymptotically stable at the unique fixed point Qθ⋆Q _θ of (8), giving Qn→a.s.Qθ⋆Q_n a.s.Q _θ. ∎ Remark 1. Theorem 1 is a statement about the surrogate chain (r¯θ,P¯θ)( r_θ, P_θ): the iteration converges, and π^θ π_θ is soft-optimal for that chain. It does not by itself certify that π^θ π_θ is near-optimal for the environment. Two gaps separate the two. The first is the temperature, which biases the soft-optimal policy away from the greedy one by at most τlog||/(1−γ)τ |A|/(1-γ) in value; this gap is under the designer’s control and is the price paid for the smoothness of θ↦π^θ π_θ that Section 5 requires. The second is representational, and is the essential one: π^θ π_θ acts on sts_t rather than on the history, so it can be no better than the best policy the compression fθf_θ admits, and (r¯θ,P¯θ)( r_θ, P_θ) are themselves averages taken under πb _b. Bounding this second gap requires structure that a general non-Markovian environment does not provide. When the environment is a POMDP and fθf_θ is a filter whose prediction error contracts, filter-stability arguments bound the loss in value by the expected filtering error accumulated over the effective horizon 1/(1−γ)1/(1-γ) [11, 17], and in that regime π^θ π_θ is near-optimal in the usual sense. This also locates the result relative to prior work. The closest antecedent is [11], which fixes a finite-window memory as the agent state and establishes both convergence and, under filter stability, near-optimality of the learned policy. Here the agent state is instead the output of a parametrized, designable kernel fθf_θ, so the surrogate chain and hence the limit Qθ⋆Q _θ move with θ, and the argument must hold uniformly over the family fθ∈Θ\f_θ\_θ∈ ; what the proof isolates is that the non-Markovian correction ζns,aζ^s,a_n integrates to zero under the stationary measure for every θ, and it is this uniformity that makes the outer problem well posed. It is precisely because the representational gap depends on θ, and is untouched by the inner loop, that we treat the choice of θ as an optimization problem in its own right. Theorem 1 establishes that the inner step of Algorithm 1 converges almost surely to a well-defined fixed point Qθ⋆Q _θ, yielding a policy π^θ π_θ with which the agent can act in the non-Markovian environment for any fixed θ. However, this addresses only the inner problem, and the outer question (which θ to use) is still to be addressed. While Algorithm 1 provides a general iterative procedure for adapting θ, without further structure on the environment it is difficult to characterize the quality of the stationary points it reaches. In what follows, we restrict the environment to be a POMDP (Assumption 4) and analyze the properties of the transition parameters obtained by running Algorithm 1 in this setting. 5 Theoretical Guarantees under a POMDP Environment The convergence results in Section 4 hold for an arbitrary non-Markovian environment. To prove any structural properties for the stationary points of VD(θ)V_D(θ), such as Lipschitzness of the gradient, we need additional structure on the environment. We now assume that it is a Partially Observed Markov Decision Process (POMDP), which captures most practically relevant settings while enabling sharper analysis. 4POMDP environment. There exist a finite latent state space X, a transition kernel P(x′|x,a)P(x |x,a), and an emission kernel O(o|x)O(o|x) such that xt+1∼P(⋅∣xt,at),ot+1∼O(⋅∣xt+1),x_t+1 P(· x_t,a_t), o_t+1 O(· x_t+1), with the agent’s internal state evolving via st+1∼fθ(⋅∣st,at,ot+1)s_t+1 f_θ(· s_t,a_t,o_t+1). Under Assumption 4, the joint process (xt,st)(x_t,s_t) is Markovian, even though the observations and internal states alone are not. This latent Markov structure is the key that allows us to express VD(θ)V_D(θ) as the value of a well-defined joint Markov chain and then differentiate it. 5.1 Lipschitz Gradient of the Outer Objective Our goal is to show that ∇θVD(θ) _θV_D(θ) is Lipschitz continuous, which is the regularity condition needed for both convergence proofs that follow. Establishing this requires bounding the first and second derivatives of VDV_D with respect to θ, which we build up in two lemmas: one for the quantities (r¯θ,P¯θ)( r_θ, P_θ) defined by the behavioral data, and another one for the closed-loop joint model under the optimized policy. 2Smooth stationary averages. Under Assumptions 2, 3, and 4, there exist finite constants Cr¯,1,Cr¯,2,CP¯,1,CP¯,2C_ r,1,C_ r,2,C_ P,1,C_ P,2 such that for all s,s′∈s,s , a∈a , and θ∈Θθ∈ : ‖∇θr¯θ(s,a)‖2 \| _θ r_θ(s,a)\|_2 ≤Cr¯,1, ≤ C_ r,1, ‖∇θ2r¯θ(s,a)‖2 \|∇^2_θ r_θ(s,a)\|_2 ≤Cr¯,2, ≤ C_ r,2, ‖∇θP¯θ(s′|s,a)‖2 \| _θ P_θ(s |s,a)\|_2 ≤CP¯,1, ≤ C_ P,1, ‖∇θ2P¯θ(s′|s,a)‖2 \|∇^2_θ P_θ(s |s,a)\|_2 ≤CP¯,2. ≤ C_ P,2. Proof. Let =×Z=X×S and z=(x,s)z=(x,s). Under πb _b, fθf_θ, and the POMDP dynamics (P,O)(P,O), the joint process on Z is a Markov chain with transition kernel Pjt(z′|z)=∑aπb(a|s)P(x′|x,a)∑oO(o|x′)fθ(s′|s,a,o).P_jt(z |z)= _a _b(a|s)\,P(x |x,a) _oO(o|x )\,f_θ(s |s,a,o). By Assumption 3 this chain is ergodic with unique stationary distribution dθd_θ, satisfying dθ⊺=dθ⊺Pjtd_θ 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $=d_θ 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $P_jt. Let Zθ=(I−Pjt+dθ⊺)−1Z_θ=(I-P_jt+1d_θ 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $)^-1 be the fundamental matrix. Differentiating the stationarity equation gives ∇θdθ⊺=dθ⊺(∇θPjt)Zθ. _θd_θ 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $=d_θ 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $( _θP_jt)Z_θ. By Assumption 2, ‖∇θfθ‖2≤Cf,1\| _θf_θ\|_2≤ C_f,1, and thus ‖∇θPjt‖2\| _θP_jt\|_2 is bounded. Since Z is finite and the chain is ergodic, ‖Zθ‖\|Z_θ\| is bounded by a constant proportional to the mixing time, yielding a constant Cd,1C_d,1 with ∑x‖∇θdθ(x,s)‖2≤Cd,1 _x\| _θd_θ(x,s)\|_2≤ C_d,1 for all s. Define the conditional observation weight wθ(o|s,a)=Nθ(o,s,a)/Dθ(s)w_θ(o|s,a)=N_θ(o,s,a)/D_θ(s), where Dθ(s)=∑xdθ(x,s)D_θ(s)= _xd_θ(x,s) and Nθ(o,s,a)=∑xdθ(x,s)∑x′P(x′|x,a)O(o|x′)N_θ(o,s,a)= _xd_θ(x,s) _x P(x |x,a)O(o|x ). Differentiating the numerator and the denominator separately gives ‖∇θDθ(s)‖2≤Cd,1\| _θD_θ(s)\|_2≤ C_d,1 and ‖∇θNθ(o,s,a)‖2≤Cd,1\| _θN_θ(o,s,a)\|_2≤ C_d,1. Applying the quotient rule with Dθ(s)≥μminD_θ(s)≥ _ (Assumption 3): ‖∇θwθ(o|s,a)‖2≤2Cd,1μmin≜Cw,1.\| _θw_θ(o|s,a)\|_2\;≤\; 2\,C_d,1 _ \; \;C_w,1. Since r¯θ(s,a)=∑owθ(o|s,a)r(s,a,o) r_θ(s,a)= _ow_θ(o|s,a)\,r(s,a,o), and |r(⋅)|≤Rmax|r(·)|≤ R_ : ‖∇θr¯θ(s,a)‖2≤||Cw,1Rmax≜Cr¯,1.\| _θ r_θ(s,a)\|_2\;≤\;|O|\,C_w,1\,R_ \; \;C_ r,1. Since P¯θ(s′|s,a)=∑owθ(o|s,a)fθ(s′|s,a,o) P_θ(s |s,a)= _ow_θ(o|s,a)\,f_θ(s |s,a,o), the product rule and the fact that ∑ofθ(s′|s,a,o) _of_θ(s |s,a,o) and ∑owθ(o|s,a) _ow_θ(o|s,a) each equal 11 lead to ‖∇θP¯θ(s′|s,a)‖2≤Cw,1+Cf,1≜CP¯,1.\| _θ P_θ(s |s,a)\|_2\;≤\;C_w,1+C_f,1\; \;C_ P,1. The second-derivative bounds Cr¯,2C_ r,2 and CP¯,2C_ P,2 follow by differentiating each expression above once more. Assumption 2 supplies ‖∇θ2fθ‖2≤Cf,2\|∇^2_θf_θ\|_2≤ C_f,2, which propagates through PjtP_jt, dθd_θ, wθw_θ, and finally r¯θ r_θ and P¯θ P_θ by iterated application of the product and quotient rules. ∎ Lemma 2 controls how the stationary averages r¯θ r_θ and P¯θ P_θ change as θ varies. The next lemma lifts this to the closed-loop joint model—the reward and transition seen by the joint process (xt,st)(x_t,s_t) when the agent follows the optimized policy π^θ π_θ. The key step is propagating the θ-dependence of π^θ π_θ through the soft Bellman equation. 3Smooth closed-loop model. Define the joint reward and transition under the closed-loop system (fθ,π^θ)(f_θ, π_θ): rθ(z) r^θ(z) =∑a,o,x′π^θ(a|s)P(x′|x,a)O(o|x′)r(s,a,o), = _a,o,x π_θ(a|s)\,P(x |x,a)\,O(o|x )\,r(s,a,o), Pθ(z′|z) P^θ(z |z) =∑a,oπ^θ(a|s)P(x′|x,a)O(o|x′)fθ(s′|s,a,o). = _a,o π_θ(a|s)\,P(x |x,a)\,O(o|x )\,f_θ(s |s,a,o). Under Assumptions 1–4, there exist finite constants Cr,1,Cr,2,CP,1,CP,2C_r,1,C_r,2,C_P,1,C_P,2 such that for all z,z′∈z,z and θ∈Θθ∈ : ‖∇θrθ(z)‖2≤Cr,1,‖∇θPθ(z′|z)‖2≤CP,1,\| _θr^θ(z)\|_2≤ C_r,1, \| _θP^θ(z |z)\|_2≤ C_P,1, and the same bounds hold for second derivatives with constants Cr,2C_r,2 and CP,2C_P,2. Proof. Since P and O are fixed (independent of θ), bounding ‖∇θrθ‖\| _θr^θ\| and ‖∇θPθ‖\| _θP^θ\| reduces to bounding ‖∇θπ^θ(a|s)‖2\| _θ π_θ(a|s)\|_2. Since π^θ(a|s)∝exp(Qθ⋆(s,a)/τ) π_θ(a|s) (Q _θ(s,a)/τ) (with temperature τ>0τ>0), the chain rule through the softmax gives ‖∇θπ^θ(a|s)‖2≤2τBQ,BQ≜maxs,a‖∇θQθ⋆(s,a)‖2.\| _θ π_θ(a|s)\|_2\;≤\; 2τ\,B_Q, B_Q\; \; _s,a\| _θQ _θ(s,a)\|_2. To bound BQB_Q, differentiate the soft Bellman equation (8) implicitly with respect to θ: ∇θQθ⋆(s,a) _θQ _θ(s,a) =∇θr¯θ(s,a)+γ∑s′[∇θP¯θ(s′|s,a)Vθ⋆(s′) = _θ r_θ(s,a)+γ _s \! [ _θ P_θ(s |s,a)\,V _θ(s ) +P¯θ(s′|s,a)∑a′π^θ(a′|s′)∇θQθ⋆(s′,a′)], + P_θ(s |s,a) _a π_θ(a |s )\, _θQ _θ(s ,a ) ], where Vθ⋆(s′)=τlog∑a′exp(Qθ⋆(s′,a′)/τ)V _θ(s )=τ _a (Q _θ(s ,a )/τ). Taking the ℓ2 _2 norm, using |Vθ⋆(s′)|≤Rmax/(1−γ)|V _θ(s )|≤ R_ /(1-γ), and exploiting the contraction factor γ<1γ<1, yields the self-consistent bound BQ≤11−γ(Cr¯,1+γRmax||1−γCP¯,1)≜CQ,B_Q\;≤\; 11-γ\! (C_ r,1+ γ R_ \,|S|1-γ\,C_ P,1 )\; \;C_Q, which is finite by Lemma 2. This gives constants Cr,1C_r,1 and CP,1C_P,1. The second-derivative bounds Cr,2C_r,2 and CP,2C_P,2 follow by differentiating the soft Bellman equation once more with respect to θ. The resulting expression for ∇θ2Qθ⋆∇^2_θQ _θ involves ∇θ2r¯θ∇^2_θ r_θ, ∇θ2P¯θ∇^2_θ P_θ, ∇θπ^θ _θ π_θ, and ∇θQθ⋆ _θQ _θ—all of which are already bounded—together with the same γ-contraction argument, yielding a finite constant BQ,2B_Q,2. The bounds Cr,2C_r,2 and CP,2C_P,2 then follow by substitution. ∎ With both lemmas in hand, we can now establish the key structural property of VDV_D. 4Lipschitz gradient of VDV_D. Under Assumptions 1–4, the gradient ∇θVD(θ) _θV_D(θ) is Lipschitz continuous on Θ . Proof. Under Assumption 4, define the joint state zt=(xt,st)∈z_t=(x_t,s_t) . Under the closed-loop pair (fθ,π^θ)(f_θ, π_θ), the joint process is a Markov chain with transition PθP^θ and one-step reward rθr^θ from Lemma 3. The value function Vθ∈ℝ||V^θ ^|Z| satisfies the Bellman equation Vθ=rθ+γPθVθ⟹Vθ=(I−γPθ)−1rθ,V^θ=r^θ+γ\,P^θV^θ\;\; \;\;V^θ=(I-γ P^θ)^-1r^θ, and VD(θ)=μ0⊺VθV_D(θ)= _0 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $ 0.75346pt$ $V^θ for some initial distribution μ0∈Δ() _0∈ (Z). Since ‖Vθ‖∞≤Rmax/(1−γ)\|V^θ\|_∞≤ R_ /(1-γ), differentiating the Bellman equation gives ∇θVθ=(I−γPθ)−1(∇θrθ+γ(∇θPθ)Vθ). _θV^θ=(I-γ P^θ)^-1\! ( _θr^θ+γ\,( _θP^θ)\,V^θ ). Since ‖(I−γPθ)−1‖≤1/(1−γ)\|(I-γ P^θ)^-1\|≤ 1/(1-γ), Lemma 3 yields ‖∇θVθ‖≤Cr,1+γRmaxCP,1/(1−γ)1−γ≜CV,1.\| _θV^θ\|\;≤\; C_r,1+γ\,R_ \,C_P,1/(1-γ)1-γ\; \;C_V,1. Differentiating the Bellman equation once more: ∇θ2Vθ ∇^2_θV^θ =(I−γPθ)−1(∇θ2rθ+γ(∇θ2Pθ)VθCLOSE =(I-γ P^θ)^-1\! (∇^2_θr^θ+γ\,(∇^2_θP^θ)\,V^θ OPEN+2γ(∇θPθ)(∇θVθ)). +2γ\,( _θP^θ)\,( _θV^θ) ). Applying the second-derivative bounds from Lemma 3: ‖∇θ2Vθ‖≤Cr,2+γRmaxCP,2/(1−γ)+2γCP,1CV,11−γ. \|∇^2_θV^θ\|≤ C_r,2+γ\,R_ \,C_P,2/(1-γ)+2γ\,C_P,1\,C_V,11-γ. (9) Since μ0 _0 is a probability vector, defining the bound in 9 as L, we have ‖∇θ2VD(θ)‖≤L\|∇^2_θV_D(θ)\|≤ L uniformly over Θ , which implies that ∇θVD _θV_D is L-Lipschitz continuous. ∎ 5.2 Bounded Variance of the Monte Carlo Estimator In Algorithm 1 we estimate VD(θ)V_D(θ) by averaging M independent rollouts of horizon H. Since rewards are bounded, the truncated return has bounded variance and the estimator is sub-Gaussian—a property used in both convergence analyses below. 5Bounded-variance Monte Carlo estimator. For a fixed θ, let V^D(θ)=1M∑m=1MGm V_D(θ)= 1M _m=1^MG_m where Gm=∑t=0H−1γtrm(st,at,ot+1)G_m= _t=0^H-1γ^tr_m(s_t,a_t,o_t+1) is the discounted return of the m-th rollout. Then: (i) each GmG_m is bounded, with |Gm|≤Gmax≜Rmax(1−γH)/(1−γ)|G_m|≤ G_ R_ (1-γ^H)/(1-γ); (i) V^D(θ) V_D(θ) is an unbiased estimator of the H-truncated return, with conditional variance Var[V^D(θ)]≤Gmax2/M≤σ2/MVar[ V_D(θ)]≤ G_ ^2/M≤σ^2/M, where σ2≜Rmax2/(1−γ)2σ^2 R_ ^2/(1-γ)^2; and (i) V^D(θ) V_D(θ) is σ/Mσ/ M-sub-Gaussian, i.e. log[exp(λ(V^D(θ)−V^D(θ)))]≤λ2σ2/(2M) [ (λ( V_D(θ)-E V_D(θ)) ) ]≤λ^2σ^2/(2M) for all λ∈ℝλ . Proof. Part (i) is immediate from |r(⋅)|≤Rmax|r(·)|≤ R_ and the geometric series. For part (i), the M rollouts are independent, so Var[V^D(θ)]=Var[G1]/MVar[ V_D(θ)]=Var[G_1]/M, and G1G_1 being bounded by GmaxG_ , Popoviciu’s inequality gives Var[G1]≤Gmax2Var[G_1]≤ G_ ^2. Part (i) follows from Hoeffding’s lemma for bounded random variables: each Gm/MG_m/M takes values in an interval of length 2Gmax/M2G_ /M, so the average is σ/Mσ/ M-sub-Gaussian. ∎ Lemma 5 makes precise how the evaluation budget M and the discount factor γ jointly determine the estimation noise. In particular, σ2=Rmax2/(1−γ)2σ^2=R_ ^2/(1-γ)^2 grows as γ→1γ→ 1—reflecting the increasing variance of long-horizon returns—and shrinks at rate 1/M1/M as more rollouts are used. The sub-Gaussian property (part i) is what allows us to invoke GP-UCB confidence bounds in the Bayesian optimization analysis. 5.3 Convergence of Algorithm 1 with ZOO With the Lipschitz gradient established and the estimator noise characterized, we can now analyze the zeroth-order variant. The two-point estimator (4) introduces two sources of error: a bias from the finite smoothing radius δ and a variance from the Monte Carlo evaluations. The theorem below shows that both can be controlled, and balancing the two gives an (1/K)O(1/ K) convergence rate to a first-order stationary point of VDV_D. 6Convergence of ZOO variant. Under Assumptions 1–4, Algorithm 1 with Algorithm 2 as StepOptimize for K iterations with constant step size η≤1/(2L)η≤ 1/(2L) and constant smoothing radius δ>0δ>0 yields, 1K∑k=0K−1[‖Gη(θk)‖22]≤C1ηK+2Ld2σ2Mδ2+2δ2d2L2, 1K _k=0^K-1E [\|G_η( _k)\|_2^2 ]≤ C_1η K+ 2Ld^2σ^2Mδ^2+2δ^2d^2L^2, (10) where Gη(θ)=1η(θ−ΠΘ(θ+η∇VD(θ)))G_η(θ)= 1η(θ- _ (θ+η\,∇ V_D(θ))) is the gradient mapping, C1=2(V⋆−VD(θ0))C_1=2 (V -V_D( _0) ), V⋆=maxθ∈ΘVD(θ)V = _θ∈ V_D(θ), and d=dimΘd= . Choosing η=(K−1/2)η=O(K^-1/2) and δ=(K−1/4)δ=O(K^-1/4) gives 1K∑k[∥Gη(θk)∥22]=(K−1/2) 1K _kE[\|G_η( _k)\|_2^2]=O(K^-1/2). Proof. Define the spherically smoothed objective Vδ(θ)=u∼Uniform(d−1)[VD(θ+δu)]V_δ(θ)=E_u (S^d-1)[V_D(θ+δ u)]. By the Stokes’ theorem identity for uniform spherical smoothing [7], the two-point estimator satisfies [g^k∣θk]=∇Vδ(θk)E[ g_k _k]=∇ V_δ( _k). Due to L-Lipschitz gradient (Theorem 4), using standard techniques from gradient free optimization [6] and splitting g^k g_k into signal and noise and applying (a+b)2≤2a2+2b2(a+b)^2≤ 2a^2+2b^2, the bias and second moment bounds for the uniform spherical estimator are given by: ‖∇Vδ(θ)−∇VD(θ)‖2≤Ldδ2, \|∇ V_δ(θ)-∇ V_D(θ)\|_2≤ Ldδ2, [‖g^k‖22∣θk] [\| g_k\|_2^2 _k] ≤4d2‖∇VD(θk)‖22+d2σ2Mδ2+δ2d2L2, ≤ 4d^2\|∇ V_D( _k)\|_2^2+ d^2σ^2Mδ^2+δ^2d^2L^2, where σ2=Rmax2/(1−γ)2σ^2=R_ ^2/(1-γ)^2 (Lemma 5) accounts for the Monte Carlo evaluation noise. Applying the projected gradient ascent analysis of [8] to the L-smooth objective VDV_D over the convex compact set Θ , with Gη(θ)=1η(θ−ΠΘ(θ+η∇VD(θ)))G_η(θ)= 1η(θ- _ (θ+η∇ V_D(θ))) as the stationarity measure, telescoping over k=0,…,K−1k=0,…,K-1 yields the stated bound. Setting η=c1K−1/2η=c_1K^-1/2 and δ=c2K−1/4δ=c_2K^-1/4 balances all three terms at (K−1/2)O(K^-1/2). ∎ 5.4 Convergence of Algorithm 1 with Bayesian Optimization The ZOO variant makes no assumption on the global structure of VDV_D and consequently converges only to a first-order stationary point. By contrast, the BO variant exploits the smoothness of VDV_D, captured by its membership in a Reproducing Kernel Hilbert Space, to converge to the global optimum. This comes at the cost of a stronger parametrization requirement (for example, convex combination of base kernels) and the sub-Gaussian noise model, both of which we make precise below. For the convex-combination parameterization, the following lemma verifies that the structural assumptions of the paper hold automatically, and moreover that VDV_D is infinitely differentiable, the regularity needed for RKHS membership. 7Convex combination kernel. Let fθ=∑i=1Nθifif_θ= _i=1^N _if_i with θ∈Θθ∈ the standard (N−1)(N-1)-simplex, and suppose each base kernel fi>0f_i>0 induces an ergodic joint chain on Z. Then: (i) fθf_θ satisfies Assumptions 1–3 for all θ∈Θθ∈ , with a uniform lower bound μmin>0 _ >0. (i) VD∈C∞(Θ)V_D∈ C^∞( ), i.e. all derivatives of VDV_D are bounded on Θ . Proof. The simplex is compact (Assumption 1). Since fθf_θ is linear in θ, all derivatives of order ≥2≥ 2 vanish identically, and thus fθ∈C∞(Θ)f_θ∈ C^∞( ) with trivially bounded derivatives (Assumption 2). Positivity holds because θj>0 _j>0 for some j and fj>0f_j>0. For ergodicity, note that Pθ=∑iθiPi≥θjPjP_θ= _i _iP_i≥ _jP_j for any j with θj>0 _j>0. Since PjP_j is irreducible and aperiodic, for any z,z′z,z there exists l with (Pj)l(z′|z)>0(P_j)^l(z |z)>0, so (Pθ)l(z′|z)≥θjl(Pj)l(z′|z)>0(P_θ)^l(z |z)≥ _j^l(P_j)^l(z |z)>0 and aperiodicity is inherited. Hence PθP_θ is ergodic. The map θ↦dθ d_θ is continuous (since θ↦Pθ P_θ is linear and matrix inversion is continuous on invertibles). The function D(s,θ)=∑xdθ(x,s)D(s,θ)= _xd_θ(x,s) is therefore continuous on the compact simplex, and ergodicity ensures D(s,θ)>0D(s,θ)>0 everywhere. The Extreme Value Theorem yields μmin=mins,θD(s,θ)>0 _ = _s,θD(s,θ)>0. For part (i), since fθf_θ is linear in θ, the stationary averages r¯θ r_θ and P¯θ P_θ are C∞C^∞ in θ. The joint transition PθP^θ and reward rθr^θ are compositions of C∞C^∞ maps (the softmax with τ>0τ>0 is C∞C^∞, and Qθ⋆Q _θ is C∞C^∞ by implicit differentiation of the Bellman equation, which is well-conditioned because γ<1γ<1). The value function Vθ=(I−γPθ)−1rθV^θ=(I-γ P^θ)^-1r^θ inherits C∞C^∞ smoothness since the resolvent is an analytic function of PθP^θ. Hence VD∈C∞(Θ)V_D∈ C^∞( ). ∎ 8Global convergence of BO variant. Under Assumptions 1–4 and the convex combination parametrization of Lemma 7, the objective function satisfies VD∈ℋκV_D _κ with ‖VD‖κ≤B<∞\|V_D\|_κ≤ B<∞. Setting βk=B+σM2(γk−1+1+ln(1/ε)) _k=B+ σ M 2( _k-1+1+ (1/ )) (with σ2=Rmax2/(1−γ)2σ^2=R_ ^2/(1-γ)^2 from Lemma 5), the cumulative regret of Algorithm 1 with Algorithm 3 as StepOptimize satisfies, with probability at least 1−ε1- : RK=∑k=1K(VD(θ⋆)−VD(θk))≤(KβKγK),R_K= _k=1^K (V_D(θ )-V_D( _k) )\;≤\;O\! ( K\, _K\, _K ), where γK _K is the maximum information gain of κ on Θ . Since the Matérn-5/25/2 kernel has sublinear information gain (γK=o(K) _K=o(K)), average regret RK/K→0R_K/K→ 0 as K→∞K→∞, guaranteeing convergence to the global optimum θ⋆θ . Proof. The Matérn-5/25/2 kernel κ on ℝNR^N has a reproducing kernel Hilbert space norm-equivalent to the Sobolev space H2.5+N/2(ℝN)H^2.5+N/2(R^N). By Lemma 7(i), VD∈C∞(Θ)V_D∈ C^∞( ) with all derivatives bounded on the compact set Θ , so VDV_D admits a compactly supported C∞C^∞ extension V~D V_D to ℝNR^N. Any such extension lies in H2.5+N/2(ℝN)H^2.5+N/2(R^N), and hence in ℋκH_κ. Since the RKHS of κ restricted to Θ consists of the restrictions of functions in ℋκH_κ, with norm no larger than that of any extension, we obtain ‖VD‖κ≤‖V~D‖ℋκ≜B<∞\|V_D\|_κ≤\| V_D\|_H_κ B<∞. To prove the regret bound, notice that by Lemma 5(i), the evaluation noise ξ=V^D(θ)−VD(θ)ξ= V_D(θ)-V_D(θ) is (σ/M)(σ/ M)-sub-Gaussian. With VD∈ℋκV_D _κ and sub-Gaussian noise, the standard conditions for GP-UCB [16] are satisfied. With the chosen βk _k, the confidence intervals |VD(θ)−μk−1(θ)|≤βkσk−1(θ)|V_D(θ)- _k-1(θ)|≤ _k\, _k-1(θ) hold with probability at least 1−ε1- uniformly over Θ and k≥1k≥ 1. The UCB acquisition ensures that θk _k maximizes the upper confidence bound, meaning μk−1(θk)+βkσk−1(θk)≥μk−1(θ⋆)+βkσk−1(θ⋆) _k-1( _k)+ _k\, _k-1( _k)≥ _k-1(θ )+ _k\, _k-1(θ ). Conditioned on the high-probability event that VD(θ)∈[μk−1(θ)±βkσk−1(θ)]V_D(θ)∈[ _k-1(θ)± _k _k-1(θ)] for all θ, this gives an instantaneous regret of rk≤2βkσk−1(θk)r_k≤ 2 _k\, _k-1( _k). Summing over K iterations and applying the Cauchy–Schwarz inequality bounds the cumulative predictive standard deviations by KγK K _K, yielding the cumulative regret RK≤(KβKγK)R_K ( K _K _K). For a Matérn-5/25/2 kernel on a domain of effective dimension N−1N-1, the maximum information gain is bounded by γK=(K(N−1)N5+(N−1)NlogK) _K=O (K (N-1)N5+(N-1)N K ) [16]. Because the exponent is strictly less than 1 for any finite N, γK=o(K) _K=o(K) and the average regret RK/K→0R_K/K→ 0. Consequently, the simple regret SK=mink≤K(VD(θ⋆)−VD(θk))≤RK/K→0S_K= _k≤ K(V_D(θ )-V_D( _k))≤ R_K/K→ 0, establishing exact asymptotic convergence to the global optimum θ⋆θ . ∎ While Theorem 8 guarantees exact convergence because VD∈C∞V_D∈ C^∞, the repeated application of the chain rule through the Bellman matrix inversion (I−γPθ)−1(I-γ P^θ)^-1 implies that the theoretical RKHS norm B scales aggressively with the number of base kernels N. 6 Numerical Experiments We illustrate the practical utility of adaptive agent design in a non-Markovian setting, analyzing how structural choices over the internal kernels strongly dictate bounding limits on optimization and capacity. Our continuous routing environment utilizes target observation delays, defining non-Markovian tracking properties mathematically. The observation space is =0,1,2,3O=\0,1,2,3\ and action space is =0,1,2A=\0,1,2\. When the agent is initialized or completes a cycle, the environment stochastically transitions to a true hidden target state c∈0,1,2c∈\0,1,2\ sampled uniformly. At the start of the sequence, the environment emits the true objective o=co=c. For all subsequent interim steps, prior to a routing junction, the environment exclusively outputs the null observation o=3o=3. The agent must execute its internal transition rules recursively over the sequence to match its ultimate action a against the hidden target c. The reward matrix r(s,a,o)r(s,a,o) distributes biased, asymmetric payoffs to prevent trivial exploitation: choosing correctly yields r(⋅,a=0,⋅)=2.0r(·,a=0,·)=2.0, r(⋅,a=1,⋅)=1.0r(·,a=1,·)=1.0, and r(⋅,a=2,⋅)=0.5r(·,a=2,·)=0.5 correspondingly. Incorrect routing actions distribute penalties of −1.0-1.0 or −2.0-2.0. An optimal agent must mathematically compress its long-horizon observation history dynamically across its available finite states. We formulate candidate basis transition kernels fi(s′|s,a,o)f_i(s |s,a,o) mapping observations into the parametrized internal states recursively. Specifically, we set f0(s′=min(0,|S|−1)|s,a,o=0)=1.0f_0(s = (0,|S|-1)|s,a,o=0)=1.0, f1(s′=min(1,|S|−1)|s,a,o=1)=1.0f_1(s = (1,|S|-1)|s,a,o=1)=1.0, and f2(s′=min(2,|S|−1)|s,a,o=2)=1.0f_2(s = (2,|S|-1)|s,a,o=2)=1.0. Null observations o=3o=3 maintain the identity transition. The adaptive agent transition model fθf_θ is defined as the strict convex combination of these basis candidate components: fθ(s′|s,a,o)=∑i=1Kθifi(s′|s,a,o)f_θ(s |s,a,o)= _i=1^K _if_i(s |s,a,o) parametrized along the probability simplex. 6.1 Landscape Geometry and Optimizer Performance We bound our empirical analysis utilizing K=3K=3 distinct basis components (f0,f1,f2f_0,f_1,f_2) mapped across |S|=2|S|=2 available internal states. By scanning the 2-degrees-of-freedom parametrized variables (θ0,θ1)( _0, _1) spanning θ∈Δ2θ∈ ^2, we calculate the continuous total reward bounds evaluated iteratively across independent episodes (Fig. 1). Figure 1: The evaluated total reward plot parameterized empirically over the fθf_θ convex combination simplex. Heavily penalized stochastic regions create strict isolation bounds. As logged in Table 1, local-gradient Zeroth-Order Optimization (ZOO) actively traps within sub-optimal fif_i compositions. Activating global Bayesian Optimization (BO) leverages statistical exploitation to securely bypass these gradient walls, isolating the best combinatorial parameters equivalent optimally to the finite exhaustive limit calculated. Table 1: Total Reward Optimizer Performance (|S|=2|S|=2, K=3K=3) Method Max Reward Grid Search (Theoretical Max) 0.474 Bayesian Optimization (BO) 0.474 Zeroth-Order Ascent (ZOO) 0.191 6.2 Impact of Kernel Parametrization We analyze how dynamically isolating the basis kernels fif_i determines the absolute global convergence maximum available structurally (Table 2). The base formulation of structurally divergent fif_i mappings provides fθf_θ strong capacity bounds. Reconstituting the dictionary fif_i completely using identically redundant copies (degenerate parameterization) uniformly eliminates all topological optimization potential, sealing maximum output equivalent strictly to identical combinations. Populating the candidate bases naively with strict independent uniform noise vectors immediately plummets the fθf_θ matrix directly into severely generalized negative penalties computationally independent of standard search limits, indicating the value of side information about “good” kernels to seed the agent design framework. Table 2: Total Reward Peak Objective across Parameter Bases Kernel Component Matrices Max Reward Orthogonal Baseline Candidates 0.474 Identical Degenerate Mappings 0.462 Uniform Pure Noise Kernels -0.453 6.3 Role of Exploratory Behavioral Policy Data collection fundamentally structures algorithm evaluation validity. Utilizing biased or deterministic behavioral selection mappings (πb _b) drastically minimizes the state-action data trajectory breadth compiled to the discrete inner-loop planner buffer (Table 3), algorithmically crippling the soft Q-learning estimates regardless of optimum candidate kernels fif_i. Applying identically uniform random exploration naively secures standard global bounds across limited dimensionalities inherently. Table 3: Effect of Directed Trajectory Policy πb _b Action Sampling Bias Max Reward Uniform (0.33,0.33,0.330.33,0.33,0.33) 0.489 Minor Metric Bias (0.6,0.2,0.20.6,0.2,0.2) 0.469 Severe Trajectory Bias (0.9,0.05,0.050.9,0.05,0.05) 0.448 6.4 State Capacity Bounds Finally, we illustrate mathematically how limiting the generalized internal memory cardinality bounds total configuration optimization potential irrespective of available fif_i elements iteratively applied. By evaluating fθ=∑i=13θifif_θ= _i=1^3 _if_i across sequentially scaling dimensions of available internal agent state sets |S||S|, we directly plot structural memory ceilings. Formally expanding the available capacity limits maps a direct continuous scaling improvement metric optimally over θ bounds (Fig. 2). The total reward generated strictly climbs linearly as the matrix expands functionality, precisely matching limits and completely flattening out for bounds |S|>3|S|>3 exactly as logically dictated by satisfying the true native 3-environment targets fully securely. Additional dimensionality provides objectively zero generalized mathematical tracking progression. Figure 2: Total empirical expected reward evaluated monotonically maximizing iteratively as the cardinality of the internal state space linearly expands to encompass the correct environment requirements inherently. 7 Conclusions In this paper, we considered the question of an agent optimizing its own transition kernel among a collection of agent states affected through its actions, playing against an unknown possibly non-Markovian environment. Given a parametrized set of transition kernels, we showed that for every choice of that parameter, a soft Q-iteration converges almost surely to the fixed point of a soft Bellman equation built from the stationary averages that the behavioral policy induces, and we delineated what separates the policy it yields from an optimal one. Then, we considered the question of optimizing the parameter choice through zeroth-order optimization and Bayesian optimization methods. For POMDP environments, we obtained convergence to stationary points and global sub-linear regret, respectively. There are several interesting directions for future research. Our current study only considers the case where the dataset obtained via a behavioral policy remains fixed throughout. When the agent is learning to act against an unknown environment, it can leverage the flexibility of using newly learned policies to collect further data. We want to analyze the performance of such an adaptive agent. In our analysis, the agent keeps the cardinality of the agent state space constant. In practice, the agent can even tweak that cardinality over time. We are keen to analyze the performance of such adaptation. Finally, our work only considers a simple agent acting against an unknown but stationary non-Markovian environment. We hope to study interactions between two or more such adaptive agents playing against a known/unknown dynamic environment. This takes an alternative view point for agents acting in partial information environment as opposed to the common information based approach [13], information compression [12] or persuasion [19, 18, 20, 21, 22]. References [AES25] A. Anjarlekar, S. R. Etesami, and R. Srikant (2025) Scalable policy-based rl algorithms for POMDPs. In The Thirty-Ninth Annual Conference on Neural Information Processing Systems, Cited by: §1. [AST65] K. J. Aström (1965) Optimal control of Markov processes with incomplete state information. Journal of Mathematical Analysis and Applications 10, p. 174–205. Cited by: §1. [BOR08] V. S. Borkar (2008) Stochastic approximation: a dynamical systems viewpoint. Vol. 100, Springer. Cited by: §4. [CSB+24] S. Chandak, P. Shah, V. S. Borkar, and P. Dodhia (2024) Reinforcement learning in non-Markovian environments. Systems & Control Letters 185, p. 105751. Cited by: §1. [DRZ22] S. Dong, B. V. Roy, and Z. Zhou (2022) Simple agent, complex environment: efficient reinforcement learning with agent states. Journal of Machine Learning Research 23 (255), p. 1–54. External Links: Link Cited by: §1. [DJW+15] J. C. Duchi, M. I. Jordan, M. J. Wainwright, and A. Wibisono (2015) Optimal rates for zero-order convex optimization: the power of two function evaluations. IEEE Transactions on Information Theory 61 (5), p. 2788–2806. Cited by: §5.3. [FKM04] A. D. Flaxman, A. T. Kalai, and H. B. McMahan (2004) Online convex optimization in the bandit setting: gradient descent without a gradient. arXiv preprint cs/0408007. Cited by: §5.3. [GL13] S. Ghadimi and G. Lan (2013) Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization 23 (4), p. 2341–2368. Cited by: §5.3. [HZA+18] T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine (2018) Soft actor-critic: off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Conference on Machine Learning, p. 1861–1870. Cited by: §4. [KLC98] L. P. Kaelbling, M. L. Littman, and A. R. Cassandra (1998) Planning and acting in partially observable stochastic domains. Artificial intelligence 101 (1-2), p. 99–134. Cited by: §1. [KY23] A. D. Kara and S. Yüksel (2023) Convergence of finite memory Q-learning for POMDPs and near optimality of learned policies under filter stability. Mathematics of Operations Research 48 (4), p. 2066–2093. External Links: Document Cited by: Remark 1, Remark 1. [MZM+20] W. Mao, K. Zhang, E. Miehling, and T. Başar (2020) Information state embedding in partially observable cooperative multi-agent reinforcement learning. In 2020 59th IEEE Conference on Decision and Control (CDC), p. 6124–6131. Cited by: §7. [NGL+13] A. Nayyar, A. Gupta, C. Langbort, and T. Başar (2013) Common information based Markov perfect equilibria for stochastic games with asymmetric information: finite games. IEEE Transactions on Automatic Control 59 (3), p. 555–570. Cited by: §7. [PGT+03] J. Pineau, G. Gordon, S. Thrun, et al. (2003) Point-based value iteration: an anytime algorithm for POMDPs. In Ijcai, Vol. 3, p. 1025–1032. Cited by: §1. [SM24] A. Sinha and A. Mahajan (2024) Agent-state based policies in POMDPs: beyond belief-state MDPs. In 2024 IEEE 63rd Conference on Decision and Control (CDC), p. 6722–6735. Cited by: §1. [SKK+09] N. Srinivas, A. Krause, S. M. Kakade, and M. Seeger (2009) Gaussian process optimization in the bandit setting: no regret and experimental design. arXiv preprint arXiv:0912.3995. Cited by: §5.4, §5.4. [S+22] J. Subramanian, A. Sinha, R. Seraj, and A. Mahajan (2022) Approximate information state for approximate planning and reinforcement learning in partially observed systems. Journal of Machine Learning Research 23 (12), p. 1–83. Cited by: §1, Remark 1. [VBB23] R. K. Velicheti, M. Bastopcu, and T. Başar (2023) Strategic information design in quadratic multidimensional persuasion games with two senders. In 2023 American Control Conference (ACC), p. 1716–1722. Cited by: §7. [VBB25a] R. K. Velicheti, M. Bastopcu, and T. Başar (2025) Value of information in games with multiple strategic information providers. IEEE Transactions on Automatic Control 70 (7), p. 4532–4547. Cited by: §7. [VBE+24] R. K. Velicheti, M. Bastopcu, S. R. Etesami, and T. Başar (2024) Learning how to strategically disclose information. In 2024 American Control Conference (ACC), p. 1604–1609. Cited by: §7. [VBB25b] R. K. Velicheti, S. Bose, and T. Başar (2025) Harnessing information in incentive design. In 2025 IEEE 64th Conference on Decision and Control (CDC), p. 7286–7291. Cited by: §7. [VBB26] R. K. Velicheti, S. Bose, and T. Başar (2026) Learning against a strategic agent in principal-agent games. In AIMS Workshop at the International Conference on Learning Representations (ICLR), Cited by: §7. [YB24] S. Yüksel and T. Başar (2024) Stochastic teams, games, and control under information constraints. Springer. Cited by: §1, §1.