A Fast Algorithm for k-Memory Messaging Scheme Design in Dynamic Environments with Uncertainty

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-07 03:29:13

Abstract: We study the problem of designing the optimal k-memory messaging scheme in a dynamic environment. Specifically, a sender, who can perfectly observe the state of a dynamic environment but cannot take actions, aims to persuade an uninformed, far-sighted receiver to take actions to maximize the long-term utility of the sender, by sending messages. After receiving a message, the self-interested receiver derives a posterior belief and takes an action. The immediate reward of each player can be unaligned, thus the sender needs to ensure persuasiveness when designing the messaging scheme.

We formulate this problem as a bi-linear program and show that there exist infinitely many non-trivial persuasive messaging schemes for any problem instance. Moreover, we show that when the sender uses a k-memory messaging scheme, the optimal strategy for the receiver is also a k-memory strategy. We propose a fast heuristic algorithm for this problem and show that it can be extended to the setting where the sender has threat ability. We experimentally evaluate our algorithm, comparing it with the solution obtained by the Gurobi solver, in terms of performance and running time. Extensive experimental results show that our algorithm outperforms the solution in terms of running time, yet achieves comparable performance.

Main paper: 
 introduction: 
 The phenomenon of information asymmetry is commonly seen in many applications and has attracted extensive research attention from both computer science and economics.In these applications, an information sender can influence a receiver's behavior by strategically revealing information to them. Such interactions are usually modeled by the Bayesian persuasion framework (Kamenica and Gentzkow 2011) . And in such environments, the information sender has an advantage in information, which often leads to an advantage in their reward or utility. For example, a navigation platform that has access to complete information about the traffic conditions of an area may recommend several routes to a user who only possesses local information. The user then chooses the best route based on the recommendations.The platform and the user may have misaligned goals, and the navigation platform can send route recommendations to influence the user's choice. Following the Bayesian persua-44 sion framework, the platform can strategically design rec-45 ommendation strategies to persuade users into taking spe-46 cific actions that benefit the platform most.Most existing studies only consider persuasions in a static 48 environment. However, in real-world applications, the infor-49 mation sender and the receiver usually interact in a dynamic 50 way. In this paper, we consider the persuasion model in a 51 Markov decision process (MDP), where the sender has ac-52 cess to the state of the environment and the receiver is able to 53 take action. We assume that both players are far-sighted and 54 aim to optimize their accumulated rewards. The following 55 example shows how the sender can improve their long-term 56 reward by sending information to the receiver. a 3 , (0,0.5) a i , (5,0.5) a i , ( 0 ,0 ) ,0 .5 ai , ( 0 ,0 ) ,0 .5 Example 1. Consider the example MDP shown in Figure 58 1. The states {s i } 4 i=1 are connected by directed edges indi-59 cating state transitions. Solid lines represent deterministic 60 transitions and dashed ones probabilistic transitions. Each 61 edge is labeled with the action triggering the transition and 62 the immediate rewards for the sender and the receiver re-63 spectively. Dashed lines are also marked with the transition 64 probabilities. There are 3 available actions {a i } 3 i=1 for the 65 receiver. Assume that the initial state distribution is 0.5 for 66 s 1 and s 2 , and 0 for both s 3 and s 4 , i.e., the game will start at 67 state s 1 or s 2 randomly. The discount factor for both players 68 is 0.5. If the sender does not reveal any information to the 69 receiver, the receiver will not be able to distinguish between 70 s 1 and s 2 , and thus will choose the "safe" action a 3 in the 71 first step. The state then transits to s 4 deterministically. The 72 receiver always gets 0 in state s 4 no matter which action the an environment with an external parameter. The key dif-125 ference is that they focus on Markov signaling schemes, 126 whereas we consider a more general k-memory messaging 127 scheme. Actually, the Markov signaling scheme studied by 128 (Gan et al. 2022 ) is exactly equivalent to the 1-memory messaging scheme in our setting. They show that it is NP-hard to even approximate the optimal 1-memory messaging scheme against a far-sighted receiver. (Wu et al. 2022 ) design an efficient no-regret algorithm under an online learning setting. They aim to persuade a sequence of myopic receivers, while we consider persuading a single far-sighted receiver.Our paper is also related to dynamic mechanism design (Papadimitriou et al. 2016; Pavan, Segal, and Toikka 2014; Athey and Segal 2007) . In particular, recent work by (Zhang and Conitzer 2021) studies dynamic mechanism design in a finite horizon, where the mechanism designer, who has partial information about the state, aims to design a mechanism to elicit state information from an agent so as to make a better decision. On the contrary, we stand on the side of information design, studying how the sender can use this information advantage to maximize their utility. The common point is that we both adopt history-based strategies for the designer.Another related topic is planning in MDPs. Particularly related to our work is (Zhang, Cheng, and Conitzer 2022) , where the authors study a setting where an informed planner interacts with a self-interested agent with the choice to exit the environment. We both use history-based strategies. However, they impose participation constraints on the agent when the principle computes the optimal policy, while we need to guarantee persuasiveness constraints when the sender designs the optimal messaging scheme.In the standard Markov decision process (MDP), a decision maker chooses an action at each time step to maximize their long-term reward. Now, consider a variant of MDP where there are two agents in the game, namely the sender and the receiver. The receiver can take action but has no access to the state. However, the sender can perfectly observe the state and send messages to inform the receiver about the state in order to influence their behavior. Both agents are rational and attempt to maximize their long-term expected utilities.Formally, such a setting can be described by a tuple hN, S, A, P, ⇢ 0 , u, i, where:• N = {s, r} denotes the player set, where s and r denote the sender and the receiver, respectively.• S is a finite set of environment states, only observable for the sender.• A is a finite set of actions that the receiver can choose to take in each state. We assume all states share the same action set and let d = |A| be the number of available actions.• P : S ⇥ A 7 ! (S) is the state transition function. We use P (s, a, s 0 ) to denote the probability that the receiver would arrival state t 0 when he takes action a in state s.• ⇢ 0 denotes the initial state distribution, i.e., the initial state will be s i with probability ⇢ 0 (s i ).• u = (u s , u r ), where u s : S ⇥A 7 ! R + and u r : S ⇥A 7 ! R + are the sender's and the receiver's immediate reward functions.• is a common discount factor.We assume that the decision process repeats infinitely many time steps and consider the setting where the receiver can observe the immediate reward. Put differently, we assume that the receiver can speculate the state s t after taking action a t , since the immediate reward u r (s t , a t ) reveals information about s t .1 As a result, the receiver has a prior belief ⇢ t+1 = P (s t , a t ) about the next state s t+1 .This setting induces a game between the sender and the receiver. The game proceeds as follows: the sender announces a messaging scheme at the beginning of the game, where a messaging scheme (M, ⇡) contains a message set M and a policy ⇡ specifying how a message is chosen. At each time step t, the sender first observes a state s t 2 S and then sends a message m t 2 M to the receiver according to the announced messaging scheme. Here, we assume that the sender has commitment power, i.e., the sender will never deviate from the announced scheme. After receiving the message, the receiver makes the best response to that message.Then the time step becomes t + 1 and the state transits to the next one according to the transition function.If two players are fully cooperative, i.e., their utilities align perfectly, then the sender can just send all the information they have, and the problem reduces to a standard MDP.However, the sender may only want to reveal partial information to the receiver, since the two players may have conflicting interests. We adopt the so-called Bayesian persuasion framework (Kamenica and Gentzkow 2011) to describe the sender's strategy.The game between the two agents can be described by a game tree of infinite depth. The sender may use different messaging schemes at different tree nodes. In other words, the sender's messaging scheme can depend on the history information. We define t-length history h = (s 1 , a 1 , . . . , s t , a t ) as a sequence of states and receiver's actions of the previous t time steps. In this work, we mainly focus on the k-memory messaging scheme, which depends on the latest history with a length equal to or less than k. If k = 0, we call such a strategy a Markov strategy.Denote by H t the set of all histories of length t. Let H = S k t=0 H t be the set of all histories with length no more than k, where H 0 is the singleton containing the empty history h 0 . At the beginning of the game, there is no history information but a prior distribution ⇢ 0 over the state set S.Thus the prior ⇢ 0 carries the same information as the empty history.Given any t-length history h, we use h + (s, a) to denote the new history by adding (s, a) to the end of history h. Note that we may need to remove the earliest state and action to prevent the history length from exceeding k, i.e.,h + (s, a) = ⇢ (s 1 , a 1 , . . . , s t , a t , s, a), if t < k (s 2 , a 2 , . . . , s t , a t , s, a), if t = k .A k-memory messaging scheme is a function that maps 236 history-state pairs to distributions over the message space. 237 Formally, denoted by ⇡ : H ⇥ S 7 ! (M ) the k-memory 238 messaging scheme. We use ⇡(h, s, m) to denote the proba-239 bility that message m is sent by the sender when state s is 240 reached, given history h. Such a scheme is also called a "sig-241 naling scheme" in the literature (Kamenica and Gentzkow 242 2011).Given history h 2 H, denote by ⇢ h the receiver's belief 244 about the state s. As described in the previous section, ⇢ h (s) 245 depends only on the state and action of the last time step, i.e., 246 ⇢ h (s) = P (s t , a t , s)2 . We make the mild assumption that 247 ⇢ h (s) > 0, 8s throughout the paper. Once receiving mes-248 sage m, a rational receiver will derive a posterior belief over 249 the state according to the standard Bayes rule:EQUATION)Optimization Problem FormulationWe study how the sender can make use of this information 252 advantage to influence the receiver's actions. The goal of the 253 sender is to design a k-memory messaging scheme that max-254 imizes their cumulative expected utility.It is already known from (Gan et al. 2022 ) that solving 256 the 1-memory messaging scheme design problem against a 257 far-sighted receiver is NP-hard. Therefore, one cannot hope 258 to find an efficient algorithm to solve this problem unless 259 P=NP. In this section, we formulate the problem as a bi-260 linear optimization problem which will be useful for later 261 analysis.In the above definition, we have no restriction on how 263 many messages the sender can use. However, it is known 264 that we can view each message as an action recommenda-265 tion since each message induces a posterior belief of the re-266 ceiver, which leads to a certain receiver action (Kamenica 267 and Gentzkow 2011; Dughmi and Xu 2016) . Thus the num-268 ber of messages can be set equal to the number of ac-269 tions without harming the sender's interest, i.e., |M | = d. 270 In other words, given any messaging scheme, we can al-271 ways construct an equivalent scheme ⇡ with the message 272 set M A = {m a : a 2 A}, where each message m a corre-273 sponds to an action recommendation a 2 A, achieving the 274 same expected utility as the original messaging scheme.Persuasiveness. Before giving a formal definition of per-276 suasiveness, we first need to define the long-term utility for 277 each player. Let V ⇡ 1 (h, s) be the expected cumulative util-278 ity function when the sender uses strategy ⇡ when the his-279 tory is h and the state is s. Similar to the Bellman equa-280 tion (Bellman 1966) , given a k-memory messaging scheme 281 ⇡, the cumulative expected utility function of the sender 282V ⇡ 1 : H ⇥ S 7 ! R should satisfy: 283 V ⇡ 1 (h, s) = X ma2M A ⇡(h, s, m a ) • " u s (s, a)+ • X s 0 2S P (s, a, s 0 ) • V ⇡ 1 (h + (s, a), s 0 ) .(2)Given this, the overall expected utility of the sender from the 284 beginning can be defined as follow:EQUATIONSimilarly, the receiver's long-term expected utility func-EQUATIONNow we are ready to give a formal definition of persua-289 siveness:290 Definition 1 (Persuasiveness). A k-memory messaging 291 scheme ⇡ is persuasive if it satisfies the following persua-EQUATIONSimply put, a messaging scheme is persuasive if the re-294 ceiver is always willing to take the recommended action, i.e.,the recommended action always maximizes the receiver's 296 long-term utility.With the above analysis, we can now formulate the prob-298 lem as the following mathematical program, with decision 4), ( 5)299 variables ⇡(h, s, m a ), V ⇡ 1 (h, s), V ⇡ 2 (h, s, a): 300 maximize (3) subject to (2), (EQUATIONProgram ( 6) is a bi-linear program since constraint ( 5) is 301 a bi-linear constraint.Theoretical AnalysesIn this section, we analyze the problem in theory and de-304 rive some structural results. We first show that there exist in-305 finitely many non-trivial persuasive messaging schemes for 306 the sender, in any problem instance. Moreover, we show that 307 the receiver can achieve optimality by using a k-memory 308 strategy if the sender also uses a k-memory messaging scheme.In the standard Bayesian persuasion setting, there always exist trivial persuasive schemes, e.g., revealing full or no information to the receiver. Such trivial schemes also exist in our setting, but it is not clear if a non-trivial persuasive scheme exists, since our setting has much more complicated constraints. Before trying to find an optimal messaging scheme, we need to ensure that there indeed exist non-trivial persuasive schemes, since otherwise, there are only trivial schemes and we can just consider these special cases instead of searching the entire space.To give some intuition about this result, we first consider a simple setting where = 0. We construct a trivial persuasive Markov messaging scheme as follows. Let ⇤ r be the optimal strategy of the receiver if they can observe the environment state s, i.e., ⇤ r (s) = arg max a2A u r (s, a). We define the following Markov messaging scheme:⇡ ⇤ (s, m a ) = ⇢ 1 if a = ⇤ r (s) 0 otherwise .This messaging scheme is trivially persuasive since following the sender's recommendation already maximizes the receiver's utility. The proof of Lemma 1 is based on the above construction.Lemma 1. Assume that there are at least two actions a i1 and a i2 , with corresponding states s i1 and s i2 , such that a i1 and a i2 are the unique maximizers of u r (s i1 , a) and u r (s i2 , a), respectively. When = 0, there are infinitely many non-trivial Markov messaging schemes that are persuasive.The intuition behind the proof is that adding a small enough perturbation to a trivial scheme will not change the receiver's optimal strategy, thus maintaining persuasiveness. We defer the detailed proof into the appendix.Then we show that infinitely many persuasive messaging schemes exist for any problem instance. Actually, this can be simply derived by applying the revelation principle (Myerson 1981) from the mechanism design literature. We also provide an alternative proof in the appendix that does not use the revelation principle.Theorem 1. For any problem instance, there are infinitely many persuasive messaging schemes.Proof. The intuition behind our proof is to "relabel" messages in any messaging scheme so that they correspond to the actual actions of the receiver. Let (M, ⇡) be any messaging scheme. If the sender uses this scheme, the receiver is then faced with an MDP as defined in the proof of Lemma 2. Let (h, m) be the receiver's optimal strategy in the MDP. Let M a (h) = {m | (h, m) = a} be the set of messages that lead to the receiver's action a when the history is h. According to the revelation principle, we can construct a new scheme that simply uses message set M A and replace each m 2 M a (h) with m a , and get the same receiver response (h, m) = 0 (h, m a ), 8m 2 M a (h). Thus the new scheme is persuasive.In fact, the receiver is also faced with an MDP after the sender commits to a messaging scheme. Thus the problem studied in this paper is an MDP environment design problem for the sender. Based on this intuition, we have the following result.Theorem 2. When the sender uses a k-memory messaging scheme, the optimal strategy for the receiver is also a kmemory strategy.Proof. We prove this by showing that the receiver's problem can be viewed as an MDP. Since the sender has commitment power, their strategy will not change throughout the game. Thus the receiver can simply view the sender as part of the environment. From the receiver's point of view, they are faced with an MDP problem, where the environment of the MDP contains both the original environment and the sender. The state of the MDP contains both the history h and the message m sent by the sender.After receiving a message m, the receiver will derive a posterior distribution by applying the Bayes rule:EQUATION)The expected immediate reward of the receiver for taking action a is thenP s ⇢ h (s|h, m)u r (s, a).Formally, we can formulate the MDP faced by the receiver as follows:• The state space is S ⇤ = H ⇥ M ;• The actions spaces is A ⇤ = A;• The state transition function isP ⇤ ((h, m), a, (h + (s, a), m 0 )) = ⇢ h (s) • P s 0 2S ⇢ h+(s,a) (s 0 ) • ⇡(h + (s, a), s 0 , m 0 ); • the reward function is R ⇤ ((h, m), a) = P s2S ⇢ h (s|h, m) • u r (s, a).Since the sender uses a k-memory messaging scheme ⇡(h, s, m), the receiver's posterior belief of the environment state ⇢ h (s|m, h) only depends on the information of the previous k steps. And even if the receiver uses a strategy that depends on a longer memory, they cannot obtain more information that can affect their behaviors. And in such an MDP, the receiver's optimal strategy is to choose an action for each MDP state (h, m), which only contains information about previous k time steps.In this section, we propose an efficient heuristic algorithm.The intuition behind our algorithm is as follows. The game proceeds in a Stackelberg way: the sender first announces their strategy and then the receiver follows. We view the game as a standard Bayesian extensive-form game as it provides a lower bound of the original game. However, the game still contains infinitely many steps. We further simplify the game by setting a parameter T and only consider T time steps. Thus the game tree has a maximum depth of T .We then modify the backward induction algorithm (Aumann 1995) and apply it to find a solution.Backward induction is a strategy for analyzing a game 414 by working backwards from the end to the beginning. The 415 algorithm starts at time T 1 and considers all possible k-416 length histories, of which there are |H k | types of terminal 417 nodes. Each node at this stage is labeled with the sender's 418 messaging scheme, denoted as ⇡ h : S ⇥ M A 7 ! R. For each 419 node, the optimal messaging scheme ⇡ ⇤ h is computed, along 420 with the expected utilities for both players. This informa-421 tion is then used to compute the optimal messaging scheme 422 for the previous time period, time T 2, and the process 423 continues recursively until the optimal messaging scheme is 424 determined for all nodes in the game tree.Specifically, starting from time t = T 1, we solve the 426 following linear program for all nodes at time t, where each 427 node can be uniquely identified by a history h:EQUATIONNote that at any terminal node, there is no future reward 429 thus we set V (h + (s, a)) = 0 at begin. At each backward 430 step t, for each history h, after solving the above program, 431 we obtain the optimal messaging scheme ⇡ ⇤ h for node h. We 432 let V 1 (h) equal to the objective of the program, and compute 433 V 2 (h) as follow:EQUATIONIn the end, we aggregate ⇡ ⇤ h with all relevant histories h 435 and output a backward message scheme ⇡ backward . Our de-436 tailed algorithm is listed in Algorithm 1.Our algorithm can also be applied to the setting where the 439 sender is able to threaten the receiver. The receiver's utility 440 is minimized when the sender provides no additional infor-441 mation about the underlying state, e.g., always sending the 442 same message. If the sender threaten the receiver with a k-443 memory scheme, according to Theorem 2, such a threat lasts 444 only for at most k steps. In this section we consider threats 445 that last forever.In this section, we experimentally evaluate our algorithm and report the experiment results. We compare our algorithm with the method of using Gurobi to solve the bilinear program defined in our paper, in terms of performance and running time. The experiment results demonstrate that our algorithm achieves solution quality comparable to that of the solution found by Gurobi, yet outperforms it in terms of running time.We also conduct experiments with the sender being able to threaten the receiver. Due to space limitations, these results are deferred to the appendix.Experiment setup. We conduct experiments on games with different sizes (number of states ⇥ number of actions), ranging from 2 ⇥ 2 to 12 ⇥ 12, and different discount factors , ranging from 0.1 to 0.9. Furthermore, we evaluate how the memory length influences the performance, by changing k from 1 to 6. For each game size, we generate 20 game instances, where for each instance, the reward matrices of both players are generated randomly from the uniform distribution U [0, 1], and the transition functions are also uniformly generated at random. All the algorithms are implemented with Python, and all the linear programs and bi-linear programs are solved using Gurobi (Python version, v9.5.2). All results with the same game size are based on the same set of reward matrices by varying and k.Since bi-linear programs are intractable to solve, we set the time limit parameter of Gurobi to 30 minutes (1800 seconds) when solving bi-linear programs, but do not limit the running time when solving linear programs.We found that the Gurobi solver can hardly solve any bilinear program of our generated game instances within the 30-minute time limit, even for 2 ⇥ 2 games. However, it can report the best feasible solutions obtained so far. Thus all the reported results in such cases are based on these feasible solutions.All the results of our algorithm are obtained by setting the backward step to 100 (T = 100 in Algorithm 1) unless otherwise stated. Furthermore, all the reported results are averaged over the 20 randomly generated game instances.Performance. We evaluate different algorithms' performance by comparing the expected utility of the sender obtained by them. We compare the performance of the two algorithms under different game sizes and different memory lengths. Since Gurobi does not even provide feasible solutions to the bi-linear program of some game instances in 30 minutes, the results are incomparable even if our algorithm can output feasible solutions. Thus all results are only average over the instances that Gurobi provides feasible solutions within 30 minutes. And we only compare the performance for games with sizes up to 5 ⇥ 5 and memory lengths up to 4, since Gurobi can hardly find a feasible solution for the bi-linear program of more complicated games.Figure 2 shows the performances of two algorithms under different game sizes. Our algorithm achieves performances comparable to the bi-linear formulation. In general, for larger games, the sender can have higher utilities. Note that our algorithm sometimes achieves higher utilities than The results of solving bi-linear programs with Gurobi are shown in Table 1 and Table 2 . It is clearly seen from Table 1 that as the game size increases, the number of games that Gurobi can provide a feasible solution decreases. Furthermore, this number also decreases when the discount factor increases, which means that the more the receiver cares about long-term utilities, the harder it is for Gurobi to find a As shown in Table 2 , when the discount factor is small enough, Gurobi is able to find feasible solutions for all the game instances with different memory lengths k. However, for larger discount factors , it becomes less likely for Gurobi to find a feasible solution within 30 mins as the memory length k grows.The results in Table 1 and 2 align well with our intuitions.As the game size and memory length increase, the strategy space of the sender grows larger. Therefore, solving these games becomes harder. Although the sender's scheme depends on previous time steps, it can also affect both agents' future utilities, since the receiver considers future utilities when making a decision and the current decision becomes past information in the future. With a larger , future utilities have a larger weight in the long-term utility and thus have more influence when the receiver chooses an action, making it difficult to find a good enough scheme.We report the running time of our algorithm in Table 3 and 4 . Our algorithm runs much faster compared with solving the bi-linear program. Our algorithm is able to find a feasible solution for all 20 game instances within 30 minutes, for all different game settings. In fact, our algorithm terminates within 30 seconds for most of the games.We also conduct experiments to explore how large instances our algorithm can handle in 30 minutes, and record the corresponding average utility in different game sizes.Figure 4 shows that our algorithm can handle 12 ⇥ 12 games within 30 minutes. Unlike the bi-linear program formulation, the discount factor actually has little impact on the running time of our algorithm. Changing the discount factor does not affect the execution of our algorithm except for the part of solving linear programs, which is also implemented using Gurobi. Thus we conjecture that the slight increase in running time is also due to the Gurobi solver. Hyperparameter. We evaluate how the backward step af-586 fects the performance of our algorithms with k = 1, in in-587 stances with 2 ⇥ 2 game size and different discount factors. 588The results are provided in Figure 5 . When = 0.9, the 589 sender can obtain more utility by increasing the backward 590 step from 20 to 40. Figure 5 also shows that increasing the 591 backward step may not bring an obvious increase in utility, 592 but may increase the running time quickly. Therefore, the 593 backward step parameter can be used to balance the running 594 time and the performance. We studied the problem of designing the optimal k-memory 597 messaging scheme against a far-sighted receiver in a dy-598 namic environment. We formulated this problem as a bi-599 linear program. Then we analyzed this problem in theory 600 and derived some structural results. We also proposed a fast 601 heuristic algorithm to solve this problem. Our experiment re-602 sults show that the solution quality of our algorithm is com-603 parable to that of the bi-linear program solved by Gurobi, 604 and that our algorithm is much faster than solving the bi-605 linear program.The receiver is able to perfectly identify st in a non-degenerate case, i.e., ur(st, at) 6 = ur(s 0 t , at), 8st, s 0 t 6 = st, 8at.Assume that h = (s1, a1, . . . , st, at), then the previous stateaction pair is (st, at).: H ⇥ S ⇥ A 7 ! R, under k-memory messaging 287 scheme ⇡ can be define as: 
 
 Appendix:  


Decision: This paper looks at a Bayesian persuasion problem, where the receiver plans for the long term and the sender uses a k-memory messaging scheme. Although Bayesian persuasion is usually studied in game theoretic settings, this paper looks at the long-term problem, and presents a bi-linear optimization approach which can compute an optimal policy, making this also suitable to ICAPS.

When preparing the final version of the paper, please take the reviewers' comments into account - I am confident they will improve the paper even more.

Reviews: review: strength_weakness: strength_weakness: The discussion of the complexity of the bi-level optimization problems is not particularly clear. The authors should explain the model of Gan et al and the changes they made and why they think it does not impact the complexity. 

The discussion of the use of Gurobi is muddled. The authors should really refer to the results as to the results of their heuristic. "Gurobi" is often associated with exact methods, and indeed, the bi-level optimization problem could be formulated as a MIP and solved with Gurobi exactly. This is not explained, though. 

There is no code provided, so it is impossible to check the experimental results.
questions: questions: Would the code be accessible in pastebin or similar?
strength_weakness: strength_weakness: Detailed Comments:

1. The proof of Theorem 1 seems incomplete. It is clear from the proof that a new scheme constructed by replacing each m \in M_a(h) with m_a is persuasive, but it is not clear that this implies that there are infinitely many unique persuasive messaging schemes. It seems possible for some problem instance that all (M, \pi) are constructed into the same (or a finite set of ) messaging scheme with the technique in the proof as it is written.

2. Theorem 1 also doesn’t exactly show that there are infinitely many (non-trivial) persuasive schemes for a given message set M_a. Since the argument is that you can just use M_a as the message set, and M_a is the message set used for the algorithm, it seems important to prove it for the case of M_a.

3. The paper claims (lines 117-118) that it considers the general problem with infinite horizon, the algorithm actually only solves the T time step problem for a fixed parameter T.

Minor comments:

1. The condition/assumption of the sender announcing the messaging scheme at the beginning of the game and committing to it seems very strong. I understand that this is a common condition in the Bayesian Persuasion literature, but it is difficult to see where this sort of game can be applied.

2. It is not fully clear from the paper what the message space is, and I assume |M| < \infty?

3. V_1(h,s) should be defined as the expected cumulative utility function for the sender (line 278-280).

4. Equations 2-4 is a little ill defined, since V_1^\pi and V_2^\pi should depend on both the sender’s policy \pi_1 and receiver’s policy \pi_2, and not just \pi. a in equation 2 and a’ in equation 4 is not well defined without defining receiver’s policy \pi_2 (or receiver's optimal policy \pi*_2).
questions: questions: 1. Clarification on the proof of Theorem 1 (detailed comment 1 and 2).
2. In what settings would the messaging scheme be given to the receiver a-priori with commitment?
strength_weakness: strength_weakness: There are a few things that I did not fully grasp or found a bit unsatisfying in
the current version.

My main issue with the paper is that k does not influence all of your
benchmarks. One of the key insights of using the k-messaging scheme is to
exploit the last k steps. But in your benchmark, increasing k gives no advantage
whatsoever. It just seems from the experiments that the 1-message scheme is
enough in any case. I am not sure, but it seems to me like this is a flaw in the
benchmark design. My intuition says that one case where a larger k would be
useful in cases where the receiver is "stubborn": the sender keeps telling the
receiver to go from s1 to s2, but he keeps performing an action that self-loops
(with bad rewards, let's say) to s1, then the sender tries to move it to s3 to
see if it leaves from this bad state. But there is no parameter in your setup
where you can play with this. The generation of the randomized instances seemed
a bit too artificial to me.

Related to the last paragraph, the intro gives several applications and
scenarios where this sort of formulation could be useful. But then, in the
experimental results, all problems solved are randomly generated. While I do not
think this is crucial, I would have expected some domains closer to the things
you mentioned as motivation. At least, I think you should add one or two
sentences acknowledging that you did not do so and that there is no benchmark
for these problems (yet).

The part about the "threats" was the most unclear to me. Not sure I understood
what a threat would look like. If I understood it correctly, it is simply a
sequence of misleading messages so the sender reduces the reward of the
receiver. But why would this be the case? In which domains are threats
interesting or useful? What would such threats look like in practice? Perhaps
these questions are too basic, but it was not clear to me why the whole threat
bit is relevant.

Minor:

Everywhere: You use references as an "object" or a noun (e.g., "Since (Gan et
a. 2022) already..."). I would recommend rewriting it as "Since Gan et
al. (2022)" for example.

Optimization Problem Formulation: you say first that we want a scheme "maximizes
their cumulative expect utility." This is ambiguous: maximizes the sum of their
utilities or each wants to maximize their own? From the paper this becomes
obvious, but the first time it was misleading.

Equation (3): V^\pi_1(h_0) is overloading notation. V^pi_1 should have two
parameters by definition above. I believe you need a different symbol for the
left-hand side. (Not convinced the symbol is ever needed actually.)

After Equation (7): "action spaces" should be "action space"

After (8): "at begin" -> "at the beginning"

Performance: "we evaluate different algorithms" -> "we evaluate *the* different..." I believe.

References: Inconsistent naming of proceedings: for SODA and STOC you spelled
out the full name and added even the number of the proceedings -- this wasn't
done for AAAI for example.

References: almost half of the entries have missing page numbers. In particular,
all where the venue is written in short form.

Appendix: "defined above" -> "defined in the paper"?
questions: questions: - Why does k play no role in your experiments? Could you design benchmarks where
  it does indeed play a role? Would you have experiments showing it? If not, are
  1-messaging schemes sufficient in most cases? Would a greedy choice by the
  receiver be enough (without caring about previous messages) in most cases?

- Could you clarify my misunderstanding of the threat-based schemes? (See
  above.) Could you give a concrete example of its usefulness?

- Are you planning to make the source code public in case of acceptance?