  Bayesian persuasion studies the problem faced by an informed sender who
strategically discloses information to influence the behavior of an uninformed
receiver. Recently, a growing attention has been devoted to settings where the
sender and the receiver interact sequentially, in which the receiver's
decision-making problem is usually modeled as a Markov decision process (MDP).
However, previous works focused on computing optimal information-revelation
policies (a.k.a. signaling schemes) under the restrictive assumption that the
receiver acts myopically, selecting actions to maximize the one-step utility
and disregarding future rewards. This is justified by the fact that, when the
receiver is farsighted and thus considers future rewards, finding an optimal
Markovian signaling scheme is NP-hard. In this paper, we show that Markovian
signaling schemes do not constitute the "right" class of policies. Indeed,
differently from most of the MDPs settings, we prove that Markovian signaling
schemes are not optimal, and general history-dependent signaling schemes should
be considered. Moreover, we also show that history-dependent signaling schemes
circumvent the negative complexity results affecting Markovian signaling
schemes. Formally, we design an algorithm that computes an optimal and
{\epsilon}-persuasive history-dependent signaling scheme in time polynomial in
1/{\epsilon} and in the instance size. The crucial challenge is that general
history-dependent signaling schemes cannot be represented in polynomial space.
Nevertheless, we introduce a convenient subclass of history-dependent signaling
schemes, called promise-form, which are as powerful as general
history-dependent ones and efficiently representable. Intuitively, promise-form
signaling schemes compactly encode histories in the form of honest promises on
future receiver's rewards.
