Convergence and Regret of the Policy Gradient for Multi-Armed Bandits in Diffusion Environment Yanwei Jia Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, New Territories, Hong Kong SAR, [email protected]
Du Ouyang
arXiv:2607.29593v1 [cs.LG] 31 Jul 2026
Department of Mathematical Sciences, Tsinghua University, Beijing, Beijing 100084, China, [email protected]
This paper studies the policy gradient update for a multi-arm bandit problem in diffusion environment that is described by a stochastic differential equation (SDE) under the continuous-time reinforcement learning framework by Wang et al. (2020), Jia and Zhou (2022b). With the logit parameterization for the stochastic policy, we show that it converges almost surely to the optimal arm under an arbitrary constant learning rate. Furthermore, we derive the non-asymptotic regret upper bound when the constant learning rate is below a time-invariant threshold; and the regret bound has order 𝑂 (log 𝑇). We improve the analysis in Lattimore (2026a) for the same SDE by constructing a novel Lyapunov function and demonstrate the transparency of analyzing policy gradient using the tools in SDEs. In addition, the same Lyapunov function is also helpful in analyzing the discrete-time policy gradient algorithm. Key words: Multi-armed bandits, continuous-time reinforcement learning, policy gradient, SDEs, regret and convergence
1. Introduction The bandit problem (cf. Lattimore and Szepesvári 2020) is a classical model to describe a decision maker who sequentially selects one of multiple “arms”, collecting the associated random reward, and aims to maximize the expected reward. Predominantly, two classes of algorithms based on statistical principles have been extensively studied: upper confidence bound algorithm and Thompson sampling. By contrast, little attention has been paid to the gradient method, a generally applicable optimization principle, in bandit problems. Until recently, there is growing 1
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
2
theoretical interest in understanding the convergence and regret of policy gradient algorithm in bandit problems, see, e.g., Walton and Denisov (2023), Mei et al. (2023, 2024), Baudry et al. (2025), Lattimore (2026a,b). In this paper, we examine the policy gradient method for the multi-armed bandit (MAB) problem in a diffusion environment. Intuitively speaking, this is the most difficult situation for learning because incrementally, the noise is much larger than the signal (referred to as the “weak signal regime” in Kuang and Wager 2024). We work under the continuous-time reinforcement framework by Wang et al. (2020). With a commonly used logit parameterization for the choice probability of arm 𝑎 ∈ A = {1, · · · , 𝑑} given by exp(𝜙 (𝑎) ) 𝜋 (𝑎) (𝝓) = Í𝑑 , with 𝝅(𝝓) = (𝜋 (1) (𝝓), . . . , 𝜋 (𝑑) (𝝓)) ⊤ ∈ P 𝑑 , 𝝓 = (𝜙 (1) , . . . , 𝜙 (𝑑) ) ⊤ ∈ R𝑑 , ( 𝑗)) exp(𝜙 𝑗=1 Í where P 𝑑 := 𝒑 = ( 𝑝 (1) , . . . , 𝑝 (𝑑) ) ⊤ ∈ [0, 1] 𝑑 : 𝑑𝑎=1 𝑝 (𝑎) = 1 . Jia and Zhou (2022b) suggest the
resulting online, incremental (actor-critic) policy gradient update can be informally described by (see E-Companion EC.1 for the introduction) d𝛽𝑡 =𝛼𝑡 d𝑅𝑡( 𝐴𝑡 ) − 𝛽𝑡 d𝑡 , d𝝓𝑡 =ℓ𝑡 ∇𝝓 log 𝜋
( 𝐴𝑡 )
(𝝓𝑡 ) d𝑅𝑡( 𝐴𝑡 ) − 𝛽𝑡 d𝑡 = ℓ𝑡
𝑑 ∑︁
1 { 𝐴𝑡 =𝑎} (𝒆 𝑎 − 𝝅(𝝓𝑡 )) (d𝑅𝑡(𝑎) − 𝛽𝑡 d𝑡),
(1)
𝑎=1
where 𝒆 𝑎
= (0, · · · , 0, 1, 0, · · · , 0) ⊤ ∈ R𝑑 stands for the unit vector with 𝑎 -th entry 1; 𝐴
𝑡 ∼ 𝝅(𝝓 𝑡 ) is a
random draw; d𝑅𝑡( 𝐴𝑡 ) = 𝜇 ( 𝐴𝑡 ) d𝑡 + 𝜎 ( 𝐴𝑡 ) d𝐵𝑡( 𝐴𝑡 ) is the selected arm and its associated instantaneous 𝑑 are the mean and volatility reward; and 𝝁 = (𝜇 (1) , · · · , 𝜇 (𝑑) ) ⊤ ∈ R𝑑 , 𝝈 = (𝜎 (1) , · · · , 𝜎 (𝑑) ) ⊤ ∈ R++
of the reward rate of the each arm. Here, 𝛼𝑡 and ℓ𝑡 are the critic and actor learning rates respectively. With a constant learning rate for the policy ℓ𝑡 ≡ ℓ and under high-frequency sampling limit, Jia et al. (2026) show that the distribution of 𝝓𝑡 process can be described by the following well-posed stochastic differential equation (SDE):1 𝜙
d𝝓𝑡 = ℓ 𝑱(𝝅𝑡 ) 𝝁 d𝑡 + ℓ𝑮 𝝈 (𝝅𝑡 ) d𝑩𝑡 ,
𝝅𝑡 = 𝝅(𝝓𝑡 ),
(2)
where 𝑩 𝜙 is a standard 𝑑 -dimensional Brownian motion, and 𝑱(𝝅𝑡 ) = diag{𝝅𝑡 } − 𝝅𝑡 𝝅𝑡⊤ ∈ S+𝑑 , and o n √ √ 𝑮 𝝈 (𝝅) = ( 𝑰 − 𝝅𝒆 ⊤ ) diag 𝜎 (1) 𝜋 (1) , . . . , 𝜎 (𝑑) 𝜋 (𝑑) ∈ R𝑑×𝑑 , 𝒆 := (1, . . . , 1) ⊤ ∈ R𝑑 1 SDE (2) can also be viewed as the diffusion limit of the discrete-time policy gradient algorithm in the sense of Fan and
Glynn (2021), Kuang and Wager (2024), see E-Companion EC.2.
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
3
To understand the behavior of the policy gradient update, it suffices to examine the property of SDE (2). In this paper, we prove that, the policy gradient update (2) almost surely converges to the best arm under any arbitrary constant learning rate, and achieved 𝑂 (log 𝑇) order (instancedependent) regret upper bound when the learning rate is below a threshold that is determined by the gap in means of each arm and their volatilities. Under this condition, our regret upper bound holds for any finite time 𝑇 . The key analytical tool is to construct a suitable Lyapunov function that induces stabilizing behavior of the underlying process. With the help of Itô’s calculus, such verification becomes much easier. Furthermore, it turns out the same Lyapunov function is also helpful in analyzing the conventional discrete-time policy gradient algorithm. The problem we attacked in this paper has recently been studied in Lattimore (2026a), who obtained the similar regret upper bound and a regret lower bound (both of 𝑂 (log 𝑇) order) by analyzing the same SDE using a different method. We relax the conditions on the learning rate in Lattimore (2026a) and give a straightforward, unifying proof for both two-arm and multi-arm cases, and it is valid in both continuous and discrete time environment. Our method is also related to other recent analysis of policy gradient for MAB in the discrete time, such as Walton and Denisov (2023), Mei et al. (2023, 2024), Baudry et al. (2025), Lattimore (2026b). In particular, our results on the threshold of the learning rate to ensure logarithmic regret coincide with the conjecture on the maximum learning rate proposed in Baudry et al. (2025), which scales in 𝑂 ( 𝑑1 ) , where 𝑑 is the number of arms. Table 1 gives a comparison of the main results between this paper and these literature. In the following, Section 2 shows the main results on the regret and almost sure convergence of this SDE. The key construction of the Lyapunov function and the proof is presented. Section 3 makes concluding remarks. E-Companion contains the background of SDE (2) and explains where it comes from. We also provide more intuitive illustrations in E-Companion.
2. Main Results Unlike Lattimore (2026a) who analyzes the two-arm and multi-arm cases separately, we give a unifying account. The special case of two-arm is illustrated in E-Companion EC.5 to highlight several intuitions of the SDE (2) and the role of learning rate ℓ .
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
4 Table 1
Comparison of results on the policy-gradient for stochastic multi-armed bandits. The column
“Learning rate” summarizes the condition on the learning rate ℓ, where 𝑑 is the number of arms, 𝑇 and 𝑁 are the time horizon for continuous-time and discrete-time systems, respectively. The columns “a.s. conv.” and “Logarithmic regret” stands for the conclusion of the almost sure convergence and logarithmic expected regret, where “N/A” means no conclusions. Literature
Learning rate
a.s. conv.
Logarithmic regret
Remark
N/A ✓ ✓
✓ ✓ N/A
Non-asymptotic Non-asymptotic
State-dependent
✓
✓
Non-asymptotic
ℓ = 𝑂 (1/𝑑 3/2 ) Any constant ℓ Small constant ℓ ℓ ≤ 𝑂 (1/log(𝑑 𝑁 ) ) ℓ ≤ 𝑂 (1/𝑑)
✓ ✓ N/A N/A ✓
✓ N/A ✓ ✓ ✓
Nonexplicit constant in regret bound Pathwise asymptotic 𝑂 (log 𝑁 ) Two-arm Non-asymptotic Non-asymptotic
Panel A: Continuous time Lattimore (2026a) ℓ ≤ 𝑂 (1/log 𝑇 ) This paper ℓ ≤ 𝑂 (1/𝑑) Any constant ℓ Panel B: Discrete time Walton and Denisov (2023) Mei et al. (2023) Mei et al. (2024) Baudry et al. (2025) Lattimore (2026b) This paper
2.1. Logarithmic regret under small learning rate
We first establish a finite-time logarithmic expected-regret bound based on SDE (2). Assume throughout this subsection that arm 1 is the unique optimal arm, and put Δ𝑖 = 𝜇 (1) − 𝜇 (𝑖) > 0, Δmin = min2≤𝑖 ≤𝑑 Δ𝑖 , Δmax = max2≤𝑖 ≤𝑑 Δ𝑖 . Only the optimal arm is required to be unique; the
suboptimal arms may have equal means. Define the instantaneous regret rate and its expected h∫ i Í𝑑 𝑇 cumulative version by 𝑟 𝑡 = 𝜇 (1) − 𝝁⊤ 𝝅𝑡 = 𝑖=2 Δ𝑖 𝜋𝑡(𝑖) , and R𝑇 = E 0 𝑟 𝑡 d𝑡 , respectively. Denote 𝑠 𝑎 := 𝜎 (𝑎) , 𝑠 := max1≤𝑎≤𝑑 𝑠 𝑎 , 𝑠 𝑎𝑏 := 𝑠 𝑎 ∨ 𝑠 𝑏 , 1 ≤ 𝑎 < 𝑏 ≤ 𝑑. Furthermore, denote 𝑸𝝈 (𝝅) = 2
𝑮 𝝈 𝑮 𝝈⊤ = ( 𝑰 − 𝝅𝒆 ⊤ ) diag{𝜋 (1) 𝜎 (1) , . . . , 𝜋 (𝑑) 𝜎 (𝑑) }( 𝑰 − 𝝅𝒆 ⊤ ) ⊤ ∈ S+𝑑 . 2
2
Lemma 1. For every finite deterministic initial condition 𝝓0 , the SDE (2) has a unique nonexplosive strong solution. Moreover, 𝒆 ⊤ 𝝓𝑡 = 𝒆 ⊤ 𝝓0 for all 𝑡 ≥ 0 almost surely. Proof.
For every finite 𝝓, all softmax probabilities are strictly positive. The drift and volatility
of SDE (2) are global Lipschitz functions of 𝝓. They are also bounded because 𝝅 takes values in the Í probability simplex and ∥𝑮 𝝈 (𝝅) ∥ 2F = tr 𝑸𝝈 (𝝅) ≤ 𝑠 𝑑𝑎=1 𝜋 (𝑎) ∥𝒆 𝑎 − 𝝅∥ 22 = 𝑠 tr( 𝑱) ≤ 𝑠. Standard SDE theory (e.g., Karatzas and Shreve 1991, Chapter 5, Theorem 2.5) therefore gives a unique global strong solution. Furthermore, by direction calculation, 𝒆 ⊤ 𝑱 = 0⊤ and 𝒆 ⊤ 𝑮 𝝈 = 0⊤ . Multiplying (2) by 𝒆 ⊤ and integrating from 0 to 𝑡 gives the desired result.
□
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
5
Next, we shall repeatedly use the elementary identity ∑︁
𝒗 ⊤ 𝑱(𝝅)𝒘 =
𝜋 (𝑎) 𝜋 (𝑏) (𝑣 𝑎 − 𝑣 𝑏 ) (𝑤 𝑎 − 𝑤 𝑏 ),
𝒗, 𝒘 ∈ R𝑑 .
(3)
1≤𝑎<𝑏≤𝑑
To see this, expanding the right-hand side as one half of the corresponding double sum gives ! 𝑑 ! 𝑑 𝑑 ∑︁ ∑︁ ∑︁ (𝑎) (𝑎) (𝑏) 𝜋 𝑣𝑎𝑤𝑎 − 𝜋 𝑣𝑎 𝜋 𝑤 𝑏 = 𝒗 ⊤ 𝑱(𝝅)𝒘. 𝑎=1
𝑎=1
𝑏=1
Let 𝐼 = {2, . . . , 𝑑} be the set of suboptimal arm index. For every nonempty 𝐴 ⊆ 𝐼 , define ℎ 𝐴 (𝝓) =
Ö
𝑒𝜙
(𝑖) − 𝜙 (1)
𝑖∈ 𝐴
=
Ö 𝜋 (𝑖) 𝑖∈ 𝐴
𝜋 (1)
(4)
.
We first record an estimate on the covariance matrix useful for verifying Lyapunov function. Lemma 2. For every probability vector 𝝅 ∈ P 𝑑 and every 𝒗 ∈ R𝑑 , 𝒗 ⊤ 𝑸𝝈 (𝝅)𝒗 ≤
∑︁
𝜋 (𝑎) 𝜋 (𝑏) 𝑠 𝑎𝑏 (𝑣 𝑎 − 𝑣 𝑏 ) 2 .
(5)
1≤𝑎<𝑏≤𝑑
In particular, 𝑸𝝈 (𝝅) ⪯ 𝑠 𝑱(𝝅).
(6)
Í Proof Write 𝑣 = 𝝅 ⊤ 𝒗 . Then 𝒗 ⊤ 𝑸𝝈 (𝝅)𝒗 = 𝑑𝑎=1 𝜋 (𝑎) 𝑠 𝑎 (𝑣 𝑎 − 𝑣) 2 . Fix 𝐻 ⊆ {1, . . . , 𝑑} and let Í 𝑝 = 𝑎∈ 𝐻 𝜋 (𝑎) . Suppose that 0 < 𝑝 < 1. Denote 1 ∑︁ (𝑎) 1 ∑︁ (𝑎) 𝜋 𝑣𝑎, 𝑉𝐻 := 𝜋 (𝑣 𝑎 − 𝑚 𝐻 ) 2 , 𝑝 𝑎∈ 𝐻 𝑝 𝑎∈ 𝐻 1 ∑︁ (𝑎) 1 ∑︁ (𝑎) 𝜋 𝑣 𝑎 , 𝑉𝐻 𝑐 := 𝜋 (𝑣 𝑎 − 𝑚 𝐻 𝑐 ) 2 . 𝑚 𝐻 𝑐 := 1 − 𝑝 𝑎∈ 𝐻 𝑐 1 − 𝑝 𝑎∈ 𝐻 𝑐 𝑚 𝐻 :=
Since 𝑣 = 𝑝𝑚 𝐻 + (1 − 𝑝)𝑚 𝐻 𝑐 , ∑︁
𝜋 (𝑎) (𝑣 𝑎 − 𝑣) 2 = 𝑝𝑉𝐻 + 𝑝(1 − 𝑝) 2 (𝑚 𝐻 − 𝑚 𝐻 𝑐 ) 2 .
(7)
𝑎∈ 𝐻
On the other hand, separating the pairs inside 𝐻 from those crossing from 𝐻 to 𝐻 𝑐 gives ∑︁ 𝜋 (𝑎) 𝜋 (𝑏) 1 {𝑎∈ 𝐻 or 𝑏∈ 𝐻 } (𝑣 𝑎 − 𝑣 𝑏 ) 2 (8)
𝑎<𝑏
= 𝑝𝑉𝐻 + 𝑝(1 − 𝑝)𝑉
𝐻𝑐
+ 𝑝(1 − 𝑝) (𝑚 𝐻 − 𝑚
𝐻𝑐
2
) .
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
6
The right-hand side of (8) minus (7) equals 𝑝(1 − 𝑝)𝑉𝐻 𝑐 + 𝑝 2 (1 − 𝑝) (𝑚 𝐻 − 𝑚 𝐻 𝑐 ) 2 ≥ 0. Thus, ∑︁ ∑︁ 𝜋 (𝑎) (𝑣 𝑎 − 𝑣) 2 ≤ 𝜋 (𝑎) 𝜋 (𝑏) 1 {𝑎∈ 𝐻 or 𝑏∈ 𝐻 } (𝑣 𝑎 − 𝑣 𝑏 ) 2 . (9) 𝑎∈ 𝐻
𝑎<𝑏
The above inequality also holds when 𝑝 ∈ {0, 1}. For every 𝑥 ≥ 0, the indicator 1 { 𝑥 ≥𝑢} equals one for 𝑢 ∈ [0, 𝑥] and zero for 𝑢 > 𝑥 . Consequently, since 𝑠 𝑎𝑏 = 𝑠 𝑎 ∨ 𝑠 𝑏 , we can write ∫ ∞ 𝑠𝑎 = 1 {𝑠𝑎 ≥𝑢} d𝑢,
∫ ∞ 𝑠 𝑎𝑏 =
0
1 {𝑠𝑎 ≥𝑢 or 𝑠𝑏 ≥𝑢} d𝑢.
(10)
0
For each 𝑢 ≥ 0, set 𝐻𝑢 := {𝑎 : 𝑠 𝑎 ≥ 𝑢}. Applying the inequality (9) with 𝐻 = 𝐻𝑢 gives 𝑑 ∑︁
𝜋 (𝑎) 1 {𝑠𝑎 ≥𝑢} (𝑣 𝑎 − 𝑣) 2 ≤
𝑎=1
∑︁
𝜋 (𝑎) 𝜋 (𝑏) 1 {𝑠𝑎 ≥𝑢 or 𝑠𝑏 ≥𝑢} (𝑣 𝑎 − 𝑣 𝑏 ) 2 .
(11)
𝑎<𝑏
All terms in (11) are nonnegative, and both sums are finite. We may therefore integrate over 𝑢 ∈ [0, ∞) and interchange each sum with the integral. By (10), the integral of the left-hand side is ∫ ∞ ∑︁ 𝑑 𝑑 ∑︁ (12) 𝜋 (𝑎) 𝑠 𝑎 (𝑣 𝑎 − 𝑣) 2 = 𝒗 ⊤ 𝑸𝝈 (𝝅)𝒗. 𝜋 (𝑎) 1 {𝑠𝑎 ≥𝑢} (𝑣 𝑎 − 𝑣) 2 d𝑢 = 0
𝑎=1
𝑎=1
Similarly, the integral of the right-hand side is ∫ ∞ ∑︁ ∑︁ 𝜋 (𝑎) 𝜋 (𝑏) 1 {𝑠𝑎 ≥𝑢 or 𝑠𝑏 ≥𝑢} (𝑣 𝑎 − 𝑣 𝑏 ) 2 d𝑢 = 𝜋 (𝑎) 𝜋 (𝑏) 𝑠 𝑎𝑏 (𝑣 𝑎 − 𝑣 𝑏 ) 2 . 0
𝑎<𝑏
(13)
𝑎<𝑏
Integrating (11) and using (12)–(13) proves (5). Finally, 𝑠 𝑎𝑏 ≤ 𝑠 and (3) imply, for every 𝒗 ∈ R𝑑 , ∑︁ 𝜋 (𝑎) 𝜋 (𝑏) (𝑣 𝑎 − 𝑣 𝑏 ) 2 = 𝑠 𝒗 ⊤ 𝑱(𝝅)𝒗. 𝒗 ⊤ 𝑸𝝈 (𝝅)𝒗 ≤ 𝑠 𝑎<𝑏
This proves (6).
□
Theorem 1. Let 𝑑 ≥ 2 and let 𝝓0 be finite and deterministic. Assume that arm 1 is uniquely optimal. 2Δ Suppose 0 < ℓ < min2≤ 𝑗 ≤𝑑 𝑑𝑠1𝑗𝑗 . Define 𝑐 ℓ,𝝈 := min2≤ 𝑗 ≤𝑑 Δ 𝑗 − ℓ𝑑 2 𝑠1 𝑗 > 0. Denote 𝐾ℓ,𝝈 ℓ𝑠 𝑒 −𝑆0 /𝑑 ℓ2 𝑠 ⊤ , 𝑆0 = 𝒆 𝝓0 , 𝑎 ℓ,𝝈 = ℓΔmax + , (14) 𝐾ℓ,𝝈 = Δmax + , 𝐶ℓ,𝝈 = 2 𝑐 ℓ,𝝈 𝑑 2 and define the Lyapunov function 𝑉ℓ,𝝈 (𝝓) :=
∑︁ ∅≠𝐴⊆ 𝐼
| 𝐴| −1 𝐶ℓ,𝝈 ℎ 𝐴 (𝝓) =
1
𝑑 Ö
𝐶ℓ,𝝈 𝑖=2
1 + 𝐶ℓ,𝝈 𝑒
𝜙 (𝑖) − 𝜙 (1)
! −1 .
(15)
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
7
For the same fixed learning rate, for every 𝑇 ≥ 0, R𝑇 ≤
𝑑 Δ (𝑑 − 1) (𝑖) 1 ∑︁ max 𝑉ℓ,𝝈 (𝝓0 ). log 1 + 𝑎 ℓ,𝝈 𝑒 𝜙0 𝑇 + ℓ 𝑖=2 2ℓ𝑐 ℓ,𝝈
(16)
In particular, if 𝝓0 = 0, then ! ℓΔmax + 12 ℓ 2 𝑠 𝑑 −1 Δmax (𝑑 − 1) (1 + 𝐶ℓ,𝝈 ) 𝑑−1 − 1 R𝑇 ≤ . log 1 + 𝑇 + ℓ 𝑑 2ℓ𝑐 ℓ,𝝈 𝐶ℓ,𝝈
Proof
(17)
Let L𝝈 be the generator of (2). For 𝑓𝒗 (𝝓) = exp(𝒗 ⊤ 𝝓) , Lemma 2 and (3) imply L𝝈 𝑓𝒗 (𝝓) ℓ2 = ℓ𝒗 ⊤ 𝑱(𝝅) 𝝁 + 𝒗 ⊤ 𝑸𝝈 𝒗 𝑓𝒗 (𝝓) 2 ∑︁ ℓ2 2 (𝑎) (𝑏) (𝑎) (𝑏) ≤ 𝜋 𝜋 ℓ(𝑣 𝑎 − 𝑣 𝑏 ) (𝜇 − 𝜇 ) + 𝑠 𝑎𝑏 (𝑣 𝑎 − 𝑣 𝑏 ) . 2 𝑎<𝑏
(18)
Fix a nonempty 𝐴 ⊆ 𝐼 and write 𝑚 = | 𝐴| ≤ 𝑑 − 1. Define 𝒗 𝐴 ∈ R𝑑 by 𝑣 1𝐴 = −𝑚, 𝑣 𝑖𝐴 = 1 {𝑖 ∈ 𝐴} , 2 ≤ 𝑖 ≤ 𝑑. By (4), ℎ 𝐴 (𝝓) = exp((𝒗 𝐴) ⊤ 𝝓) . We examine the square bracket term in (18). The pair (1, 𝑗)
with 𝑗 ∈ 𝐴 has coefficient ℓ2 ℓ(𝑚 + 1) 2 (19) − ℓ(𝑚 + 1)Δ 𝑗 + (𝑚 + 1) 𝑠1 𝑗 = −ℓ(𝑚 + 1) Δ 𝑗 − 𝑠1 𝑗 ≤ −ℓ(𝑚 + 1)𝑐 ℓ,𝝈 , 2 2 where 𝑚 + 1 ≤ 𝑑 was used. If 𝑗 ∈ 𝐼 \ 𝐴, the analogous coefficient is −ℓ𝑚 Δ 𝑗 − ℓ𝑚 𝑠 ≤ −ℓ𝑚𝑐 ℓ,𝝈 . 1 𝑗 2
For a pair of suboptimal arms, the contribution vanishes when both indices belong to 𝐴 or both 2
lie outside 𝐴. If exactly one belongs to 𝐴, its coefficient is at most ℓ|𝜇 (𝑖) − 𝜇 ( 𝑗 ) | + ℓ2 𝑠𝑖 𝑗 ≤ ℓ𝐾ℓ,𝝈 . Consequently, L𝝈 ℎ 𝐴 ≤ − ℓ𝑐 ℓ,𝝈 ℎ 𝐴 𝜋
∑︁ ∑︁ ∑︁ ( 𝑗) (𝑖) 𝜋 + ℓ𝐾 ℎ (𝑚 + 1) 𝜋 + 𝑚 𝜋 (𝑖) 𝜋 ( 𝑗 ) . ℓ,𝝈 𝐴 𝑖∈ 𝐴 𝑖∈ 𝐴 𝑗 ∈ 𝐼\𝐴 𝑗 ∈ 𝐼\𝐴
(1)
(20)
To simplify notation within this calculation, write 𝑐 = 𝑐 ℓ,𝝈 , 𝐾 = 𝐾ℓ,𝝈 , 𝐶 = 𝐶ℓ,𝝈 . We next consider the upper bound L 𝜎 𝑉ℓ, 𝜎 ≤ 𝑃 + 𝑁 , where, due to (20), the possibly positive contribution is 𝑃 := ℓ𝐾
∑︁ ∅≠𝐴⊆ 𝐼
𝐶 | 𝐴| −1 ℎ 𝐴
∑︁ 𝑖∈ 𝐴 𝑗 ∈ 𝐼\𝐴
𝜋 (𝑖) 𝜋 ( 𝑗 ) ,
(21)
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
8
Í and the negative contribution (with the negative term 𝑚 𝑗 ∈ 𝐼\𝐴 𝜋 ( 𝑗 ) in (20) being relaxed to 0) is ∑︁ ∑︁ 𝑁 := −ℓ𝑐 (| 𝐴| + 1)𝐶 | 𝐴| −1 ℎ 𝐴 𝜋 (1) 𝜋 (𝑖) . (22) ∅≠𝐴⊆ 𝐼
𝑖∈ 𝐴
For a triple ( 𝐴, 𝑖, 𝑗) occurring in (21), set 𝐷 = 𝐴 ∪ { 𝑗 } and 𝑟 = |𝐷 | = | 𝐴| + 1. Since ℎ 𝐷 = ℎ 𝐴𝑒 𝜙
( 𝑗) − 𝜙 (1)
( 𝑗)
= ℎ 𝐴 𝜋𝜋 (1) , we have the identity ℎ 𝐴 𝜋 (𝑖) 𝜋 ( 𝑗 ) = ℎ 𝐷 𝜋 (1) 𝜋 (𝑖) .
(23)
Conversely, fix 𝐷 ⊆ 𝐼 with |𝐷 | = 𝑟 ≥ 2 and fix 𝑖 ∈ 𝐷 . Therefore, 𝑃 = ℓ𝐾
𝑑−1 ∑︁
∑︁
(𝑟 − 1)𝐶 𝑟 −2
ℎ 𝐷 𝜋 (1)
𝐷⊆𝐼 | 𝐷 |=𝑟
𝑟=2
∑︁
𝜋 (𝑖) .
(24)
𝑖 ∈𝐷
Grouping (22) by 𝑟 = |𝐷 | similarly gives 𝑁 = −ℓ𝑐
𝑑−1 ∑︁
(𝑟 + 1)𝐶 𝑟 −1
𝑟=1
∑︁
ℎ 𝐷 𝜋 (1)
𝐷⊆𝐼 | 𝐷 |=𝑟
∑︁
𝜋 (𝑖) .
(25)
𝑖 ∈𝐷
For every 𝑟 ≥ 2, the combined coefficient in (24) and (25) is ℓ𝐶 𝑟 −2 [𝐾 (𝑟 − 1) − 𝑐𝐶 (𝑟 + 1)] = ℓ𝐾𝐶 𝑟 −2 (𝑟 − 1) − (𝑟 + 1) = −2ℓ𝐾𝐶 𝑟 −2 ≤ 0,
(26)
where 𝑐𝐶 = 𝐾 by the provided condition (14). At level 𝑟 = 1, there is no positive term. Moreover, 𝜋 (𝑖) (1) (𝑖) 𝜋 𝜋 = (𝜋 (𝑖) ) 2 . (1) 𝜋 Í𝑑 Thus, the singleton level contributes exactly −2ℓ𝑐 𝑖=2 (𝜋 (𝑖) ) 2 , and every higher level is nonpositive ℎ {𝑖 } 𝜋 (1) 𝜋 (𝑖) =
by (26). We have therefore proved the global Lyapunov inequality L𝝈 𝑉ℓ,𝝈 (𝝓) ≤ −2ℓ𝑐 ℓ,𝝈
𝑑 ∑︁
(𝜋 (𝑖) ) 2 .
(27)
𝑖=2
To the desired finite-time regret bound, denote 𝜏𝑛 := inf{𝑡 ≥ 0 : ∥𝝓𝑡 ∥ 2 ≥ 𝑛}. By Lemma 1, 𝜏𝑛 ↑ ∞ almost surely. On [0, 𝑇 ∧ 𝜏𝑛 ] , the state remains in a compact set, and the stochastic integral in Itô’s formula for 𝑉ℓ,𝝈 is therefore a true martingale. Hence (27) gives ∫ 𝑇∧𝜏𝑛 L𝝈 𝑉ℓ,𝝈 (𝝓𝑡 ) d𝑡 0 ≤ E 𝑉ℓ,𝝈 (𝝓𝑇∧𝜏𝑛 ) = 𝑉ℓ,𝝈 (𝝓0 ) + E 0
≤ 𝑉ℓ,𝝈 (𝝓0 ) − 2ℓ𝑐 ℓ,𝝈 E
∫ 𝑇∧𝜏𝑛 ∑︁ 𝑑 0
𝑖=2
(𝜋𝑡(𝑖) ) 2 d𝑡.
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
9
Applying the monotone convergence theorem to the right-hand side, and first letting 𝑛 → ∞, and then letting 𝑇 → ∞; this proves "∫
𝑑 ∞ ∑︁
E 0
# (𝜋𝑡(𝑖) ) 2 d𝑡
≤
𝑖=2
𝑉ℓ,𝝈 (𝝓0 ) . 2ℓ𝑐 ℓ,𝝈
(28)
It remains to control the part of regret containing the best-arm probability. Fix 𝑖 ∈ 𝐼 and let (𝑖)
𝑌𝑖 (𝝓) = 𝑒 − 𝜙 . The gradient and Hessian of 𝑌𝑖 are −𝑌𝑖 𝒆 𝑖 and 𝑌𝑖 𝒆 𝑖 𝒆 ⊤ 𝑖 , respectively. Moreover, (6)
gives (𝑸𝝈 )𝑖𝑖 ≤ 𝑠𝐽𝑖𝑖 = 𝑠 𝜋 (𝑖) (1 − 𝜋 (𝑖) ). Itô’s formula therefore gives L𝝈𝑌𝑖 = 𝑌𝑖 ℓ𝜋
(𝑖)
⊤
(𝝁 𝝅 − 𝜇
(𝑖)
ℓ2 ℓ2 𝑠 (𝑖) ) + (𝑸𝝈 )𝑖𝑖 ≤ 𝑌𝑖 𝜋 ℓΔmax + , 2 2
where 𝝁⊤ 𝝅 − 𝜇 (𝑖) ≤ 𝜇 (1) − 𝜇 (𝑖) = Δ𝑖 ≤ Δmax . Writing 𝑍 (𝝓) =
Í𝑑
𝑗=1 𝑒
(29)
𝜙 ( 𝑗) , the softmax definition gives
𝑌𝑖 𝜋 (𝑖) = 1/𝑍 (𝝓) . By the Jensen’s inequality and Lemma 1, 𝑍 (𝝓𝑡 ) ≥ 𝑑
Î
( 𝑗) 𝑑 𝜙𝑡 𝑗=1 𝑒
1/𝑑
= 𝑑𝑒 𝑆0 /𝑑 .
Combining this inequality with (29) gives the pointwise bound L𝝈𝑌𝑖 (𝝓𝑡 ) ≤ 𝑎 ℓ,𝝈 . (𝑖)
By applying Itô’s formula on [0, 𝑡 ∧ 𝜏𝑛 ] , we obtain E𝑌𝑖 (𝝓𝑡∧𝜏𝑛 ) ≤ 𝑒 − 𝜙0 + 𝑎 ℓ,𝝈 𝑡. Since 𝜏𝑛 ↑ ∞ almost surely and 𝑌𝑖 ≥ 0, by letting 𝑛 → ∞, Fatou’s lemma gives (𝑖)
(𝑖)
E𝑒 − 𝜙𝑡 ≤ 𝑒 − 𝜙0 + 𝑎 ℓ,𝝈 𝑡.
(30)
The coefficients of (2) are bounded, so every coordinate of 𝝓𝑡 is integrable at any finite time. Í𝑑 (𝑖) Moreover, Lemma 1 gives 𝜙𝑇(1) − 𝜙0(1) = 𝑖=2 𝜙0 − 𝜙𝑇(𝑖) . By Jensen’s inequality and (30), E[𝜙𝑇(1) − 𝜙0(1) ] =
𝑑 ∑︁ 𝑖=2
𝑑 𝑑 (𝑖) ∑︁ (𝑖) ∑︁ (𝑖) (𝑖) (𝑖) E log 𝑒 𝜙0 𝑒 − 𝜙𝑇 ≤ log 𝑒 𝜙0 E𝑒 − 𝜙𝑇 ≤ log 1 + 𝑎 ℓ,𝝈 𝑒 𝜙0 𝑇 . 𝑖=2
𝑖=2
(31) 𝜙 Finally, the first coordinate of (2) satisfies d𝜙𝑡(1) = ℓ𝜋𝑡(1) 𝑟 𝑡 d𝑡 + ℓ𝒆 ⊤ 1 𝑮 𝝈 (𝝅 𝑡 ) d𝑩𝑡 . The stochastic
integrand is bounded, so its integral is square-integrable on every finite interval. Consequently, E[𝜙𝑇(1) − 𝜙0(1) ] = ℓE
∫ 𝑇 0
𝜋𝑡(1) 𝑟 𝑡 d𝑡.
(32)
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
10
Í𝑑 (𝑖) Denote 𝑢 𝑡 := 1 − 𝜋𝑡(1) = 𝑖=2 𝜋𝑡 . Since 𝑟 𝑡 ≤ Δmax 𝑢 𝑡 , the Cauchy–Schwarz inequality gives 𝑢 𝑡 𝑟 𝑡 ≤ Í𝑑 2 Δmax 𝑢 𝑡 ≤ Δmax (𝑑 − 1) 𝑖=2 (𝜋𝑡(𝑖) ) 2 . Using 𝑟 𝑡 = 𝜋𝑡(1) 𝑟 𝑡 + 𝑢 𝑡 𝑟 𝑡 , and then applying (28), (31), and (32),
we obtain ∫ 𝑇 R𝑇 = E
𝜋𝑡(1) 𝑟 𝑡 d𝑡 + E
∫ 𝑇
0
0
1 𝑢 𝑡 𝑟 𝑡 d𝑡 ≤ E[𝜙𝑇(1) − 𝜙0(1) ] + Δmax (𝑑 − 1)E ℓ ≤
𝑑 1 ∑︁
ℓ 𝑖=2
(𝑖)
log 1 + 𝑎 ℓ,𝝈 𝑒 𝜙0 𝑇 +
∫ 𝑇 ∑︁ 𝑑 0
(𝜋𝑡(𝑖) ) 2 d𝑡
𝑖=2
Δmax (𝑑 − 1) 𝑉ℓ,𝝈 (𝝓0 ). 2ℓ𝑐 ℓ,𝝈
This proves (16). If 𝝓0 = 0, then 𝑆0 = 0 and every ℎ 𝐴 (0) = 1. By the binomial theorem, 𝑉ℓ,𝝈 (0) = Í𝑑−1 𝑑−1 𝑚−1 (1+𝐶ℓ,𝝈 ) 𝑑−1 −1 . Substitution into (16) proves (17). □ 𝑚=1 𝑚 𝐶ℓ,𝝈 = 𝐶ℓ,𝝈 2.2. Almost sure convergence under arbitrary constant learning rate
The logarithmic expected-regret theorem requires a small learning rate ℓ . Almost sure convergence has a different threshold: under pairwise distinct 𝜇 (𝑖) , it holds for every fixed ℓ > 0. The following lemma isolates the stochastic comparison principle used in the arbitrary-learningrate argument. Its purpose is to absorb an integrable positive coefficient in a Lyapunov drift inequality and to retain the convergence and occupation-time consequences of the remaining negative drift. Lemma 3. Let 𝑠 ≥ 0 be deterministic, let 𝜏 ≥ 𝑠 be a stopping time which may take the value ∞, and let 𝑋 be a nonnegative continuous semimartingale such that, for every 𝑡 ≥ 𝑠, ∫ 𝑡∧𝜏 𝑋𝑡∧𝜏 = 𝑋𝑠 + 𝛽𝑢 d𝑢 + 𝑀𝑡∧𝜏 − 𝑀𝑠 ,
(33)
𝑠
where 𝑋𝑠 ∈ 𝐿 1 , 𝑀 is a continuous local martingale, and 𝛽 is progressively measurable and locally integrable. Suppose that there are a constant 𝑐 > 0 and nonnegative progressively measurable, locally integrable processes 𝛼 and 𝑔 such that 𝛽𝑢 ≤ 𝛼𝑢 𝑋𝑢 − 𝑐𝑋𝑢 𝑔𝑢
for 𝑠 ≤ 𝑢 < 𝜏,
d𝑢 ⊗ dP-almost everywhere.
(34)
∫ 𝑡∧𝜏 Define 𝐴𝑡 := 𝑠 𝛼𝑢 d𝑢, 𝑌𝑡 := 𝑒 − 𝐴𝑡 𝑋𝑡∧𝜏 , 𝑡 ≥ 𝑠. Then 𝑌 is a nonnegative supermartingale and
converges almost surely to a finite limit. Moreover, ∫ 𝜏 𝑒 − 𝐴𝑢 𝑋𝑢 𝑔𝑢 d𝑢 < ∞ 𝑠
almost surely.
(35)
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
11
On the event { 𝐴∞ < ∞}, one further has ∫ 𝜏 𝑋𝑡∧𝜏 converges to a finite limit as 𝑡 → ∞, and
𝑋𝑢 𝑔𝑢 d𝑢 < ∞.
(36)
𝑠
Proof.
Set 𝑞 𝑢 := 𝛼𝑢 𝑋𝑢 − 𝛽𝑢 . By (34), 𝑞 𝑢 ≥ 𝑐𝑋𝑢 𝑔𝑢 ≥ 0 for 𝑠 ≤ 𝑢 < 𝜏 , almost everywhere. By
integration by parts in (33), and the fact that 𝐴 is continuous and has finite variation, we obtain ∫ 𝑡∧𝜏 ∫ 𝑡∧𝜏 − 𝐴𝑢 e e 𝑌𝑡 = 𝑋𝑠 − 𝐾𝑡 + 𝑀𝑡 , 𝐾𝑡 := 𝑒 𝑞 𝑢 d𝑢, 𝑀𝑡 := 𝑒 − 𝐴𝑢 d𝑀𝑢 . (37) 𝑠
𝑠
e is a continuous local martingale. The process 𝐾 is continuous, adapted, and nondecreasing, while 𝑀
Since 𝑌 ≥ 0, (37) shows that 𝑌 is a nonnegative local supermartingale, and hence, a supermartingale. By supermartingale convergence theorem implies that 𝑌𝑡 converges almost surely to a finite limit (cf. Karatzas and Shreve 1991, Chapter 1, Theorem 3.15). We next prove the rest of the statement by the localization techniques. For 𝑛 ∈ N, define 𝜂 𝑛 := e𝑡 | ≥ 𝑛} ∧ (𝑠 + 𝑛), 𝜃 𝑛 := 𝜂 𝑛 ∧ inf{𝑡 ≥ 𝑠 : 𝐾𝑡 ≥ 𝑛}, where inf ∅ = ∞. Continuity implies inf{𝑡 ≥ 𝑠 : | 𝑀 e𝑡∧𝜂𝑛 is bounded, and hence is a martingale. Since 𝜃 𝑛 ≤ 𝜂 𝑛 ≤ 𝑠 + 𝑛, optional stopping gives that 𝑀 e 𝜃𝑛 ] = 0. We consider the stopped process (37) at 𝜃 𝑛 , and take the expectation at the deterministic E[ 𝑀
time 𝑠 + 𝑛, since 𝑌 𝜃𝑛 ≥ 0;and it yields E[𝐾 𝜃𝑛 ] = E[𝑋𝑠 ] − E[𝑌 𝜃𝑛 ] ≤ E[𝑋𝑠 ].
(38)
e , and the The stopping times 𝜃 𝑛 increase to ∞ almost surely. Indeed, 𝜂 𝑛 ↑ ∞ by continuity of 𝑀
hitting times of the levels 𝑛 by the continuous process 𝐾 , which is finite on every compact interval, also tend to infinity. Thus 𝐾 𝜃𝑛 ↑ 𝐾∞ , and monotone convergence in (38) gives ∫ 𝜏 − 𝐴𝑢 E[𝐾∞ ] = E 𝑒 𝑞 𝑢 d𝑢 ≤ E[𝑋𝑠 ] < ∞. 𝑠
In particular, 𝐾∞ < ∞ almost surely. Moreover, since 𝑞 𝑢 ≥ 𝑐𝑋𝑢 𝑔𝑢 , the above also implies (35). Finally, on { 𝐴∞ < ∞}, both 𝑒 𝐴𝑡 and 𝑌𝑡 have finite limits. Hence 𝑋𝑡∧𝜏 = 𝑒 𝐴𝑡 𝑌𝑡 has a finite limit. ∫𝜏 ∫𝜏 Moreover, 𝐴𝑢 ≤ 𝐴∞ and therefore 𝑠 𝑋𝑢 𝑔𝑢 d𝑢 ≤ 𝑒 𝐴∞ 𝑠 𝑒 − 𝐴𝑢 𝑋𝑢 𝑔𝑢 d𝑢 < ∞. This proves (36). □ Theorem 2. Assume there are no ties in the expected reward rate among the arms, and 𝜇 (1) > 𝜇 (2) > · · · > 𝜇 (𝑑) ,
𝜌 :=
min
1≤𝑎<𝑏≤𝑑
𝜇 (𝑎) − 𝜇 (𝑏) > 0.
(39)
Then for every fixed constant learning rate ℓ > 0 and every finite deterministic initial condition 𝝓0 , 𝝅𝑡 −→ 𝒆 1 almost surely. That is, the policy converges to the best arm.
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
12
Proof.
n 𝜌 o , then it satisfies Fix an arbitrary ℓ > 0, and set 𝛾 = min 1, 2ℓ𝑠 0 < 𝛾 ≤ 1,
𝛾ℓ𝑠 ≤
𝜌 . 2
(40)
For 𝑗 ∈ {2, . . . , 𝑑}, define 𝒗
( 𝑗)
:= 𝒆 𝑗 − 𝒆 1 ,
𝐻 𝑗 (𝝓) := exp 𝛾(𝜙
( 𝑗)
−𝜙
𝜋( 𝑗) ) = (1) 𝜋
(1)
𝛾 ,
Λ 𝑗 (𝝅) :=
𝑑 ∑︁
𝜋 (𝑘 ) ,
(41)
𝑘= 𝑗+1
where the empty sum gives Λ𝑑 (𝝅) = 0. Denote 𝛾ℓ𝜌 𝑎 𝛾 := > 0, 2
𝛾ℓ𝑠 𝑏 𝛾 := 𝛾ℓ Δmax + > 0. 2
(42)
The generator of 𝐻 𝑗 is L𝝈 𝐻 𝑗 (𝝓) 𝛾 2ℓ2 ( 𝑗 ) ⊤ = 𝛾ℓ(𝒗 ( 𝑗 ) ) ⊤ 𝑱(𝝅) 𝝁 + (𝒗 ) 𝑸𝝈 (𝝅)𝒗 ( 𝑗 ) . 𝐻 𝑗 (𝝓) 2
We now apply Lemma 2 to the quadratic term and use (3) for the drift. Separating all pairs which contain index 1 or index 𝑗 gives the upper bound L𝝈 𝐻 𝑗 (𝝓) ∑︁ (𝑎) (𝑏) 𝛾 2 ℓ 2 𝑠 𝑎𝑏 ( 𝑗 ) ( 𝑗) ( 𝑗) ( 𝑗) 2 (𝑎) (𝑏) ≤ 𝜋 𝜋 𝛾ℓ(𝑣 𝑎 − 𝑣 𝑏 ) (𝜇 − 𝜇 ) + (𝑣 𝑎 − 𝑣 𝑏 ) 𝐻 𝑗 (𝝓) 2 𝑎<𝑏 𝑑 ∑︁ 𝛾 2 ℓ 2 𝑠1𝑘 (1) ( 𝑗 ) (1) ( 𝑗) 2 2 (1) (𝑘 ) (1) (𝑘 ) =𝜋 𝜋 + 2𝛾 ℓ 𝑠1 𝑗 + + −2𝛾ℓ 𝜇 − 𝜇 𝜋 𝜋 −𝛾ℓ 𝜇 − 𝜇 2 𝑘=2 𝑘≠ 𝑗
+
𝑗 −1 ∑︁
" 𝜋 ( 𝑗 ) 𝜋 (𝑘 ) −𝛾ℓ 𝜇 (𝑘 ) − 𝜇
𝑘=2
( 𝑗)
# # " 𝑑 2ℓ2 𝑠 ∑︁ 𝛾 2ℓ2 𝑠 𝑘 𝑗 𝛾 𝑗 𝑘 + + 𝜋 ( 𝑗 ) 𝜋 (𝑘 ) 𝛾ℓ 𝜇 ( 𝑗 ) − 𝜇 (𝑘 ) + . 2 2 𝑘= 𝑗+1 (43)
For any 𝑥 ≥ 𝜌 , the property of 𝛾 in (40) and 𝑠 𝑎𝑏 ≤ 𝑠, 𝛾ℓ𝑠 ≤ 𝜌/2 imply −2𝛾ℓ𝑥 + 2𝛾 2 ℓ 2 𝑠 𝑎𝑏 ≤ −𝛾ℓ𝜌 = −2𝑎 𝛾 ,
−𝛾ℓ𝑥 +
𝛾 2 ℓ 2 𝑠 𝑎𝑏 3 ≤ − 𝛾ℓ𝜌 ≤ −𝑎 𝛾 . 2 4
For 𝑗 < 𝑘 , the definition of Δmax gives 𝛾 2ℓ2 𝑠 𝑗 𝑘 𝛾ℓ 𝜇 ( 𝑗 ) − 𝜇 (𝑘 ) + ≤ 𝑏𝛾 . 2
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
13
All terms involving the best arm in (43) are bounded above by −𝑎 𝛾 𝜋 (1) (1 − 𝜋 (1) ) . The third term on the right-hand side of (43) is nonpositive. Hence, we conclude that L𝝈 𝐻 𝑗 (𝝓) ≤ 𝐻 𝑗 (𝝓) −𝑎 𝛾 𝜋 (1) (1 − 𝜋 (1) ) + 𝑏 𝛾 𝜋 ( 𝑗 ) Λ 𝑗 (𝝅) ,
2 ≤ 𝑗 ≤ 𝑑.
Itô’s formula also gives the semimartingale decomposition ∫ 𝑡 𝑗,𝛾 𝐻 𝑗 (𝝓𝑡 ) = 𝐻 𝑗 (𝝓0 ) + L𝝈 𝐻 𝑗 (𝝓 𝑠 ) d𝑠 + 𝑀𝑡 ,
(44)
(45)
0 𝑗,𝛾
where 𝑀𝑡
∫𝑡 𝜙 := 𝛾ℓ 0 𝐻 𝑗 (𝝓 𝑠 ) (𝒆 𝑗 − 𝒆 1 ) ⊤ 𝑮 𝝈 (𝝅 𝑠 ) d𝑩𝑠 is a continuous local martingale.
We first verify the integrability needed to apply Lemma 3 at a deterministic time. Since 0 ≤ 𝜋 ( 𝑗 ) Λ 𝑗 (𝝅) ≤ 1, (44) implies L𝝈 𝐻 𝑗 ≤ 𝑏 𝛾 𝐻 𝑗 . For 𝑚 ∈ N, let 𝜁 𝑚 := inf{𝑡 ≥ 0 : |𝝓𝑡 | 2 ≥ 𝑚}. By
Lemma 1, 𝜁 𝑚 ↑ ∞ almost surely. The stochastic integral in (45), stopped at 𝜁 𝑚 , is a martingale. Hence Itô’s formula and the drift bound give, for every 𝑡 < ∞, ∫ 𝑡∧𝜁𝑚 E[𝐻 𝑗 (𝝓𝑡∧𝜁𝑚 )] ≤ 𝐻 𝑗 (𝝓0 ) + 𝑏 𝛾 E 𝐻 𝑗 (𝝓 𝑠 )d𝑠 0 ∫ 𝑡 ≤ 𝐻 𝑗 (𝝓0 ) + 𝑏 𝛾 E[𝐻 𝑗 (𝝓 𝑠∧𝜁𝑚 )] d𝑠.
(46)
0
Applying Gronwall’s inequality to (46), followed by Fatou’s lemma as 𝑚 → ∞, proves E[𝐻 𝑗 (𝝓𝑡 )] ≤ 𝐻 𝑗 (𝝓0 )𝑒 𝑏𝛾 𝑡 < ∞,
𝑡 < ∞.
(47)
Thus, 𝐻 𝑗 (𝜙𝑡 ) ∈ 𝐿 1 for every 𝑡 > 0. We now state explicitly how that lemma will be used. Since 𝜋 ( 𝑗 ) ≤ 1, (44) implies L𝝈 𝐻 𝑗 ≤ 𝐻 𝑗 𝑏 𝛾 Λ 𝑗 (𝝅) − 𝑎 𝛾 𝜋 (1) (1 − 𝜋 (1) ) .
(48)
Apply Lemma 3 to (45) and (48) with 𝑋𝑡 = 𝐻 𝑗 (𝝓𝑡 ), 𝛼𝑡 = 𝑏 𝛾 Λ 𝑗 (𝝅𝑡 ), 𝑐 = 𝑎 𝛾 , 𝑔𝑡 = 𝜋𝑡(1) (1 − 𝜋𝑡(1) ) . It ∫∞ follows that, almost surely on the event { 0 Λ 𝑗 (𝝅𝑡 ) d𝑡 < ∞}, ∫ ∞ 𝐻 𝑗 (𝝓𝑡 ) converges to a finite limit, and 𝐻 𝑗 (𝝓𝑡 )𝜋𝑡(1) (1 − 𝜋𝑡(1) ) d𝑡 < ∞. (49) 0
We claim that
∫ ∞ 0
𝜋𝑡(1) d𝑡 = ∞
almost surely.
(50)
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
14
We prove this claim by contradiction. Suppose otherwise, that the event 𝐸 :=
n∫
∞ (1) 𝜋𝑡 d𝑡 < ∞ 0
o
has
positive probability. Since Λ𝑑 (𝝅) = 0, (49) shows that 𝐻 𝑑 (𝝓𝑡 ) converges to a finite limit almost surely. Recall 𝐻 𝑑 (𝝓𝑡 ) has continuous paths, so it is also bounded on [0, ∞) . Hence, almost surely on 𝐸 , the identity in (41) consequently gives ∫ ∞ ∫ ∞ ∫ ∞ (𝑑) (1) 1/𝛾 1/𝛾 𝜋𝑡 d𝑡 = 𝜋𝑡 𝐻 𝑑 (𝝓𝑡 ) d𝑡 ≤ sup 𝐻 𝑑 (𝝓𝑡 ) 𝜋𝑡(1) d𝑡 < ∞. 0
𝑡 ≥0
0
(51)
0
We next use induction. Now let 𝑗 ∈ {2, . . . , 𝑑 − 1} and suppose, in descending order, that ∫ ∞ (𝑘 ) 𝜋𝑡 d𝑡 < ∞ almost surely on 𝐸 for every 𝑘 > 𝑗 . Then 0 ∫ ∞
𝑑 ∫ ∞ ∑︁
Λ 𝑗 (𝝅𝑡 ) d𝑡 = 0
𝜋𝑡(𝑘 ) d𝑡 < ∞
almost surely on 𝐸 .
(52)
𝑘= 𝑗+1 0
Applying (49) on the event in (52) shows that 𝐻 𝑗 (𝝓𝑡 ) converges to a finite limit and is therefore bounded, almost surely on 𝐸 . Repeating the calculation in (51) proves ∫ ∞ ( 𝑗) 𝜋𝑡 d𝑡 < ∞ almost surely on 𝐸 .
(53)
0
Descending induction using (51) and (53) proves that every arm has finite occupation time almost surely on 𝐸 . This is a contradiction, since there are only finitely many arms, and we have ∞>
𝑑 ∫ ∞ ∑︁ 𝑖=1
𝜋𝑡(𝑖) d𝑡 =
0
∫ ∞ ∑︁ 𝑑 0
𝜋𝑡(𝑖) d𝑡 =
𝑖=1
∫ ∞ 1 d𝑡 = ∞.
(54)
0
Thus P(𝐸) = 0, which proves (50). We next prove 𝐻 𝑗 (𝝓𝑡 ) −→ 0,
2 ≤ 𝑗 ≤ 𝑑,
almost surely,
by descending induction. Since Λ𝑑 (𝝅) = 0, (49) gives ∫ ∞ 𝐻 𝑑 (𝝓𝑡 ) −→ 𝐻 𝑑,∞ < ∞, and 𝐻 𝑑 (𝝓𝑡 )𝜋𝑡(1) (1 − 𝜋𝑡(1) ) d𝑡 < ∞
(55)
(56)
0
almost surely. On the event {𝐻 𝑑,∞ > 0}, there exists 𝑇0 < ∞ and 𝑐 > 0 such that, for all 𝑡 ≥ 𝑇0 , 𝐻 𝑑 (𝝓𝑡 ) ≥
𝜋 (𝑑) 𝐻 𝑑,∞ , and 𝑡(1) = 𝐻 𝑑 (𝝓𝑡 ) 1/𝛾 ≥ 𝑐. 2 𝜋 𝑡
(57)
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
15
The second inequality in (57) implies 1 − 𝜋𝑡(1) ≥ 𝜋𝑡(𝑑) ≥ 𝑐𝜋𝑡(1) , hence, 1 − 𝜋𝑡(1) ≥
𝑐 , 1+𝑐
𝑡 ≥ 𝑇0 .
(58)
Combining (57) and (58), the integrand in (56) is bounded below, for 𝑡 ≥ 𝑇0 , by 𝐻 𝑑 (𝝓𝑡 )𝜋𝑡(1) (1 − 𝜋𝑡(1) ) ≥
𝐻 𝑑,∞ 𝑐 𝜋𝑡(1) . 2 1+𝑐
(59)
This contradicts (50). Hence 𝐻 𝑑,∞ = 0 almost surely, proving the base case of (55). Fix 𝑗 ∈ {2, . . . , 𝑑 − 1} and suppose that 𝐻 𝑘 (𝝓𝑡 ) → 0 as 𝑡 → ∞ almost surely for all 𝑘 > 𝑗 . By (41), 𝑄 𝑗 (𝑡) :=
Λ 𝑗 (𝝅𝑡 ) 𝜋𝑡(1)
=
𝑑 ∑︁ 𝜋 (𝑘 )
𝑑 ∑︁ 𝑡 = 𝐻 𝑘 (𝝓𝑡 ) 1/𝛾 −→ 0 (1) 𝑘= 𝑗+1 𝜋 𝑡 𝑘= 𝑗+1
as 𝑡 → ∞
almost surely.
(60)
𝑛 ∈ N,
(61)
Let 𝜀 :=
𝑎𝛾 > 0, 2𝑏 𝛾
𝜏 𝑗,𝑛 := inf 𝑡 ≥ 𝑛 : 𝑄 𝑗 (𝑡) > 𝜀 ,
with inf ∅ = ∞. The process 𝑄 𝑗 is continuous and adapted, so 𝜏 𝑗,𝑛 is a stopping time. On {𝜏 𝑗,𝑛 > 𝑛}, we have 𝑄 𝑗 (𝑡) ≤ 𝜀 , and hence Λ 𝑗 (𝝅𝑡 ) ≤ 𝜀𝜋𝑡(1) , for 𝑛 ≤ 𝑡 < 𝜏 𝑗,𝑛 . If 𝜏 𝑗,𝑛 = 𝑛, the process stopped at 𝜏 𝑗,𝑛 is constant from its starting time and the conclusion below is immediate. Since 𝜋 ( 𝑗 ) ≤ 1 − 𝜋 (1) ,
it follows from (42) and (61) that ( 𝑗)
𝑏 𝛾 𝜋𝑡 Λ 𝑗 (𝝅𝑡 ) ≤ 𝑏 𝛾 (1 − 𝜋𝑡(1) )Λ 𝑗 (𝝅𝑡 ) ≤
𝑎 𝛾 (1) 𝜋 (1 − 𝜋𝑡(1) ), 2 𝑡
𝑛 ≤ 𝑡 < 𝜏 𝑗,𝑛 .
Consequently, the generator estimate (44) strengthens on this stopped interval to L𝝈 𝐻 𝑗 ≤ −
𝑎𝛾 𝐻 𝑗 𝜋 (1) (1 − 𝜋 (1) ). 2
By (47), 𝐻 𝑗 (𝝓 𝑛 ) ∈ 𝐿 1 . Applying Lemma 3 with 𝑠 = 𝑛, 𝜏 = 𝜏 𝑗,𝑛 , 𝑋𝑡 = 𝐻 𝑗 (𝝓𝑡 ) , 𝛼𝑡 = 0, 𝑐 = 𝑎 𝛾 /2, and 𝑔𝑡 = 𝜋𝑡(1) (1 − 𝜋𝑡(1) ) , we obtain ∫ 𝜏 𝑗,𝑛 lim 𝐻 𝑗 (𝝓𝑡∧𝜏 𝑗,𝑛 ) =: 𝐻 𝑗,𝑛,∞ < ∞, and
𝑡→∞
𝐻 𝑗 (𝝓𝑡 )𝜋𝑡(1) (1 − 𝜋𝑡(1) ) d𝑡 < ∞
(62)
𝑛
almost surely. The convergence in (60) implies P
∞ Ø 𝑛=1
! {𝜏 𝑗,𝑛 = ∞} = 1.
(63)
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
16
Indeed, on every path on which 𝑄 𝑗 (𝑡) → 0, some integer 𝑛 satisfies 𝑄 𝑗 (𝑡) ≤ 𝜀 for all 𝑡 ≥ 𝑛, and hence 𝜏 𝑗,𝑛 = ∞. For each 𝑛 ∈ N, let Ω 𝑗,𝑛 be the probability-one event on which (62) holds, and define Ω 𝑗 := Ð∞ Ñ∞ 𝑛=1 Ω 𝑗,𝑛 ∩ 𝑛=1 {𝜏 𝑗,𝑛 = ∞} . Since N is countable, (62) and (63) imply that P(Ω 𝑗 ) = 1. Fix 𝜔 ∈ Ω 𝑗 . Then there exists an integer 𝑛 = 𝑛(𝜔) such that 𝜏 𝑗,𝑛 (𝜔) = ∞. For this 𝑛, 𝑡 ∧ 𝜏 𝑗,𝑛 (𝜔) = 𝑡 , and hence lim𝑡→∞ 𝐻 𝑗 (𝝓𝑡 (𝜔)) = lim𝑡→∞ 𝐻 𝑗 (𝝓𝑡∧𝜏 𝑗,𝑛 (𝜔)) = 𝐻 𝑗,𝑛,∞ (𝜔) < ∞. Moreover, ∫∞ ∫ 𝜏 ( 𝜔) 𝐻 𝑗 (𝝓𝑡 (𝜔))𝜋𝑡(1) (𝜔) (1 − 𝜋𝑡(1) (𝜔)) d𝑡 = 𝑛 𝑗,𝑛 𝐻 𝑗 (𝝓𝑡 (𝜔))𝜋𝑡(1) (𝜔) (1 − 𝜋𝑡(1) (𝜔)) d𝑡 < ∞. Since 𝑛
the integrand is continuous in 𝑡 , its integral over the compact interval [0, 𝑛] is also finite. Therefore, ∫∞ 𝐻 𝑗 (𝝓𝑡 )𝜋𝑡(1) (1 − 𝜋𝑡(1) ) d𝑡 < ∞ almost surely. If the limit of 𝐻 𝑗 (𝝓𝑡 ) were positive, repeating the 0 argument in (57)– (59), with 𝑗 in place of 𝑑 , would contradict (50). Therefore the limit is zero. Descending induction proves (55) for every 𝑗 ≥ 2. ( 𝑗)
Equations (41) and (55) give (1) = 𝐻 𝑗 (𝝓𝑡 ) 1/𝛾 → 0, 𝜋𝑡(1) = 𝜋 𝜋𝑡
( 𝑗)
1+
𝑡
This proves almost sure convergence of the policy.
Í𝑑
𝜋𝑡
𝑗=2 𝜋 (1)
−1 → 1 almost surely.
𝑡
□
Theorem 2 removes the learning-rate restriction only from the pathwise convergence statement. It does not imply logarithmic expected regret for arbitrary ℓ : rare paths can prevent the uniform integrability needed for such a conclusion. The proof also uses 𝜌 > 0 and therefore does not cover tied suboptimal means. 2.3. Discrete-time policy gradient algorithm
We now return to the conventional discrete-time stochastic-gradient algorithm, and present a new proof for the convergence and regret based on the same Lyapunov function discovered in our earlier analysis for the policy gradient SDE. Let (F𝑛 ) 𝑛≥0 be the information available immediately before round 𝑛. The vectors 𝝓 𝑛 and 𝝅 𝑛 (𝑎)
and the scalar baseline 𝐵𝑛 are F𝑛 -measurable, with 𝜋 𝑛(𝑎) = Í𝑑𝑒 𝑛 ( 𝑗) , 𝐴𝑛 | F𝑛 ∼ 𝝅 𝑛 . After sampling 𝜙
𝑗=1 𝑒
𝜙𝑛
𝐴𝑛 , an arm-dependent reward 𝑌𝑛 is observed. Its conditional law may vary with the selected arm
and with the past, and we only require E[𝑌𝑛 | F𝑛 , 𝐴𝑛 = 𝑎] = 𝜇 (𝑎) . The baseline 𝐵𝑛 is predictable and action-independent: It may depend on all past observations, but not on the action or reward at round 𝑛. Put 𝑋𝑛 := 𝑌𝑛 − 𝐵𝑛 . The direct discrete-time update is 𝝓 𝑛+1 = 𝝓 𝑛 + ℓ𝑋𝑛 (𝒆 𝐴𝑛 − 𝝅 𝑛 ).
(64)
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
17
Retain the unique-best-arm convention and the quantities Δ𝑖 , Δmin , Δmax and 𝐼 = {2, . . . , 𝑑}. Define 𝐾 = Δmax +
Δmin , 2𝑑
𝐶=
2𝐾 , Δmin
∑︁
𝑉 (𝝓) =
𝐶 | 𝐴| −1 ℎ 𝐴 (𝝓) =
∅≠𝐴⊆ 𝐼
∑︁
𝐶 | 𝐴| −1
∅≠𝐴⊆ 𝐼
Ö
𝑒𝜙
(𝑖) − 𝜙 (1)
.
𝑖∈ 𝐴
(65) Define the conditional instantaneous regret and expected regret by " 𝑁 −1 # " 𝑁 −1 # 𝑑 ∑︁ ∑︁ ∑︁ (𝑖) (1) ( 𝐴𝑛 ) (1) ⊤ Δ𝑖 𝜋 𝑛 , R 𝑁 := E 𝜇 −𝜇 𝑟𝑛 . 𝑟 𝑛 := 𝜇 − 𝝁 𝝅 𝑛 = =E 𝑛=0
𝑖=2
(66)
𝑛=0
Theorem 3. Suppose that arm 1 is uniquely optimal. For 𝑞 ∈ {1, 𝑑}, suppose that there are deterministic, arm-dependent constants Γ𝑞,𝑎 < ∞ such that, almost surely for every 𝑛 and 𝑎 , E 𝑋𝑛2 𝑒 ℓ𝑞 | 𝑋𝑛 | | F𝑛 , 𝐴𝑛 = 𝑎 ≤ Γ𝑞,𝑎 .
(67)
Put Γ𝑞 = max1≤𝑎≤𝑑 Γ𝑞,𝑎 , 𝑞 ∈ {1, 𝑑}. Take 𝝓0 = 0 and assume that the fixed learning rate satisfies ℓ𝑑Γ𝑑 ≤ Δmin . Then 𝜋 𝑛(1) −→ 1,
𝜋 𝑛(𝑖) −→ 0,
2≤𝑖 ≤𝑑
almost surely.
(68)
Moreover, for every integer 𝑁 ≥ 0, ! ℓΔmax + 21 ℓ 2 Γ1 𝑑 −1 Δmax (𝑑 − 1) (1 + 𝐶) 𝑑−1 − 1 R𝑁 ≤ log 1 + 𝑁 + . ℓ 𝑑 ℓΔmin 𝐶
Proof
(69)
We prove a slightly stronger estimate for an arbitrary finite deterministic 𝝓0 and spe⊤
cialize to 𝝓0 = 0 at the end. Write E𝑛 [·] = E[· | F𝑛 ] . Fix 𝒗 ∈ R𝑑 and define 𝑓𝒗 (𝝓) := 𝑒 𝒗 𝝓 , 𝑣¯ 𝑛 := 𝝅 𝑛⊤ 𝒗, osc(𝒗) := max𝑎 𝑣 𝑎 − min𝑎 𝑣 𝑎 . By (64) and Taylor’s formula, we obtain 𝑓𝒗 (𝝓 𝑛+1 ) − 𝑓𝒗 (𝝓 𝑛 ) ≤ 𝑓𝒗 (𝝓 𝑛 )ℓ𝑋𝑛 (𝑣 𝐴𝑛 − 𝑣¯ 𝑛 ) +
ℓ2 𝑓𝒗 (𝝓 𝑛 ) 𝑋𝑛2 (𝑣 𝐴𝑛 − 𝑣¯ 𝑛 ) 2 𝑒 ℓ | 𝑋𝑛 | |𝑣𝐴𝑛 − 𝑣¯𝑛 | . 2
(70)
Denote 𝑱𝑛 = diag{𝝅 𝑛 } − 𝝅 𝑛 𝝅 𝑛⊤ . Because 𝐵𝑛 is F𝑛 -measurable and action-independent, E𝑛 [𝑋𝑛 (𝑣 𝐴𝑛 − 𝑣¯ 𝑛 )] =
𝑑 ∑︁
𝜋 𝑛(𝑎) (𝜇 (𝑎) − 𝐵𝑛 ) (𝑣 𝑎 − 𝑣¯ 𝑛 )
𝑎=1
=
𝑑 ∑︁ 𝑎=1
𝜋 𝑛(𝑎) 𝜇 (𝑎) (𝑣 𝑎 − 𝑣¯ 𝑛 ) − 𝐵𝑛
𝑑 ∑︁ 𝑎=1
(71) 𝜋 𝑛(𝑎) (𝑣 𝑎 − 𝑣¯ 𝑛 ) = 𝒗 ⊤ 𝑱𝑛 𝝁.
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
18
If osc(𝒗) ≤ 𝑞 for 𝑞 ∈ {1, 𝑑}, then (67) and |𝑣 𝑎 − 𝑣¯ 𝑛 | ≤ osc(𝒗) imply 𝑑 ∑︁ E𝑛 𝑋𝑛2 (𝑣 𝐴𝑛 − 𝑣¯ 𝑛 ) 2 𝑒 ℓ | 𝑋𝑛 | |𝑣𝐴𝑛 − 𝑣¯𝑛 | = E𝑛 𝑋𝑛2 (𝑣 𝐴𝑛 − 𝑣¯ 𝑛 ) 2 𝑒 ℓ | 𝑋𝑛 | |𝑣𝐴𝑛 − 𝑣¯𝑛 | | 𝐴𝑛 = 𝑎 𝜋 𝑛(𝑎) 𝑎=1
≤Γ𝑞
𝑑 ∑︁
(72) 𝜋 𝑛(𝑎) (𝑣 𝑎 − 𝑣¯ 𝑛 ) 2 = Γ𝑞 𝒗 ⊤ 𝑱𝑛 𝒗.
𝑎=1
Taking conditional expectations in (70) and using (71)– (72) yields ℓ2 ⊤ ⊤ E𝑛 [ 𝑓𝒗 (𝝓 𝑛+1 )] − 𝑓𝒗 (𝝓 𝑛 ) ≤ 𝑓𝒗 (𝝓 𝑛 ) ℓ𝒗 𝑱𝑛 𝝁 + Γ𝑞 𝒗 𝑱𝑛 𝒗 . 2
(73)
Recall from (3) the identity ∑︁
𝒗 ⊤ 𝑱𝑛 𝒘 =
𝜋 𝑛(𝑎) 𝜋 𝑛(𝑏) (𝑣 𝑎 − 𝑣 𝑏 ) (𝑤 𝑎 − 𝑤 𝑏 ).
(74)
1≤𝑎<𝑏≤𝑑
Following the same idea as in the proof of Theorem 1, for a fixed nonempty 𝐴 ⊆ 𝐼 , write 𝑚 = | 𝐴| , 𝐴 ⊤
and define 𝑣 1𝐴 = −𝑚, 𝑣 𝑖𝐴 = 1 {𝑖 ∈ 𝐴} , 2 ≤ 𝑖 ≤ 𝑑. Then ℎ 𝐴 = 𝑒 (𝒗 ) 𝝓 and osc(𝒗 𝐴) = 𝑚 + 1 ≤ 𝑑 . Equations (73) and (74) imply " # 2Γ ℓ E𝑛 [ℎ 𝐴 (𝝓 𝑛+1 )] − ℎ 𝐴 (𝝓 𝑛 ) ∑︁ (𝑎) (𝑏) 𝑑 ≤ 𝜋 𝑛 𝜋 𝑛 ℓ(𝑣 𝑎𝐴 − 𝑣 𝑏𝐴) (𝜇 (𝑎) − 𝜇 (𝑏) ) + (𝑣 𝑎𝐴 − 𝑣 𝑏𝐴) 2 . ℎ 𝐴 (𝝓 𝑛 ) 2 𝑎<𝑏
(75)
Using the same method as in the proof of Theorem 1, we obtain E𝑛 [ℎ 𝐴 (𝝓 𝑛+1 )] − ℎ 𝐴 (𝝓 𝑛 ) ∑︁ ∑︁ ∑︁ ℓΔmin ( 𝑗 ) ( 𝑗) (1) (𝑖) 𝜋 𝑛 + ℓ𝐾 ℎ 𝐴 ℎ 𝐴 𝜋 𝑛 (𝑚 + 1) 𝜋𝑛 + 𝑚 𝜋 𝑛(𝑖) 𝜋 𝑛 . ≤− 2 𝑖∈ 𝐴 𝑖∈ 𝐴 𝑗 ∈ 𝐼\𝐴 𝑗 ∈ 𝐼\𝐴
Thus, by the definition of the Lyapunov function 𝑉 (𝜙) , we have E𝑛 [𝑉 (𝝓 𝑛+1 )] − 𝑉 (𝝓 𝑛 ) ∑︁ 𝑑 𝑑−1 ∑︁ ∑︁ ∑︁ Δmin𝐶 (𝑖) 2 𝑟 −2 ≤ −ℓΔmin (𝜋 𝑛 ) + ℓ 𝐶 𝐾 (𝑟 − 1) − (𝑟 + 1) ℎ 𝐷 (𝝓 𝑛 )𝜋 𝑛(1) 𝜋 𝑛(𝑖) 2 𝐷⊆𝐼 𝑖 ∈𝐷 𝑖=2 𝑟=2 | 𝐷 |=𝑟
= −ℓΔmin
𝑑 ∑︁
(𝜋 𝑛(𝑖) ) 2 − 2ℓ𝐾
𝑖=2
≤ −ℓΔmin
𝑑 ∑︁ 𝑖=2
𝑑−1 ∑︁ 𝑟=2
(𝜋 𝑛(𝑖) ) 2 .
𝐶 𝑟 −2
∑︁ 𝐷⊆𝐼 | 𝐷 |=𝑟
ℎ 𝐷 (𝝓 𝑛 )𝜋 𝑛(1)
∑︁ 𝑖 ∈𝐷
𝜋 𝑛(𝑖)
(76)
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
19
Here the first term is the singleton contribution, because ℎ {𝑖 } 𝜋 𝑛(1) 𝜋 𝑛(𝑖) = (𝜋 𝑛(𝑖) ) 2 , and the equality uses Δmin𝐶/2 = 𝐾 . Summing (76) from 𝑛 = 0 to 𝑁 − 1, taking expectations, and using 𝑉 ≥ 0 gives i hÍ (𝑖) 2 𝑁 −1 Í𝑑 ≤ 𝑉ℓΔ(𝝓min0 ) . Letting 𝑁 → ∞ yields E 𝑛=0 (𝜋 ) 𝑖=2 𝑛
E
"∞ 𝑑 ∑︁ ∑︁
# (𝜋 𝑛(𝑖) ) 2
≤
𝑛=0 𝑖=2
𝑉 (𝝓0 ) . ℓΔmin
(77)
The nonnegative series in (77) has finite expectation and is therefore finite almost surely. Hence 𝜋 𝑛(𝑖) → 0 for every 𝑖 ≥ 2, and normalization gives 𝜋 𝑛(1) → 1.
The update conserves the sum of the logits pathwise: ! 𝑑 𝑑 𝑑 ∑︁ ∑︁ ∑︁ (𝑎) = 𝜙 𝑛(𝑎) + ℓ𝑋𝑛 1 − 𝜙 𝑛+1 𝜋 𝑛(𝑎) = 𝑆0 , 𝑎=1
𝑎=1
𝑎=1
𝑆0 :=
𝑑 ∑︁
𝜙0(𝑎) .
𝑎=1
(𝑖) ⊤ (𝑖) Fix 𝑖 ≥ 2 and apply (73) with 𝒗 = −𝒆 𝑖 , whose oscillation is one. Since −𝒆 ⊤ 𝑖 𝑱𝑛 𝝁 = 𝜋 𝑛 ( 𝝁 𝝅 𝑛 − 𝜇 ) ≤ (𝑖) (𝑖) (𝑖) Δmax 𝜋 𝑛(𝑖) and 𝒆 ⊤ 𝑖 𝑱𝑛 𝒆 𝑖 = 𝜋 𝑛 (1 − 𝜋 𝑛 ) ≤ 𝜋 𝑛 , we obtain
ℓ 2 Γ1 . E𝑛 [𝑒 ]−𝑒 ≤𝑒 ℓΔmax + 2 Í ( 𝑗) (𝑖) Í −𝑆 /𝑑 ( 𝑗) Let 𝑍 𝑛 := 𝑑𝑗=1 𝑒 𝜙𝑛 . Then 𝑒 − 𝜙𝑛 𝜋 𝑛(𝑖) = 1/𝑍 𝑛 ≤ 𝑑1 exp − 𝑑1 𝑑𝑗=1 𝜙 𝑛 = 𝑒 𝑑0 . Thus, (𝑖)
− 𝜙𝑛+1
(𝑖)
(𝑖)
− 𝜙𝑛
− 𝜙𝑛
(𝑖)
(𝑖)
𝜋 𝑛(𝑖)
E[𝑒 − 𝜙 𝑁 ] ≤ 𝑒 − 𝜙0 + 𝑎 ℓ,disc 𝑁, −𝑆 /𝑑
where 𝑎 ℓ,disc := 𝑒 𝑑0
(78)
2 ℓΔmax + ℓ 2Γ1 . Conservation also yields (1) 𝜙𝑁 − 𝜙0(1) =
𝑑 ∑︁
(𝑖) ). (𝜙0(𝑖) − 𝜙 𝑁
(79)
𝑖=2
Since the exponential factor in (67) is at least one, conditional Cauchy–Schwarz gives E𝑛 [|𝑋𝑛 |] ≤ √ Γ𝑑 . The update (64) therefore implies, by induction over the finite number of steps, that every coordinate of 𝝓 𝑁 is integrable. For each 𝑖 ≥ 2, Jensen’s inequality and (78) imply h (𝑖) i (𝑖) (𝑖) (𝑖) (𝑖) (𝑖) E[𝜙0(𝑖) − 𝜙 𝑁 ] = E log 𝑒 𝜙0 𝑒 − 𝜙 𝑁 ≤ log 𝑒 𝜙0 E[𝑒 − 𝜙 𝑁 ] ≤ log 1 + 𝑎 ℓ,disc 𝑒 𝜙0 𝑁 .
(80)
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
20
Summing (80) and using (79) gives (1) E[𝜙 𝑁 − 𝜙0(1) ] ≤
𝑑 ∑︁
(𝑖) log 1 + 𝑎 ℓ,disc 𝑒 𝜙0 𝑁 .
(81)
𝑖=2 (1) The conditional drift of the best coordinate is E𝑛 [𝜙 𝑛+1 − 𝜙 𝑛(1) ] = ℓ
(𝑎) (𝑎) − 𝐵 ) (1 𝑛 {𝑎=1} − 𝑎=1 𝜋 𝑛 (𝜇
Í𝑑
𝜋 𝑛(1) ) = ℓ𝜋 𝑛(1) (𝜇 (1) − 𝝁⊤ 𝝅 𝑛 ) = ℓ𝜋 𝑛(1) 𝑟 𝑛 . Therefore, (1) E[𝜙 𝑁 − 𝜙0(1) ] = ℓE
" 𝑁 −1 ∑︁
# 𝜋 𝑛(1) 𝑟 𝑛
.
(82)
𝑛=0
Í𝑑 (𝑖) Let 𝑢 𝑛 := 1 − 𝜋 𝑛(1) = 𝑖=2 𝜋 𝑛 . Then 𝑟 𝑛 ≤ Δmax 𝑢 𝑛 and, by Cauchy–Schwarz, 𝑢 2𝑛 ≤ (𝑑 − Í𝑑 Í𝑑 1) 𝑖=2 (𝜋 𝑛(𝑖) ) 2 . Consequently, 𝑟 𝑛 = 𝜋 𝑛(1) 𝑟 𝑛 + 𝑢 𝑛 𝑟 𝑛 ≤ 𝜋 𝑛(1) 𝑟 𝑛 + Δmax (𝑑 − 1) 𝑖=2 (𝜋 𝑛(𝑖) ) 2 . Summing 𝑟 𝑛 ,
taking expectations, and applying (77), (81), and (82), we conclude that R𝑁 ≤
𝑑 Δ (𝑑 − 1) (𝑖) 1 ∑︁ max 𝑉 (𝝓0 ). log 1 + 𝑎 ℓ,disc 𝑒 𝜙0 𝑁 + ℓ 𝑖=2 ℓΔmin
(83)
2 Í𝑑−1 𝑑−1 𝑚−1 (1+𝐶 ) 𝑑−1 −1 If 𝝓0 = 0, then 𝑆0 = 0, 𝑎 ℓ,disc = 𝑑1 ℓΔmax + ℓ 2Γ1 , 𝑉 (0) = 𝑚=1 = . This 𝑚 𝐶 𝐶
proves (69).
□
Remark 1. The zero initialization in Theorem 3 only simplifies the constants. For any finite deterministic 𝝓0 , the same conclusions hold with (77) and (83). When 𝑌𝑛 , 𝐵𝑛 ∈ [0, 1] , the exact condition is ℓ𝑑𝑒 ℓ𝑑 ≤ Δmin , while ℓ ≤ Δmin /(2𝑑) is a simpler sufficient condition. Remark 2. Suppose that 𝐵𝑛 = 0 and, conditionally on F𝑛 and 𝐴𝑛 = 𝑎 , 𝑌𝑛 ∼ N (𝜇 (𝑎) , 𝑠 𝑎 ) , where n o (𝑎) 𝑠 𝑎 = (𝜎 (𝑎) ) 2 . Define 𝜈𝐺,𝝈 := 2 max1≤𝑎≤𝑑 (|𝜇 (𝑎) | + 𝑠 𝑎 ) 2 + 𝑠 𝑎 𝑒 | 𝜇 |+𝑠𝑎 /2 . Then all conclusions of Theorem 3 hold whenever ℓ ≤ min{1/𝑑, Δmin /(𝑑𝜈𝐺,𝝈 )}. More generally, any predictable baseline satisfying (67) is admissible. If |𝐵𝑛 | ≤ 𝐵max , the same conclusion follows after replacing |𝜇 (𝑎) | above by |𝜇 (𝑎) | + 𝐵max .
3. Concluding Remarks Despite we work under the Brownian diffusions, our analysis is based on constructing Lyapuov functions; hence, it is possible to extend our framework and method to more general stochastic processes. The analysis based on SDEs presented in this paper may open up many interesting
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
21
research questions for a complete understanding of online policy gradient in diffusion environment. Beyond MABs, the policy gradient can also be applied to contextual bandits and general stochastic control problems. It would be interesting to examine the performance of policy gradient in these more general problems. The success of policy gradient suggests the potential of “model-free” learning that only relies on the optimization principle and bypasses statistical principles in devising algorithms. In MAB, the exploration-exploitation tradeoff is naturally entailed by the policy gradient update without further adjustment. Whereas, the “instance-free” regret bound still remains an open problem and the order of our regret upper bound in terms of the number of arms 𝑑 is larger than the typical regret bound for MAB.
Acknowledgments We thank Xuefeng Gao and Jiacheng Zhang for helpful discussion at the early stage of this work. We especially thank Shuaijie Qian for contributing an elegant alternative proof for the two-arm case during our discussion, which is, however, not reflected in this paper. All errors are our own.
References Baudry D, Johnson E, Vary S, Pike-Burke C, Rebeschini P (2025) Does stochastic gradient really succeed for bandits? The Thirty-ninth Annual Conference on Neural Information Processing Systems. Elliott RJ, Moore JB, Aggoun L (1995) Hidden Markov Models: Estimation and Control (Springer). Fan L, Glynn PW (2021) Diffusion approximations for Thompson sampling. arXiv preprint 2105.09232 . Fleming WH, Nisio M (1984) On stochastic relaxed control for partially observed diffusions. Nagoya Mathematical Journal 93:71–108. Ispány M, Pap G (2010) A Note on Weak Convergence of Random Step Processes. Acta Mathematica Hungarica 126(4):381–395. Jacod J, Shiryaev AN (2003) Limit Theorems for Stochastic Processes, volume 288 of Grundlehren der mathematischen Wissenschaften (Springer), 2nd edition. Jia Y, Ouyang D, Zhang Y (2026) Accuracy of discretely sampled stochastic policies in continuous-time reinforcement learning. SIAM Journal on Control and Optimization 64(3):1889–1929.
Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
22 Jia Y, Zhou XY (2022a) Policy evaluation and temporal-difference learning in continuous time and space: A martingale approach. Journal of Machine Learning Research 23(154):1–55. Jia Y, Zhou XY (2022b) Policy gradient and actor-critic learning in continuous time and space: Theory and algorithms. Journal of Machine Learning Research 23(275):1–50. Jia Y, Zhou XY (2023) q-Learning in continuous time. Journal of Machine Learning Research 24(161):1–61. Karatzas I, Shreve S (1991) Brownian Motion and Stochastic Calculus, volume 113 (Springer Science & Business Media). Kuang X, Wager S (2024) Weak signal asymptotics for sequentially randomized experiments. Management Science 70(10):7024–7041. Lattimore T (2026a) A diffusion analysis of policy gradient for stochastic bandits. arXiv preprint arXiv:2603.10219 . Lattimore T (2026b) A Lyapunov analysis of softmax policy gradient for stochastic bandits. arXiv preprint arXiv:2603.26547 . Lattimore T, Szepesvári C (2020) Bandit Algorithms (Cambridge University Press). Mei J, Dai B, Agarwal A, Vaswani S, Raj A, Szepesvári C, Schuurmans D (2024) Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates. Advances in Neural Information Processing Systems 37:74487–74527. Mei J, Zhong Z, Dai B, Agarwal A, Szepesvari C, Schuurmans D (2023) Stochastic gradient succeeds for bandits. International Conference on Machine Learning, 24325–24360 (PMLR). Walton N, Denisov D (2023) Regret analysis of a Markov policy gradient algorithm for multiarm bandits. Mathematics of Operations Research 48(3):1553–1588. Wang H, Zariphopoulou T, Zhou XY (2020) Reinforcement learning in continuous time and space: A stochastic control approach. Journal of Machine Learning Research 21(198):1–34.
e-companion to Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
ec1
Electronic Companion EC.1. MAB as A Stochastic Control Problem We formulate the multi-armed bandit under the continuous-time stochastic control framework. The decision maker (DM) chooses from a collection of arms A = {1, . . . , 𝑑}. Arm 𝑎 ∈ A generates cumulative reward 𝑅𝑡(𝑎) satisfying the following stochastic differential equation (SDE): d𝑅𝑡(𝑎) = 𝜇 (𝑎) d𝑡 + 𝜎 (𝑎) d𝐵𝑡(𝑎) ,
𝑎 ∈ A,
(EC.1)
where 𝝁 = (𝜇 (1) , . . . , 𝜇 (𝑑) ) ⊤ ∈ R𝑑 and 𝝈 = (𝜎 (1) , . . . , 𝜎 (𝑑) ) ⊤ ∈ R𝑑 stand for the reward rate and volatility of the reward flow, and 𝑩 = (𝐵 (1) , . . . , 𝐵 (𝑑) ) ⊤ ∈ R𝑑 is a standard Brownian motion. A classical control problem is to choose an action process 𝐴𝑡 ∈ A , to maximize the long-run average of the cumulative reward 𝑅 𝐴 of the selected arms: 𝑑 ∑︁ 1 𝐴 𝐴 sup lim inf E[𝑅𝑇 ] subject to d𝑅𝑡 = 1 { 𝐴𝑡 =𝑎} d𝑅𝑡(𝑎) , 𝑅0𝐴 = 0. 𝑇→∞ 𝑇 𝐴 𝑎=1
(EC.2)
The bandit problem is nontrivial because 𝝁 is unknown and must be learned only from the rewards generated by the selected arms. We follow the model-free continuous-time reinforcementlearning framework by Wang et al. (2020) and the actor-critic learning in Jia and Zhou (2022b) to showcase how stochastic controls in unknown environment can be attacked systematically.2 EC.1.1. Continuous-time actor–critic learning via relaxed controls
Wang et al. (2020) suggest a relaxed control framework to describe DM’s learning via trial and error. In particular, DM follows a stochastic policy 𝝅𝑡 = (𝜋𝑡(1) , . . . , 𝜋𝑡(𝑑) ) ⊤ ∈ P 𝑑 , a probability vector that describes the choice probability, and considers a relaxed control problem (Fleming and Nisio 1984): √︁ 1 e e𝑡 = 𝝁⊤ 𝝅𝑡 d𝑡 + (𝝈 2 ) ⊤ 𝝅𝑡 d𝐵𝑡𝑅 , 𝑅 e0 = 0 E 𝑅𝑇 , subject to d 𝑅 𝑇→∞ 𝑇
sup lim inf 𝝅
(EC.3)
2 A partially observed control formulation (cf. Elliott et al. 1995) could append a filter for the unknown means, but it
would require a specified likelihood model and would generally enlarge the state space, causing difficulty in solving the augmented control problem.
ec2
e-companion to Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
e𝑡 reflects where 𝐵 𝑅 is a standard Brownian motion, and 𝝈 2 ∈ R𝑑 stands for the entry-wise square. 𝑅
the “average” trajectory of the accumulative reward by “integrating out” the randomness in choosing 𝑎 𝑡 ∼ 𝝅𝑡 “almost continuously in time”. See Jia et al. (2026) for rigorous account of the relations
between SDEs in (EC.2) and (EC.3). The relaxed control problem (EC.3) by itself is still a trivial control problem. Its formal (ergodic) Hamilton–Jacobi–Bellman equation is ′′ ′ 1 max ( 𝝁⊤ 𝝅)𝑉 ★ (𝑅) + (𝝈 2 ) ⊤ 𝝅𝑉 ★ (𝑅) + 𝝁⊤ 𝝅 − 𝛽★ = 0, 2 𝝅∈ P𝑑 where the solution is given by 𝑉 ★ ≡ 0, 𝛽★ = max𝑎∈ A 𝜇 (𝑎) , and the optimal policy is to always choose optimal arms. Whereas, adopting relaxed controls is not to study a new control problem, instead, Jia and Zhou (2022a,b, 2023) demonstrate that principled model-free learning algorithms can be devised for relaxed stochastic controls. We specialize the online policy-gradient actor–critic method of Jia and Zhou (2022b) to the MAB. For this actor-critic learning procedure, one needs to parameterize the value function and the policy separately. Since 𝑉 ★ ≡ 0 is common knowledge that does not depend on 𝝁, we only need to learn the long-run average reward, represented by a scalar parameter 𝛽. The policy is commonly parameterized by the logit function exp(𝜙 (𝑎) ) , with 𝝅(𝝓) = (𝜋 (1) (𝝓), . . . , 𝜋 (𝑑) (𝝓)) ⊤ ∈ P 𝑑 , 𝝓 = (𝜙 (1) , . . . , 𝜙 (𝑑) ) ⊤ ∈ R𝑑 . 𝜋 (𝑎) (𝝓) = Í𝑑 ( 𝑗)) exp(𝜙 𝑗=1
The derivation in Jia and Zhou (2022b) suggests the learning scheme via stochastic approximation to solve the following martingale conditions and the first order conditions of the policy gradient: ∫ 𝐴 ★ (d𝑅𝑡 + d𝑉𝑡 − 𝛽𝑡 d𝑡) = 0 (for learning 𝛽) E ∫ . ( 𝐴 ) 𝐴 ★ 𝑡 (𝝓𝑡 ) (d𝑅𝑡 + d𝑉𝑡 − 𝛽𝑡 d𝑡) = 0 (for learning 𝝓) ∇𝝓 log 𝜋 E Thus, the online, incremental learning can be informally represented by (1). A common choice is to take the learning rates as 𝛼𝑡 = 1/(𝑡 + 𝜂) and ℓ𝑡 ≡ ℓ . Under this choice, we can solve 𝛽𝑡 in (1) explicitly as 𝛽𝑡 = (𝑅𝑡𝐴 + 𝛽0 𝜂)/(𝑡 + 𝜂) ; thus 𝛽𝑡 can be interpreted as the approximate average-reward, and it is used as a natural “benchmark” in the update of 𝝓𝑡 . The policy gradient update for 𝝓𝑡 in (1) is only informal in continuous-time because continuous independent sampling is infeasible. Its implementation is summarized in E-Companion EC.3.
e-companion to Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
ec3
Following Wang et al. (2020) and Jia et al. (2026), we “integrate out” the impact of randomization of action 𝑎 𝑡 ∼ 𝝅𝑡 with the high frequency sampling, and the statistical properties of 𝝓𝑡 is fully characterized by the aggregated SDE (2). We present an intuitive derivation of (2) in the ECompanion EC.4, and such a derivation is rigorously proved as the weak limit of the high-frequency sampling in Jia et al. (2026).
EC.2. Diffusion Limit of the Discrete-Time Policy Gradient Algorithm To connect the continuous-time framework with the conventional discrete-time policy gradient (e.g., Mei et al. 2023), we consider the latter in the “diffusion limit” (Fan and Glynn 2021, Kuang and √ Wager 2024). To be more precise, upon every draw, arm 𝑎 generates reward 𝑟 𝑘(𝑎) , (𝑛) = 𝜇 (𝑎) + 𝑛𝜉 𝑘(𝑎) , where 𝑛 is a scaling parameter that measures the noise to signal ratio of the reward, and 𝜉 𝑘(𝑎) are i.i.d. noise whose distribution is irrelevant of 𝑛. The conventional discrete-time policy gradient updates the policy (with the same logit parameterization and a constant learning rate ℓ ) via: (𝐴
(𝑛)
) , (𝑛)
(𝑛) (𝑛) , 𝑅0(𝑛) = 0, = 𝑅 𝑘(𝑛) + 𝑟 𝑘 𝑘 = 𝑅 𝑘(𝑛) + Δ𝑅 𝑘+1 𝑅 𝑘+1 (𝑛) (𝑛) − 𝛽 𝑘(𝑛) , = 𝝓 𝑘(𝑛) + ℓ 𝒆 𝐴(𝑛) − 𝝅 𝑘(𝑛) Δ𝑅 𝑘+1 𝝓 𝑘+1
(EC.4)
𝑘
where 𝝅 𝑘(𝑛) = 𝝅(𝝓 𝑘(𝑛) /𝑛) , and 𝐴 𝑘(𝑛) ∼ 𝝅 𝑘(𝑛) is an independent random draw. e𝑡(𝑛) ) be scaled piecewise-constant interpolation of this recursion, defined as Let ( 𝝓e𝑡(𝑛) , 𝑅 1 (𝑛) e(𝑛) 1 (𝑛) 𝝓e𝑡(𝑛) = 𝝓 ⌊𝑡 , 𝑅 = 𝑅 ⌊𝑡 𝑛⌋ . 𝑛 𝑛⌋ 𝑡 𝑛
Theorem EC.1. Fix 𝑇 > 0. Let F𝑘(𝑛) contain the history before round 𝑘 , so that 𝝓 𝑘(𝑛) , 𝑅 𝑘(𝑛) , and (𝑛) 𝛽 𝑘(𝑛) are F𝑘(𝑛) -measurable, and let F𝑘+1 contain the sampled action and observed innovation. (𝑛) (𝑛) e ) = (𝝓0 , 0) is deterministic and independent of 𝑛. Write 𝑠 𝑎 = (𝜎 (𝑎) ) 2 and Suppose that ( 𝝓e , 𝑅
0 0 (𝑛) (𝑛) E 𝑘,𝑎 [·] := E[· | F𝑘 , 𝐴 𝑘(𝑛) = 𝑎] . Assume, uniformly in 𝑛, 𝑘 , and 𝑎 , (𝑛) (𝑛) (𝑛) E 𝑘,𝑎 [𝜉 𝑘(𝑎) ] = 0, E 𝑘,𝑎 [(𝜉 𝑘(𝑎) ) 2 ] = 𝑠 𝑎 , E 𝑘,𝑎 [|𝜉 𝑘(𝑎) | 4 ] ≤ 𝐶 𝜉 , sup
max
𝑛≥1 0≤ 𝑘 ≤ ⌊𝑛𝑇 ⌋
h i E |𝛽 𝑘(𝑛) | 4 < ∞. (EC.5)
Then the following statements hold. (i) Weak convergence. As 𝑛 → ∞, e(𝑛) ) =⇒ (𝝓, 𝑅) e ( 𝝓e(𝑛) , 𝑅
in
𝐷 ( [0, 𝑇]; R𝑑+1 ),
(EC.6)
e-companion to Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
ec4
e is the unique (weak) solution of (2) and where 𝐷 ([0, 𝑇]; R𝑑+1 ) is the Skorokhod space and (𝝓, 𝑅) ⊤ √︁ √︁ 2 2 (EC.3) with d𝑩𝝓𝑡 d𝐵𝑡𝑅 = √ 2 1⊤ 𝜋 (1) (𝝓𝑡 )𝜎 (1) , · · · , 𝜋 (𝑑) (𝝓𝑡 )𝜎 (𝑑) . (𝝈 ) 𝝅 (𝝓𝑡 )
(ii) Weak convergence order. For every 𝑓 ∈ 𝐶𝑏4 (R𝑑+1 ) , i.e., a fourth-time continuously differentiable function whose up to fourth-time order derivatives are bounded, there is a constant 𝐶 𝑓 ,𝑇 < ∞, independent of 𝑛, such that e𝑡(𝑛) ) − E 𝑓 (𝝓𝑡 , 𝑅 e𝑡 ) ≤ 𝐶 𝑓 ,𝑇 𝑛 −1/2 . sup E 𝑓 ( 𝝓e𝑡(𝑛) , 𝑅
(EC.7)
0≤𝑡 ≤𝑇
If, in addition, (𝑛) E 𝑘,𝑎 [(𝜉 𝑘(𝑎) ) 3 ] = 0
for all 𝑛, 𝑘, 𝑎,
(EC.8)
then the weak error is first order: e𝑡 ) ≤ 𝐶 𝑓 ,𝑇 𝑛 −1 . e𝑡(𝑛) ) − E 𝑓 (𝝓𝑡 , 𝑅 sup E 𝑓 ( 𝝓e𝑡(𝑛) , 𝑅
(EC.9)
0≤𝑡 ≤𝑇
(𝑛) . Write E 𝑘 [·] = Put ℎ = 1/𝑛, 𝑡 𝑘 = 𝑘 ℎ, 𝑿 𝑘(𝑛) = (𝑛 −1 (𝝓 𝑘(𝑛) ) ⊤ , 𝑛 −1 𝑅 𝑘(𝑛) ) ⊤ , and 𝑿𝑡(𝑛) = 𝑿 ⌊𝑛𝑡 ⌋ E[· | F (𝑛) ] and 𝒑 = 𝝅( 𝝓e(𝑛) ) . For 𝒖 𝑎 = 𝒆 𝑎 − 𝒑 , set 𝒘 𝑎 = (ℓ𝒖 ⊤𝑎 , 1) ⊤ and 𝒅 𝑎,𝑘 = (ℓ(𝜇 (𝑎) −
Proof.
𝑘 𝑘/𝑛 (𝑛) ⊤ (𝑎) ⊤ 𝛽 𝑘 )𝒖 𝑎 , 𝜇 ) . Then the scaled recursion has the exact increment
(𝑛) √ (𝐴 ) (𝑛) Δ𝑿 𝑘+1 = ℎ𝒅 𝐴(𝑛) ,𝑘 + ℎ 𝒘 𝐴(𝑛) 𝜉 𝑘 𝑘 . 𝑘
(EC.10)
𝑘
For 𝒑 ∈ P 𝑑 , define
ℓ 𝑱( 𝒑) 𝝁 ℓ𝑮 𝝈 ( 𝒑) 𝒃( 𝒑) := , 𝚪( 𝒑) := , 𝒂( 𝒑) := 𝚪( 𝒑)𝚪( 𝒑) ⊤ . 𝝁⊤ 𝒑 𝒈𝝈 ( 𝒑) ⊤ Í The identity 𝑎 𝑝 (𝑎) 𝒖 𝑎 = 0 cancels the baseline in the conditional drift, and direct conditioning
gives (𝑛) E 𝑘 [Δ𝑿 𝑘+1 ] = ℎ𝒃( 𝒑), (𝑛) Cov 𝑘 (Δ𝑿 𝑘+1 ) = ℎ𝒂( 𝒑) + ℎ2 𝑹 𝑘,𝑛 , h i (𝑛) 4 E 𝑘 ∥Δ𝑿 𝑘+1 ∥ ≤ 𝐶ℎ2 (1 + |𝛽 𝑘(𝑛) | 4 ).
where 𝑹 𝑘,𝑛 =
Í
𝑎𝑝
(𝑎) 𝒅
(EC.11) ∥ 𝑹 𝑘,𝑛 ∥ ≤ 𝐶 (1 + |𝛽 𝑘(𝑛) | 2 ),
(EC.12) (EC.13)
⊤ ⊤ 𝑎,𝑘 𝒅 𝑎,𝑘 − 𝒃( 𝒑)𝒃( 𝒑) . Moreover,
2 ℓ 𝑸𝝈 ( 𝒑) ℓ 𝑱( 𝒑)𝒔 𝒂( 𝒑) = , ℓ𝒔⊤ 𝑱( 𝒑) 𝒔⊤ 𝒑
𝒔 = (𝑠1 , . . . , 𝑠 𝑑 ) ⊤ ,
(EC.14)
e-companion to Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
ec5
Thus 𝒃 and 𝒂 are the drift and covariance of the following SDE d𝝓𝑡 = ℓ 𝑱(𝝅𝑡 ) 𝝁 d𝑡 + ℓ𝑮 𝝈 (𝝅𝑡 ) d𝑾𝑡 , e𝑡 = 𝝁⊤ 𝝅𝑡 d𝑡 + 𝒈𝝈 (𝝅𝑡 ) ⊤ d𝑾𝑡 , d𝑅
𝝅𝑡 = 𝝅(𝝓𝑡 ),
e0 ) = (𝝓0 , 0), (𝝓0 , 𝑅
(EC.15)
where 𝑾 is a standard 𝑑 -dimensional Brownian motion. In particular, the actor–reward crosscovariance is ℓ 𝑱( 𝒑)𝒔, which vanishes for common volatility since then 𝒔 ∝ 𝒆 . Apply Ispány and Pap (2010, Corollary 2.2), the random-step-process specialization of Jacod (𝑛) (𝑛) and Shiryaev (2003, Theorem IX.3.39), with initial term 𝑿0(𝑛) and increments 𝑼 𝑘+1 = Δ𝑿 𝑘+1 . Put
𝑁𝑡 = ⌊𝑛𝑡⌋ , 𝒃 𝑠(𝑛) = 𝒃(𝝅( 𝝓e𝑠(𝑛) )) , and 𝒂 𝑠(𝑛) = 𝒂(𝝅( 𝝓e𝑠(𝑛) )) . Equations (EC.11), (EC.12), (EC.13), and
(EC.5) give the three required estimates: sup
∑︁
𝑡 ≤𝑇 𝑘<𝑁 𝑡
E sup
∑︁
𝑡 ≤𝑇 𝑘<𝑁 𝑡
E
∑︁
(𝑛) ]− E 𝑘 [Δ𝑿 𝑘+1
∫ 𝑡
𝒃 𝑠(𝑛) d𝑠 ≤ 𝐶ℎ,
0
(𝑛) )− Cov 𝑘 (Δ𝑿 𝑘+1
∫ 𝑡
𝒂 𝑠(𝑛) d𝑠 ≤ 𝐶𝑇 ℎ,
0
h i ∑︁ (𝑛) 2 (𝑛) 4 E 𝑘 ∥Δ𝑿 𝑘+1 ∥ 1 { ∥Δ𝑿 (𝑛) ∥ > 𝜀 } ≤ 𝜀 −2 ∥ ≤ 𝐶 𝜀,𝑇 ℎ. E∥Δ𝑿 𝑘+1 𝑘+1
𝑘<𝑁𝑇
𝑘<𝑁𝑇
Thus the three conditions hold uniformly on [0, 𝑇] in probability. The initial-state condition is exact. Moreover, 𝒃(𝝅(·)) and 𝚪(𝝅(·)) are bounded and globally Lipschitz, so (EC.15) has a unique weak solution by Karatzas and Shreve (1991, Chapter 5, Theorem 2.9). Hence Ispány and Pap (2010, Corollary 2.2) yields (EC.6). For the weak orders, let (𝑃𝑟 )𝑟 ≥0 and L be the semigroup and generator of (EC.15). Its 𝐶𝑏∞ coefficients and standard backward-Kolmogorov regularity give, for 𝑓 ∈ 𝐶𝑏4 , sup𝑟 ≤𝑇 (∥𝑃𝑟 𝑓 ∥ 𝐶 4 + 𝑏
∥L 2 𝑃𝑟 𝑓 ∥ ∞ ) ≤ 𝐶 𝑓 ,𝑇 . For a grid time 𝑡 𝑚 = 𝑚ℎ, set 𝑔 𝑘 = 𝑃𝑡𝑚 −𝑡𝑘 𝑓 . Since 𝑔𝑚 = 𝑓 and 𝑔 𝑘 = 𝑃 ℎ 𝑔 𝑘+1 , E 𝑓 ( 𝑿𝑚(𝑛) ) − 𝑃𝑡𝑚 𝑓 ( 𝑿0(𝑛) ) =
𝑚−1 ∑︁
h i (𝑛) E E 𝑘 𝑔 𝑘+1 ( 𝑿 𝑘+1 ) − 𝑃 ℎ 𝑔 𝑘+1 ( 𝑿 𝑘(𝑛) ) .
𝑘=0
Thus, as in Jia et al. (2026, Theorem 4.1), it remains to compare the one-step moments of the present non-Gaussian recursion. The remaining third moment follows from (EC.10): (𝑛) ⊗3 E 𝑘 [(Δ𝑿 𝑘+1 ) ] = ℎ3/2
𝑑 ∑︁ 𝑎=1
(𝑛) 𝑝 (𝑎) E 𝑘,𝑎 [(𝜉 𝑘(𝑎) ) 3 ]𝒘 𝑎⊗3 + 𝑂 ℎ2 (1 + |𝛽 𝑘(𝑛) | 4 ) .
(EC.16)
ec6
e-companion to Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
(𝑛) Put 𝒙 = 𝑿 𝑘(𝑛) and 𝜹 = Δ𝑿 𝑘+1 . Conditional Taylor expansion gives
1 E 𝑘 𝑔(𝒙 + 𝜹) = 𝑔(𝒙) + 𝐷𝑔(𝒙) · E 𝑘 [𝜹] + 𝐷 2 𝑔(𝒙) : E 𝑘 [𝜹 ⊗2 ] 2 1 3 ⊗3 + 𝐷 𝑔(𝒙) : E 𝑘 [𝜹 ] + 𝑂 ∥𝑔∥ 𝐶 4 E 𝑘 ∥𝜹∥ 4 . 𝑏 6
Here “:” denotes full tensor contraction. Since E 𝑘 [𝜹 ⊗2 ] = Cov 𝑘 (𝜹) + (E 𝑘 𝜹) ⊗2 , (EC.11) and (EC.12) make the linear and quadratic terms ℎL𝑔(𝒙) + 𝑂 (ℎ2 (1 + |𝛽 𝑘(𝑛) | 2 )) . Meanwhile, the semigroup ∫ℎ identity 𝑃 ℎ 𝑔 − 𝑔 − ℎL𝑔 = 0 (ℎ − 𝑠)𝑃𝑠 L 2 𝑔 d𝑠 is 𝑂 (ℎ2 ) . Hence (EC.16) is the only possible ℎ3/2 contribution; it becomes 𝑂 (ℎ2 (1 + |𝛽 𝑘(𝑛) | 4 )) under (EC.8), while (EC.13) bounds the remainder at the same order. Uniformly for 𝑔 = 𝑃𝑟 𝑓 , 0 ≤ 𝑟 ≤ 𝑇 , we therefore have ( ℎ3/2 , in general, (𝑛) (𝑛) (𝑛) 4 E 𝑘 𝑔( 𝑿 𝑘+1 ) − 𝑃 ℎ 𝑔( 𝑿 𝑘 ) ≤ 𝐶 𝑓 ,𝑇 (1 + |𝛽 𝑘 | ) 2 ℎ , under (EC.8),
(EC.17)
which is the only use of the third-moment condition. Summing at most 𝑇/ℎ terms and using (EC.5) gives grid-time errors 𝐶 𝑓 ,𝑇 ℎ1/2 and 𝐶 𝑓 ,𝑇 ℎ, respectively. Between grid points 𝑿 (𝑛) is constant and |𝑃𝑡 𝑓 (𝒙) − 𝑃𝑠 𝑓 (𝒙)| ≤ ∥L 𝑓 ∥ ∞ |𝑡 − 𝑠| for |𝑡 − 𝑠| ≤ ℎ. Taking the supremum over [0, 𝑇] and using ℎ = 1/𝑛 proves (EC.7) and (EC.9).
□
The weak convergence of the scaled discrete-time policy gradient algorithm is established using a semimartingale convergence theorem from Jacod and Shiryaev (2003). Similar diffusion limit of other classical bandit algorithms have been studied by Fan and Glynn (2021), Kuang and Wager (2024) but it is new for the policy gradient. In addition to the weak convergence, we also obtain the rate of convergence in terms of bounded test functions, which is derived for a discrete sampling of SDEs in Jia et al. (2026). The obtained aggregated SDE (2) is consistent with the one suggested in Lattimore (2026a), thus, we provide a solid micro-foundation for this stochastic system and the framework by Wang et al. (2020), Jia and Zhou (2022b).
EC.3. Pseudo Code for Actor-Critic Algorithm For MAB We summarize the implementation of the algorithm (1) by discrete sampling as Algorithm 1. It turns out to coincide with the conventional (discrete-time) policy gradient algorithm with a particular baseline.
e-companion to Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
ec7
Algorithm 1 Online Actor–Critic Algorithm for Multi-Armed Bandit 1: Input: intervention times 0 = 𝑡 0 < 𝑡 1 < · · · , actor learning rates ℓ𝑘 , and critic learning rates 𝛼 𝑘 . 2: Initialize 𝝓0 , 𝛽0 , and 𝑅0 = 0. 3: for 𝑘 = 0, 1, . . . do 4:
Set ℎ 𝑘 = 𝑡 𝑘+1 − 𝑡 𝑘 and 𝝅 𝑘 = 𝝅(𝝓 𝑘 ) .
5:
Draw 𝐴 𝑘 ∼ 𝝅 𝑘 , hold arm 𝐴 𝑘 on [𝑡 𝑘 , 𝑡 𝑘+1 ) , and observe its reward increment Δ𝑅 𝑘+1 .
6:
Update the actor using the pre-update critic, 𝝓 𝑘+1 = 𝝓 𝑘 + ℓ𝑘 (𝒆 𝐴𝑘 − 𝝅 𝑘 ) Δ𝑅 𝑘+1 − 𝛽 𝑘 ℎ 𝑘 .
7:
Update the critic and accumulated reward, 𝛽 𝑘+1 = 𝛽 𝑘 + 𝛼 𝑘 Δ𝑅 𝑘+1 − 𝛽 𝑘 ℎ 𝑘 ,
𝑅 𝑘+1 = 𝑅 𝑘 + Δ𝑅 𝑘+1 .
8: end for
EC.4. Intuitive Derivation of Policy Gradient SDE (2) For reader’s convenience and pedagogical purpose, we use the heuristic argument in Wang et al. (2020) to demonstrate how to obtain the aggregated SDE (2) from its informal counterpart (1). The rigorous argument can be found in Jia et al. (2026) for more general SDEs. Í The d𝑡 term in d𝝓𝑡 in (1) is ℓ𝑡 𝑑𝑎=1 1 { 𝐴𝑡 =𝑎} (𝒆 𝑎 − 𝝅(𝝓𝑡 )) (𝜇𝑡(𝑎) − 𝛽𝑡 ) . We take the expectation of this term with respect to 𝐴𝑡 ∼ 𝝅(𝝓𝑡 ) conditioned on 𝝓𝑡 , 𝛽𝑡 , we get " E 𝐴𝑡 ∼𝝅 (𝝓𝑡 ) ℓ𝑡
𝑑 ∑︁
# 1 { 𝐴𝑡 =𝑎} (𝒆 𝑎 − 𝝅(𝝓𝑡 )) (𝜇𝑡(𝑎) − 𝛽𝑡 )
𝑎=1 =ℓ𝑡 diag{𝝅(𝝓𝑡 )}( 𝝁 − 𝛽𝑡 𝒆) − (𝝅(𝝓𝑡 ) ⊤ 𝝁 − 𝛽𝑡 )𝝅(𝝓𝑡 ) = ℓ𝑡 diag{𝝅(𝝓𝑡 )} − 𝝅(𝝓𝑡 )𝝅(𝝓𝑡 ) ⊤ 𝝁
=ℓ𝑡 𝑱(𝝅𝑡 ) 𝝁.
e-companion to Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
ec8
The d𝐵𝑡 term in d𝝓𝑡 in (1) is ℓ𝑡
(𝑎) (𝑎) 𝑎=1 1 { 𝐴𝑡 =𝑎} (𝒆 𝑎 − 𝝅(𝝓 𝑡 ))𝜎𝑡 d𝐵𝑡 . We take the expectation
Í𝑑
to the quadratic variation of this term with respect to 𝐴𝑡 ∼ 𝝅(𝝓𝑡 ) conditioned on 𝝓𝑡 , 𝛽𝑡 , we get E 𝐴𝑡 ∼𝝅 (𝝓𝑡 ) d𝝓𝑡 d𝝓⊤ 𝑡 | 𝝓 𝑡 , 𝛽𝑡 " 𝑑 # ∑︁ 2 =ℓ𝑡2 E 𝐴𝑡 ∼𝝅 (𝝓𝑡 ) 1 { 𝐴𝑡 =𝑎} 𝜎 (𝑎) (𝒆 𝑎 − 𝝅(𝝓𝑡 )) (𝒆 𝑎 − 𝝅(𝝓𝑡 )) ⊤ d𝑡 𝑎=1
=ℓ𝑡2
h
i ⊤ diag{𝝅(𝝓𝑡 )} diag{𝝈 2 } − diag{𝝅(𝝓𝑡 )}𝝈 2 𝝅(𝝓𝑡 ) ⊤ − 𝝅(𝝓𝑡 )𝝈 2 diag{𝝅(𝝓𝑡 )} + (𝝅(𝝓𝑡 ) ⊤ 𝝈 2 )𝝅(𝝓𝑡 )𝝅(𝝓𝑡 ) ⊤ d𝑡
=ℓ𝑡2 ( 𝑰 − 𝝅𝒆 ⊤ ) diag{𝜋 (1) 𝜎 (1) , . . . , 𝜋 (𝑑) 𝜎 (𝑑) }( 𝑰 − 𝝅𝒆 ⊤ ) ⊤ d𝑡. 2
2
The expected drift and quadratic variation (taking the expectation with respect to 𝐴𝑡 ) of d𝝓𝑡 in (1) coincides that in the aggregated SDE (2) with constant learning rate ℓ𝑡 ≡ ℓ . The relations between SDEs in (EC.2) and (EC.3) can be similarly obtained. The above investigation only restricts to 𝝓𝑡 and 𝑅𝑡 separately. We can further examine their cross variation by integrating out 𝐴𝑡 ∼ 𝝅(𝝓𝑡 ) conditioned on 𝝓𝑡 , 𝛽𝑡 , that is, E 𝐴𝑡 ∼𝝅 (𝝓𝑡 ) d𝑅𝑡𝐴d𝝓𝑡 | 𝝓𝑡 , 𝛽𝑡 " 𝑑 # ∑︁ (𝑎) 2 =ℓ𝑡 E 𝐴𝑡 ∼𝝅 (𝝓𝑡 ) 1 { 𝐴𝑡 =𝑎} 𝜎 (𝒆 𝑎 − 𝝅(𝝓𝑡 )) d𝑡 𝑎=1 =ℓ𝑡 diag{𝝅(𝝓𝑡 )}𝝈 2 − 𝝅(𝝓𝑡 ) ⊤ 𝝈 2 𝝅(𝝓𝑡 ) d𝑡 = ℓ𝑡 𝑱(𝝅𝑡 )𝝈 2 d𝑡.
The cross-variation structure motivates the correlation between d𝐵𝑡𝑅 and d𝑩𝝓𝑡 in (EC.3) and (2).
EC.5. Intuition from Two-Armed Bandit To gain some intuition about the aggregated SDE (2), we look at the special case of two-armed bandit 𝑑 = 2. In this case, the policy can be represented by 𝜋𝑡(1) = 𝜋𝑡(2) =
(1)
𝑒 𝜙𝑡
1
(2) − 𝜙𝑡
+1
(1) 𝑒 𝜙𝑡 (2) (1) 𝑒 𝜙𝑡 +𝑒 𝜙𝑡
=
(2) (1) − 𝜙𝑡 (2) (1) 𝑒 𝜙𝑡 − 𝜙𝑡 +1
𝑒 𝜙𝑡
, and
. Hence, it suffices to examine the property of 𝛿𝜙𝑡 = 𝜙𝑡(1) − 𝜙𝑡(2) ∈ R, a scalar
variable; or equivalently 𝜋𝑡(1) = 𝑒 𝑒𝛿 𝜙𝑡 +1 . 𝛿 𝜙𝑡
Then (2) reduces to √︃ √︃ (1) (1) (1) (2) 1 − 𝜋𝑡 𝜎 , − 𝜋𝑡 𝜎 d𝑩𝝓𝑡 √︃ √︃ 𝑑 2 2 =2ℓ𝜋𝑡(1) (1 − 𝜋𝑡(1) ) (𝜇 (1) − 𝜇 (2) )d𝑡 + 2ℓ 𝜋𝑡(1) (1 − 𝜋𝑡(1) ) (1 − 𝜋𝑡(1) )𝜎 (1) + 𝜋𝑡(1) 𝜎 (2) d𝐵𝑡 ,
d𝛿𝜙𝑡 =2ℓ𝜋𝑡(1) (1 − 𝜋𝑡(1) ) (𝜇 (1) − 𝜇 (2) )d𝑡 + 2ℓ
𝑑
where “=” means equality in distribution.
√︃
𝜋𝑡(1) (1 − 𝜋𝑡(1) )
e-companion to Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
ec9
We notice that the direction of the drift in the parameter space (𝛿𝜙𝑡 ) is a constant and governed by the difference of drift 𝜇 (1) − 𝜇 (2) and its magnitude is determined by the learning rate ℓ . Since 𝛿𝜙𝑡 is a scalar, the volatility part can be equivalently represented by a scalar Brownian motion 𝐵𝑡 ,
and it also scales with the learning rate ℓ . Such a structure does not immediately imply 𝛿𝜙𝑡 would grow to infinity caused by the drift 𝜇 (1) − 𝜇 (2) as such a force would be canceled with the term 𝜋𝑡(1) (1 − 𝜋𝑡(1) ) which is diminishing as 𝛿𝜙𝑡 approaches to infinity.
Therefore, we have to examine the dynamic of the policy 𝜋𝑡(1) in the policy space. By Itô’s lemma, we have 1 d𝜋𝑡(1) =𝜋𝑡(1) (1 − 𝜋𝑡(1) )d𝛿𝜙𝑡 + 𝜋𝑡(1) (1 − 𝜋𝑡(1) ) (1 − 2𝜋𝑡(1) )d⟨𝛿𝜙⟩𝑡 2 3/2 √︃ 2 2 2 (1) (1) =2ℓ 𝜋𝑡 (1 − 𝜋𝑡 ) (𝜇 (1) − 𝜇 (2) )d𝑡 + 2ℓ 𝜋𝑡(1) (1 − 𝜋𝑡(1) ) (1 − 𝜋𝑡(1) )𝜎 (1) + 𝜋𝑡(1) 𝜎 (2) d𝐵𝑡 2 h i 2 2 + 2ℓ 2 𝜋𝑡(1) (1 − 𝜋𝑡(1) ) (1 − 2𝜋𝑡(1) ) (1 − 𝜋𝑡(1) )𝜎 (1) + 𝜋𝑡(1) 𝜎 (2) d𝑡 | {z } Itô’s correction term
2 2 2 = 2ℓ 𝜋𝑡(1) (1 − 𝜋𝑡(1) ) 𝜇 (1) − 𝜇 (2) + ℓ(1 − 2𝜋𝑡(1) ) (1 − 𝜋𝑡(1) )𝜎 (1) + 𝜋𝑡(1) 𝜎 (2) d𝑡 | {z } | {z } | {z } desired driving force distortion in signal how fast learning vanishes √︃ 3/2 2 2 + 2ℓ 𝜋𝑡(1) (1 − 𝜋𝑡(1) ) (1 − 𝜋𝑡(1) )𝜎 (1) + 𝜋𝑡(1) 𝜎 (2) d𝐵𝑡 . {z } | {z }| how fast volatility vanishes
bounded from below and above
(EC.18) On the one hand, the leading direction of the dynamic of the policy 𝜋𝑡(1) is governed by two forces: the reward rate gap 𝜇 (1) − 𝜇 (2) , which is the desired signal indicating the better arm, and 2 2 the distortion term ℓ(1 − 2𝜋𝑡(1) ) (1 − 𝜋𝑡(1) )𝜎 (1) + 𝜋𝑡(1) 𝜎 (2) , caused by the propagation of noises.
Any limiting point of (EC.18), if exists, must enforce the drift of 𝜋𝑡(1) to be 0. Besides two obvious absorbing points 0 and 1, the distortion term may cause another point of such an equilibrium point, 2 2 that value 𝜋ˆ such that 𝜇 (1) − 𝜇 (2) + ℓ(1 − 2𝜋) ˆ (1 − 𝜋)𝜎 ˆ (1) + 𝜋𝜎 ˆ (2) = 0. If 𝜋ˆ ∉ (0, 1) , then it does not affect the limiting behavior; otherwise if 𝜋ˆ ∈ (0, 1) , it becomes an undesired equilibrium point. Despite 𝜋ˆ is not an absorbing point because there is still random noise that will drive 𝜋𝑡(1) away from 𝜋ˆ , it may still slow down the convergence rate of the process. The value of 𝜋ˆ can be controlled by
the learning rate ℓ . When ℓ is sufficiently small, it is guaranteed that 𝜋ˆ ∉ (0, 1) , thus, we can expect faster convergence. This intuition is consistent with the small learning rate condition in Theorem 1.
ec10
e-companion to Jia and Ouyang: Convergence and Regret of the Policy Gradient for MAB in Diffusion Environment
On the other hand, between two absorbing points 0 and 1, whether it is attainable within a finite time is largely determined by the relative magnitude of the drift and volatility as 𝜋𝑡(1) approaches to 0 or 1. In the one-dimension case, there is the well-known Feller’s test for explosion which describes a rate function that serves as the Lyapunov function to analyze the limiting behavioral, see, e.g., Karatzas and Shreve (1991, Chapter 5, Proposition 5.22). Applying the conclusion therein to (EC.18), one can prove the almost sure convergence for arbitrary constant learning rate. This conclusion is a special case of Theorem 2.