Paper deep dive
Meta-Learning for Repeated Bayesian Persuasion
Ata Poyraz Turna, Asrin Efe Yorulmaz, Tamer Başar
Intelligence
Status: succeeded | Model: anthropic/claude-sonnet-4.6 | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/24/2026, 3:06:13 AM
Summary
This paper introduces Meta-Persuasion algorithms that combine meta-learning with Bayesian persuasion frameworks (Online Bayesian Persuasion and Markov Persuasion Processes). The authors establish the first theoretical results for meta-learning in repeated Bayesian persuasion settings under both full-feedback and bandit-feedback, achieving provably sharper regret rates when tasks share structural similarity while recovering standard single-game guarantees in adversarial settings.
Entities (28)
Relation Signals (22)
Asrın Efe Yorulmaz → affiliatedwith → University of Illinois Urbana-Champaign
confidence 99% · Asrın Efe Yorulmaz, University of Illinois Urbana–Champaign
Tamer Başar → affiliatedwith → University of Illinois Urbana-Champaign
confidence 99% · Tamer Başar, University of Illinois Urbana–Champaign
Ata Poyraz Turna → affiliatedwith → Bogazici University
confidence 99% · Ata Poyraz Turna, Bogazici University; e-mail: ata.turna@std.bogazici.edu.tr
Meta-Persuasion → appliedto → Online Bayesian Persuasion (OBP)
confidence 99% · we introduce Meta-Persuasion algorithms, establishing the first line of theoretical results for both full-feedback and bandit-feedback settings in the Online Bayesian Persuasion (OBP) and Markov Persuasion Process (MPP) frameworks
Meta-Persuasion → appliedto → Markov Persuasion Process (MPP)
confidence 99% · we introduce Meta-Persuasion algorithms, establishing the first line of theoretical results for both full-feedback and bandit-feedback settings in the Online Bayesian Persuasion (OBP) and Markov Persuasion Process (MPP) frameworks
Ata Poyraz Turna → authored → Meta-Learning for Repeated Bayesian Persuasion
confidence 99% · Author list of the paper
Tamer Başar → authored → Meta-Learning for Repeated Bayesian Persuasion
confidence 99% · Author list of the paper
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Classical Bayesian persuasion studies how a sender influences receivers through carefully designed signaling policies within a single strategic interaction. In many real-world environments, such interactions are repeated across multiple games, creating opportunities to exploit structural similarity across tasks. In this work, we introduce Meta-Persuasion algorithms, establishing the first line of theoretical results for both full-feedback and bandit-feedback settings in the Online Bayesian Persuasion (OBP) and Markov Persuasion Process (MPP) frameworks. We show that our proposed meta-persuasion algorithms achieve provably sharper regret rates under natural notions of task similarity, improving upon the best-known convergence rates for both OBP and MPP. At the same time, they recover the standard single-game guarantees when the sequence of games is picked arbitrarily. Finally, we complement our theoretical analysis with numerical experiments that highlight our regret improvements and the benefits of meta-learning in repeated persuasion environments.
Tags
Links
- Source: https://arxiv.org/abs/2603.20408v1
- Canonical: https://arxiv.org/abs/2603.20408v1
Trouble viewing inline? Open PDF directly →
Full Text
166,747 characters extracted from source content.
Expand or collapse full text
Meta-Learning for Repeated Bayesian Persuasion Ata Poyraz Turna111Bogazici University; e-mail: ata.turna@std.bogazici.edu.tr Asrın Efe Yorulmaz 222University of Illinois Urbana–Champaign; e-mail: ay20@illinois.edu Tamer Başar333University of Illinois Urbana–Champaign; e-mail: basar1@illinois.edu Abstract Classical Bayesian persuasion studies how a sender influences receivers through carefully designed signaling policies within a single strategic interaction. In many real-world environments, such interactions are repeated across multiple games, creating opportunities to exploit structural similarity across tasks. In this work, we introduce Meta-Persuasion algorithms, establishing the first line of theoretical results for both full-feedback and bandit-feedback settings in the Online Bayesian Persuasion (OBP) and Markov Persuasion Process (MPP) frameworks. We show that our proposed meta-persuasion algorithms achieve provably sharper regret rates under natural notions of task similarity, improving upon the best-known convergence rates for both OBP and MPP. At the same time, they recover the standard single-game guarantees when the sequence of games is picked arbitrarily. Finally, we complement our theoretical analysis with numerical experiments that highlight our regret improvements and the benefits of meta-learning in repeated persuasion environments. 1 Introduction Information design has become a central tool for understanding how strategic agents behave when information is scarce, costly, or asymmetric. In the classical Bayesian Persuasion framework (Kamenica and Gentzkow, 2011), a sender observes the true state of the world and strategically commits to a signaling policy that shapes the posterior beliefs and consequently the actions of a Bayesian receiver. The sender’s goal is to choose an information structure that induces desirable behavior, despite the receivers acting in their own best interest. This model has found applications in economics (Kamenica and Gentzkow, 2011), policy design (Başar, 2024; Yorulmaz et al., 2025), online marketplaces (Arieli et al., 2024), and recommendation systems (Mansour et al., 2016), where the ability to influence actions through information is often as valuable as the ability to influence incentives. While the original formulation concerns a single persuasion instance, many real-world scenarios involve repeated persuasion problems that share structural similarity. Regulators routinely interact with similar firms, platforms continually seek to guide users with the same backgrounds across repeated recommendation sessions, and automated systems must repeatedly persuade agents whose preferences vary but are not entirely arbitrary. Each persuasion instance is rarely isolated: it is typically one draw from a family of related problems. This suggests that a principal may benefit from transferring knowledge across persuasion tasks. In other words, persuasion itself may admit a notion of learning to persuade. Concept of meta-learning (Thrun and Pratt, 1998) provides such a paradigm: an agent faces a sequence of related tasks and aims to exploit shared structure to improve performance on each new task. Meta-learning has shown substantial gains in multi-task optimization, online learning, and bandit problems, especially when worst-case guarantees are overly pessimistic for structured environments (Khodak et al., 2019). Despite rapid progress in Repeated Bayesian Persuasion (RBP), where a receiver interacts with a sender who aims to minimize his regret over rounds, the literature has almost exclusively treated each persuasion task independently. Existing no-regret algorithms operate from scratch on every new instance, ignoring any similarity across tasks. This creates a gap, although there are RBP algorithms achieving near-optimal worst-case regret, they may be conservative in settings where tasks share a latent structure, a regime where meta-learning would in principle offer substantial improvements. This work addresses this gap by incorporating meta-learning techniques into two RBP frameworks studied in the literature, namely Online Bayesian Persuasion (OBP) (Castiglioni et al., 2020; Bernasconi et al., 2023) and Markov Persuasion Processes (MPPs) (Wu et al., 2022; Bacchiocchi et al., 2025). The main difference between these two frameworks is that, in MPP, agents interact within a Markov Decision Process (MDP) environment. We formalize a setting in which the sender repeatedly engages in persuasion tasks drawn from an unknown but structured environment. Motivated by these considerations, we ask: Can we design meta-learning algorithms with full and bandit-feedback for Repeated Bayesian Persuasion? We answer this question in the affirmative by designing algorithms that achieve provably faster convergence rates for the cumulative regret of the sender when learning a signaling policy over a sequence of “similar” games, in both the OBP and MPP frameworks. Moreover, the convergence rate of the regret achieved by our algorithms strictly reduces upon the best-known bounds, when the sequence of games the sender interacts is chosen adversarially. 1.1 Related Work Computational studies of Bayesian persuasion originate with work of Dughmi and Xu (2016), which studies the efficient methods for computing optimal signaling schemes. In particular, Castiglioni et al. (2020) extended this framework and introduced OBP, where the sender repeatedly interacts with receivers and learns optimal signaling policies over time. This line of work was later extended to multiple receivers by Castiglioni et al. (2021), who analyzed learning dynamics when receivers simultaneously react to the sender’s signals. More recently, Bernasconi et al. (2023) proposed gradient-based methods operating in the loss space, establishing optimal regret rates for OBP. A complementary direction considers sequential environments. The MPP framework was introduced by Wu et al. (2022) to model repeated persuasion in Markovian environments where the sender sequentially interacts with a stream of receivers. This framework was further extended by Bacchiocchi et al. (2025), who consider settings in which neither the sender nor the receivers have prior knowledge of the environment and must learn the underlying dynamics from interaction. In contrast to these works, our setting is the first work that combines Bayesian persuasion with meta-learning across tasks. From a methodological perspective, our approach is related to gradient-based meta-learning. Theoretical foundations of such methods were studied by Khodak et al. (2019), who established convergence guarantees for meta-learning algorithms using tools from online convex optimization and task-similarity assumptions. Meta-learning has also been investigated in bandit settings, including Multi-Armed Bandits (MABs) and Bandit Linear Optimization (BLO), as studied in Balcan et al. (2022). These frameworks are particularly relevant to our OBP formulation, which can be viewed as an instance of bandit linear optimization over signaling policies. Finally, bridging meta-learning with game-theoretic learning dynamics, Harris et al. (2023) proposed no-regret meta-learning algorithms that improve convergence rates in strategic settings such as zero-sum, general-sum, and Stackelberg games under full-information feedback. 2 Preliminaries For an integer n≥1n≥ 1, we write [n]:=1,2,…,n[n]:=\1,2,…,n\. For a statement p, let p∈0,11\p\∈\0,1\ denote its indicator. For a vector v∈ℝmv ^m, v[i]v[i] denotes its i-th coordinate, and ⟨u,v⟩ u,v denotes the Euclidean inner product with u. We use O~(⋅) O(·) to hide factors logarithmic in their argument(s). Unless stated otherwise, all utilities take values in [0,1][0,1]. We denote each game (task) with t∈[T]t∈[T] and iteration of the each task as i∈[m]i∈[m]. Subscripts are to represent the time index i∈[m]i∈[m] while the superscripts are for the task iterations t∈[T]t∈[T]. 2.1 Online Bayesian Persuasion In this work, we focus on a single sender–receiver interaction, as this model can be trivially extended to multiple receivers without inter-agent externalities interacting with an information sender (Bernasconi et al., 2023). We assume that the receiver is chosen from a finite set K with |||K| many different types. Each receiver type chooses her actions from a finite set of of available actions A, in which a∈a specifying an action and =|| A=|A|. Moreover, the utilities of the sender and the receiver depend on the current state of nature, which is drawn from a finite set Ω according to the publicly-known prior probability distribution μ∈int(ΔΩ)μ ( _ ). Therefore, we define the utility functions of both sender and the receiver as us,ur,k:×Ω→u^s,u^r,k:A× → [0,1][0,1]. In OBP setting, the sender gets to know the realized state of the nature ω∼μω μ, and has the ability to signal agents to maximize his own utility. This is done using a publicly announced signaling scheme ϕ:Ω→Δφ: → _S , where S is the finite set of signals. We define ϕω(s) _ω(s) as the probability of sending s∈s when the realized state of nature is ω∈Ωω∈ . The repeated interaction for OBP is as follows : Protocol 1 Sender-Receiver Interaction at i∈[m]i∈[m] for Task t∈[T]t∈[T] in OBP 1:At each round i∈[m]i∈[m], the sender publicly announces a signaling scheme ϕi _i, and the state of nature (outcome) ω∼μω μ is realized. 2:The sender samples a signal s∼ϕi,ωs _i,ω and shares it with the receiver. 3:Upon receiving the signal s, the receiver updates her posterior according to Bayes’ rule based on the prior μ and the announced signaling policy ϕi,ω _i,ω. 4:The receiver chooses an action a∈a that maximizes her utility under the posterior belief. The posterior ρs∈ΔΩρ^s∈ _ after each interaction is calculated as, ρωs≔μωϕω(s)∑ω′∈Ωμω′ϕω′(s) _ω^s _ω\, _ω(s) _ω ∈ _ω _ω (s) for every ω∈Ω.ω∈ . Given a posterior ρ∈ΔΩρ∈ _ , the set of best-response actions for the receiver of type k∈k is defined as, ℬρk≔argmaxa∈∑ω∈Ωρωukr(a,ω).B^k_ρ _a \; _ω∈ _ω\,u^r_k(a,ω). Moreover, assuming receiver break ties in favor of the sender, the sender’s expected utility for signaling scheme ϕφ and receiver’s type k∈k is provided as us(ϕ,k)≔∑s∈(argmaxa∈ℬρsk∑ω∈Ωμωϕω(s)us(a,ω)).u^s(φ,k) _s ( _a ^k_ρ^s\; _ω∈ _ω\, _ω(s)\,u^s(a,ω) ). We will be focusing on computing a sequence ϕii∈[m]\ _i\_i∈[m] of signaling schemes in an online manner which can be employed by the sender in order to maximize his utility. We assume that the sequence of receiver’s type profiles kii∈[m]\k_i\_i∈[m], with ki∈k_i , is selected by an oblivious adversary. At each round i∈[m]i∈[m] of the repeated interaction, the sender receives a payoff us(ϕi,ki)u^s( _i,k_i) and receives some feedback about the receiver types. In the full feedback setting, the sender gets to know the receiver’s type profile kik_i, while in the bandit feedback setting the sender only observes the action profile ai∈a_i played by the receiver at round i. In this work, without loss of generality, we focus on signaling schemes that are direct and persuasive, since the Revelation Principle holds in our setting. Particularly, a signaling scheme ϕφ is direct if signals correspond to action recommendations where the set of signals of a receiver is =||S=A^|K|, with each signal defining an action recommendation to the receiver type. Moreover, a direct signaling scheme is persuasive if receiver type is incentivized to follow the action recommendations issued by the sender. Formally, the set of direct and persuasive signaling schemes P is the set of all ϕ:Ω→ΔA||φ: → _A^|K| such that, for each receiver’s type k∈k , and each action a∈a , it holds ∑ω∈Ω∑s∈||μωϕω(s)(ur,k(ak,ω)−ur,k(a,ω))≥0 _ω∈ _s ^|K| _ω _ω(s) (u^r,k(a_k,ω)-u^r,k(a,ω) )≥ 0 where, we let aka_k be the action in direct signal s corresponding to type k∈k . We note that the set P can be represented as a polytope, due to the persuasiveness constraints. We impose the conditions ensuring that ϕφ is a valid signaling rule. Namely ∑s∈||ϕω(s)=1 _s ^|K| _ω(s)=1 for all ω∈Ω.for all ω∈ . Finally, given any direct and persuasive signaling scheme ϕ∈φ , the sender’s utility under type profile k∈k is us(ϕ,k):=∑ω∈Ω∑s∈||μωϕω(s)us(ak,ω).u^s(φ,k):= _ω∈ _s ^|K| _ω _ω(s)u^s\! (a_k,ω ). 2.2 Markov Persuasion Processes MPPs extend the classical one-shot Bayesian persuasion model to dynamic environments where a sender interacts sequentially with multiple receivers within an MDP. In this setting, the sender encounters a sequence of myopic receivers who choose actions based solely on immediate payoffs, without considering future ones. Formally an episodic MPP is defined by a tuple for the task t∈[T]t∈[T] as M≔(X,A,Ω,μ,P,uisi=1m,uiri=1m)M (X,A, ,μ,P,\u_i^s\^m_i=1,\u_i^r\^m_i=1) where: • m is the number of episodes • X, A, and Ω are finite sets of states, actions, and outcomes, respectively. • μ:X→Δ(Ω)μ:X→ ( ) is a prior function defining a probability distribution over outcomes at each state. We let μ(ω∣x)μ(ω x) be the probability with which outcome ω∈Ωω∈ is sampled in state x∈Xx∈ X. • P:X×Ω×A→Δ(X)P:X× × A→ (X) is a transition function. We let P(x′∣x,ω,a)P(x x,ω,a) be the probability of moving from x∈Xx∈ X to x′∈Xx ∈ X by taking action a∈Aa∈ A, when the outcome sampled in state x is ω∈Ωω∈ . • uisi=1m\u_i^s\^m_i=1 is a sequence specifying a sender’s reward function uis:X×Ω×A→[0,1]u^s_i:X× × A→[0,1] at each episode i. Given x∈Xx∈ X, ω∈Ωω∈ , and a∈Aa∈ A, each uis,t(x,ω,a)u^s,t_i(x,ω,a) for i∈[m]i∈[m] is sampled independently from a bounded distribution between [0,1][0,1] with mean us,t(x,ω,a)u^s,t(x,ω,a) for task t∈[T]t∈[T]. • uiri=1m\u_i^r\^m_i=1 is a sequence defining a receiver’s reward function uir,t:X×Ω×A→[0,1]u_i^r,t:X× × A→[0,1] at each episode t. Given x∈Xx∈ X, ω∈Ωω∈ , and a∈Aa∈ A, each uir,t(x,ω,a)u^r,t_i(x,ω,a) for i∈[m]i∈[m] is sampled independently from a bounded distribution between [0,1][0,1] with mean ur,t(x,ω,a)u^r,t(x,ω,a) for task t∈[T]t∈[T]. As we are interested with episodic MPPs, we focus on MPPs enjoying the loop-free property, as justified in case of online learning in MDPs (Bacchiocchi et al., 2025; Aviv and Mansour, 2019). In a loop-free MPP, states are partitioned into L+1L+1 layers X0⋯XLX_0·s X_L such that X0≔x0X_0 \x_0\ and XL≔xLX_L \x_L\ with x0x_0 being the initial state and xLx_L being the final one, in which the episode ends. Moreover, by letting =[0⋯L−1]K=[0·s L-1], P(x′|x,ω,a)>0P(x |x,ω,a)>0 only when x′∈Xk+1x ∈ X_k+1 and x∈Xkx∈ X_k for some k∈k . In the MPP framework, the sender publicly commits to a signaling policy ϕ:X×Ω→Δ(),φ:X× → (S), which specifies, for every state x∈Xx∈ X and outcome ω∈Ωω∈ , a distribution over signals. We write ϕ(⋅∣x,ω)∈Δ(),φ(· x,ω)∈ (S), where ϕ(s∣x,ω)φ(s x,ω) denotes the probability of sending signal s∈s when the system is in state x and the realized outcome is ω. Analogous to each round of OBP, a myopic receiver who observes state x∈x and receives signal s∈s updates her belief over outcomes via Bayes’ rule and selects a best-response action. We denote by bϕ(s,x)∈Ab^φ(s,x)∈ A the action chosen as a best response under the signaling policy ϕφ. Furthermore, we assume that neither the sender nor the receivers have any prior knowledge of the transition kernel P, the prior distribution μ, or the reward functions uis,t(x,ω,a)u_i^s,t(x,ω,a) and uir,t(x,ω,a)u_i^r,t(x,ω,a). As is in the OBP setting, Revelation Principle allows us to focus on signaling policies that are direct and persuasive. Formally, a signaling policy is direct if the set of signals coincides with the set of actions, and a signaling policy ϕ:X×Ω→Δ(A)φ:X× → (A) is persuasive if, for every state x∈Xx∈ X and action recommendation a∈Aa∈ A, the inequality, ∑ω∈Ωμ(ω∣x)ϕ(a∣x,ω)(ur,t(x,ω,a)−ur,t(x,ω,bϕ(a,x)))≥0, _ω∈ μ(ω x)φ(a x,ω) (u^r,t(x,ω,a)-u^r,t (x,ω,b_φ(a,x) ) )≥ 0, holds. To enable meta-learning across repeated games, we assume an across-task model for the task-dependent primitives. For each task t∈[T]t∈[T], let Pt(⋅∣x,ω,a),μt(⋅∣x),us,t(x,ω,a),ur,t(x,ω,a)P^t(· x,ω,a),\;μ^t(· x),\;u^s,t(x,ω,a),\;u^r,t(x,ω,a) denote the task-specific mean transition kernel, prior, and sender/receiver reward means, respectively. We posit the existence of global, across-task, reference means PG(⋅∣x,ω,a),μG(⋅∣x),uGs(x,ω,a),uGr(x,ω,a),P_G(· x,ω,a),\; _G(· x),\;u_G^s(x,ω,a),\;u_G^r(x,ω,a), such that, for every fixed coordinate, (x,ω,a,x′)∈X×Ω×A×X(x,ω,a,x )∈ X× × A× X and (x,ω,a)∈X×Ω×A(x,ω,a)∈ X× × A, the corresponding task parameter is drawn i.i.d. across tasks around its global mean with bounded inter-task variance. Concretely, for each (x,ω,a,x′)(x,ω,a,x ), the scalar random variable Pt(x′∣x,ω,a)P^t(x x,ω,a) is i.i.d. over t with [Pt(x′∣x,ω,a)]=PG(x′∣x,ω,a),Var(Pt(x′∣x,ω,a))≤ιP2,E\! [P^t(x x,ω,a) ]=P_G(x x,ω,a),\;Var\! (P^t(x x,ω,a) )≤ _P^2, and for each (x,ω)(x,ω), [μt(ω∣x)]=μG(ω∣x),Var(μt(ω∣x))≤ιμ2.E\! [μ^t(ω x) ]= _G(ω x),\;Var\! (μ^t(ω x) )≤ _μ^2. Similarly, for each (x,ω,a)(x,ω,a), [us,t(x,ω,a)]=uGs(x,ω,a),Var(us,t(x,ω,a))≤ιs2,[ur,t(x,ω,a)]=uGr(x,ω,a),Var(ur,t(x,ω,a))≤ιr2.E\! [u^s,t(x,ω,a) ]=u_G^s(x,ω,a),\;Var\! (u^s,t(x,ω,a) )≤ _s^2,\;E\! [u^r,t(x,ω,a) ]=u_G^r(x,ω,a),\;Var\! (u^r,t(x,ω,a) )≤ _r^2. Within each task t, episode-wise observations are generated with bounded support and bounded within-task variance. In particular, conditioned on the task means above, rewards are sampled independently across episodes with support in [0,1][0,1] and [uis,t(x,ω,a)∣us,t(x,ω,a)]=us,t(x,ω,a),Var(uis,t(x,ω,a)∣us,t(x,ω,a))≤σs2,E\! [u_i^s,t(x,ω,a) u^s,t(x,ω,a) ]=u^s,t(x,ω,a), \! (u_i^s,t(x,ω,a) u^s,t(x,ω,a) )≤ _s^2, [uir,t(x,ω,a)∣ur,t(x,ω,a)]=ur,t(x,ω,a),Var(uir,t(x,ω,a)∣ur,t(x,ω,a))≤σr2,E\! [u_i^r,t(x,ω,a) u^r,t(x,ω,a) ]=u^r,t(x,ω,a), \! (u_i^r,t(x,ω,a) u^r,t(x,ω,a) )≤ _r^2, for all (x,ω,a)(x,ω,a) and all episodes i∈[m]i∈[m]. Finally, the sender-receiver interaction for time i∈[m]i∈[m] for task t∈[T]t∈[T] is as follows from (Bacchiocchi et al., 2025): Protocol 2 Sender-Receivers Interaction at i∈[m]i∈[m] for Task t∈[T]t∈[T] in MPPs 1:All the rewards uis,t(x,ω,a)u_i^s,t(x,ω,a), uir,t(x,ω,a)u^r,t_i(x,ω,a) are sampled 2:Sender publicly commits to ϕit:X×Ω→Δ(A)φ^t_i:X× → (A) 3:The state of the MPP is initialized to x0x_0 4:for k=0,…,L−1k=0,…,L-1 do 5: Sender observes outcome ωk∼μ(xk) _k μ(x_k) 6: Sender draws recommendation ak∼ϕ(⋅∣xk,ωk)a_k φ(· x_k, _k) 7: A new Receiver observes aka_k and plays it 8: The MPP evolves to state xk+1∼P(⋅∣xk,ωk,ak)x_k+1 P(· x_k, _k,a_k) 9: Sender observes the next state xk+1x_k+1 10:end for 11:Sender observes feedback for every k∈[0…L−1]k∈[0… L-1]: • full →uis,t(xk,ωk,a),uir,t(xk,ωk,a)∀a∈A→ u_i^s,t(x_k, _k,a),\,u_i^r,t(x_k, _k,a)\ \ ∀ a∈ A • partial →uis,t(xk,ωk,ak),uir,t(xk,ωk,ak)→ u_i^s,t(x_k, _k,a_k),\,u_i^r,t(x_k, _k,a_k) We emphasize that neither the sender nor the receiver types have any knowledge of the transition kernel P, the prior distribution μ, or the reward functions uis,t(x,ω,a)u_i^s,t(x,ω,a) and uir,t(x,ω,a)u_i^r,t(x,ω,a), including any prior information about their underlying distributions. Under this assumption, Protocol 2 prescribes that receiver types always follow the recommended actions. The rationale is that, in the oblivious MPP setting, learning algorithms ensure that the average per-round violation of persuasiveness constraints converges to zero as the number of episodes increases. Since no algorithm can guarantee persuasiveness in every single episode, if algorithm wants to be a no-regret algorithm, the violation necessarily vanishes only asymptotically. Consequently, it is optimal for receiver types to adhere to the recommendations in the long run (Bacchiocchi et al., 2025). 2.3 Meta-Learning Across Repeated Games We consider the problem of meta-learning across tasks t∈[T]t∈[T] over some compact and convex action set ⊆ℝKJ ^K. On each round, i∈[m]i∈[m] of task t∈[T]t∈[T] we play action it∈x^t_i and receive feedback ℒit(it)L^t_i(x^t_i) for some loss function ℒit:↦[0,1]L^t_i:J [0,1]. For the class of loss functions, we assume that they have a linear form of ℒit()=⟨ℓit,⟩L^t_i(x)= ^t_i,x . In online learning, the goal in a single task is to play actions 1t,…,mtx^t_1,…,x^t_m that minimize the regret ∑i=1mℒit(it)−ℒit(∗t) _i=1^mL^t_i(x^t_i)-L^t_i(x t), with respect to ∗t∈argmin∈∑i=1mℒit()x t∈ _x _i=1^mL^t_i(x). Lifting this to the meta-learning setting, we define our goal as minimizing the task-averaged regret given as: RmT≔1T∑t=1T∑i=1mℒit(it)−ℒit(∗t)R^T_m 1T _t=1^T _i=1^mL^t_i(x^t_i)-L^t_i(x t) (1) In particular, we aim to leverage multi-task data to improve the average performance. Formally, our goal is to achieve a task-averaged regret of ~(Vm), O( Vm), where V∈ℝ≥0V _≥ 0 is a task-similarity measure that remains small when tasks are highly similar, while still recovering the worst-case single-task performance when they are heterogeneous. To this end, we adopt a meta-learning perspective. Specifically, we aim to learn a within-task algorithm (or base learner), i.e., a parameterized method that is deployed independently on each task t. The objective is to learn improved initializations and meta-hyperparameters that minimize the task-averaged regret across tasks (Harris et al., 2023; Balcan et al., 2022). The underlying premise is that the task-specific optimal parameters are close to one another; hence, a suitably meta-learned initialization enables rapid adaptation, yielding strong performance after only a few within-task updates. The base learner we choose for the meta-persuasion algorithms for OBP framework is the Online Mirror Descent (OMD). For a strictly convex regularizer ℛ:¯↦ℝR: J and step-size η>0η>0, the OMD update is being performed as, i+1t=argmin∈¯Dℛ(∥it)+η⟨ℓit,⟩x^t_i+1= \ _x∈ JD_R(x\|x^t_i)+η ^t_i,x \ where Dℛ(∥)=ℛ()−ℛ()−⟨∇ℛ(),−⟩D_R(x\|y)=R(x)-R(y)- (y),x-y is the Bregman divergence of ℛR. It is notable that, OMD recovers online gradient descent (OGD) when ℛ()=12‖22R(x)= 12\|x\|_2^2, in which case Dℛ(∥)=12‖−‖22D_R(x\|y)= 12\|x-y\|_2^2. Specifically, we utilize OGD and OMD with a self-concordant barrier ℛR as the regularizer, which serve as the base learners in the full-feedback and bandit-feedback settings, respectively. We remark that OMD and follow the regularized leader (FTRL) methods recover the same iterates under the condition of the regularizer is both convex and differentiable as in our case (Abernethy et al., 2008). On the other hand, for the MPP framework, we consider carefully designed estimators for enabling meta-learning task, as specified in the Section 4. 3 The Meta-Learning for Online Bayesian Persuasion In the online learning problem for OBPs, at each round i∈mi∈ m, of task t∈Tt∈ T an agent takes a decision ϕitφ^t_i from a set ⊆ℝMP ^M, and, then, an adversary selects an element kik_i from a finite set K of K:=||K:=|K| elements. Then, the loss suffered by the agent is ℒkit(ϕit)L^t_k_i(φ^t_i), where functions ℒk:→[0,1]L_k:P→[0,1] are loss functions indexed by the elements k∈k . Thus, the performance of the agent over the m rounds of T tasks is evaluated in terms of task averaged regret given as RmT≔1T∑t=1T∑i=1m[ℒkit(ϕit)]−ℒkit((ϕ∗)t),R^T_m 1T _t=1^T _i=1^mE[L_k^t_i(φ^t_i)]-L_k^t_i ((φ^*)^t ), (2) where the expectation is with respect to the (possible) randomization that the agent adopts in choosing ϕitφ^t_i. Next, we introduce a general no-regret algorithm that works by exploiting the linear structure of the online learning problem described above. In order to do so, we introduce a vector-valued function ν:→ℝKν:P ^K defined as ν(ϕ):=[−us(ϕ,k)]k∈=[ℒk(ϕ)]k∈ν(φ):=[-u^s(φ,k)]_k =[L_k(φ)]_k and ℒkit(ϕit):=ν(ϕ)⊤kitL_k^t_i(φ^t_i):=ν(φ) 1_k^t_i for all ϕ∈. for all φ . We denote the convex hull of such functions as ν¯(⋅) ν(·). Furthermore, we assume that ν is a linear map, i.e. there exists ∈ℝK×MM ^K× M such that ν(ϕ)=ϕν(φ)=Mφ for all ϕ∈φ . Knowing that inverse map ν†ν exists, we can map our signaling scheme ϕφ to the loss space ν()ν(P) to perform the iterations and map back the result to our set of direct and persuasive signaling schemes P to play an actual scheme ϕitφ^t_i. However, since the set ν()ν(P) is not guaranteed to be convex, we make use of Carathéodory’s Theorem. Theorem 3.1 (Carathéodory’s Theorem). For any set ⊂ℝKJ ^K and any point z¯ z in its convex hull ¯ J, there exist at most K+1K+1 points z1,…,zn∈z^1,…,z^n with n≤K+1n≤ K+1 such that z=∑i=1nλixiz= _i=1^n _i\,x^i, where λi≥0 _i≥ 0 and ∑i=1nλi=1 _i=1^n _i=1. Departing from the theorem, we now describe the Carathéodory Oracle, which takes ν()ν(P), the loss space, and a point in its convex hull, as inputs and returns a sparse representation of the input point using elements from the original set. Concretely, given a point z¯it∈ν¯() z_i^t∈ ν(P), the oracle returns at most K+1K+1 points in ν()ν(P) together with associated weights such that z¯it z_i^t can be expressed as their convex combination. By Carathéodory’s Theorem, such a representation always exists in ℝKR^K. Formally, (zi,jt,λi,jt)j=1m←Carathe´odory(z¯it,ν()),\(z_i,j^t, _i,j^t)\_j=1^m eodory ( z_i^t,\,ν(P) ), where m≤K+1m≤ K+1, zi,jt∈ν()z_i,j^t∈ν(P), λi,jt≥0 _i,j^t≥ 0, ∑j=1mλi,jt=1 _j=1^m _i,j^t=1, and z¯it=∑j=1mλi,jtzi,jt. z_i^t= _j=1^m _i,j^tz_i,j^t. We then sample one of the points zi,jtz_i,j^t with probability λi,jt _i,j^t and play the corresponding signaling scheme ϕit=ν†(zi,jt), _i^t=ν (z_i,j^t), where ν†ν denotes the inverse map. Since ν†ν exists and is efficiently computable, this procedure yields a signaling scheme whose expected loss vector matches (z¯i)t( z_i)^t, thereby implementing the desired policy in expectation. Then, by equivalence in expectation, our algorithm performs OGD over the convex domain ν¯() ν(P). At each iteration, the resulting iterate in the lifted space is mapped back to the signaling space P, from which the sender samples and implements a signaling policy. We depict this process in Figure 1. Importantly, to our knowledge such an algorithm first introduced in Bernasconi et al. (2023). A crucial observation is that computing an optimal direct and persuasive signaling scheme is NP-hard, even when the distribution over the receiver type is known (Castiglioni et al., 2020). This hardness result implies that the polytope P of feasible signaling schemes has exponential size. Moreover, reductions from offline to online optimization indicate that no computationally efficient algorithm with polynomial per-iteration running time can exist for this problem (Castiglioni et al., 2020). Consequently, in the OBP setting, the primary objective is to improve the sender’s sample complexity, rather than to address the computational complexity of identifying direct and persuasive signaling schemes ϕ∈φ . Furthermore, the reason our optimization procedure is carried out in the convex hull of the loss space, ν¯() ν(P), rather than directly over the set of direct and persuasive signaling schemes, ¯ P, stems from the formulation of OBP. In this setting, the receiver type set is significantly smaller than the set of signaling schemes, which is exponential in size; that is, ||≪|||K| |P|. Consequently, performing optimization in the loss space reduces the task-averaged regret, since the cardinality of the decision set appears in the regret upper bound. Hence, operating in a lower-dimensional space yields improved performance guarantees. In the OBP framework, task heterogeneity is introduced by allowing the player type set K to vary across tasks, as well as the prior μ, receiver utilities ur,ku^r,k, for each type k∈k , and the sender utility usu^s. Meanwhile, the action set A and the signal set S remain fixed across tasks. Pϕ∈φ ν()ν(P)z∈ν()z∈ν(P)ν¯() ν(P)z^1∈ν¯() z_1∈ ν(P)z^2 z_2ν(ϕ)ν(φ)ν†(z)ν (z)Carathéodory Figure 1: Illustration of the Carathéodory oracle used in Algorithms 4 and 5. 3.1 Full Feedback Setting For the full-feedback setting, the sender observes the types of the receiver encountered at each interaction. Then, we can employ OGD, where gradients are with respect to ν(ϕit)ν(φ^t_i), as specified in Algorithm 4. Our ultimate goal is to learn the hyperparameter η and to identify a suitable initialization for subsequent tasks. Algorithm 3 ϵε-EWOO 1:Require: meta-hyperparameter β>0,U~(s)(η)s=1tβ>0,\ \ U^(s)(η)\_s=1^t 2:Initialize: η1∈[ϵ,A2+ϵ2]η^1∈[ε, A^2+ε^2] 3:η(t+1)←∫ϵA2+ϵ2ηexp(−β∑s≤tU~(s)(η))η∫ϵA2+ϵ2exp(−β∑s≤tU~(s)(η))η^(t+1)← _ε A^2+ε^2η (-β _s≤ t U^(s)(η) )\,dη _ε A^2+ε^2 (-β _s≤ t U^(s)(η) )\,dη Algorithm 4 Full-feedback Meta-Persuasion 1:Require: inverse-map ν†ν , meta-hyperparameter β>0β>0, 2:Initialize: (z¯1)1=argminz∈ν¯()12‖z‖22( z_1)^1= _z∈ ν(P)\ 12\|z\|^2_2 3:for task t=1,…,Tt=1,…,T do 4: for i=1,…,mi=1,…,m do 5: (zi,jt,λi,jt)j∈[K+1]←Carathe´odory((z¯i)t,ν())\(z^t_i,j\,,λ^t_i,j)\_j∈[K+1]←Carath eodory\ \! (( z_i)^t,\,\ ν(P) ) 6: Draw j′∈[K+1]j ∈[K+1] with probabilities λi,1t,λi,2t,⋯,λi,K+1tλ^t_i,1,λ^t_i,2,·s,λ^t_i,K+1 7: Play ϕit←ν†(zi,j′t)φ^t_i←ν (z^t_i,j ) 8: Observe kit∈k^t_i and suffer loss ℒkit(⋅)L_k^t_i(·) 9: (z¯i+1)t←Πν¯()((z¯i)t−ηt∇ℒkit(ϕit))( z_i+1)^t← _ ν(P) (( z_i)^t-η^t _k^t_i(φ^t_i) ) 10: end for 11: (z∗)t←argminz∈ν¯()⟨∑i=1m1kit,z⟩(z^*)^t← _z∈ ν(P) Σ^m_i=11_k^t_i,z 12: (z¯1)t+1←1t∑s≤t(z∗)s( z_1)^t+1← 1t _s≤ t(z^*)^s 13: U~(t)(η)←(‖(z∗)t−(z¯1)t‖22mη+ρ2A2η+η)m2 U^(t)(η)← ( \|(z^*)^t-( z_1)^t\|_2^2mη\!+\! ρ^2\!A^2η\!+\!η )\! m2 14: ηt+1←ϵ-EWOO(β,U~(s)(η)s=1t)η^t+1←ε-EWOO (β,\ U^(s)(η)\_s=1^t ) 15:end for To achieve this goal, the Algorithm 3 learns a sequence of losses for each task t of the form U(t)(η)≔((B(t))2η+η)γ(t)=(‖(z∗)t−(z1)t‖22mη+η)m2U^(t)(η) ( (B^(t))^2η+η )γ^(t)= ( \|(z )^t-(z_1)^t\|_2^2mη+η ) m2 and applies the main idea of Exponentially Weighted Online Optimization (EWOO) method (Hazan et al., 2007) to obtain an updated value of η for the next task t+1t+1. However, U(t)(η)U^(t)(η) functions we derive are not exp-concave and are ill-conditioned near η=0η=0. Therefore, we employ the modified version of the algorithm, ϵε-EWOO (Khodak et al., 2019). For ϵε-EWOO we define U~t(⋅) U^t(·) as: U~t(η)≔((B(t))2+ϵ2η+η)γ(t)=(‖(z∗)t−(z1)t‖22m+ρ2A2η+η)m2. U^t(η) (\! (B^(t))^2\!+\!ε^2η\!+\!η )γ^(t)\!=\! ( \|(z )^t-(z_1)^t\|_2^2m\!+\!ρ^2\!A^2\!\!η\!+\!η )\! m2. where we specify ϵ=ρA=KmT−1/4ε=ρ A= Km\,T^-1/4. As shown in Algorithm 3, ϵε-EWOO differs from EWOO (Hazan et al., 2007) only through this modified objective and the corresponding adjusted integration limits, which together ensure that the loss functions are smooth and convex. Then, using ϵε-EWOO as a subroutine for meta-learning, we iterate over each persuasion task as described for the single instance of an OBP process and formalized in Algorithm 4. Next, we present our theorem for the meta-persuasion for OBP framework within the full-feedback setting. Theorem 3.2. Algorithm 4 with parameters ϵ=ρA,ε=ρ A, ρ=T−1/4,ρ=T^-1/4, A=Km,A= Km, β=4mAminϵ2A2,1β= 4mA \ ε^2A^2,1\ achieves task-averaged regret RmT=O(mVar(z∗(t)t=1T))R_m^T=O\! ( \,m\,Var\! (\z^*(t)\_t=1^T )\; ) as T→∞,as T→∞, where z∗(t)=ν(ϕ∗(t))z^*(t)=ν(φ^*(t)) denotes the optimal sender strategy at task t, and Var(z∗(t)t=1T)Var\! (\z^*(t)\_t=1^T ) denotes the empirical variance of z∗(t)t=1T\z^*(t)\_t=1^T. 3.2 Partial Feedback Setting In our second setting, we assume that only a scalar loss value is revealed to the sender after interacting with the environment, as in the standard Bandit Linear Optimization (BLO) framework. Formally, at each round i of task t we observe loss ⟨ν(ϕit),kit⟩=⟨ℓit,ϕit⟩∈[0,1] ν(φ^t_i),1_k^t_i = ^t_i,φ^t_i ∈[0,1], where we defined ℓit=kit,⋅ ^t_i=M_k^t_i,· denoting the kitthk^t_i^th row of M. Before, introducing the algorithm, we first define the related tools. We define the b-restricted space ν¯b()=z∈ℝK:πz1(z)≤1/(1+b)⊂ν¯(), ν_b(P)=\z ^K: _z_1(z)≤ 1/(1+b)\⊂ ν(P)\, where z1=argminz∈ν¯()ℛ(z)z_1= _z∈ ν(P)R(z) and πz1(z)=infλ>0:z1+λ−1(z−z1)∈ν¯() _z_1(z)= \λ>0:z_1+λ^-1(z-z_1)∈ ν(P)\ is the Minkowski function. For such a task, we employ ϑ -self-concordant barriers ℛR as the regularizer in OMD iterations. A convex function ℛ:int(ν¯())→ℝR:int ( ν(P) ) is called self-concordant if it is C3C^3 and satisfies |d3ℛ(z)[h,h,h]|≤2(d2ℛ(z)[h,h])3/2, |d^3R(z)[h,h,h] |≤ 2 (d^2R(z)[h,h] )^3/2, which relates the second and third-order differentials. In addition, it must satisfy |dℛ(z)[h]|≤ϑ1/2(d2ℛ(z)[h,h])1/2, |dR(z)[h] |≤ ^1/2 (d^2R(z)[h,h] )^1/2, which relates the first and second-order differentials. We define the local norm of a vector with respect to a given z∈ν¯()z∈ ν(P), as ‖h‖z=(⟨h,h⟩z)1/2\|h\|_z= ( h,h _z )^1/2, where we define ⟨g,h⟩z=g⊤∇2ℛ(z)h g,h _z=g ∇^2R(z)\,h. Furthermore, we denote the dual local norm as, ‖g‖zi,∗:=g⊤Hi−1g.\|g\|_z_i,*:= g H_i^-1g. Finally, using the local norms we define the Dikin ellipsoid of radius r centered at z∈ν¯()z∈ ν(P) where the sampling procedure takes place as, Wr(z)=y∈ν¯():‖y−z‖z<r.W_r(z)=\\,y∈ ν(P):\|y-z\|_z<r\,\. Algorithm 5 CTOMD 1:Require: inverse mapping ν†ν , ϑ -self-concordant ℛR, η, and z1tz^t_1 2:for i=1,…,mi=1,…,m do 3: Let 1,…,K and v1,…,vK\e_1,…,e_K\ and \v_1,…,v_K\ be the set of eigenvectors and eigenvalues of ∇2ℛ(z¯it)∇^2R( z^t_i). 4: Choose j′j uniformly at random from 1,⋯,K\1,·s,K\ and εit=±1 ^t_i=± 1 with probability 1/21/2 5: Predict (y¯i)t←(z¯i)t+εitvj′−1/2j′( y_i)^t←( z_i)^t+ ^t_iv^-1/2_j e_j 6: (yi,jt,λi,jt)j∈[K+1]←Carathe´odory((y¯i)t,ν())\(y^t_i,j\,,λ^t_i,j)\_j∈[K+1]\;←\;Carath eodory\ \! (( y_i)^t,\,ν(P) ) 7: Draw j′∈[K+1]j ∈[K+1] with probabilities λi,1t,λi,2t,⋯,λi,K+1tλ^t_i,1,λ^t_i,2,·s,λ^t_i,K+1 8: Play ϕit←ν†(yi,j′t)φ^t_i←ν (y^t_i,j ) 9: Suffer loss ⟨ℓit,ϕit⟩∈ℝ ^t_i,φ^t_i 10: Define ℓit~≔K⟨ℓit,ϕit⟩εitvj′1/2j′ ^t_i K ^t_i,φ^t_i ^t_iv^1/2_j e_j 11: (z¯i+1)t←argminz∈ν¯()ηt⟨ℓ~it,z⟩+DR(z,(z¯i)t)( z_i+1)^t← _z∈ ν(P)\η^t ^t_i,z +D_R(z,( z_i)^t)\ 12:end for 13:ℓ~t=∑i=1mℓit~ ^t= _i=1^m ^t_i Conceptually, Algorithm 5 is the Bandit Online Linear Optimization algorithm of the Abernethy et al. (2008), applied over ν¯() ν(P), and augments them with a Carathéodory oracle to map iterates back to the signaling space, whose existence was first implied in Bernasconi et al. (2023). One can observe that another difference between our algorithm and the one proposed in Abernethy et al. (2008) is that we iterate over policies using an OMD procedure, whereas they employ an FTRL-based formulation. However, as noted in the same work, these two policy update methods yield identical iterates when self-concordant regularizers are used. At round i of task t, Algorithm 5 maintains an interior point (z¯i)t∈ν¯()( z_i)^t∈ ν(P) and only uses the scalar loss ⟨ℓit,ϕit⟩=ν(ϕit)⊤kit∈[0,1] _i^t, _i^t =ν( _i^t) 1_k_i^t∈[0,1] after playing ϕit _i^t. To obtain a low-variance estimator while staying feasible, Algorithm 5 explores inside the Dikin ellipsoid induced by the ϑ -self-concordant barrier ℛR. Let ∇2ℛ(z¯it)∇^2R( z_i^t) have eigenpairs (j,vj)j=1K\(e_j,v_j)\_j=1^K. Sampling j′∼Unif([K])j ([K]) and εit∈±1 _i^t∈\± 1\ uniformly, the algorithm forms the perturbed point (y¯i)t=(z¯i)t+εitvj′−1/2j′,( y_i)^t\;=\;( z_i)^t+ _i^t\,v_j ^-1/2e_j , which lies in W1(z¯it)⊂ν¯()W_1( z_i^t)⊂ ν(P). Geometrically, the eigenvectors je_j are the principal axes of the Dikin ellipsoid, and the scaling vj−1/2v_j^-1/2 moves one unit in the local norm, producing exploration that is adapted to the curvature of ℛR. Although, the sampled (y¯i)t( y_i)^t is a valid point in the convex hull ν¯() ν(P), the sender must play an actual ϕit∈ _i^t . Then, the Carathéodory oracle decomposes (y¯i)t( y_i)^t as (yi,jt,λi,jt)j∈[K+1]\(y_i,j^t, _i,j^t)\_j∈[K+1] and Algorithm 5 samples j′j with ℙ(j′=j)=λi,jtP(j =j)= _i,j^t, then plays ϕit=ν†(yi,j′t) _i^t=ν (y_i,j ^t). This guarantees the implementation-in-expectation, [ν(ϕit)∣(y¯i)t]=(y¯i)t,E [ν( _i^t) ( y_i)^t ]=( y_i)^t, so linear losses evaluated at the played policy match the losses at the mapped point in expectation. From the scalar observation ⟨ℓit,ϕit⟩ _i^t, _i^t , Algorithm 5 forms the estimator ℓ~it:=K⟨ℓit,ϕit⟩εitvj′1/2j′. _i^t:=K\, _i^t, _i^t \, _i^t\,v_j ^1/2e_j . along with the Carathéodory implementation, this yields an unbiased estimator of the loss direction. Finally, Algorithm 5 performs the mirror descent step on ν¯() ν(P) with barrier regularizer ℛR. We refer readers to (Abernethy et al., 2008) for more detailed discussion on the core algorithm. Algorithm 6 Partial-Feedback Meta-Persuasion 1:Input: compact ν¯()⊂ℝK ν(P) ^K, meta-hyperparameters α>0α>0 , ⊂ℝ2G ^2 over (η,b)(η,b), OPTbOPT_b. 2:for g=(η,b)∈g=(η,b) do 3: 1,(g)←argmin∈ν¯()ℛ(ϕ)z^1,(g)← _z∈ ν(P)R(φ) 4:end for 5:1←||/||p_1 1_|G|/|G| 6:for task t=1,…,Tt=1,…,T do 7: sample gt=(ηt,bt)∼tg^t=(η^t,b^t) ^t from G 8: ℓ~t←CTOMD(t,(gt)) ^t (z^t,(g^t)) 9: for g=(η,b)∈g=(η,b) do 10: t+1,(g)←1t∑s=1tOPTb(ℓ~s)z^t+1,(g)← 1t _s=1^tOPT_b( ^s) 11: t+1(g)←t+1(g)exp(−αUt(t,(g),g))p^t+1(g) ^t+1(g) \! (-α U^t(z^t,(g),g) ) 12: end for 13: t+1←t+1/‖t+1‖1p^t+1 ^t+1/\|p^t+1\|_1 14:end for We now explain how we leverage repeated persuasion tasks to tune the bandit learner in Algorithm 5. The inner-loop objective of the sender within each task is to perform well against the best fixed signaling rule for that task, but the similarity of the task compared to previous tasks can vary across t. In particular, the performance of Algorithm 5 depends critically on two quantities: (i) the within-task step size η, and (i) the boundary offset b which affects the barrier geometry and the estimator variance. Rather than choosing (η,b)(η,b) a priori, Algorithm 6 learns these hyperparameters online across tasks using an experts-style meta-procedure, following the meta-algorithm given in Balcan et al. (2022). To learn a better initialization of the parameters, the meta-algorithm utilizes the the cumulative estimated loss vector ℓ~t:=∑i=1mℓ~it, ^t:= _i=1^m _i^t, outputted by Algorithm 5 at the end of task t, which serves as an unbiased proxy for the (unknown) cumulative loss in the loss space. From ℓ~t ^t we form the b-restricted optimum-in-hindsight OPTb(ℓ~t)∈argminz∈ν¯b()⟨ℓ~t,z⟩,OPT_b( ^t)∈ _z∈ ν_b(P) ^t,z , summarizes the task-specific best response of the sender in the loss space. It can be intuitively seen that when tasks are similar these optima tend to cluster; when tasks are more heterogeneous, they tend to be more dispersed. To exploit task similarity, Algorithm 6 maintains, for each hyperparameter pair g=(η,b)∈g=(η,b) , a meta-initialization zt,(g)∈ν¯()z^t,(g)∈ ν(P) given by the running average of past optima at that offset z¯t+1,(g)←1t∑s=1tOPTb(ℓ~s). z^t+1,(g)← 1t _s=1^tOPT_b( ^s). This can be seen as a principled warm-start, as if the task-wise optima OPTb(ℓ~t)OPT_b( ^t) concentrate around a common center, then z¯t,(g) z^t,(g) quickly approaches that center and the divergence term shrinks, improving the average regret. Thus, Algorithm 6 discretizes a continuous admissible range of (η,b)(η,b) into a finite grid ⊂ℝ>0×(0,1)G _>0×(0,1). Each g=(η,b)∈g=(η,b) is treated as an expert. At the beginning of task t, the meta-learner samples gt=(ηt,bt)∼ptg^t=(η^t,b^t) p^t and runs Algorithm 6 with the corresponding initialization zt,(gt)z^t,(g^t). After observing ℓ~t ^t, the meta-learner can evaluate, for every g=(η,b)∈g=(η,b) , the task-level upper bound Ut(zt,(g),g):=1ηDℛ(OPTb(ℓ~t)∥zt,(g))+(32K2η+b)m.U^t\! (z^t,(g),g )\;:=\; 1η\,D_R\! (OPT_b( ^t)\, \|\,z^t,(g) )\;+\;(32K^2η+b)\,m. Finally, the distribution over experts is updated by multiplicative weights followed by normalization. Next, we provide the task averaged regret guaranteed by Algorithm (6) in the following theorem. Theorem 3.3. For each b, define the constants Db2:=maxx,y∈ν¯bDℛ(x∥y),D_b^2:= _x,y∈ ν_bD_R(x\|y), Sb:=maxx∈ν¯b‖∇2ℛ(x)‖2,S_b:= _x∈ ν_b\|∇^2R(x)\|_2, :=maxx,y∈ν¯‖x−y‖2, K:= _x,y∈ ν\|x-y\|_2, and the barrier-divergence, by V^b2:=minz∈ν¯[1T∑t=1TDℛ(OPTb(ℓ^t)∥z)]. V_b^2\;:=\; _z∈ ν\;E\! [ 1T _t=1^TD_R\! (OPT_b( ^t)\,\|\,z ) ]. Then, choosing η=V^b232mη= V_b2 32 Km, there exist a grid size k=O~(Db¯2KmT)k= O(D_ b^2K mT) and a meta step-size α such that for Algorithm 6, the expected task-averaged regret satisfies RmT≤O~(Db¯KmT1/4+Sb¯2KmDb¯T3/4)+minb∈[b¯,b¯](4KV^b2m+bm).R_m^T\;≤\; O\! ( D_ bKmT^1/4+ S_ b K^2K mD_ bT^3/4 )\;+\; _b∈[ b, b] (4K V_b 2m+bm ). (3) Following Theorem 3.3, we present Corollary 3.1 to show how task similarity improves the averaged regret. Corollary 3.1 (Corollary 5.1 in Balcan et al. (2022)). Assume that the feasible region is ν¯()=z∈ℝK:‖z‖2≤1, ν(P)=\z ^K:\ \|z\|_2≤ 1\, and take the self-concordant barrier ℛ(z)=−ln(1−‖z‖22).R(z)=- (1-\|z\|_2^2 ). Let the b-restricted set be the ν¯b():=z∈ℝK:‖z‖2≤1−b,b∈(0,1). ν_b(P)\;:=\;\z ^K:\ \|z\|_2≤ 1-b\,\;b∈(0,1). Then, running Algorithm 6, the expected task-averaged regret satisfies RmT≤O~(Km2T1/4)+min1/m≤b≤1/m4K[ 2mln(1−‖z¯^(b)‖222b−b2)]+bm,R_m^T\;≤\; O\! ( K\,m^2T^1/4 )\;+\; _1/m≤ b≤ 1/ m \4K\,E\! [ \,2m ( 1-\| z^(b)\|_2^22b-b^2 ) ]\;+\;bm \, where z¯^(b):=1T∑t=1TOPTb(ℓ~t). z^(b):= 1T _t=1^TOPT_b( ^t). Moreover, in this geometry the constrained optimizer has the closed form OPTb(ℓ~t)∈argmin‖z‖2≤1−b⟨ℓ~t,z⟩=−(1−b)ℓ~t‖ℓ~t‖2OPT_b( ^t)∈ _\|z\|_2≤ 1-b ^t,z \;=\;-(1-b) ^t\| ^t\|_2 . It can be seen that the Corollary 3.1 captures task similarity, as the quantity z¯^(b) z^(b) is an average of estimated loss directions across tasks. If tasks are similar, these directions align, and thus ‖z¯^(b)‖2\| z^(b)\|_2 is close to 1−b1-b. Then 1−‖z¯^(b)‖22≈2b−b21-\| z^(b)\|_2^2≈ 2b-b^2, making the logarithmic term close to 11 and hence V^b≈0 V_b≈ 0. Consequently, as T→∞T→∞ the dominant term becomes bmbm; choosing b=1/mb=1/m yields constant asymptotic task-averaged regret. If tasks are dissimilar, the normalized directions cancel out and ‖z¯^(b)‖2\| z^(b)\|_2 is small, making the logarithmic term large and recovering a worst-case scaling. 4 The Meta-Learning for Markov Persuasion Processes For the MPP setting, we first define the occupancy measures. Given a transition function P, a signaling policy ϕφ, and a prior function μ, the occupancy measure induced by (P,ϕ,μ)(P,φ,μ) is a vector qP,ϕ,μ∈[0,1]|X×Ω×A×X|q^P,φ,μ∈[0,1]^|X× × A× X| whose entries are defined as follows. For every x∈Xkx∈ X_k, ω∈Ωω∈ , a∈Aa∈ A, and x′∈Xk+1x ∈ X_k+1 with k∈k , we define qP,ϕ,μ(x,ω,a,x′):=ℙ((xk,ωk,ak,xk+1)=(x,ω,a,x′)|P,ϕ,μ),q^P,φ,μ(x,ω,a,x ):=P ((x_k, _k,a_k,x_k+1)=(x,ω,a,x )\, |\,P,φ,μ ), which is the probability that the next state is x′x after playing action a in state x when the realized outcome is ω, under transition function P, signaling policy ϕφ, and prior function μ. Moreover, we let: qP,ϕ,μ(x,ω,a):=∑x′∈Xk+1qP,ϕ,μ(x,ω,a,x′),qP,ϕ,μ(x,ω):=∑a∈AqP,ϕ,μ(x,ω,a),qP,ϕ,μ(x):=∑ω∈ΩqP,ϕ,μ(x,ω).q^P,φ,μ(x,ω,a)\!:=\!\!\!\!\!\! _x ∈ X_k+1\!\!\!\!q^P,φ,μ(x,ω,a,x ), q^P,φ,μ(x,ω)\!:=\!\! _a∈ A\!q^P,φ,μ(x,ω,a), q^P,φ,μ(x)\!:=\!\! _ω∈ \!q^P,φ,μ(x,ω). As it is the case in standard MDPs, a valid occupancy measure q∈[0,1]|X×Ω×A×X|q∈[0,1]^|X× × A× X| induces a transition function PqP^q, a signaling policy ϕqφ^q, and prior function μqμ^q defined as follows: Pq(x′∣x,ω,a):=q(x,ω,a,x′)q(x,ω,a),ϕq(a∣x,ω):=q(x,ω,a)q(x,ω),μq(ω∣x):=q(x,ω)q(x).P^q(x x,ω,a):= q(x,ω,a,x )q(x,ω,a), φ^q(a x,ω):= q(x,ω,a)q(x,ω), μ^q(ω x):= q(x,ω)q(x). We denote by ⊆[0,1]|X×Ω×A×X|Q [0,1]^|X× × A× X| the set of all the valid occupancy measures of an MPP. The following lemma characterizes the set of valid occupancy measures and it is a generalization to the MPP setting. Lemma 4.1 (Lemma 1, Bacchiocchi et al. (2025)). A vector q∈[0,1]|X×Ω×A×X|q∈[0,1]^|X× × A× X| is a valid occupancy measure of an MPP if and only if it holds: 1 -∑x∈Xk∑ω∈Ω∑a∈A∑x′∈Xk+1q(x,ω,a,x′)=1∀k∈2 -∑x′∈Xk−1∑ω∈Ω∑a∈Aq(x′,ω,a,x)=q(x)∀k∈[1…L−1],∀x∈Xk3 -Pq=P4 -μq=μ, \ array[]l1 -~~ _x∈ X_k _ω∈ _a∈ A _x ∈ X_k+1q(x,ω,a,x )=1&∀ k \\[5.16663pt] 2 -~~ _x ∈ X_k-1 _ω∈ _a∈ Aq(x ,ω,a,x)=q(x)&∀ k∈[1… L-1],∀ x∈ X_k\\[5.16663pt] 3 -~~P^q=P\\[2.58334pt] 4 -~~μ^q=μ, array . where P is the transition function of the MPP and μ its prior function, while PqP^q and μqμ^q are the transition and prior functions, respectively, induced by occupancy measure q. Our objective is to construct algorithms that produce sequences of signaling policies ϕit\ _i^t\ which maximize the sender’s cumulative reward over m episodes across T tasks, while ensuring that violations of the persuasiveness constraints remain controlled. Crucially, we do not attempt to enforce that each policy ϕit _i^t be persuasive at every episode t, as such a guarantee is unattainable since the sender does not have access to the receiver types’ reward distributions (Bacchiocchi et al., 2025). Accordingly, our goal is to design algorithms that achieve vanishing average regret together with vanishing average constraint violations. We now introduce the benchmark offline optimization problem that the sender would solve for each task t∈[T]t∈[T]: maxqt∈ _q^t ∑x∈X∑ω∈Ω∑a∈Aqt(x,ω,a)us,t(x,ω,a) _x∈ X _ω∈ _a∈ Aq^t(x,ω,a)\,u^s,t(x,ω,a) (1a) s.t. ∑ω∈Ωqt(x,ω,a)(ur,t(x,ω,a)−ur,t(x,ω,a′))≥0 _ω∈ q^t(x,ω,a) (u^r,t(x,ω,a)-u^r,t(x,ω,a ) )≥ 0 ∀x∈X,∀ω∈Ω,∀a∈A,∀a′∈A∖a. ∀ x∈ X,\ ∀ω∈ ,\ ∀ a∈ A,\ ∀ a ∈ A \a\. (1b) It follows that Problem (1a) determines the optimal occupancy measure—and, by correspondence, the associated optimal signaling policy—subject to the persuasiveness constraints in (1b). Since, in the MPP setting, the players’ rewards are stochastic, we let us,t,ur,t∈[0,1]|X×Ω×A|u^s,t,u^r,t∈[0,1]^|X× × A| denote the random vectors whose components represent the mean sender and receiver types’ rewards. We define the optimal benchmark value for task t as OPTt:=(us,t)⊤q⋆t,OPT^t:=(u^s,t) q^t_ , where q⋆t∈q^t_ is an optimal solution to Problem (1a). Throughout, we denote by ϕ⋆tφ^t_ an optimal signaling policy for task t∈[T]t∈[T], induced by q⋆tq^t_ , i.e., ϕ⋆t:=ϕq⋆t.φ^t_ :=φ^q^t_ . We evaluate learning performance using two standard metrics. The first metric is the task-averaged cumulative regret RmTR_m^T, defined as RmT:=1T∑t∈[T](m⋅OPTt−∑i∈[m](us,t)⊤qit)=1T∑t∈[T]∑i∈[m](us,t)⊤(q⋆t−qit),R_m^T:= 1T _t∈[T] (m·OPT^t- _i∈[m](u^s,t) q_i^t )= 1T _t∈[T] _i∈[m](u^s,t) (q^t_ -q^t_i), where qit:=qPt,ϕit,μtq^t_i:=q^P^t,φ^t_i,μ^t denotes the occupancy measure induced by the signaling policy ϕitφ^t_i with known prior function μtμ^t and transition function PtP^t for task t∈[T]t∈[T]. The second metric is the task-averaged cumulative violation VmTV_m^T, which measures deviations from persuasiveness. Since the sender does not observe the receivers’ reward distributions or types, unlike in the OBP framework, we evaluate violations cumulatively. Formally, VmT:=1T∑t∈[T]∑i∈[m]∑x∈X∑ω∈Ω∑a∈Aqit(x,ω,a)(ur,t(x,ω,bϕit(a,x))−ur,t(x,ω,a)),V_m^T:= 1T _t∈[T] _i∈[m] _x∈ X _ω∈ _a∈ Aq_i^t(x,ω,a) (u^r,t (x,ω,b^φ^t_i(a,x) )-u^r,t(x,ω,a) ), where bϕit(a,x)b^φ^t_i(a,x) denotes the receiver’s best response under policy ϕitφ^t_i upon receiving signal a∈Aa∈ A in state x∈Xx∈ X. We emphasize that, the violation metric is only considered for the MPP part. As in the OBP part, all of the signaling scheme’s ϕit∈φ^t_i are already persuasive. Accordingly, our objective is to design learning algorithms that generate signaling policies ϕit _i^t while ensuring that both regret and constraint violations grow sublinearly in the number of episodes m. Although the persuasiveness constraints may be violated in some episodes, such violations occur only in a vanishing fraction of rounds. Consequently, in the long run, it remains optimal for receivers to follow, i.e., be obedient to, the sender’s recommendations. 4.1 Estimators and Confidence Bounds for Meta-Learning in Markov Persuasion Processes Before presenting the learning algorithms, we first construct estimators and confidence sets for the stochastic components of the MPP model, namely the transition dynamics, the prior distribution, the sender’s rewards, and the receiver types’ rewards. For each task t∈[T]t∈[T] and episode index i∈[m]i∈[m], we introduce empirical visitation counts. Specifically, for every (x,ω,a,x′)∈X×Ω×A×X(x,ω,a,x )∈ X× × A× X, let Nit(x,ω,a,x′):=∑j=1i−1(xjt,ωjt,ajt,xj+1t)=(x,ω,a,x′).N_i^t(x,ω,a,x ):= _j=1^i-11\! \(x_j^t, _j^t,a_j^t,x_j+1^t)=(x,ω,a,x ) \. Similarly, we define the lower-order counts by marginalization: Nit(x,ω,a):=∑x′∈Xk(x)+1Nit(x,ω,a,x′),N_i^t(x,ω,a):= _x ∈ X_k(x)+1N_i^t(x,ω,a,x ), Nit(x,ω):=∑a∈ANit(x,ω,a),Nit(x):=∑ω∈ΩNit(x,ω).N_i^t(x,ω):= _a∈ AN_i^t(x,ω,a),\;N_i^t(x):= _ω∈ N_i^t(x,ω). Thus, each counter records how many times the corresponding coordinate has been observed strictly before episode i in task t. For every scalar entry of the unknown primitives that we estimate in task t∈[T]t∈[T]—namely, a transition probability Pt(x′∣x,ω,a)P^t(x x,ω,a), a prior entry μt(ω∣x)μ^t(ω x), or a reward entry us,t(x,ω,a)u^s,t(x,ω,a) or ur,t(x,ω,a)u^r,t(x,ω,a)— we use the same meta-learning template. For a fixed coordinate c, let n:=Nit(c)n:=N_i^t(c) denote the number of observations of that coordinate collected up to, but excluding, episode i in task t, and let Q¯it(c) Q_i^t(c) denote the corresponding within-task empirical estimator. We set Q¯it(c):=0wheneverNit(c)=0 Q_i^t(c):=0\;whenever\;N_i^t(c)=0 by convention. To leverage information gathered from previous tasks, we define an across-task meta-mean using past tasks. For each τ∈[t−1]τ∈[t-1], let Q¯τ(c) Q^τ(c) denote the terminal within-task empirical estimator of coordinate c in task τ, computed from all observations collected up to episode m, and let Nτ(c):=Nmτ(c)N_τ(c):=N_m^τ(c) be the corresponding terminal count. Since a coordinate may be unobserved in some tasks, we average only over tasks in which that coordinate has been observed. Formally, define the within-task empirical mean for the new task and the task-wise terminal empirical means for past tasks as Q¯it+1:=1max1,n∑j=1nQjt+1,Q¯τ:=1max1,Nτ∑j=1NτQjτ,∀τ∈[t]. Q_i^\,t+1:= 1 \1,n\ _j=1^nQ_j^t+1, Q^τ:= 1 \1,N_τ\ _j=1^N_τQ_j^τ, ∀τ∈[t]. If we have Nmτ(c)=0N_m^τ(c)=0, we set Q¯τ(c)=0 Q^τ(c)=0 by convention. Define the active-task indicator and active-task count by Iτ(c):=Nτ(c)>0,I_τ(c):=1\N_τ(c)>0\, Mt−1(c):=∑τ=1t−1Iτ(c).M_t-1(c):= _τ=1^t-1I_τ(c). Then, the across-task meta-mean is Q¯Gt−1(c):=1max1,Mt−1(c)∑τ=1t−1Iτ(c)Q¯τ(c). Q_G^\,t-1(c):= 1 \1,M_t-1(c)\ _τ=1^t-1I_τ(c)\, Q^τ(c). To make proposed estimator well-defined for all values of the count and similarity parameter, including the degenerate case Nit(c)=0N_i^t(c)=0 and κ=0κ=0, we define the weights piecewise as wκ(n):=1,κ=0,n+κ,κ>0,w¯κ(n):=1−wκ(n)=0,κ=0,κn+κ,κ>0.w_κ(n):= cases1,&κ=0,\\[4.0pt] nn+κ,&κ>0, cases w_κ(n):=1-w_κ(n)= cases0,&κ=0,\\[4.0pt] κn+κ,&κ>0. cases Using these weights, the meta-estimator for coordinate c at episode i of task t is defined by Q^it(c):=wκ(Nit(c))Q¯it(c)+w¯κ(Nit(c))Q¯Gt−1(c). Q_i^t(c):=w_κ\! (N_i^t(c) )\, Q_i^t(c)+ w_κ\! (N_i^t(c) )\, Q_G^\,t-1(c). Hence, when κ=0κ=0, the estimator reduces exactly to the within-task empirical estimator, while for κ>0κ>0 it interpolates between the within-task estimate and the across-task meta-mean. Such an idea of estimator can be traced back to empirical Bayesian estimation of different types of distributions (Efron and Morris, 1973; Raiffa and Schlaifer, 1961). Its main advantage is that it preserves within-task consistency: for any fixed κ, as n→∞n→∞, we have wt→1w_t→ 1, and therefore Q^it−Q¯it→0 Q_i^t- Q_i^t→ 0. At the same time, when n is small, the estimator can substantially reduce variance by borrowing strength from previous tasks. Moreover, the proposed estimator interpolates smoothly between pure within-task learning and aggressive transfer across tasks. When κ is small, the weight on the current task is close to one; when κ is large, the estimator places more weight on the across-task meta-mean. A natural similarity parameter is of the form κ≍within-task noise levelacross-task variability.κ within-task noise levelacross-task variability. To formalize this construction, we first introduce the following assumption, which is standard in the meta-learning and Bayesian persuasion literatures. Assumption 4.1 For every coordinate (x,ω,a,x′)∈X×Ω×A×X(x,ω,a,x )∈ X× × A× X and (x,ω,a)∈X×Ω×A(x,ω,a)∈ X× × A, we assume that the sender knows the within-task variance σ2σ^2 and the across-task variance ι2 ^2 associated with the task parameters Pt(x′∣x,ω,a)P^t(x x,ω,a), μt(ω∣x)μ^t(ω x), us,t(x,ω,a)u^s,t(x,ω,a), ur,t(x,ω,a)u^r,t(x,ω,a) . In many meta-learning work, the observation noise variance is assumed to be known or estimated offline from abundant data, while the primary goal is to estimate task-specific means (Basu et al., 2021; Kveton et al., 2021). By contrast, in classical Bayesian persuasion models, the sender typically assumed to know the prior over the state and the payoff functions, and thus the analogous “mean” and “variance” parameters are not themselves learned, (Velicheti et al., 2023; Akyol et al., 2016). Our repeated setting sits between these extremes: we learn task-dependent quantities online while using σ2σ^2 and ι2 ^2 only as quantities that summarize within-task noise and cross-task similarity through κ. In our setting, the precise meaning of the within-task noise depends on the primitive being estimated, as formalized next. For every transition coordinate (x,ω,a,x′)(x,ω,a,x ), the task-dependent parameter Pt(x′∣x,ω,a)P^t(x x,ω,a) is drawn i.i.d. across tasks with mean PG(x′∣x,ω,a)P_G(x x,ω,a) and across-task variance bounded by ιP2 _P^2. Likewise, for every prior coordinate (x,ω)(x,ω), the task-dependent parameter μt(ω∣x)μ^t(ω x) is drawn i.i.d. across tasks with mean μG(ω∣x) _G(ω x) and across-task variance bounded by ιμ2 _μ^2. Within a fixed task t, the quantities PtP^t and μtμ^t are fixed. The randomness within the task comes from repeated visits to the corresponding coordinates: • whenever (x,ω,a)(x,ω,a) is visited, the next state is sampled from the categorical distribution Pt(⋅∣x,ω,a)P^t(· x,ω,a); • whenever x is visited, the realized outcome is sampled from the categorical distribution μt(⋅∣x)μ^t(· x). Equivalently, for every fixed entry x′x of Pt(⋅∣x,ω,a)P^t(· x,ω,a) and every fixed entry ω of μt(⋅∣x)μ^t(· x), the associated one-time observation is Bernoulli with mean equal to that entry’s probability. Therefore, Var(xk+1=x′∣Pt,x,ω,a)≤14,Var(ωk=ω∣μt,x)≤14.Var\! (1\x_k+1=x \ P^t,x,ω,a )≤ 14, \! (1\ _k=ω\ μ^t,x )≤ 14. For reward coordinates, conditioned on the task means us,t(x,ω,a)u^s,t(x,ω,a) and ur,t(x,ω,a)u^r,t(x,ω,a), the within-task observations are independent across episodes, take values in [0,1][0,1], and satisfy [uis,t(x,ω,a)∣us,t(x,ω,a)]=us,t(x,ω,a),Var(uis,t(x,ω,a)∣us,t(x,ω,a))≤σs2,E\! [u_i^s,t(x,ω,a) u^s,t(x,ω,a) ]=u^s,t(x,ω,a), \! (u_i^s,t(x,ω,a) u^s,t(x,ω,a) )≤ _s^2, [uir,t(x,ω,a)∣ur,t(x,ω,a)]=ur,t(x,ω,a),Var(uir,t(x,ω,a)∣ur,t(x,ω,a))≤σr2.E\! [u_i^r,t(x,ω,a) u^r,t(x,ω,a) ]=u^r,t(x,ω,a), \! (u_i^r,t(x,ω,a) u^r,t(x,ω,a) )≤ _r^2. Finally, due to variance bounds of the observable parameters, for the similarity parameters we choose κP=1/4ιP2,κμ=1/4ιμ2,κus=σs2ιs2,κur=σr2ιr2. _P= 1/4 _P^2,\; _μ= 1/4 _μ^2,\; _u^s= _s^2 _s^2,\; _u^r= _r^2 _r^2. We now specialize the generic meta-estimator to each primitive. For transition kernel estimator we have P^it(x′∣x,ω,a):=wκP(Nit(x,ω,a))Nit(x,ω,a,x′)max1,Nit(x,ω,a)+w¯κP(Nit(x,ω,a))P¯Gt−1(x′∣x,ω,a), P_i^t(x x,ω,a):=w_ _P\! (N_i^t(x,ω,a) )\, N_i^t(x,ω,a,x ) \1,N_i^t(x,ω,a)\+ w_ _P\! (N_i^t(x,ω,a) )\, P_G^\,t-1(x x,ω,a), where we define P¯Gt−1(x′∣x,ω,a):=1max1,Mt−1(x,ω,a)∑τ=1t−1Nmτ(x,ω,a)>0Nmτ(x,ω,a,x′)max1,Nmτ(x,ω,a). P_G^\,t-1(x x,ω,a):= 1 \1,M_t-1(x,ω,a)\ _τ=1^t-11\N_m^τ(x,ω,a)>0\\, N_m^τ(x,ω,a,x ) \1,N_m^τ(x,ω,a)\. For prior distribution estimator, we have μ^it(ω∣x):=wκμ(Nit(x))∑j=1i−1xjt=x,ωjt=ωmax1,Nit(x)+w¯κμ(Nit(x))μ¯Gt−1(ω∣x), μ_i^t(ω x):=w_ _μ\! (N_i^t(x) )\, _j=1^i-11\x_j^t=x,\ _j^t=ω\ \1,N_i^t(x)\+ w_ _μ\! (N_i^t(x) )\, μ_G^\,t-1(ω x), where we define, μ¯Gt−1(ω∣x):=1max1,Mt−1(x)∑τ=1t−1Nmτ(x)>0∑j=1mxjτ=x,ωjτ=ωmax1,Nmτ(x). μ_G^\,t-1(ω x):= 1 \1,M_t-1(x)\ _τ=1^t-11\N_m^τ(x)>0\\, _j=1^m1\x_j^τ=x,\ _j^τ=ω\ \1,N_m^τ(x)\. For reward estimators, for ℓ∈s,r ∈\s,r\ we have: u^iℓ,t(x,ω,a):=wκuℓ(Nit(x,ω,a))∑j=1i−1ujℓ,t(x,ω,a)xjt=x,ωjt=ω,ajt=amax1,Nit(x,ω,a)+w¯κuℓ(Nit(x,ω,a))u¯Gℓ,t−1(x,ω,a)\! u_i ,t(x,\!ω,\!a)\!\!:=\!w_ _u \! (\!N_i^t(x,ω,a) ) \! _j=1^i-1\!u_j ,t(x,\!ω,\!a\!)\,\!1\x_j^t\!=\!x, _j^t\!=\!ω,a_j^t\!=\!a\!\\!\! \1,N_i^t(x,ω,a)\+ w_ _u \! (\!N_i^t(x,\!ω,\!a) ) u_G ,t-1\!(x,\!ω,\!a) where, u¯Gℓ,t−1(x,ω,a):=1max1,Mt−1(x,ω,a)∑τ=1t−1Nmτ(x,ω,a)>0∑j=1mujℓ,τ(x,ω,a)xjτ=x,ωjτ=ω,ajτ=amax1,Nmτ(x,ω,a). u_G ,t-1(x,ω,a)\!:=\! 1 \1,M_t-1(x,ω,a)\ _τ=1^t-11\N_m^τ(x,ω,a)>0\ _j=1^m\!u_j ,τ(x,ω,a)1\x_j^τ=x, _j^τ=ω,a_j^τ=a\ \1,N_m^τ(x,ω,a)\. For notational simplicity in the sequel, and in particular in the Appendices, we take κP=κμ=κus=κur=κ, _P= _μ= _u^s= _u^r=κ, while keeping in mind that the interpretation of the within-task noise differs across primitives. The corresponding confidence radii are denoted by ϵit(x,ω,a), _i^t(x,ω,a), ζit(x), _i^t(x), ξis,t(x,ω,a), _i^s,t(x,ω,a), ξir,t(x,ω,a) _i^r,t(x,ω,a). We provide the concentration proofs in Appendix B.1. For a confidence parameter δ∈(0,1)δ∈(0,1), we define the good event in which all confidence bounds hold as ℰ(δ)E(δ). With the updated concentration lemmas in Appendix B.1, the event ℰ(δ)E(δ) holds with probability at least 1−8δ1-8δ, in both the full-feedback and partial-feedback settings. Algorithm 7 Full-Feedback Meta Optimistic Persuasive Policy Search (Full-Meta-OPPS) 1:X, A, Ω , m, T, confidence parameter δ∈(0,1)δ∈(0,1) 2:for task t=1,…Tt=1,… T do 3: for iteration i=1,…,mi=1,…,m do 4: Update all estimators P^it,μ^it,u^s,t,u^ir,t P_i^t, μ_i^t, u_s^s,t, u_i^r,t and bounds ϵit,ζit,ξis,t,ξir,t _i^t, _i^t, _i^s,t, _i^r,t given new observations 5: q^it← q_i^t← Solve Meta-Opt-Opt 6: ϕit←ϕq^itφ^t_i←φ q_i^t 7: Run Protocol 2 by committing to ϕit _i^t 8: Observe full feedback from Protocol 2 9: end for 10:end for 4.2 Full Feedback Setting In this section, we utilize the Optimistic Persuasive Policy Search, Algorithm 7, proposed by (Bacchiocchi et al., 2025) to learn and solve Problem 1a. At each episode of every task, the algorithm solves a linear optimization problem, referred to as Meta-Opt-Opt (see B.2). This program constitutes the meta-learning variant of the original Opt-Opt formulation in (Bacchiocchi et al., 2025), where the optimization is performed using the linear constraints set by our meta-estimators and their confidence bounds. Simply, Meta-Opt-Opt is a linear program whose goal is to maximize sender’s utility as: maxqt,ζt,ϵt∑x∈Xk∑ω∈Ω∑a∈A∑x′∈Xk+1qt(x,ω,a,x′)(u^is,t(x,ω,a)+ξis,t(x,ω,a)) _q^t,ζ^t,ε^t\;\; _x∈ X_k _ω∈ _a∈ A _x ∈ X_k+1q^t(x,ω,a,x ) ( u^s,t_i(x,ω,a)+ξ^s,t_i(x,ω,a) ) subject to the linear constraints on the transition functions, outcomes, occupancy measure and the incentive compatibility. Since we do not know the receiver types’ true mean utility ur,t(x,ω,a)u^r,t(x,ω,a), the classical persuasiveness constraint could not be used. Therefore, an optimistic incentive compatibility constraint is used ensuring that as our estimations get closer to the true mean ur,t(x,ω,a)u^r,t(x,ω,a). It can be seen that, the incentive compatibility becomes the persuasiveness constraint, as violation goes to 0. The optimistic incentive compatibility is given as follows: ∑ω∈Ω∑x′∈Xk+1qt(x,ω,a,x′)(u^ir,t(x,ω,a)+ξir,t(x,ω,a)−u^ir,t(x,ω,a′)+ξir,t(x,ω,a′))≥0\!\!\!\! _ω∈ _x ∈ X_k+1q^t(x,ω,a,x ) ( u_i^r,t(x,ω,a)+ _i^r,t(x,ω,a)- u_i^r,t(x,ω,a )+ _i^r,t(x,ω,a ) )≥ 0\\ In Algorithm 7, at each iteration the algorithm first updates all estimators and confidence bounds using the feedback obtained from previous episodes as in Line 3. It then commits to the signaling policy ϕit _i^t induced by an optimal solution q^it q_i^t of Meta-Opt-Opt, which is computed in Line 4. Notice that, the occupancy measure qitq^t_i resulting from committing to ϕitφ^t_i is in general different from computed q^it q^t_i, as the former is defined in terms of the true and unknown transition and prior functions, namely P and μ. Furthermore, as stated in Bacchiocchi et al. (2025) under the good event ℰ(δ)E(δ), there exists a feasible solution to Meta-Opt-Opt program. Then, by bounding the difference between the estimated and true occupancy measures, and establishing high-probability guarantees for the feasibility of the Meta-Opt-Opt program under the proposed estimators, which ensures that the estimated occupancy measures remain close to the true ones, we arrive at the following theorem. We provide the detailed analysis in Appendix B.2 and B.3. Algorithm 8 Partial Feedback Meta Optimistic Persuasive Policy Search (Partial-Meta-OPPS) 1:X,Ω,A,m,TX, ,A,m,T, δ∈(0,1)δ∈(0,1), α∈[1/2,1]α∈[1/2,1] 2:N←⌈mα⌉N← m^α 3:for task t=1,…,Tt=1,…,T do 4: Initialize counter C(x,ω,a)C(x,ω,a) to 0 for all (x,ω,a)(x,ω,a) 5: for iteration i=1,…,mi=1,…,m do 6: Update all estimators P^it,μ^it,u^is,t,u^ir,t P^t_i, μ^t_i, u_i^s,t, u^r,t_i and bounds ϵit,ζit,ξis,t,ξir,tε^t_i,ζ^t_i,ξ^s,t_i,ξ^r,t_i given new observations 7: if i≤N|X||Ω||A|i≤ N|X|| ||A| then 8: (x,ω,a)←argmin(x,ω,a)∈X×Ω×AC(x,ω,a)(x,ω,a)← _(x,ω,a)∈ X× × AC(x,ω,a) 9: q^it← q^t_i← Solve Meta-Opt-Opt with its objective modified as ∑x′∈Xqt(x,ω,a,x′) _x ∈ Xq^t(x,ω,a,x ) 10: C(x,ω,a)←C(x,ω,a)+1C(x,ω,a)← C(x,ω,a)+1 11: else 12: q^it← q^t_i← Solve Meta-Opt-Opt 13: end if 14: ϕit←ϕq^itφ^t_i←φ q_i^t 15: Run Protocol 2 by committing to ϕitφ^t_i 16: Observe partial feedback from Protocol 2 17: end for 18:end for Theorem 4.1. Given any δ∈(0,1)δ∈(0,1), with probability at least 1−11δ1-11δ, Algorithm 7 attains the given cumulative task averaged regret and cumulative task averaged violation: RmT≤(L2m+κ|X||Ω||A||X|m|Ω||A|ln(m|X||Ω||A|δ))R^T_m ( L^2 m m+ κ|X|| ||A|\;|X| m| ||A| \! ( m|X|| ||A|δ ) ) VmT≤(L2m+κ|X||Ω||A||X|m|Ω||A|ln(m|X||Ω||A|δ))V^T_m ( L^2 m m+ κ|X|| ||A|\;|X| m| ||A| \! ( m|X|| ||A|δ ) ) 4.3 Partial Feedback Setting In the partial-feedback setting, the main difficulty compared to the full-feedback case lies in the limited observability of persuasiveness constraints. Specifically, after committing to a signaling policy ϕit _i^t, the sender does not observe sufficient information to directly evaluate whether ϕit _i^t satisfies the persuasiveness constraints or not. Consequently, obtaining sublinear constraint violation in the partial-feedback regime is substantially more challenging than in the full-feedback setting. This limited feedback introduces an inherent trade-off between regret minimization and constraint violation, governed by the amount of exploration performed. To address this challenge, we utilize the exploration included version of OPPS, leading to Algorithm 8, again introduced in Bacchiocchi et al. (2025). The key idea is to partition the episodes of each task into two distinct phases as exploration and exploitation phases. The first phase is dedicated to the objective of constructing accurate estimates of the persuasiveness constraints to guarantee sublinear cumulative violation. This phase lasts for the first N|X||Ω||A|N|X|| ||A| episodes, where N≔⌈mα⌉N m^α and α∈[1/2,1]α∈[1/2,1] is a parameter provided to the algorithm that controls the relative duration of the exploration and exploitation phases. The second phase is devoted to regret minimization. During this phase, the algorithm proceeds analogously to Algorithm 7, using the estimates obtained during the exploration phase. This two-phase structure explicitly balances exploration for constraint estimation and exploitation for regret minimization, enabling sublinear regret while controlling cumulative persuasiveness violations. This leads to the following theorems, for which we provide details in Appendices B.2 and B.3. Theorem 4.2. Given any δ∈(0,1)δ∈(0,1), with probability at least 1−11δ1-11δ, Algorithm 8 attains cumulative task averaged expected regret and cumulative task averaged violation: RmT≤(NL|X||Ω||A|+L2m+κ|X||Ω||A||X|m|Ω||A|ln(m|X||Ω||A|δ))R^T_m (NL|X|| ||A|+ L^2 m m+ κ|X|| ||A|\;|X| m| ||A| \! ( m|X|| ||A|δ ) ) where N≔⌈mα⌉N m^α is the length of the exploration phase. Theorem 4.3. Given any δ∈(0,1)δ∈(0,1), with probability at least 1−13δ1-13δ, Algorithm 8 attains cumulative task averaged violation: VmT V^T_m ≤~[ρ(Lm+κ|X||Ω||A|+|X||Ω||A|NL+κ|X|Ω||A|+N+mNL+κ|X|Ω||A|+mN)] \!≤ O [ρ ( Lm m\!+\! κ|X|| ||A|\!+\! |X|| ||A|N\! NL\!+\! κ|X| ||A|\!\!+\! N\!+\! m\! NL\!+\! κ|X| ||A|\!\!+\! m N ) ] whereρ:=|X||Ω||A|2Lln(1δ)where\ ρ:=|X|| ||A|^2L\, ( 1δ ), and N≔⌈mα⌉N m^α is the length of the exploration phase. 5 Numerical Results 5.1 Numerical Results for Online Bayesian Persuasion In the OBP experiments, we use the classic judge–prosecutor example of Kamenica and Gentzkow (2011). We consider an environment with two actions, two outcomes, and two receiver types, K=2K=2. For each task, prior, the utilities of the sender and the receiver are sampled from a uniform distribution around their means, provided below, with width τ1=0.05 _1=0.05. To construct persuasive policies ϕ∈φ , we sample these policies from a uniform probability grid while only those signaling schemes that satisfy the persuasiveness constraints for both receiver types are retained. The means for the prior, sender utility and 2 receiver types’ utilities are given as: μ(w)=(0.20.8),us(ω,a)=−(0.70.30.70.3),u1r(ω,a)=−(0.70.30.30.7),u2r(ω,a)=−(0.80.20.20.8).μ(w)= pmatrix0.2&0.8 pmatrix, u^s(ω,a)=- pmatrix0.7&0.3\\ 0.7&0.3 pmatrix, u_1^r(ω,a)=- pmatrix0.7&0.3\\ 0.3&0.7 pmatrix, u_2^r(ω,a)=- pmatrix0.8&0.2\\ 0.2&0.8 pmatrix. Furthermore, the loss vectors of the persuasive policies ϕ∈φ are bounded in [0,1]⊂ℝ2[0,1] ^2 and the interval of the learning rate η is chosen to be [0.05,0.25][0.05,0.25]. The within-task iteration number is set to m=5m=5, while the total number of tasks is T=25T=25 for the experiments. Finally, we report on the average trajectory over 20 runs for both the non-meta-learning and meta-learning cases. The shaded regions indicate one standard deviation around the mean trajectories, which is given in the Figures 2(a) and 2(b). (a) Task-averaged regret, full feedback (b) Task-averaged regret, partial feedback 5.2 Numerical Results for Markov Persuasion Processes In the MPP experiments, we again use the judge–prosecutor persuasion example. The environment consists of two states, two actions, two outcomes, and two layers. The across-task mean parameters are defined as follows. The transition to the second layer is deterministic, and given as PG(x2∣x1,ω,a)=1.P_G(x_2 x_1,ω,a)=1. The outcome kernel, conditional on the state, on average, with the sender’s and receiver’s mean utilities are given by μG(ω∣x)=(0.20.80.80.2),uGs(⋅,ω,a)=(0.70.30.70.3),uGr(⋅,ω,a)=(0.70.30.30.7). _G(ω x)= pmatrix0.2&0.8\\ 0.8&0.2 pmatrix,\;u_G^s(·,ω,a)= pmatrix0.7&0.3\\ 0.7&0.3 pmatrix,\;u_G^r(·,ω,a)= pmatrix0.7&0.3\\ 0.3&0.7 pmatrix.\; Across tasks, the probability distributions of the random variables are drawn from a uniform distribution around their mean with width τ2=0.01 _2=0.01. Within each task, sampling is again done by a uniform distribution centered around the sampled mean with width τ3=0.1 _3=0.1. The number of tasks is set to T=1000T=1000, and each task consists of m=200m=200 iterations. At every iteration, Meta-Opt-Opt is solved with updated estimators. Since incentive compatibility constraints are not known exactly at the beginning, the algorithm exhibits positive violation and negative regret. However, as more tasks are observed, the estimators improve, and produce increasingly feasible solutions with lower violation. Consequently, regret approaches zero from the negative side. Finally, we report on the average regret and violation trajectories over 20 runs for both the OPPS and Meta-OPPS algorithms under partial and full feedback. The shaded regions indicate the one standard deviation around the mean trajectories. The results are shown in Figures 3(a)–3(b) and Figures 4(a)–4(b). (a) Task-averaged regret, full feedback (b) Task-averaged violation, full feedback (a) Task-averaged regret, partial feedback (b) Task-averaged violation, partial feedback 6 Conclusion Building on the classical Bayesian persuasion framework and the meta-learning paradigm of leveraging structure across related tasks, we have introduced meta-persuasion algorithms for repeated Bayesian persuasion in both the Online Bayesian Persuasion (OBP) and Markov Persuasion Process (MPP) settings under full and partial feedback. Our approach establishes that when tasks share a common latent structure, the sender can achieve strictly improved task-averaged regret guarantees relative to learning each task independently, while recovering standard worst-case rates under heterogeneous or adversarial task sequences. Our work opens several promising directions for future research. First, extending meta-persuasion to adversarially drifting task families would clarify when transfer remains beneficial and when it may degrade performance. Second, incorporating forward-looking strategic receivers and studying sequential persuasion problems within the meta-learning framework would introduce dynamic incentive compatibility considerations to the model. Finally, extending the meta-learning layer beyond linear loss structures to convex–concave or more general nonlinear classes, and analyzing settings in which receivers themselves learn over time, would connect meta-persuasion to broader themes in learning-in-games and dynamic information design. 7 Acknowledgments Research of the authors was supported in part by the Army Research Office (ARO) Grant Number W911NF-24-1-0085 References Abernethy et al. (2008) Jacob Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. Proceedings of the 21st Annual Conference on Learning Theory (COLT), 2008. Akyol et al. (2016) Emrah Akyol, Cédric Langbort, and Tamer Başar. Information-theoretic approach to strategic communication as a hierarchical game. Proceedings of the IEEE, 105(2):205–218, 2016. Arieli et al. (2024) Itai Arieli, Omer Madmon, and Tennenholtz Moshe. Reputation-based persuasion platforms. Games and Economic Behavior, 147(1):128–147, 2024. Auer et al. (2008) Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. 21st Conference on Neural Information Processing Systems (NeurIPS), 2008. Aviv and Mansour (2019) Rosenberg Aviv and Yishay Mansour. Online convex optimization in adversarial markov decision processes. Proceedings of the 36th International Conference on Machine Learning (ICML, 2019. Bacchiocchi et al. (2025) Francesco Bacchiocchi, Francesco Emanuele Stradi, Matteo Castiglioni, Alberto Marchesi, Francesco Trovo, and Nicola Gatti. Markov persuasion processes: Learning to persuade from scratch. 39th Conference on Neural Information Processing Systems (NeurIPS), 2025. Balcan et al. (2022) Maria-Florina Balcan, Harris Keegan, Khodak Mikhai l, and Zhiwei Steven Wu. Meta-learning adversarial bandits. arXiv preprint,arXiv:2205.141128, 2022. Basu et al. (2021) Soumya Basu, Branislav Kveton, Manzil Zaheer, and Csaba Szepesvari. No regrets for learning the prior in bandits. In Advances in Neural Information Processing Systems (NeurIPS), 2021. Başar (2024) Tamer Başar. Inducement of desired behavior via soft policies. International Game Theory Review, 26(02):2440002, 2024. Bernasconi et al. (2023) Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Alberto Marchesi, Francesco Trovo, and Nicola Gatti. Optimal rates and efficient algorithms for online Bayesian persuasion. Proceedings of the 40th International Conference on Machine Learning (ICML), 2023. Castiglioni et al. (2020) Matteo Castiglioni, Andrea Celli, Alberto Marchesi, and Nicola Gatti. Online Bayesian persuasion. Advances in Neural Information Processing Systems 33 (NeurIPS), 2020. Castiglioni et al. (2021) Matteo Castiglioni, Alberto Marchesi, Andrea Celli, and Nicola Gatti. Multi-receiver online Bayesian persuasion. arXiv preprint arXiv:2106.06480, 2021. Dughmi and Xu (2016) Shaddin Dughmi and Haifeng Xu. Algorithmic Bayesian persuasion. arXiv preprint arXiv:1503.05988, 2016. Efron and Morris (1973) Bradley Efron and Carl Morris. Stein’s estimation rule and its competitors–an empirical Bayes approach. Journal of the American Statistical Association, 68(341):117–130, 1973. Harris et al. (2023) Keegan Harris, Ioannis Anagnostides, Gabriele Farina, Mikhail Khodak, Zhiwei Steven Wu, and Tuomas Sandholm. Meta-learning in games. arXiv preprint,arXiv:2209.14110, 2023. Hazan et al. (2007) Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning, 2007. Kamenica and Gentzkow (2011) Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 101(6):2590–2615, 2011. Khodak et al. (2019) Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Adaptive gradient-based meta-learning methods. 33rd Conference on Neural Information Processing Systems (NeurIPS), 2019. Kveton et al. (2021) Branislav Kveton, Mikhail Konobeev, Manzil Zaheer, Chih-Wei Hsu, Martin Mladenov, Craig Boutilier, and Csaba Szepesvari. Meta-thompson sampling. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 5884–5893, 2021. Mansour et al. (2016) Yishay Mansour, Aleksandrs Slivkins, Syrgkanis Vasilis, and Zhiwei Steven Wu. Bayesian exploration: Incentivizing exploration in Bayesian games. Proceedings of the 16th ACM Conference on Economics and Computation (EC), 2016. Nesterov and Nemirovskii (1994) Yurii Nesterov and Arkadii Nemirovskii. Interior-Point Polynomial Algorithms in Convex Programming. SIAM, 1994. Raiffa and Schlaifer (1961) Howard Raiffa and Robert Schlaifer. Applied Statistical Decision Theory. Harvard University, 1961. Thrun and Pratt (1998) Sebastian Thrun and Lorien Pratt. Learning to Learn. Springer New York, NY, 1998. ISBN 9780792380474. Velicheti et al. (2023) Raj Kiriti Velicheti, Melih Bastopcu, and Tamer Başar. Strategic Information Design in Quadratic Multidimensional Persuasion Games with Two Senders. In 2023 American Control Conference (ACC), pages 1716–1722, 2023. doi: 10.23919/ACC55779.2023.10156508. Wu et al. (2022) Jibang Wu, Zixuan Zhang, Zhe Feng, Zhaoran Wang, Zhuoran Yang, Michael I. Jordan, and Haifeng Xu. Sequential information design: Markov persuasion process and its efficient reinforcement learning. Proceedings of the 23rd ACM Conference on Economics and Computation (EC), 2022. Yorulmaz et al. (2025) Asrın Efe Yorulmaz, Raj Kiriti Velicheti, Melih Bastopcu, and Tamer Başar. A soft snducement framework for incentive-aided steering of no-regret players. Conference on Decision and Control 2025 (CDC), pages 4396–4401, 2025. Zinkevich (2003) Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. Proceedings of the 20’th International Conference on Machine Learning (ICML), 2003. Appendix A Online Bayesian Persuasion A.1 Proofs for Online Bayesian Persuasion with Full Feedback In this appendix, we first present Lemmas A.1 and A.2, which will be used in the proof of Theorem 3.2. Lemma A.1. (Lemma A.1 Balcan et al. (2022)) Let ℛ:ν¯()↦ℝ≥0R: ν(P) _≥ 0 be a strictly-convex function with maxz∈ν¯()‖∇2ℛ(z)‖2≤S _z∈ ν(P)\|∇^2R(z)\|_2≤ S over a convex set ν¯()⊂ℝK ν(P) ^K with maxz∈ν¯()‖z‖2≤K _z∈ ν(P)\|z\|_2≤ K. Then, for any points 1,…,t∈ν¯()z^1,…,z^t∈ ν(P), the actions y1=argminz∈ν¯()ℛ(z)y^1= _z∈ ν(P)R(z) and yt=1t−1∑s<tsy^t= 1t-1 _s<tz^s have regret ∑t=1TDℛ(t∥yt)−Dℛ(t∥yT+1)≤8SK(1+lnT). _t=1^TD_R(z^t\|y^t)-D_R(z^t\|y^T+1)≤ 8SK(1+ T).\ Lemma A.2. (Corollary C.2. Khodak et al. (2019)) Let U(t):ℝ+→ℝt≥1\U^(t):R_+ \_t≥ 1 be a sequence of functions of the form U(t)(η)=((B(t))2η+η)γ(t)U^(t)(η)= ( (B^(t))^2η+η )γ^(t) for any positive scalars γ(1),…,γ(T)∈ℝ+γ^(1),…,γ^(T) _+ and adversarially chosen Bt∈[0,A]B_t∈[0,A]. Then, the ϵ−EWOOε-EWOO algorithm, with β=4mAminϵ2A2,1β= 4mA \ ε^2A^2,1\, for which ϵ>0ε>0, uses the actions of EWOOEWOO run on the functions U~t(η)=((B(t))2+ϵ2η+η)γ(t) U_t(η)= ( (B^(t))^2+ε^2η+η )γ^(t) over the domain [ϵ,A2+ϵ2][ε, A^2+ε^2] to determine η(t)η^(t) achieves regret minϵ2η∗,ϵ∑t=1Tγ(t)+Aγmax2maxA2ϵ2, 1(1+ln(T+1)) \ ε^2η^*,\,ε \ _t=1^Tγ^(t)+ A _ 2 \ A^2ε^2,\,1 \ (1+ (T+1) ) for all η∗>0η^*>0. Theorem 3.2. Algorithm 4 with ϵ=Km1T1/4ε= Km 1T^1/4, ρ=1T1/4ρ= 1T^1/4, A=KmA= Km and β=4mAminϵ2A2,1β= 4mA \ ε^2A^2,1\ achieves task-averaged regret of RmT=O(mVar(z∗(t)t=1T))+oT(poly(m,A))R^T_m=O( mVar\! (\z^*(t)\_t=1^T ))+o_T(poly(m,A)) Proof. In the proof, we first argue that enlarging the comparator class to the convex hull only upper bounds the regret notion of interest. Indeed, observe that Rm R_m =∑i=1m[ν(ϕi)⊤ki]−minϕ∗∈∑i=1mν(ϕ∗)⊤ki = _i=1^mE\! [ν( _i) 1_k_i ]- _φ _i=1^mν(φ ) 1_k_i =∑i=1mz~i⊤ki−minz∗∈ν()∑i=1m(z∗)⊤ki≤∑i=1mz~i⊤ki−minz∗∈ν¯()∑i=1m(z∗)⊤ki = _i=1^m z_i 1_k_i- _z ∈ν(P) _i=1^m(z ) 1_k_i\!≤ _i=1^m z_i 1_k_i-\!\!\! _z ∈ ν(P) _i=1^m(z ) 1_k_i since ν()⊆ν¯()ν(P) ν(P), and minimizing over a larger set can only decrease the minimum. Next, by Carathéodory’s theorem, any element of ν¯() ν(P) can be written as a convex combination of finitely many elements of ν()ν(P). In Algorithm 4, the strategy sampling procedure exactly implements such convex decompositions. Therefore, by linearity of the loss, we can replace the expectation in the first term with evaluation at the mean strategy: [ν(ϕi)⊤ki]=z~i⊤ki,E\! [ν( _i) 1_k_i ]= z_i 1_k_i, where z~i:=[ν(ϕi)].where z_i:=E[ν( _i)]. Finally, since the mapping ν(⋅)ν(·) is linear, it commutes with convexification: ν(¯)=ν¯().ν( P)= ν(P). Thus, bounding the regret reduces to a standard online linear optimization problem over the convex set ν¯() ν(P), and we may directly invoke the regret guarantees of OGD on this convex domain to bound RmR_m. For OGD (Zinkevich, 2003), let z∗=ν(ϕ∗)z^*=ν(φ^*) denote the optimal point for the sender, and let z¯i=ν¯(ϕi) z_i= ν( _i) denote the iterates. Since the loss functions over ν¯() ν(P) are linear and given by ℒk(ϕ)=ν(ϕ)⊤k,L_k(φ)=ν(φ) 1_k, their gradients with respect to the Euclidean norm have unit norm. Thus, we have Rm≤‖z∗−z¯1‖222η+η2mR_m≤ \|z^*- z_1\|_2^22η+ η2m Then, across the tasks we get RmT \!R^T_m ≤1T∑t=1T‖(z∗)t−(z¯1)t‖222ηt+1T∑t=1Tηt2m ≤ 1T _t=1^T \|(z^*)^t-( z_1)^t\|_2^22η^t+ 1T _t=1^T η^t2m =1T[∑t=1T‖(z∗)t−(z¯1)t‖222ηt+∑t=1Tηtm2+minη>0∑t=1T‖(z∗)t−(z¯1)t‖222η+ηm2−minη>0∑t=1T‖(z∗)t−(z¯1)t‖222η+ηm2] \!=\! 1T\! [\! _t=1^T\! \|(z^*)^t\!-\!( z_1)^t\|_2^2\!2η^t\!+\!\! _t=1^T\! η^tm2\!+\!\! _η>0\! \\! _t=1^T\! \!\|(z^*)^t\!-\!( z_1)^t\|_2^2\!2η\!+\! \!η m\!2\! \\!\!-\! _η>0\! \\! _t=1^T\! \!\|(z^*)^t\!-( z_1)^t\|_2^2\!2η\!+\! \!η m\!2\! \\! ] =ΔU+1Tminη>0∑t=1T‖(z∗)t−(z¯1)t‖222η+ηm2 \!= _U+ 1T _η>0 \ _t=1^T \|(z^*)^t-( z_1)^t\|_2^22η+ η m2 \ where, ΔU≔1T∑t=1T(‖(z∗)t−(z¯1)t‖222ηt+ηtm2)−1Tminη¯>η>0∑t=1T‖(z∗)t−(z¯1)t‖222η+ηm2 _U 1T _t=1^T( \|(z^*)^t-( z_1)^t\|_2^22η^t+ η^tm2)- 1T _ η>η>0 \ _t=1^T \|(z^*)^t-( z_1)^t\|_2^22η+ η m2 \. Then, we have: RmT \!R^T_m ≤ΔU+minη>01Tminz∈ν¯()[∑t=1T‖(z∗)t−z‖222η]+1T∑t=1T‖(z∗)t−(z¯1)t‖222η+ηm2−1Tminz∈ν¯()[∑t=1T‖(z∗)t−z‖222η] ≤\! _U\!+\! _η>0\! \\! 1T\!\! _z∈ ν(P)\! [ _t=1^T\! \!\|(z^*)^t-z\|_2^22η ]\!\!+\! 1T\! _t=1^T\! \|(z^*)^t-( z_1)^t\|_2^2\!2η\!+\! \!η m\!2\!-\! 1T\!\! _z∈ ν(P)\!\! [ _t=1^T\! \!\|(z^*)^t\!-\!z\|_2^2\!2η ]\! \ One can see that the minimization with respect to z in the second term trivially yields z=1T∑t=1T(z∗)t,z= 1T _t=1^T(z^*)^t, which we denote by z∗¯ z^*. Furthermore, the term becomes 12η∑t=1T‖(z∗)t−z∗¯‖22, 12η _t=1^T \|(z^*)^t- z^* \|_2^2, which corresponds to the empirical variance of the sequence (z∗)tt=1T\(z^*)^t\_t=1^T. We denote this quantity by Var(z∗(t)t=1T)Var\! (\z^*(t)\_t=1^T ). The first term after ΔU _U becomes Var(z∗(t)t=1T)2η Var\! (\z^*(t)\_t=1^T )2η. For the second term, we use Lemma A.1 with S=1S=1, K=K=K, ℛ(z)=12‖z‖22R(z)= 12\|z\|_2^2, with the identification, zt≡(z∗)t,z^t≡(z^*)^t, yt≡(z¯1)t=1t−1∑s<t(z∗)s,y^t≡( z_1)^t= 1t-1 _s<t(z^*)^s, yT+1=1T∑t=1T(z∗)t=z∗¯.y^T+1= 1T _t=1^T(z^*)^t= z^*. Since we use the Euclidean regularizer, we have Dℛ(a∥b)=12‖a−b‖22,D_R(a\|b)= 12\|a-b\|_2^2, and ‖∇2ℛ(z)‖2=1\|∇^2R(z)\|_2=1, so S=1S=1. Therefore, substituting the Euclidean Bregman divergence and dividing both sides by ηTη T yields, 1T∑t=1T‖(z∗)t−(z¯1)t‖222η−1T∑t=1T‖(z∗)t−z∗¯‖222η≤8K(1+lnT)ηT. 1T _t=1^T \|(z^*)^t-( z_1)^t\|_2^22η- 1T _t=1^T \|(z^*)^t- z^*\|_2^22η≤ 8K(1+ T)η T. Now observe that z∗¯∈argminz∑t=1T‖(z∗)t−z‖22, z^*∈ _z _t=1^T\|(z^*)^t-z\|_2^2, and therefore we may directly bound regret as RmT≤ΔU+minη>0ηm2+Var(z∗(t)t=1T)2η+8K(1+lnT)ηTR^T_m≤ _U+ _η>0 \ η m2+ Var\! (\z^*(t)\_t=1^T )2η+ 8K(1+ T)η T \\ (4) Now we bound the ΔU _U term using Lemma A.2 with U~t(η)=(‖(z∗)t−(z¯1)t‖22+mρ2A22η+mη2) U_t(η)= ( \|(z^*)^t-( z_1)^t\|_2^2+mρ^2A^22η+ mη2 ) where ϵ=ρAε=ρ A, γ(t)=m2γ^(t)= m2, ρ=1T1/4ρ= 1T^1/4, Bt=‖(z∗)t−(z¯1)t‖22mB_t= \|(z^*)^t-( z_1)^t\|_2^2 m, A=KmA= K m. Then, by direct application of Lemma A.2 we get, ΔU≤minKη∗T,KT1/4m2+mK2(1+ln(T+1))T=mK2(minKη∗T,1T1/4+1+ln(T+1)T) _U\!≤\! \ Kη^* T, KT^1/4 \ m2+ m K2 (1+ (T+1)) T\!=\! m K2\! (\! \! \ Kη^* T, 1T^1/4 \\!+\! 1\!+\! (T\!+\!1) T\! ) (5) for all η∗>0η^*>0. Now, combining equations (4) and (5): RmT≤ R^T_m≤ minη>0ηm2+Var(z∗(t)t=1T)2η+8K(1+lnT)ηT+mK2(minKη∗T,1T1/4+1+ln(T+1)T) _η>0\! \ η m2\!+\! Var\! (\z^*(t)\_t=1^T )2η\!+\! 8K(1+ T)η T \\!+\! m K2\! (\! \ Kη^* T, 1T^1/4 \+ 1+ (T+1) T\! ) Then, choosing η=Var(z∗(t)t=1T)mη= Var\! (\z^*(t)\_t=1^T )m, yields RmT=O(mVar(z∗(t)t=1T))+oT(poly(m,K))R^T_m=O ( mVar\! (\z^*(t)\_t=1^T )\; )+o_T(poly(m,K)). ∎ A.2 Proofs for Online Bayesian Persuasion with Partial Feedback In this appendix, we first present and prove Theorem A.1 and Lemma A.3, and then present the proof of Theorem 3.3. Theorem A.1 (Single-task regret of CTOMD). Fix a task t∈[T]t∈[T] and suppress the superscript t. Run Algorithm 5 with ηK≤14η K≤ 14, and let b:=1/mb:=1/ m. Then, for every comparator u∈ν¯b(P)u∈ ν_b(P), choosing η=Klnm4Kmη= K m4K m yields [∑i=1mν(ϕi)⊤ki]≤minu∈ν¯1/m(P)∑i=1mu⊤ki+ 16K3/2mlnm.E\! [ _i=1^mν( _i) 1_k_i ]\;≤\; _u∈ ν_1/ m(P) _i=1^mu 1_k_i\;+\;16K^3/2 m m. Proof. We write Hi:=∇2ℛ(zi)H_i:=∇^2R(z_i). First, a standard property of self-concordant barriers implies W1(zi)⊂int(ν¯(P))W_1(z_i) ( ν(P)) for all zi∈int(ν¯(P))z_i ( ν(P)) (Abernethy et al., 2008). Hence the sampling in Algorithm 5, i.e. y¯i=z¯i+εivj′−1/2ej′, y_i= z_i+ _iv_j ^-1/2\,e_j , is feasible as it has the local norm of 11, with respect to z¯i z_i. Since y¯i∈ν¯(P) y_i∈ ν(P) , Carathéodory’s theorem yields points yi,1,…,yi,mi∈ν(P)y_i,1,…,y_i,m_i∈ν(P) and weights λi,j≥0 _i,j≥ 0 with ∑jλi,j=1 _j _i,j=1 such that y¯i=∑jλi,jyi,j y_i= _j _i,jy_i,j. Algorithm 5 samples j′∼λij _i and plays ϕi=ν†(yi,j′) _i=ν (y_i,j ), so that ν(ϕi)=yi,j′ν( _i)=y_i,j , and therefore [ν(ϕi)∣y¯i]=y¯i.E [ν( _i) y_i ]= y_i. (6) Since the loss is linear in the lifted vector, conditioning on yiy_i gives [ν(ϕi)⊤ki∣y¯i]=y¯i⊤ki.E [ν( _i) 1_k_i y_i ]= y_i 1_k_i. (7) For the estimator, ℓ~i:=K⋅(ν(ϕi)⊤ki)⋅εivj′1/2ej′∈ℝK. _i:=K· (ν( _i) 1_k_i )· _i\,v_j ^1/2\,e_j ^K. We first show that [ℓ~i∣z¯i]=ki.E[ _i z_i]=1_k_i. Indeed, we have [y¯i∣z¯i]=z¯iE[ y_i z_i]= z_i since [εi]=0E[ _i]=0. Next, conditioning on z¯i z_i and on the event j′=j =j, using (7) and y¯i=z¯i+εivj−1/2ej y_i= z_i+ _iv_j^-1/2e_j, we get [ν(ϕi)⊤ki|z¯i,j′=j,εi]=(z¯i+εivj−1/2ej)⊤ki.E\! [ν( _i) 1_k_i\ |\ z_i,j =j, _i ]= ( z_i+ _iv_j^-1/2e_j ) 1_k_i. Multiplying by εivj1/2ej _iv_j^1/2e_j and averaging over εi∈±1 _i∈\± 1\ cancels out the z¯i z_i term and yields εi[ℓ~i∣z¯i,j′=j]=K⟨ki,ej⟩ej.E_ _i\! [ _i z_i,j =j ]=K\, 1_k_i,e_j \,e_j. Finally averaging over j′j uniform on [K][K] gives [ℓ~i∣z¯i]=ki.E[ _i z_i]=1_k_i. Now, we leverage Lemma 2 from Abernethy et al. (2008), which implies that for any comparator u∈ν¯(P)u∈ ν(P), the following holds under the FTRL/OMD update: ∑i=1m⟨ℓ~i,z¯i−u⟩≤Dℛ(u,z¯1)η+∑i=1m⟨ℓ~i,z¯i−z¯i+1⟩. _i=1^m _i, z_i-u \;≤\; D_R(u, z_1)η+ _i=1^m _i, z_i- z_i+1 . (8) For a ϑ -self-concordant barrier, the barrier growth controls the Bregman divergence from z1z_1 to any point at Minkowski distance at most (1+b)−1(1+b)^-1 from the boundary; concretely Dℛ(u,z¯1)≤ℛ(u)−ℛ(z¯1)≤ϑln(1+1b),∀u∈ν¯b(P).D_R(u, z_1) (u)-R( z_1)\;≤\; (1+ 1b ), ∀ u∈ ν_b(P). With b=1/mb=1/ m, this implies Dℛ(u,z¯1)≤2ϑlnmD_R(u, z_1)≤ 2 m (Nesterov and Nemirovskii, 1994). Finally, any polytope in ℝKR^K has at least K-self concordant barrier. Then, we have Dℛ(u,z¯1)≤2KlnmD_R(u, z_1)≤ 2K m. Now, letting hi:=z¯i+1−z¯ih_i:= z_i+1- z_i and ri:=‖hi‖zir_i:=\|h_i\|_z_i, Lemma 6 from Abernethy et al. (2008), implies ‖hi‖zi<4ηK.\|h_i\|_z_i<4η K. Then, we bound the local dual norm of the estimator. Condition on z¯i z_i and take j′=j =j. Since Hi−1ej=vj−1ejH_i^-1e_j=v_j^-1e_j and ν(ϕi)⊤ki∈[0,1]ν( _i) 1_k_i∈[0,1], we get; ‖ℓ~i‖zi,∗2=ℓ~i⊤Hi−1ℓ~i=K2(ν(ϕi)⊤ki)2⋅vj⋅ej⊤Hi−1ej=K2(ν(ϕi)⊤ki)2≤K2,\| _i\|_z_i,*^2= _i H_i^-1 _i=K^2 (ν( _i) 1_k_i )^2· v_j· e_j H_i^-1e_j=K^2 (ν( _i) 1_k_i )^2≤ K^2, and hence ‖ℓ~i‖zi,∗≤K\| _i\|_z_i,*≤ K almost surely. By Cauchy–Schwarz in the local primal-dual pair we have, ⟨ℓ~i,z¯i−z¯i+1⟩=⟨ℓ~i,−hi⟩≤‖ℓ~i‖z¯i,∗‖hi‖z¯i≤32ηK2 _i, z_i- z_i+1 = _i,-h_i \;≤\;\| _i\|_ z_i,*\,\|h_i\|_ z_i≤ 32η K^2 (9) Summing over i gives ∑i=1m⟨ℓ~i,z¯i−z¯i+1⟩≤32K2ηm. _i=1^m _i, z_i- z_i+1 ≤ 32K^2η m. (10) Combining (8), and (10) yields, for all u∈ν¯1/m(P)u∈ ν_1/ m(P), ∑i=1m⟨ℓ~i,z¯i−u⟩≤2ϑlnmη+32K2ηm. _i=1^m _i, z_i-u ≤ 2 mη+32K^2η m. Taking expectations and using [ℓ~i∣zi]=kiE[ _i z_i]=1_k_i gives [∑i=1m⟨ki,z¯i−u⟩]≤2ϑlnmη+32K2ηm.E\! [ _i=1^m 1_k_i, z_i-u ]≤ 2 mη+32K^2η m. Finally, by (6)–(7) and the tower property, [ν(ϕi)⊤ki]=[y¯i⊤ki]=[z¯i⊤ki],E\! [ν( _i) 1_k_i ]=E\! [ y_i 1_k_i ]=E\! [ z_i 1_k_i ], and thus the left-hand side becomes exactly the expected cumulative loss suffered by CTOMD, proving the stated bound. The final optimized rate follows by plugging in η=ϑlnm4Kmη= m4K m. ∎ Lemma A.3. Assume that losses are value-bounded on ν¯() ν(P) in the sense that for every loss vector g∈ℝKg ^K under consideration, 0≤⟨g,z⟩≤1 for all z∈ν¯().0≤ g,z ≤ 1 for all z∈ ν(P). Then, for any sequence gii=1m\g_i\^m_i=1 we have minu∈ν¯b()∑i=1m⟨gi,u⟩≤minz∈ν¯()∑i=1m⟨gi,z⟩+bm. _u∈ ν_b(P) _i=1^m g_i,u \;≤\; _z∈ ν(P) _i=1^m g_i,z +bm. Proof. Fix any z∈ν¯()z∈ ν(P) and define the point u:=z1+11+b(z−z1).u:=z_1+ 11+b(z-z_1). We first show that u∈ν¯b()u∈ ν_b(P). Indeed, z1+(1+b)(u−z1)=z1+(1+b)⋅11+b(z−z1)=z∈ν¯(),z_1+(1+b)(u-z_1)=z_1+(1+b)· 11+b(z-z_1)=z∈ ν(P), and thus by definition of πz1(⋅) _z_1(·) we have πz1(u)≤(1+b)−1 _z_1(u)≤(1+b)^-1, and hence u∈ν¯b()u∈ ν_b(P). Next, since ⟨g,⋅⟩ g,· is linear, ⟨g,u⟩=11+b⟨g,z⟩+b1+b⟨g,z1⟩≤11+b⟨g,z⟩+b1+b⋅1=⟨g,z⟩+b1+b(1−⟨g,z⟩)≤⟨g,z⟩+b. g,u = 11+b g,z + b1+b g,z_1 ≤ 11+b g,z + b1+b· 1= g,z + b1+b (1- g,z )≤ g,z +b. Now choosing z⋆∈argminz∈ν¯()⟨g,z⟩z ∈ _z∈ ν(P) g,z , and summing the same argument over i proves the claim. ∎ Theorem 3.3. For each b in G with interval (b¯,b¯)( b, b) define the constants Db2:=maxx,y∈ν¯bDℛ(x∥y),D_b^2:= _x,y∈ ν_bD_R(x\|y), Sb:=maxx∈ν¯b‖∇2ℛ(x)‖2,S_b:= _x∈ ν_b\|∇^2R(x)\|_2, :=maxx,y∈ν¯‖x−y‖2. K:= _x,y∈ ν\|x-y\|_2. Define the divergence, at level b by V^b2:=minz∈ν¯[1T∑t=1TDℛ(OPTb(ℓ~t)∥z)] V_b^2:= _z∈ ν\;E\! [ 1T _t=1^TD_R\! (OPT_b( ^t)\,\|\,z ) ], where OPTb(ℓ~t)=argminx∈ν¯b⟨ℓ~t,x⟩OPT_b( ^t)= _x∈ ν_b ^t,x . Then, running Algorithm 6, there exist a grid size k=O~(Db¯2KmT)k= O(D_ b^2K mT) and a meta step-size α such that the expected task-averaged regret satisfies [1T∑t=1T∑i=1m(ν(ϕit)⊤kit−ν(ϕt⋆)⊤kit)] \!\!\!\!\!E [ 1T _t=1^T _i=1^m (ν( _i^t) 1_k_i^t-ν( _t ) 1_k_i^t ) ] ≤72KmT−1/4(Db¯mTlnk+Sb¯2Db¯T(1+lnT)) ≤ 72K mT^-1/4 (D_ b mT k+ S_ b K^2D_ bT(1+ T) ) +minz∈ν¯,η>0,b∈[b¯,b¯][1T∑t=1TDℛ(OPTb(ℓ^t)∥z)η+(32ηK2+b)m]. +\!\!\!\!\!\! _z∈ ν,η>0,b∈[ b, b]\!E\! [\! 1T\! _t=1^T\! D_R(OPT_b( ^t)\|z)η\!+\!(32η K^2\!+\!b)m\! ]\!. (11) Moreover, optimizing over η yields the simplified form [RmT]≤O~(Db¯KmT1/4+Sb¯2KmDb¯T3/4)+minb∈[b¯,b¯](4KV^b2m+bm).E[R_m^T]\;≤\; O\! ( D_ bKmT^1/4+ S_ b K^2K mD_ bT^3/4 )\;+\; _b∈[ b, b] (4K V_b 2m+bm ). (12) In particular, as T→∞T→∞ the O~(⋅) O(·) term vanishes and [RmT]=O(V^bm+bm)E[R_m^T]=O( V_b m+bm) for the best b in the range. Proof. Since ν is linear, ν(¯)=ν¯()=ν¯ν( P)= ν(P)= ν and the loss is linear in ν(ϕ)ν(φ). Thus the per-task comparator can be taken as zt⋆∈argminz∈ν¯∑i=1mz⊤kit,z_t ∈ _z∈ ν _i=1^mz 1_k_i^t, which upper-bounds regret against ϕt⋆∈ _t . Let git:=kitg_i^t:=1_k_i^t and let ℓt:=∑i=1mgit ^t:= _i=1^mg_i^t. Therefore, by Lemma A.3, for tasks t∈[T]t∈[T], ∑t=1T∑i=1m⟨git,(z¯i)t−zt⋆⟩ _t=1^T _i=1^m g_i^t,( z_i)^t-z_t ≤∑t=1Tbtm+∑t=1T∑i=1m⟨git,(z¯i)t−OPTbt(ℓt)⟩. _t=1^Tb_tm+ _t=1^T _i=1^m g_i^t,( z_i)^t-OPT_b^t( ^t) . (13) By unbiasedness of CTOMD’s estimator, [ℓ~it∣(z¯i)t]=gitE[ _i^t ( z_i)^t]=g_i^t, and OPTb(ℓt)OPT_b( ^t) is deterministic given the adversary’s losses, hence ⟨git,(z¯i)t−OPTb(ℓt)⟩=⟨ℓ~it,(z¯i)t−OPTb(ℓt)⟩.E\, g_i^t,( z_i)^t-OPT_b( ^t) =E\, _i^t,( z_i)^t-OPT_b( ^t) . Summing over i and t and using ℓ^t=∑i=1mℓ~it ^t= _i=1^m _i^t gives ∑i=1m⟨ℓ~it,(z¯i)t−OPTb(ℓt)⟩=[∑i=1m⟨ℓ~it,(z¯i)t⟩−⟨ℓ^t,OPTb(ℓt)⟩]≤[∑i=1m⟨ℓ~it,(z¯i)t⟩−⟨ℓ^t,OPTb(ℓ^t)⟩],E _i=1^m _i^t,( z_i)^t-OPT_b( ^t) =E [ _i=1^m _i^t,( z_i)^t - ^t,OPT_b( ^t) ] [ _i=1^m _i^t,( z_i)^t - ^t,OPT_b( ^t) ], since OPTb(ℓ^t)OPT_b( ^t) minimizes ⟨ℓ^t,⋅⟩ ^t,· over ν¯b ν_b. Thus, ∑t=1T∑i=1m⟨git,(z¯i)t−OPTb(ℓt)⟩≤∑t=1T∑i=1m⟨ℓ~it,(z¯i)t−OPTb(ℓ^t)⟩.E _t=1^T _i=1^m g_i^t,( z_i)^t-OPT_b( ^t) _t=1^T _i=1^m _i^t,( z_i)^t-OPT_b( ^t) . (14) Condition on the hyperparameter gt=(ηt,bt)g^t=(η^t,b^t) sampled by the meta-learner on task t and on the initialization z1tz^t_1 it provides. Applying (8 and 10) with comparator u=OPTb(ℓ^t)∈νbu=OPT_b( ^t)∈ _b yields ∑i=1m⟨ℓ~it,(z¯i)t−OPTb(ℓ^t)⟩≤Dℛ(OPTb(ℓ^t)∥z1t)ηt+32K2ηtm. _i=1^m _i^t,( z_i)^t-OPT_b( ^t) ≤ D_R(OPT_b( ^t)\|z^t_1) _t+32K^2 _tm. Combining with (13)–(14) gives ∑t=1T∑i=1m⟨git,(z¯i)t−zt⋆⟩≤∑t=1T[Dℛ(OPTb(ℓ^t)∥z1t)ηt+(32K2ηt+bt)m].E _t=1^T _i=1^m g_i^t,( z_i)^t-z_t _t=1^T [ D_R(OPT_b( ^t)\|z^t_1) _t+(32K^2 _t+b_t)m ]. (15) Define the meta-loss for g=(η,b)∈Gg=(η,b)∈ G and z∈ν¯z∈ ν by Ut(z,g):=Dℛ(OPTb(ℓ^t)∥z)η+(32K2η+b)m.U_t(z,g):= D_R(OPT_b( ^t)\|z)η+(32K^2η+b)m. It can be seen that Algorithm 6 is exactly the algorithm stated in Balcan et al. (2022) specialized to BLO setting with no β updates. So, we may apply Balcan et al., 2022, Thm. 3.1 with the BLO constants determined as; d←K,G←4K2,D←Db¯,S←Sb¯,K←,M←1.d← K,\;G← 4K 2,\;D← D_ b,\;S← S_ b,\;K← K,\;M← 1. With the same discretization size k as in Balcan et al., 2022, Thm. 5.1, this yields inequality (11) after dividing by T. Now, fixing b and z, let Ab(z):=[1T∑t=1TDℛ(OPTb(ℓ^t)∥z)].A_b(z):=E\! [ 1T _t=1^TD_R(OPT_b( ^t)\|z) ]. Then, minη>0Ab(z)η+32K2ηm=232KmAb(z)=4K2mAb(z). _η>0 \ A_b(z)η+32K^2η m \=2 32\,K mA_b(z)=4K 2m\, A_b(z). Minimizing over z∈ν¯z∈ ν gives Ab(z)=V^b A_b(z)= V_b, proving (12). The asymptotic statement follows as the leading O~(⋅) O(·) term is oT(1)o_T(1). ∎ Appendix B Markov Persuasion Processes As discussed earlier, the relevant task-dependent parameters of the repeated games are drawn from distributions supported on [0,1][0,1], with across-task means PG(⋅∣x,ω,a)P_G(· x,ω,a), μG(⋅∣x) _G(· x), uGs(x,ω,a)u_G^s(x,ω,a), and uGr(x,ω,a)u_G^r(x,ω,a) for each x∈Xx∈ X, ω∈Ωω∈ , and a∈Aa∈ A, together with their corresponding variances. Additionally, we assume that all tasks have the same state, outcome, and action-space cardinalities. For clarity, let Ψ denote a uniform upper bound on the ℓ1 _1-deviation of a single task draw from its across-task mean, namely Ψ>ΨP,Ψμ,Ψus,Ψur. > _P, _μ, _u^s, _u^r. B.1 Confidence Bounds for Meta-Estimators The estimated probability of transitioning from x∈Xx∈ X to x′∈Xx ∈ X by taking action a∈Aa∈ A, when the realized outcome in state x is ω∈Ωω∈ , based on the estimations from previous tasks, is given by P^it(x′∣x,ω,a):=wκP(Nit(x,ω,a))Nit(x,ω,a,x′)max1,Nit(x,ω,a)+w¯κP(Nit(x,ω,a))P¯Gt−1(x′∣x,ω,a). P_i^t(x x,ω,a):=w_ _P\! (N_i^t(x,ω,a) )\, N_i^t(x,ω,a,x ) \1,N_i^t(x,ω,a)\+ w_ _P\! (N_i^t(x,ω,a) )\, P_G^\,t-1(x x,ω,a). where we define P¯Gt−1(x′∣x,ω,a):=1max1,Mt−1(x,ω,a)∑τ=1t−1Nmτ(x,ω,a)>0Nmτ(x,ω,a,x′)max1,Nmτ(x,ω,a). P_G^\,t-1(x x,ω,a):= 1 \1,M_t-1(x,ω,a)\ _τ=1^t-11\N_m^τ(x,ω,a)>0\\, N_m^τ(x,ω,a,x ) \1,N_m^τ(x,ω,a)\. Lemma B.1. Given any δ∈(0,1)δ∈(0,1), with probability at least 1−2δ1-2δ, the following inequality holds for every x∈Xx∈ X, ω∈Ωω∈ , a∈Aa∈ A, i∈[m]i∈[m], and t∈[T]t∈[T] jointly: ||Pt(.|x,ω,a)−P^it(.|x,ω,a)||1≤ϵit(x,ω,a)||P^t(.|x,ω,a)- P_i^t(.|x,ω,a)||_1≤ _i^t(x,ω,a) where ϵit(x,ω,a):=wκ(Nit(x,ω,a))2|Xk(x)+1|ln(m|X||Ω||A|δ)max1,Nit(x,ω,a)+w¯κ(Nit(x,ω,a))[2|Xk(x)+1|ln(|X||Ω||A|Tδ)max1,Mt−1(x,ω,a)+Ψ]. _i^t(x,ω,a)\!:=\!w_κ\! (N_i^t(x,\!ω,\!a) )\! 2|X_k(x)+1| \! (\! m|X|| ||A|δ ) \1,N_i^t(x,ω,a)\+ w_κ\! (N_i^t(x,\!ω,\!a) )\!\! [\! \!2|X_k(x)+1| \! (\! |X|| ||A|Tδ )\! \1,M_t-1(x,ω,a)\\!+\! \! ]. Proof. ∥Pt(⋅∣x,ω,a)−P^it(⋅∣x,ω,a)∥1 P^t(· x,ω,a)- P_i^t(· x,ω,a) _1 ≤wp∥P¯it(⋅∣x,ω,a)−Pt(⋅∣x,ω,a)∥1 ≤ w_p P_i^t(· x,ω,a)-P^t(· x,ω,a) _1 +(1−wp)∥P¯Gt−1(⋅∣x,ω,a)−PG(⋅∣x,ω,a)∥1 +(1-w_p) P_G^t-1(· x,ω,a)-P_G(· x,ω,a) _1 +(1−wp)∥Pt(⋅∣x,ω,a)−PG(⋅∣x,ω,a)∥1. +(1-w_p) P^t(· x,ω,a)-P_G(· x,ω,a) _1. We bound the first term by using the Eq.44 in Auer et al. (2008) and employing a union bound over all x, ω, a, and i. The second term is bounded using the same inequality and a union bound over all x ω,a and t, and third term is straightforward from ΨP≤Ψ _P≤ . ∎ Next, we introduce confidence bounds for prior distributions. For every state x∈Xx∈ X, we define μ^it(.|x)∈Δ(Ω) μ_i^t(.|x)∈ ( ) as the estimator of the prior distribution at x built by using observations up to episode i∈[m]i∈[m] and task t∈[T]t∈[T]. Formally, the entries of vector μ^it(.|x) μ_i^t(.|x) are such that, for every ω∈Ωω∈ : μ^it(ω∣x):=wκμ(Nit(x))∑j=1i−1xjt=x,ωjt=ωmax1,Nit(x)+w¯κμ(Nit(x))μ¯Gt−1(ω∣x), μ_i^t(ω x):=w_ _μ\! (N_i^t(x) )\, _j=1^i-11\x_j^t=x,\ _j^t=ω\ \1,N_i^t(x)\+ w_ _μ\! (N_i^t(x) )\, μ_G^\,t-1(ω x), where we define, μ¯Gt−1(ω∣x):=1max1,Mt−1(x)∑τ=1t−1Nmτ(x)>0∑j=1mxjτ=x,ωjτ=ωmax1,Nmτ(x). μ_G^\,t-1(ω x):= 1 \1,M_t-1(x)\ _τ=1^t-11\N_m^τ(x)>0\\, _j=1^m1\x_j^τ=x,\ _j^τ=ω\ \1,N_m^τ(x)\. Lemma B.2. Given any δ∈(0,1)δ∈(0,1), with probability at least 1−2δ1-2δ, the following inequality holds for every x∈Xx∈ X, i∈[m]i∈[m], and t∈[T]t∈[T] jointly: ||μt(.|x)−μ^it(.|x)||1≤ζit(x)||μ^t(.|x)- μ_i^t(.|x)||_1≤ _i^t(x) where ζit(x):=wκ(Nit(x))2|Ω|ln(m|X|/δ)max1,Nit(x)+w¯κ(Nit(x))(2|Ω|ln(|X|T/δ)max1,Mt−1(x)+Ψ). _i^t(x):=w_κ\! (N_i^t(x) ) 2| | \! (m|X|/δ ) \1,N_i^t(x)\+ w_κ\! (N_i^t(x) ) ( 2| | \! (|X|T/δ ) \1,M_t-1(x)\+ ). Proof. The proof follows the lines in the proof of Lemma B.1. This time, we union bound the first term over all x and i, and second term over all x and t, where separate events have the cardinality of |Ω|| |. The third term follows from Ψμ≤Ψ _μ≤ . ∎ Finally, we introduce our estimators for the reward functions of the sender and the receiver types. In the following, we present the results related to the sender’s and receiver types’ rewards under both full and partial feedback. First, for every x∈Xx∈ X, ω∈Ωω∈ , and a∈Aa∈ A, the estimated sender and receiver rewards for the full feedback case is, constructed using observations up to episode i∈[m]i∈[m] in task t∈[T]t∈[T], are defined as follows: u^is,t(x,ω,a):=wκus(Nit(x,ω))∑j=1i−1ujs,t(x,ω,a)xjt=x,ωjt=ωmax1,Nit(x,ω)+w¯κus(Nit(x,ω))u¯Gs,t−1(x,ω,a)\! u_i^s,t(x,\!ω,\!a)\!\!:=\!w_ _u^s\! (\!N_i^t(x,ω) ) \! _j=1^i-1\!u_j^s,t(x,\!ω,a)\,\!1\x_j^t\!=\!x, _j^t\!=\!ω\\!\! \1,N_i^t(x,ω)\+ w_ _u^s\! (\!N_i^t(x,\!ω) ) u_G^s,t-1\!(x,\!ω,\!a) u^ir,t(x,ω,a):=wκur(Nit(x,ω))∑j=1i−1ujr,t(x,ω,a)xjt=x,ωjt=ωmax1,Nit(x,ω)+w¯κur(Nit(x,ω))u¯Gr,t−1(x,ω,a)\! u_i^r,t(x,\!ω,\!a)\!\!:=\!w_ _u^r\! (\!N_i^t(x,ω) ) \! _j=1^i-1\!u_j^r,t(x,\!ω,\!a\!)\,\!1\x_j^t\!=\!x, _j^t\!=\!ω\\!\! \1,N_i^t(x,ω)\+ w_ _u^r\! (\!N_i^t(x,\!ω) ) u_G^r,t-1\!(x,\!ω,\!a) where, u¯Gs,t−1(x,ω,a):=1max1,Mt−1(x,ω)∑τ=1t−1Nmτ(x,ω)>0∑j=1mujs,τ(x,ω,a)xjτ=x,ωjτ=ωmax1,Nmτ(x,ω), u_G^s,t-1(x,ω,a)\!:=\! 1 \1,M_t-1(x,ω)\ _τ=1^t-11\N_m^τ(x,ω)>0\ _j=1^m\!u_j^s,τ(x,ω,a)1\x_j^τ=x, _j^τ=ω\ \1,N_m^τ(x,ω)\, and receiver types’ estimators are defined analogously. Secondly, for every x∈Xx∈ X, ω∈Ωω∈ , and a∈Aa∈ A, the estimated sender and receiver rewards for the partial feedback case is, constructed using observations up to episode i∈[m]i∈[m] in task t∈[T]t∈[T], are defined as follows: u^is,t(x,ω,a):=wκus(Nit(x,ω,a))∑j=1i−1ujs,t(x,ω,a)xjt=x,ωjt=ω,ajt=amax1,Nit(x,ω,a)+w¯κus(Nit(x,ω,a))u¯Gs,t−1(x,ω,a)\! u_i^s,t(x,\!ω,\!a)\!\!:=\!w_ _u^s\! (\!N_i^t(x,ω,a) ) \! _j=1^i-1\!u_j^s,t(x,\!ω,\!a\!)\,\!1\x_j^t\!=\!x, _j^t\!=\!ω,a_j^t\!=\!a\!\\!\! \1,N_i^t(x,ω,a)\+ w_ _u^s\! (\!N_i^t(x,\!ω,\!a) ) u_G^s,t-1\!(x,\!ω,\!a) u^ir,t(x,ω,a):=wκur(Nit(x,ω,a))∑j=1i−1ujr,t(x,ω,a)xjt=x,ωjt=ω,ajt=amax1,Nit(x,ω,a)+w¯κur(Nit(x,ω,a))u¯Gr,t−1(x,ω,a)\! u_i^r,t(x,\!ω,\!a)\!\!:=\!w_ _u^r\! (\!N_i^t(x,ω,a) ) \! _j=1^i-1\!u_j^r,t(x,\!ω,\!a\!)\,\!1\x_j^t\!=\!x, _j^t\!=\!ω,a_j^t\!=\!a\!\\!\! \1,N_i^t(x,ω,a)\+ w_ _u^r\! (\!N_i^t(x,\!ω,\!a) ) u_G^r,t-1\!(x,\!ω,\!a) where, u¯Gs,t−1(x,ω,a):=1max1,Mt−1(x,ω,a)∑τ=1t−1Nmτ(x,ω,a)>0∑j=1mujs,τ(x,ω,a)xjτ=x,ωjτ=ω,ajτ=amax1,Nmτ(x,ω,a), u_G^s,t-1(x,ω,a)\!:=\! 1 \1,M_t-1(x,ω,a)\ _τ=1^t-11\N_m^τ(x,ω,a)>0\ _j=1^m\!u_j^s,τ(x,ω,a)1\x_j^τ=x, _j^τ=ω,a_j^τ=a\ \1,N_m^τ(x,ω,a)\, and receiver types’ estimators are defined analogously. The following lemma establishes confidence bounds on the sender’s rewards under the assumption that full feedback is observed. Lemma B.3. Given any δ∈(0,1)δ∈(0,1), with probability at least 1−2δ1-2δ, the following inequality holds for every x∈Xx∈ X, ω∈Ωω∈ , a∈Aa∈ A, i∈[m]i∈[m], and t∈[T]t∈[T] jointly: |us,t(x,ω,a)−u^is,t(x,ω,a)|≤ξis,t(x,w,a)|u^s,t(x,ω,a)- u_i^s,t(x,ω,a)|≤ _i^s,t(x,w,a) where ξis,t(x,ω,a)≔min1,wκ(Nit(x,ω))ln(3m|X||Ω|/δ)max1,Nit(x,ω)+w¯κ(Nit(x,ω))(ln(3|X||Ω|T)/δ)max1,Mt−1(x,w)+Ψ) _i^s,t(x,ω,a) \1,w_κ\! (N_i^t(x,ω) ) (3m|X|| |/δ) \1,N^t_i(x,ω)\+ w_κ\! (N_i^t(x,ω) )( (3|X|| |T)/δ) \1,M_t-1(x,w)\+ )\ Proof. The proof follows the lines of the proof of Lemma B.1. This time, instead of using Eq.44 in Auer et al. (2008) we use the Hoeffding’s inequality. We then union bound over all x, w and i, and second term over all x, w and t, where separate events have the cardinality of 11. The third term follows from Ψus≤Ψ _u^s≤ . ∎ The following lemma establishes confidence bounds on the receiver’s rewards in the full feedback case. Lemma B.4. Given any δ∈(0,1)δ∈(0,1), with probability at least 1−2δ1-2δ, the following condition holds for every x∈Xx∈ X, ω∈Ωω∈ , a∈Aa∈ A, i∈[m]i∈[m], and t∈[T]t∈[T] jointly: |ur,t(x,ω,a)−u^ir,t(x,ω,a)|≤ξir,t(x,w,a)|u^r,t(x,ω,a)- u_i^r,t(x,ω,a)|≤ _i^r,t(x,w,a) where ξir,t(x,ω,a)≔min1,wκ(Nit(x,ω))ln(3m|X||Ω|/δ)max1,Nit(x,ω)+w¯κ(Nit(x,ω))(ln(3|X||Ω|T)/δ)max1,Mt−1(x,w)+Ψ) _i^r,t(x,ω,a) \1,w_κ\! (N_i^t(x,ω) ) (3m|X|| |/δ) \1,N^t_i(x,ω)\+ w_κ\! (N_i^t(x,ω) )( (3|X|| |T)/δ) \1,M_t-1(x,w)\+ )\ Proof. The proof follows the lines of the proof of Lemma B.1. This time, instead of using the Eq.44 in Auer et al. (2008) we use the Hoeffding’s inequality. We then bound over all x, w and i, and second term over all x, w and t, where separate events have the cardinality of 11. The third term follows from Ψur≤Ψ _u^r≤ . ∎ The following lemma establishes confidence bounds on the sender’s rewards for the partial feedback case. Lemma B.5. Given any δ∈(0,1)δ∈(0,1), with probability at least 1−2δ1-2δ, the following condition holds for every x∈Xx∈ X, ω∈Ωω∈ , a∈Aa∈ A i∈[m]i∈[m] and t∈[T]t∈[T] jointly: |us,t(x,ω,a)−u^is,t(x,ω,a)|≤ξis,t(x,w,a)|u^s,t(x,ω,a)- u_i^s,t(x,ω,a)|≤ _i^s,t(x,w,a) where ξis,t(x,ω,a)≔min1,wκ(Nit(x,ω,a))ln(3m|X||Ω||A|/δ)max1,Nit(x,ω,a)+w¯κ(Nit(x,ω,a))(ln(3|X||Ω||A|T/δ)max1,Mt−1(x,w,a)+Ψ) _i^s,t(x,ω,a)\! \! \1,w_κ\! (N_i^t(x,ω,a) )\! (3m|X|| ||A|/δ) \1,N^t_i(x,ω,a)\+ w_κ\! (N_i^t(x,ω,a) )( (3|X|| ||A|T/δ) \1,M_t-1(x,w,a)\+ )\ Proof. The proof follows the lines of the proof of Lemma B.1. This time, instead of using Eq.44 in Auer et al. (2008) we use the Hoeffding’s inequality. We then union bound over all x, w, a and i, and second term over all x, w, a and t, where separate events have the cardinality of 11. The third term follows from Ψus≤Ψ _u^s≤ . ∎ The following lemma establishes confidence bounds on the receiver’s rewards for the partial feedback case. Lemma B.6. Given any δ∈(0,1)δ∈(0,1), with probability at least 1−2δ1-2δ, the following condition holds for every x∈Xx∈ X, ω∈Ωω∈ , a∈Aa∈ A i∈[m]i∈[m] and t∈[T]t∈[T] jointly: |ur,t(x,ω,a)−u^ir,t(x,ω,a)|≤ξir,t(x,w,a)|u^r,t(x,ω,a)- u_i^r,t(x,ω,a)|≤ _i^r,t(x,w,a) where ξir,t(x,ω,a)≔min1,wκ(Nit(x,ω,a))ln(3m|X||Ω||A|/δ)max1,Nit(x,ω,a)+w¯κ(Nit(x,ω,a))(ln(3|X||Ω||A|T/δ)max1,Mt−1(x,w,a)+Ψ) _i^r,t(x,ω,a) \1,w_κ\! (N_i^t(x,ω,a) ) (3m|X|| ||A|/δ) \1,N^t_i(x,ω,a)\+ w_κ\! (N_i^t(x,ω,a) )( (3|X|| ||A|T/δ) \1,M_t-1(x,w,a)\+ )\ Proof. The proof follows the lines of the proof of Lemma B.1. This time, instead of using Eq.44 in Auer et al. (2008) we use the Hoeffding’s inequality. We then union bound over all x, w, a and i, and second term over all x, w, a and t, where separate events have the cardinality of 11. The third term follows from Ψur≤Ψ _u^r≤ . ∎ Now that we have each estimator well defined, we introduce a generic notation that covers all coordinates used in Appendix B. For the transition coordinates, let P:=X×Ω×A.C_P:=X× × A. For the prior coordinates, let μ:=X.C_μ:=X. For the reward coordinates, let rewff:=X×Ωandrewpf:=X×Ω×A,C_rew^f:=X× \;and\;C_rew^pf:=X× × A, corresponding respectively to the full-feedback and partial-feedback settings. For a coordinate family C and a coordinate c∈c , let Iit(c)I_i^t(c) denote the indicator that coordinate c is observed at episode i of task t. Define the within-task count, terminal task indicator, and active-task count by Nit(c):=∑j=1i−1Ijt(c),Nmt(c):=∑j=1mIjt(c),It(c):=Nmt(c)>0,andMt(c):=∑τ=1tIτ(c).N_i^t(c):= _j=1^i-1I_j^t(c),\;N_m^t(c):= _j=1^mI_j^t(c),\;I_t(c):=1\N_m^t(c)>0\,\;and\;M_t(c):= _τ=1^tI_τ(c). Next, we provide the following two technical lemmas, we have leveraged while proving our regret and violation bounds. Lemma B.7. Define Bm(κ):=1+κln(1+mκ),κ>0,0,κ=0.B_m(κ):= cases1+κ \! (1+ mκ ),&κ>0,\\[5.0pt] 0,&κ=0. cases Then, for every coordinate family C and every c∈c , the following hold: ∑i=1mw¯κ(Nit(c))Iit(c) _i=1^m w_κ\! (N_i^t(c) )\,I_i^t(c) ≤Bm(κ)It(c), ≤ B_m(κ)\,I_t(c), (16) ∑t=1TIt(c)maxMt−1(c),1 _t=1^T I_t(c) \M_t-1(c),1\ ≤2MT(c)+1, ≤ 2 M_T(c)+1, (17) 1T∑t=1T∑i=1mw¯κ(Nit(c))Iit(c)βmaxMt−1(c),1 1T _t=1^T _i=1^m w_κ\! (N_i^t(c) )\,I_i^t(c)\, β \M_t-1(c),1\ ≤2Bm(κ)βT,∀β>0, ≤ 2B_m(κ) βT, ∀β>0, (18) 1T∑t=1T∑i=1mw¯κ(Nit(c))Iit(c)Ψ 1T _t=1^T _i=1^m w_κ\! (N_i^t(c) )\,I_i^t(c)\, ≤Bm(κ)ΨMT(c)T≤Bm(κ)Ψ, ≤ B_m(κ) M_T(c)T≤ B_m(κ) , (19) Proof. If κ=0κ=0, then w¯κ(⋅)≡0 w_κ(·)≡ 0, and thus (16), (18), and (19) are immediate. Assume therefore that κ>0κ>0. We first prove (16). If It(c)=0I_t(c)=0, then the left-hand side is zero. Suppose It(c)=1I_t(c)=1, and let 1≤i1<i2<⋯<int(c)≤m1≤ i_1<i_2<·s<i_n_t(c)≤ m be the episodes of task t at which coordinate c is observed, where nt(c):=Nmt(c)≥1n_t(c):=N_m^t(c)≥ 1. Then, by construction, Nijt(c)=j−1N_i_j^t(c)=j-1 for every j∈[nt(c)]j∈[n_t(c)], and hence ∑i=1mw¯κ(Nit(c))Iit(c)=∑j=1nt(c)κj−1+κ. _i=1^m w_κ\! (N_i^t(c) )\,I_i^t(c)= _j=1^n_t(c) κj-1+κ. Using integral comparison, ∑j=1nt(c)κj−1+κ≤1+∫0nt(c)−1κu+κu=1+κln(1+nt(c)−1κ). _j=1^n_t(c) κj-1+κ≤ 1+ _0^n_t(c)-1 κu+κ\,du=1+κ (1+ n_t(c)-1κ ). Since nt(c)≤mn_t(c)≤ m, we get ∑i=1mw¯κ(Nit(c))Iit(c)≤1+κln(1+mκ)=Bm(κ). _i=1^m w_κ\! (N_i^t(c) )\,I_i^t(c)≤ 1+κ (1+ mκ )=B_m(κ). This proves (16). Next we prove (17). If MT(c)=0M_T(c)=0, the claim is trivial. Otherwise, let 1≤t1<t2<⋯<tMT(c)≤T1≤ t_1<t_2<·s<t_M_T(c)≤ T be the tasks for coordinate c that have been seen. Then Mtj−1(c)=j−1M_t_j-1(c)=j-1 for every j, and therefore ∑t=1TIt(c)maxMt−1(c),1=1+∑j=2MT(c)1j−1≤2+∫0MT(c)−2du+1≤2MT(c)−1≤2MT(c)+1. _t=1^T I_t(c) \M_t-1(c),1\=1+ _j=2^M_T(c) 1 j-1≤ 2+ _0^M_T(c)-2 du u+1≤ 2 M_T(c)-1≤ 2 M_T(c)+1. This proves (17). To prove (18), combine (16) and (17): 1T∑t=1T∑i=1mw¯κ(Nit(c))Iit(c)βmaxMt−1(c),1≤Bm(κ)βT∑t=1TIt(c)maxMt−1(c),1 1T _t=1^T _i=1^m w_κ\! (N_i^t(c) )\,I_i^t(c)\, β \M_t-1(c),1\≤ B_m(κ) βT _t=1^T I_t(c) \M_t-1(c),1\ ≤2Bm(κ)βTMT(c)−1≤2Bm(κ)βT,≤ 2B_m(κ) βT M_T(c)-1≤ 2B_m(κ) βT, since MT(c)≤TM_T(c)≤ T. For (19), again using (16), 1T∑t=1T∑i=1mw¯κ(Nit(c))Iit(c)Ψ≤Bm(κ)ΨT∑t=1TIt(c)=Bm(κ)ΨMT(c)T≤Bm(κ)Ψ. 1T _t=1^T _i=1^m w_κ\! (N_i^t(c) )\,I_i^t(c)\, ≤ B_m(κ) T _t=1^TI_t(c)=B_m(κ) M_T(c)T≤ B_m(κ) . ∎ Lemma B.8. For every c∈Cc∈ C and every task t∈[T]t∈[T], the following holds: ∑i=1mwκ(Nit(c))Iit(c)max1,Nit(c)≤2Nmt(c)Nmt(c)+κ, _i=1^mw_κ\! (N_i^t(c) )\, I_i^t(c) \1,N_i^t(c)\\;≤\; 2N_m^t(c) N_m^t(c)+ κ, (20) with the convention that the right-hand side equals 0 when Nmt(c)=0=κN_m^t(c)=0=κ. More generally, for every finite subset D⊆CD C, if St(D):=∑c∈DNmt(c),S_t(D):= _c∈ DN_m^t(c), then ∑c∈D∑i=1mwκ(Nit(c))Iit(c)max1,Nit(c)≤2St(D)|D|St(D)+κ|D|, _c∈ D _i=1^mw_κ\! (N_i^t(c) )\, I_i^t(c) \1,N_i^t(c)\\;≤\; 2S_t(D) |D| S_t(D)+ κ|D|, (21) again with the convention that the right-hand side equals 0 when St(D)=0=κS_t(D)=0=κ. Proof. We first prove (20). If Nmt(c)=0N_m^t(c)=0, then the left-hand side is zero, so there is nothing to show. Assume Nmt(c)=n≥1N_m^t(c)=n≥ 1, and let 1≤i1<⋯<in≤m1≤ i_1<·s<i_n≤ m be the episodes in which c is observed. Then Nijt(c)=j−1N_i_j^t(c)=j-1, so ∑i=1mwκ(Nit(c))Iit(c)max1,Nit(c)=∑j=1nwκ(j−1)1max1,j−1. _i=1^mw_κ\! (N_i^t(c) )\, I_i^t(c) \1,N_i^t(c)\= _j=1^nw_κ(j-1)\, 1 \1,j-1\. Case 1: κ=0κ=0. Then w0(⋅)≡1w_0(·)≡ 1, hence ∑j=1nw0(j−1)1max1,j−1=1+∑j=2n1j−1=1+∑u=1n−11u. _j=1^nw_0(j-1)\, 1 \1,j-1\=1+ _j=2^n 1 j-1=1+ _u=1^n-1 1 u. Using integral comparison, 1+∑u=1n−11u≤2+∫0n−1du+1=2n=2n+0.1+ _u=1^n-1 1 u≤ 2+ _0^n-1 du u+1=2 n= 2n n+ 0. Case 2: κ>0κ>0. Then wκ(0)=0w_κ(0)=0, so the first term vanishes and ∑j=1nwκ(j−1)1max1,j−1=∑j=2nj−1j−1+κ⋅1j−1=∑u=1n−1u+κ. _j=1^nw_κ(j-1)\, 1 \1,j-1\= _j=2^n j-1j-1+κ· 1 j-1= _u=1^n-1 uu+κ. Then, we have the following inequality for this case u+κ≤2u+κ+u−1+κ=2(u+κ−u−1+κ),∀u≥1. uu+κ≤ 2 u+κ+ u-1+κ=2 ( u+κ- u-1+κ ), ∀ u≥ 1. Therefore, ∑u=1n−1u+κ≤2∑u=1n−1(u+κ−u−1+κ)=2(n−1+κ−κ). _u=1^n-1 uu+κ≤ 2 _u=1^n-1 ( u+κ- u-1+κ )=2 ( n-1+κ- κ ). Since the map x↦x/(x+κ)x x/( x+ κ) is increasing on [0,∞)[0,∞), 2(n−1+κ−κ)=2(n−1)n−1+κ+κ≤2n+κ.2 ( n-1+κ- κ )= 2(n-1) n-1+κ+ κ≤ 2n n+ κ. Hence, ∑u=1n−1u+κ≤2n+κ. _u=1^n-1 uu+κ≤ 2n n+ κ. Therefore, ∑i=1mwκ(Nit(c))Iit(c)max1,Nit(c)≤2n+κ, _i=1^mw_κ\! (N_i^t(c) )\, I_i^t(c) \1,N_i^t(c)\≤ 2n n+ κ, which proves (20). We now prove (21). Define ga(x):=x+a,x≥0,a≥0.g_a(x):= x x+a, x≥ 0,\ a≥ 0. A direct computation gives ga′(x)=−x+3a4x(x+a)3≤0∀x>0,g_a (x)=- x+3a4 x\,( x+a)^3≤ 0 ∀ x>0, and hence gag_a is concave on [0,∞)[0,∞). Applying (20) coordinate-wise and then Jensen’s inequality, ∑c∈D∑i=1mwκ(Nit(c))Iit(c)max1,Nit(c)≤2∑c∈Dgκ(Nmt(c)) _c∈ D _i=1^mw_κ\! (N_i^t(c) )\, I_i^t(c) \1,N_i^t(c)\≤ 2 _c∈ Dg_ κ\! (N_m^t(c) ) ≤2|D|gκ(1|D|∑c∈DNmt(c))=2St(D)|D|St(D)+κ|D|,≤ 2|D|\,g_ κ\! ( 1|D| _c∈ DN_m^t(c) )= 2S_t(D) |D| S_t(D)+ κ|D|, which proves (21). ∎ B.2 Meta-Opt-Opt The difference between Meta-Opt-Opt and Opt-Opt in (Bacchiocchi et al., 2025) is that we employ meta-estimators and, consequently, meta confidence bounds within the algorithm. In particular, Appendix C, Lemma 2 of Bacchiocchi et al. (2025) implies that, for any δ∈(0,1)δ∈(0,1), under the good event ℰ(δ)E(δ), Meta-Opt-Opt admits a feasible solution for every i∈[m]i∈[m] and every task t∈[T]t∈[T]. The Meta-Opt-Opt procedure, executed at each iteration i∈[m]i∈[m] and for each task t∈[T]t∈[T], is as follows: maxqt,ζt,ϵt _q^t,ζ^t,ε^t ∑x∈Xk∑ω∈Ω∑a∈A∑x′∈Xk+1qt(x,ω,a,x′)(u^is,t(x,ω,a)+ξis,t(x,ω,a))s.t. _x∈ X_k _ω∈ _a∈ A _x ∈ X_k+1q^t(x,ω,a,x ) ( u_i^s,t(x,ω,a)+ _i^s,t(x,ω,a) ) .t. (2a) ∑x∈Xk∑ω∈Ω∑a∈A∑x′∈Xk+1qt(x,ω,a,x′)=1∀k∈[0…L−1] \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! _x∈ X_k _ω∈ _a∈ A _x ∈ X_k+1q^t(x,ω,a,x )=1 ∀ k∈[0… L-1] (2b) ∑x′∈Xk−1∑ω∈Ω∑a∈Aqt(x′,ω,a,x)=∑ω∈Ω∑a∈A∑x′∈Xk+1qt(x,ω,a,x′)∀k∈[0…L−1],∀x∈Xk \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! _x ∈ X_k-1 _ω∈ _a∈ Aq^t(x ,ω,a,x)= _ω∈ _a∈ A _x ∈ X_k+1q^t(x,ω,a,x ) \;∀ k∈[0… L-1],\ ∀ x∈ X_k (2c) qt(x,ω,a,x′)−P^it(x′|x,ω,a)∑x′∈Xk+1qt(x,ω,a,x′)]≤ϵt(x,ω,a,x′) \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!q^t(x,ω,a,x )- P^t_i(x |x,ω,a)\!\!\!\!\! _x ∈ X_k+1\!\!\!\!q^t(x,ω,a,x )]≤ε^t(x,ω,a,x ) ∀k∈[0…L−1],∀(x,ω,a,x′)∈Xk×Ω×A×Xk+1 \;\;∀ k∈[0… L-1],\ ∀(x,ω,a,x )∈ X_k× × A× X_k+1 (2d) P^it(x′|x,a,ω)∑x′∈Xk+1qt(x,ω,a,x′)−qt(x,ω,a,x′)≤ϵt(x,ω,a,x′) \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! P^t_i(x |x,a,ω) _x ∈ X_k+1q^t(x,ω,a,x )-q^t(x,ω,a,x )≤ε^t(x,ω,a,x ) ∀k∈[0…L−1],∀(x,ω,a,x′)∈Xk×Ω×A×Xk+1 \;\;∀ k∈[0… L-1],\ ∀(x,ω,a,x )∈ X_k× × A× X_k+1 (2e) ∑x′∈Xk+1ϵt(x,ω,a,x′)≤ϵit(x,ω,a)∑x′∈Xk+1qt(x,ω,a,x′)∀k∈[0…L−1],∀(x,ω,a)∈Xk×Ω×A \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! _x ∈ X_k+1\!\!\!\!\!ε^t(x,ω,a,x )\!≤\!ε^t_i(x,ω,a)\!\!\!\! _x ∈ X_k+1\!\!\!\!q^t(x,ω,a,x ) \;∀ k∈[0… L-1],\ ∀(x,ω,a)∈ X_k× × A (2f) qt(x,ω)−μ^it(ω|x)∑ω′∈Ωqt(x,ω′)≤ζt(x,ω)∀k∈[0…L−1],∀(x,ω)∈Xk×Ω \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!q^t(x,ω)- μ^t_i(ω|x) _ω ∈ q^t(x,ω )≤ζ^t(x,ω) \;\;\;\;\;∀ k∈[0… L-1],\ ∀(x,ω)∈ X_k× (2g) μ^it(ω|x)∑ω′∈Ωqt(x,ω′)−qt(x,ω)≤ζt(x,ω)∀k∈[0…L−1],∀(x,ω)∈Xk×Ω \!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! μ^t_i(ω|x) _ω ∈ q^t(x,ω )-q^t(x,ω)≤ζ^t(x,ω) \;\;\;\;\;∀ k∈[0… L-1],\ ∀(x,ω)∈ X_k× (2h) ∑ω∈Ωζt(x,ω)≤ζit(x)∑ω∈Ωqt(x,ω)∀k∈[0…L−1],∀x∈Xk \!\!\!\! _ω∈ ζ^t(x,ω)≤ζ^t_i(x) _ω∈ q^t(x,ω) ∀ k∈[0… L-1],\ ∀ x∈ X_k (2i) ∑ω∈Ω∑x′∈Xk+1qt(x,ω,a,x′)(u^ir,t(x,ω,a)+ξir,t(x,ω,a)−u^ir,t(x,ω,a′)+ξir,t(x,ω,a′))≥0 \!\!\!\! _ω∈ _x ∈ X_k+1q^t(x,ω,a,x ) ( u_i^r,t(x,ω,a)+ _i^r,t(x,ω,a)- u_i^r,t(x,ω,a )+ _i^r,t(x,ω,a ) )≥ 0 ∀k∈[0…L−1],∀(x,a)∈Xk×A,∀a′∈A ∀ k∈[0… L-1],\ ∀(x,a)∈ X_k× A,\ ∀ a ∈ A (2j) qt(x,ω,a,x′)≥0∀k∈[0…L−1],∀(x,ω,a,x′)∈Xk×Ω×A×Xk+1 \!\!\!q^t(x,ω,a,x )≥ 0 ∀ k∈[0… L-1],\ ∀(x,ω,a,x )∈ X_k× × A× X_k+1 (2k) B.2.1 Occupancy Measure Bounds We begin by showing that the estimated occupancy measures, concentrate around the true occupancy measures, as both definitions of regret and violation in our setting directly leverage this quantity. Lemma B.9. Fix δ∈(0,1)δ∈(0,1) and assume that the good event ℰ(δ)E(δ) holds. Then, with probability at least 1−2δ1-2δ, 1T∑t=1T∑i∈[m]∥qit−q^it∥1≤( 1T _t=1^T _i∈[m] q_i^t- q_i^t _1\;≤\;O ( L2m+κ|X||Ω||A||X|m|Ω||A|ln(m|X||Ω||A|δ)). L^2 m m+ κ|X|| ||A|\;|X| m| ||A| ( m|X|| ||A|δ ) ). Proof. Let ℓP:=ln(m|X||Ω||A|δ),ℓμ:=ln(m|X|δ), _P:= ( m|X|| ||A|δ ), _μ:= ( m|X|δ ), and βP:=2|X|ln(|X||Ω||A|Tδ),βμ:=2|Ω|ln(|X|Tδ) _P:=2|X| ( |X|| ||A|Tδ ), _μ:=2| | ( |X|Tδ ). Write for c=(x,ω,a)∈Pc=(x,ω,a) _P and d=x∈μd=x _μ, ϵit(c)=ϵi,wt(c)+ϵi,mt(c),ζit(d)=ζi,wt(d)+ζi,mt(d), _i^t(c)= _i,w^t(c)+ _i,m^t(c), _i^t(d)= _i,w^t(d)+ _i,m^t(d), where ϵi,wt(c):=wκ(Nit(c))2|Xk(x)+1|ℓPmax1,Nit(c),ϵi,mt(c):=w¯κ(Nit(c))(βPmaxMt−1(c),1+Ψ), _i,w^t(c):=w_κ\! (N_i^t(c) ) 2|X_k(x)+1|\, _P \1,N_i^t(c)\, _i,m^t(c):= w_κ\! (N_i^t(c) ) ( _P \M_t-1(c),1\+ ), and ζi,wt(d):=wκ(Nit(d))2|Ω|ℓμmax1,Nit(d),ζi,mt(d):=w¯κ(Nit(d))(βμMt−1(d)∨1+Ψ). _i,w^t(d):=w_κ\! (N_i^t(d) ) 2| |\, _μ \1,N_i^t(d)\, _i,m^t(d):= w_κ\! (N_i^t(d) ) ( _μM_t-1(d) 1+ ). From Appendix D, Lemma 3 in (Bacchiocchi et al., 2025) we have with probability at least 1−2δ1-2δ, 1T∑t=1T∑i=1m‖qit−q^it‖1≤2LT∑c∈P∑t=1T∑i=1mϵit(c)Iit(c)+LT∑d∈μ∑t=1T∑i=1mζit(d)Iit(d)+4L|X|2mln(Lδ). 1T _t=1^T _i=1^m\|q_i^t- q_i^t\|_1≤ 2LT _c _P _t=1^T _i=1^m _i^t(c)\,I_i^t(c)+ LT _d _μ _t=1^T _i=1^m _i^t(d)\,I_i^t(d)+4L|X| 2m ( Lδ ). (22) Thus it remains to control the transition and prior contributions. Fix a task t and a layer s∈0,…,L−1s∈\0,…,L-1\. Let sP:=Xs×Ω×A.D_s^P:=X_s× × A. Then, by Lemma B.8, ∑c∈sP∑i=1mϵi,wt(c)Iit(c) _c _s^P _i=1^m _i,w^t(c)\,I_i^t(c) ≤2|X|ℓP∑c∈sP∑i=1mNit(c)Nit(c)+κIit(c)max1,Nit(c) ≤ 2|X|\, _P _c _s^P _i=1^m N_i^t(c)N_i^t(c)+κ I_i^t(c) \1,N_i^t(c)\ ≤2|X|ℓP⋅2St(sP)|sP|St(sP)+κ|sP|. ≤ 2|X|\, _P· 2S_t(D_s^P) |D_s^P| S_t(D_s^P)+ κ|D_s^P|. Since in a loop-free MPP each episode visits at most one triplet in a fixed layer, we have St(sP)≤m,S_t(D_s^P)≤ m, and it follows that |sP|=|Xs||Ω||A|≤|X||Ω||A|.|D_s^P|=|X_s|| ||A|≤|X|| ||A|. Hence ∑c∈sP∑i=1mϵi,wt(c)Iit(c)≤2m+κ|X||Ω||A||Xs|2m|Ω||A|ℓP. _c _s^P _i=1^m _i,w^t(c)\,I_i^t(c)≤ 2 m m+ κ|X|| ||A|\,|X_s| 2m| ||A|\, _P. Summing over at most L preceding layers inside each k-sum and then over k=0,…,L−1k=0,…,L-1 yields 2LT∑c∈P∑t=1T∑i=1mϵi,wt(c)Iit(c)≤4L2m+κ|X||Ω||A||X|2m|Ω||A|ℓP. 2LT _c _P _t=1^T _i=1^m _i,w^t(c)\,I_i^t(c)≤ 4L^2 m m+ κ|X|| ||A|\,|X| 2m| ||A|\, _P. (23) Next we treat the within-task prior contribution. For a fixed layer s, let sμ:=Xs.D_s^μ:=X_s. Applying Lemma B.8 again, ∑d∈sμ∑i=1mζi,wt(d)Iit(d)≤2|Ω|ℓμ⋅2St(sμ)|sμ|St(sμ)+κ|sμ|. _d _s^μ _i=1^m _i,w^t(d)\,I_i^t(d)≤ 2| |\, _μ· 2S_t(D_s^μ) |D_s^μ| S_t(D_s^μ)+ κ|D_s^μ|. Since each episode visits at most one state in a fixed layer, St(sμ)≤m,|sμ|=|Xs|≤|X|.S_t(D_s^μ)≤ m,\;|D_s^μ|=|X_s|≤|X|. Therefore ∑d∈sμ∑i=1mζi,wt(d)Iit(d)≤2m+κ|X|2m|Xs||Ω|ℓμ. _d _s^μ _i=1^m _i,w^t(d)\,I_i^t(d)≤ 2 m m+ κ|X| 2m|X_s|| |\, _μ. Summing over the at most L preceding layers and then over k=0,…,L−1k=0,…,L-1 gives LT∑d∈μ∑t=1T∑i=1mζi,wt(d)Iit(d)≤2L2m+κ|X|2m|X||Ω|ℓμ. LT _d _μ _t=1^T _i=1^m _i,w^t(d)\,I_i^t(d)≤ 2L^2 m m+ κ|X| 2m|X|| |\, _μ. (24) By Lemma B.7, 2LT∑c∈P∑t=1T∑i=1mϵi,mt(c)Iit(c) 2LT _c _P _t=1^T _i=1^m _i,m^t(c)\,I_i^t(c) ≤2LT∑c∈P∑t=1T∑i=1mκNit(c)+κIit(c)βPmaxMt−1(c),1 ≤ 2LT _c _P _t=1^T _i=1^m κN_i^t(c)+κ\,I_i^t(c) _P \M_t-1(c),1\ +2LΨT∑c∈P∑t=1T∑i=1mκNit(c)+κIit(c) + 2L T _c _P _t=1^T _i=1^m κN_i^t(c)+κ\,I_i^t(c) ≤4L|P|Bm(κ)βPT+2LBm(κ)ΨT∑c∈PMT(c). ≤ 4L|C_P|\,B_m(κ) _PT+ 2LB_m(κ) T _c _PM_T(c). Since |P|=|X||Ω||A||C_P|=|X|| ||A|, this becomes 2LT∑c∈P∑t=1T∑i=1mϵi,mt(c)Iit(c)≤4L|X||Ω||A|Bm(κ)βPT+2LBm(κ)ΨT∑c∈PMT(c). 2LT _c _P _t=1^T _i=1^m _i,m^t(c)\,I_i^t(c)≤ 4L|X|| ||A|\,B_m(κ) _PT+ 2LB_m(κ) T _c _PM_T(c). (25) Again by Lemma B.7, LT∑d∈μ∑t=1T∑i=1mζi,mt(d)Iit(d) LT _d _μ _t=1^T _i=1^m _i,m^t(d)\,I_i^t(d) ≤LT∑d∈μ∑t=1T∑i=1mκNit(d)+κIit(d)βμMt−1(d)∨1 ≤ LT _d _μ _t=1^T _i=1^m κN_i^t(d)+κ\,I_i^t(d) _μM_t-1(d) 1 +LΨT∑d∈μ∑t=1T∑i=1mκNit(d)+κIit(d) + L T _d _μ _t=1^T _i=1^m κN_i^t(d)+κ\,I_i^t(d) ≤2L|μ|Bm(κ)βμT+LBm(κ)ΨT∑d∈μMT(d). ≤ 2L|C_μ|\,B_m(κ) _μT+ LB_m(κ) T _d _μM_T(d). Since |μ|=|X||C_μ|=|X|, this becomes LT∑d∈μ∑t=1T∑i=1mζi,mt(d)Iit(d)≤2L|X|Bm(κ)βμT+LBm(κ)ΨT∑d∈μMT(d). LT _d _μ _t=1^T _i=1^m _i,m^t(d)\,I_i^t(d)≤ 2L|X|\,B_m(κ) _μT+ LB_m(κ) T _d _μM_T(d). (26) Substituting (23), (24), (25), and (26) into (22) yields 1T∑t=1T∑i=1m‖qit−q^it‖1≤Cocc(m,δ)+4L|X||Ω||A|Bm(κ)βPT+2L|X|Bm(κ)βμT+Hocc(T), 1T _t=1^T _i=1^m\|q_i^t- q_i^t\|_1≤ C_occ(m,δ)+4L|X|| ||A|\,B_m(κ) _PT+2L|X|\,B_m(κ) _μT+H_occ(T), where Cocc(m,δ;κ):=4L2m|X|m+κ|X||Ω||A|2m|Ω||A|ℓP+2L2m+κ|X|2m|X||Ω|ℓμ+4L|X|2mln(Lδ),C_occ(m,δ;κ)\!:=\! 4L^2 m|X|\! m\!+\! κ|X|| ||A|\! 2m| ||A|\, _P\!+\! 2L^2 m\! m+ κ|X|\! 2m|X|| |\, _μ\!+\!4L|X| 2m ( Lδ ), and, Hocc(T)=2LBm(κ)ΨT∑c∈PMT(c)+LBm(κ)ΨT∑d∈μMT(d).H_occ(T)= 2LB_m(κ) T _c _PM_T(c)+ LB_m(κ) T _d _μM_T(d). Finally, since MT(c)≤TM_T(c)≤ T for every c∈Pc _P and MT(d)≤TM_T(d)≤ T for every d∈μd _μ, Hocc(T)≤2LBm(κ)Ψ|P|+LBm(κ)Ψ|μ|=LBm(κ)Ψ(2|X||Ω||A|+|X|).H_occ(T)≤ 2LB_m(κ) \,|C_P|+LB_m(κ) \,|C_μ|=LB_m(κ) (2|X|| ||A|+|X| ). Taking the limit completes the proof. ∎ Lemma B.10. Fix δ∈(0,1)δ∈(0,1) and assume that the good event ℰ(δ)E(δ) holds. Then, for both (ξir,t)( _i^r,t), (ξis,t)( _i^s,t), with probability at least 1−δ1-δ, we have, 1T∑t=1T∑i=1m(ξir,t)⊤qit≤~(LmLm+κ|X||Ω||A|Lm|X||Ω||A|ln(m|X||Ω||A|δ)). 1T _t=1^T _i=1^m(ξ^r,t_i) q_i^t≤ O\! ( Lm Lm+ κ|X|| ||A| Lm|X|| ||A| \! ( m|X|| ||A|δ ) ). Proof. In the full-feedback case, define rew:=X×Ω,qit(x,ω):=∑a∈Aqit(x,ω,a),C_rew:=X× ,\;q_i^t(x,ω):= _a∈ Aq_i^t(x,ω,a), and ℓrew:=ln(3m|X||Ω|δ),βrew:=ln(3|X||Ω|Tδ). _rew:= ( 3m|X|| |δ ),\; _rew:= ( 3|X|| |Tδ ). Then, in the partial-feedback case, define rew:=X×Ω×A,C_rew:=X× × A, and ℓrew:=ln(3m|X||Ω||A|δ),βrew:=ln(3|X||Ω||A|Tδ). _rew:= ( 3m|X|| ||A|δ ),\; _rew:= ( 3|X|| ||A|Tδ ). We prove the sender-reward bound. The receiver-reward bound follows by the same argument, replacing ξis,t _i^s,t with ξir,t _i^r,t throughout. For each reward coordinate c∈rewc _rew, define ξi,ws,t(c):=wκ(Nit(c))ℓrewmax1,Nit(c),ξi,ms,t(c):=w¯κ(Nit(c))(βrewmaxMt−1(c),1+Ψ). _i,w^s,t(c):=w_κ\! (N_i^t(c) ) _rew \1,N_i^t(c)\, _i,m^s,t(c):= w_κ\! (N_i^t(c) ) ( _rew \M_t-1(c),1\+ ). Then, we have ξis,t(c)≤ξi,ws,t(c)+ξi,ms,t(c). _i^s,t(c)≤ _i,w^s,t(c)+ _i,m^s,t(c). For each pair (t,i)∈[T]×[m](t,i)∈[T]×[m], Yt,i:=(ξis,t)⊤qit−∑c∈rewξis,t(c)Iit(c)Y_t,i:=( _i^s,t) q_i^t- _c _rew _i^s,t(c)\,I_i^t(c) is a martingale-difference sequence with respect to the natural filtration. Since, every reward is at most 11, and in each episode at most one coordinate is visited per layer, we have |Yt,i|≤Lalmost surely for all (t,i)∈[T]×[m].|Y_t,i|≤ L\;almost surely for all (t,i)∈[T]×[m]. Applying Azuma–Hoeffding inequality yields the following w.p. 1−δ1-δ, 1T∑t=1T∑i=1m(ξis,t)⊤qit≤1T∑t=1T∑c∈rew∑i=1mξis,t(c)Iit(c)+L2mln(1/δ)T. 1T _t=1^T _i=1^m( _i^s,t) q_i^t≤ 1T _t=1^T _c _rew _i=1^m _i^s,t(c)\,I_i^t(c)+L 2m (1/δ)T. (27) Using the decomposition of ξis,t(c) _i^s,t(c), 1T∑t=1T∑c∈rew∑i=1mξis,t(c)Iit(c)≤1T∑t=1T∑c∈rew∑i=1mξi,ws,t(c)Iit(c)+1T∑t=1T∑c∈rew∑i=1mξi,ms,t(c)Iit(c). 1T _t=1^T _c _rew _i=1^m _i^s,t(c)\,I_i^t(c)≤ 1T _t=1^T _c _rew _i=1^m _i,w^s,t(c)\,I_i^t(c)+ 1T _t=1^T _c _rew _i=1^m _i,m^s,t(c)\,I_i^t(c). We first bound the within-task term. For each fixed task t, by Lemma B.8, applied with =rewD=C_rew, ∑c∈rew∑i=1mξi,ws,t(c)Iit(c)≤ℓrew2St(rew)|rew|St(rew)+κ|rew|, _c _rew _i=1^m _i,w^s,t(c)\,I_i^t(c)≤ _rew\, 2S_t(C_rew) |C_rew| S_t(C_rew)+ κ|C_rew|, where St(rew):=∑c∈rewNmt(c).S_t(C_rew):= _c _rewN_m^t(c). Since the process is loop-free and each episode visits at most one reward coordinate per layer, St(rew)≤Lm.S_t(C_rew)≤ Lm. Using again that x↦x/(x+a)x x/( x+a) is increasing on [0,∞)[0,∞), we obtain ∑c∈rew∑i=1mξi,ws,t(c)Iit(c)≤2LmLm+κ|rew|Lm|rew|ℓrew. _c _rew _i=1^m _i,w^s,t(c)\,I_i^t(c)≤ 2 Lm Lm+ κ|C_rew| Lm\,|C_rew|\, _rew. Since the function u↦2LmLm+u|rew|Lm|rew|ℓrewu 2 Lm Lm+ u\,|C_rew| Lm\,|C_rew|\, _rew is decreasing in u≥0u≥ 0, and κ≥κ≥κ, it follows that ∑c∈rew∑i=1mξi,ws,t(c)Iit(c)≤2LmLm+κ|rew|Lm|rew|ℓrew. _c _rew _i=1^m _i,w^s,t(c)\,I_i^t(c)≤ 2 Lm Lm+ κ|C_rew| Lm\,|C_rew|\, _rew. Averaging over t gives 1T∑t=1T∑c∈rew∑i=1mξi,ws,t(c)Iit(c)≤2LmLm+κ|rew|Lm|rew|ℓrew. 1T _t=1^T _c _rew _i=1^m _i,w^s,t(c)\,I_i^t(c)≤ 2 Lm Lm+ κ|C_rew| Lm\,|C_rew|\, _rew. (28) By the definition of ξi,ms,t(c) _i,m^s,t(c) and Lemma B.7, 1T∑t=1T∑c∈rew∑i=1mξi,ms,t(c)Iit(c) 1T _t=1^T _c _rew _i=1^m _i,m^s,t(c)\,I_i^t(c) ≤1T∑c∈rew∑t=1T∑i=1mκNit(c)+κIit(c)βrewmaxMt−1(c),1 ≤ 1T _c _rew _t=1^T _i=1^m κN_i^t(c)+κ\,I_i^t(c) _rew \M_t-1(c),1\ +ΨT∑c∈rew∑t=1T∑i=1mκNit(c)+κIit(c) + T _c _rew _t=1^T _i=1^m κN_i^t(c)+κ\,I_i^t(c) ≤2|rew|Bm(κ)βrewT+Bm(κ)ΨT∑c∈rewMT(c). ≤ 2|C_rew|\,B_m(κ) _rewT+ B_m(κ) T _c _rewM_T(c). Thus 1T∑t=1T∑c∈rew∑i=1mξi,ms,t(c)Iit(c)≤2|rew|Bm(κ)βrewT+Bm(κ)ΨT∑c∈rewMT(c). 1T _t=1^T _c _rew _i=1^m _i,m^s,t(c)\,I_i^t(c)≤ 2|C_rew|\,B_m(κ) _rewT+ B_m(κ) T _c _rewM_T(c). (29) Substituting (28) and (29) into (27) yields 1T∑t=1T∑i=1m(ξis,t)⊤qit 1T _t=1^T _i=1^m( _i^s,t) q_i^t ≤Crewsim(m,T,δ;κ)+2|rew|Bm(κ)βrewT+Bm(κ)ΨT∑c∈rewMT(c), ≤ C_rew^sim(m,T,δ;κ)+2|C_rew|\,B_m(κ) _rewT+ B_m(κ) T _c _rewM_T(c), where Crewsim(m,T,δ;κ):=2LmLm+κ|rew|Lm|rew|ℓrew+L2mln(1/δ)TC_rew^sim(m,T,δ;κ):= 2 Lm Lm+ κ|C_rew| Lm\,|C_rew|\, _rew+L 2m (1/δ)T. Finally, since MT(c)≤TM_T(c)≤ T for every c∈rewc _rew, Bm(κ)ΨT∑c∈rewMT(c)≤Bm(κ)Ψ|rew|. B_m(κ) T _c _rewM_T(c)≤ B_m(κ) |C_rew|. Taking the limit, this is the desired bound. The proof for 1T∑t=1T∑i=1m(ξir,t)⊤qit 1T _t=1^T _i=1^m( _i^r,t) q_i^t is identical, replacing ξis,t _i^s,t with ξir,t _i^r,t throughout. This yields 1T∑t=1T∑i=1m(ξir,t)⊤qit≤Crewsim(m,T,δ;κ)+2|rew|Bm(κ)βrewT+Bm(κ)ΨT∑c∈rewMT(c), 1T _t=1^T _i=1^m( _i^r,t) q_i^t≤ C_rew^sim(m,T,δ;κ)+2|C_rew|\,B_m(κ) _rewT+ B_m(κ) T _c _rewM_T(c), with Bm(κ)ΨT∑c∈rewMT(c)≤Bm(κ)Ψ|rew|, B_m(κ) T _c _rewM_T(c)≤ B_m(κ) |C_rew|, which completes the proof. ∎ B.3 Regret and Violation Bounds Theorem B.1. Given any δ∈(0,1)δ∈(0,1), with probability at least 1−11δ1-11δ, Algorithm 7 attains the following cumulative task averaged expected regret: RmT≤~(L2m+κ|X||Ω||A||X|m|Ω||A|ln(m|X||Ω||A|δ))R^T_m≤ O ( L^2 m m+ κ|X|| ||A|\;|X| m| ||A| \! ( m|X|| ||A|δ ) ) Proof. Using Lemma B.9 to bound the occupancy measure and Lemma B.10 to bound the average rewards within the proof of Appendix D.2 Theorem 1 in Bacchiocchi et al. (2025) concludes the proof. ∎ Theorem B.2. Given any δ∈(0,1)δ∈(0,1), with probability at least 1−11δ1-11δ, Algorithm 7 attains the following cumulative task averaged expected violation: VmT≤~(L2m+κ|X||Ω||A||X|m|Ω||A|ln(m|X||Ω||A|δ))V^T_m≤ O ( L^2 m m+ κ|X|| ||A|\;|X| m| ||A| \! ( m|X|| ||A|δ ) ) Proof. Using Lemma B.4 for the full feedback receiver confidence bound, Lemma B.9 to bound the occupancy measure and Lemma B.10 to bound the average rewards within the proof of Appendix D.3 Theorem 2 in Bacchiocchi et al. (2025) concludes the proof. ∎ Theorem B.3. Given any δ∈(0,1)δ∈(0,1), with probability at least 1−11δ1-11δ, Algorithm 8 attains the following cumulative task averaged expected regret: RmT≤~(NL|X||Ω||A|+L2m+κ|X||Ω||A||X|m|Ω||A|ln(m|X||Ω||A|δ))R^T_m≤ O (NL|X|| ||A|+ L^2 m m+ κ|X|| ||A|\;|X| m| ||A| \! ( m|X|| ||A|δ ) ) where N≔⌈mα⌉N m^α is the length of exploration phase Proof. Using Lemma B.9 to bound the occupancy measure and Lemma B.10 to bound the average rewards, within the proof of Appendix E.1 Theorem 3 in Bacchiocchi et al. (2025) concludes the proof. ∎ Lemma B.11. Under the event ℰ(δ)E(δ), with probability at least 1−3δ1-3δ, the following holds for task t∈[T]t∈[T]: VmT≤~(L2m|X|m+κ|X||Ω||A||Ω||A|ln(m|X||Ω||A|δ))+1T∑T∑m∑X,Ω,Aqit(x,ω,a)ξir,t(x,ω,bit(a,x))V^T_m\!≤\! O ( L^2m|X| m+ κ|X|| ||A|\;\!\! | ||A| \! ( m|X|| ||A|δ ) )+ 1T _T _m _X, ,A\!\!\!q^t_i(x,ω,a)ξ^r,t_i(x,ω,b^t_i(a,x)) Proof. Using Lemma B.9 to bound the occupancy measure and Lemma B.10 to bound the average rewards within the proof of Appendix E.1 Lemma 11 in Bacchiocchi et al. (2025) concludes the proof. ∎ Theorem B.4. Given any δ∈(0,1)δ∈(0,1), with probability at least 1−13δ1-13δ, Algorithm 8 attains the following cumulative task averaged expected violation: VmT V^T_m ≤~[ρ(Lm+κ|X||Ω||A|+|X||Ω||A|NL+κ|X|Ω||A|+N+mNL+κ|X|Ω||A|+m2N+mκNL)] \!≤ O [ρ ( Lm m\!+\! κ|X|| ||A|\!+\! |X|| ||A|N\! NL\!+\! κ|X| ||A|\!\!+\! N\!+\! m\! NL\!+\! κ|X| ||A|\!\!+\! m^2N\!+\! mκNL\! ) ] whereρ:=|X||Ω||A|2Lln(1δ)where\ ρ\;:=\;|X|| ||A|^2L\, \! ( 1δ ), and N≔⌈mα⌉N m^α is the length of exploration phase. Proof. Using Lemma B.11 together with the properties of our reward estimators and confidence bounds under partial feedback, and following the steps in Appendix E.2, Theorem 4 Bacchiocchi et al. (2025), we conclude the proof. ∎