Year: 2021

Abstract:
This paper considers the problem of learning optimal value functions for finitetime decision tasks via saddle-point optimization of a nonlinear Lagrangian function that is derived from the Q-form Bellman optimality equation. Despite a long history of research on this topic in the literature, previous works on this general approach have been focusing on a linear special case known as the linear programming approach to RL/MDP. Our paper brings new perspectives to this general approach in the following aspects: 1) Inspired by the usually-used linear V -form Lagrangian, we proposed a nonlinear Q-form Lagrangian function and proved that it enjoys strong duality property in spite of its nonlinearity. The Lagrangian duality property immediately leads to a new imitation learning algorithm, which we applied to Machine Translation and obtained favorable performance on standard MT benchmark. 2) We pointed out a fundamental limit in existing works which exclusively seeks to find the minimax-type saddle points of the Lagrangian function. We however proved that another class of saddle points, the maximin-type ones, turn out to have better optimality property. 3) In contrast to most previous works, our theory and algorithm are oriented to the undiscounted episode-wise reward, which is practically more relevant than the usually considered discounted-MDP setting, thus have filled a gap between theory and practice on the topic.

heading: 1 INTRODUCTION
text: Episodic learning Terry (2017) is a general learning paradigm in which the agent learns based on data collected from a sequence of episodes of environmental interactions. Each episode consists of a finite number of decision steps, and the goal is to maximize an episode-wise performance. With one-step episodes, episodic learning subsumes supervised learning and bandit problems as special cases; for sequential decision making problems, an episode may contain multiple (and possibly varying number of) steps, in which case episode learning encompasses most reinforcement learning and imitation learning problems encountered in current AI practice.
A pervasive idea of episodic learning, often called the value-based approach Sutton and Barto (2018), seeks to find a value function such that greedily selecting the actions with the best values (as prescribed by this function) gives good performance. For example, in most classification tasks, most deep neural networks are learned (and used) to represent such a value function. Finding good value functions can be highly challenging, especially for tasks with multi-step episodes. In this case, the classic Bellman optimality equation Bertsekas (2019) gives a sufficient condition of optimal value function (i.e. value functions with which greedy decisions have optimal performance).
In this paper, we study a Lagrangian method which learns optimal value functions by characterizing them as saddle points of the Lagrangian function of a variational (re-)formulation of the Bellman equation. The method reveals an elegant thoery on policy-value duality in machine learning. A restricted form of this high-level idea has been known as the Linear Programming (LP) approach in the literature of dynamic programming Puterman (1994); Si et al. (2004); Chen and Wang (2016); Wang (2017), which has also been introduced to reinforcement learning in recent years Dai et al. (2018); Lee and He (2018); Nachum et al. (2019); Yang et al. (2020); Nachum and Dai (2020). This paper provides a new perspective to the foundation of this elegant idea through the following contributions:
Firstly, previous works are mostly limited to the discounted-reward setting, which bypass some technical difficulties Nachum and Dai (2020), but deviate from the practical settings of many (if not
most) real-world tasks. This paper fills this well-known gap between theory and practice by establishing a value-based theory (and algorithm) that targets at directly learning optimal value functions and policies for the undiscounted episode-wise reward (see (1) in Section 2).
Secondly, previous works focused on linear formulations, which enjoys the strong duality property and generic LP techniques, but are consequently limited to treatments for the state-value functions (i.e. V-functions) in policy optimization setting. However, the optimal state-value function cannot be directly used to derive optimal policy in model-free learning. In contrast, we proved a minimax theorem for the nonlinear Lagrangian functions associated with the action-value functions (i.e. Qfunctions). The theorem opens a door to nonlinear variational treatment to the Bellman equation, which now enjoys the strong duality property too (see Section 3).
In particular, we developed a simple imitation learning algorithm based on the Lagrangian duality thus established, and applied the algorithm to Machine Translation (MT) as case study. Transformer models trained by our algorithm achieves beam-search-level performance Vaswani et al. (2017) with only greedy decoding, and leads to 1.4-BLEU improvement when also equipping with beam search (see Section 4).
Last but not the least, previous works have exclusively focused on the primal-form optimization formulation of the Bellman equation, thus are limited to solving the minimax-type saddle points of the corresponding Lagrangian function. We however showed that the minimax saddle points are not necessarily optimal value functions in learning settings. Instead, another class of the Lagrangian saddle points – the maximin-type saddle points which are derived from the dual-form optimization formulation – turn out to have rigorous guarantee on optimality. This observation points to new directions for this decades-old topic (see Section 5).

heading: 2 EPISODIC LEARNING PROCESS AND BELLMAN OPTIMAL VALUE
text: We start with introducing the mathematical formulation of episode learning problems, as well as the formal definitions of related concepts.
An infinite-horizon MDP is a tuple (S,A, R, P, ρ0), where S is the state space, A the action space, R(s) ∈ [rmin, rmax] is a bounded reward (possibly negative) associated to each state s ∈ S , 1 P (s′|s, a) specifies action-conditioned transition probabilities between states, and ρ0 is the initial distribution with S0 ∼ ρ0. A MDP is finite if both S and A are finite sets. A policy function π : S × A → [0, 1] specifies the action selection probabilities under each state, which induces a markov chain Pπ[St+1 = s′|St = s] . = ∑ a∈A P (s
′|s, a) · π(a|s). Let Π denote the policy space, i.e., the set of all policies. Without loss of generality, we assume every state s in the state space S is reachable from the initial state under at least one policy, 2 where reachable means ∃π ∈ Π, ∑∞ t=0 Pπ[St = s] > 0.
An Episodic Learning Process (ELP) White (2017); Bojun (2020) is an infinite-horizon MDP that repeatedly encounters into, and is reset by, a group of terminal states S⊥ (despite its name, a terminal state does not terminate the ELP). Formally, an infinite-horizon MDP is an ELP if there is a non-empty subset S⊥ ⊆ S such that (1) all terminal states have homogeneous and action-agnostic outbound probabilities: P (s′|s1, a1) = P (s′|s2, a2), ∀s1, s2 ∈ S⊥, ∀a1, a2 ∈ A, ∀s′ ∈ S, (2) the initial state is a terminal state: ρ0(s) = 0,∀s 6∈ S⊥, and (3) the average episode length is finite under any policy: ∀π ∈ Π, Eπ[T ] <∞, where T . = inf{t ≥ 1 : St ∈ S⊥} is called the termination time. Bojun (2020) proved that in any ELP, every policy π ∈ Π has a unique stationary distribution ρπ(s, a) such that Pπ[St+1 = s,At+1 = a] = ρπ(s, a) if Pπ[St = s,At = a] = ρπ(s, a).
Following White (2017) and Bojun (2020), we use the ELP formalism to study finite-time decision tasks, which arguably account for most AI tasks encountered in current practice. The ELP model formulates the learning process of such task, which consists of an infinite number of concatenated episodes, each starting and ending at an terminal state. In general, an episode can be arbitrarily long, but will terminate in finite steps with probability 1. The learning agent may choose to use a different behavior policy βt for each step t of the episodic learning process (based on data collected from
1Our state-based reward formulation follows Schulman et al. (2015) and Bojun (2020), and is equivalent to action-based reward formulations in terms of expressiveness. Refer to Appendix A of Bojun (2020) for details.
2Unreachable states are irrelevant to the real world whatsoever, so are excluded from our treatment.
previous steps), and the goal is to have βt converge (as t goes to infinity) towards an optimal policy that maximizes the expected episode-wise cumulative reward:
J(π) . = E ζ∼π [∑T (ζ) t=1 R(St) ]
(1)
where ζ = (S0, S1, S2, . . . ) is an infinite trajectory of the markov chain induced by policy π. Note that the termination time T is a random variable whose value may vary for different trajectory ζ. See Section D.3 for the ELP formulation of machine translation as an example.
A value function Q : S × A → R assigns a real number to each state-action pair (s, a) as the “perceived benefit” of doing action a under state s. We call the set of all possible value functions, the value space, denoted by Q. A value function Q ∈ Q is called an optimal value if (any of the) Q-greedy policy with πQ(a|s) > 0 ⇒ Q(s, a) = maxāQ(s, ā) is an optimal policy. Bellman optimal value is a special optimal value function that is characterized by the Bellman optimality operator. In its general form Degris et al. (2012); Sutton et al. (2011; 2014; 2016), a generalized Bellman optimality operator Bγ : Q → Q transforms a value function Q ∈ Q into another value function BγQ ∈ Q such that for any (s, a) ∈ S ×A,
Bγ Q(s, a) .= ∑ s′∈S P (s′|s, a) · ( R(s′) + γ(s′) ·max a′∈A Q(s′, a′) ) (2)
where γ : S → [0, 1] is a discounting function over the states. As a classic result, if the discounting function equals a constant γc < 1 on every state, the corresponding Bellman optimality operator Bγc has a unique fixed point in the value space of any MDP. However, the fixed point of Bγc is generally not an optimal value with respect to the undiscounted objective (1). In the following, we present a new theorem that guarantees the uniqueness of Bellman fixed point for a more general class of discounting functions, among which a particular “episodic discounting function” gives optimal value w.r.t. objective (1). Both the uniqueness and the optimality are fundamentally rooted from an inherent graph property of ELP-MDPs. See the proof in Appendix A for detailed elaboration. Theorem 1. In any finite Episodic Learning Process (S,A, P,R, ρ0), let γ be any discounting function such that γ(s) < 1 for all terminal state s ∈ S⊥, then
(1) Bγ has a unique fixed point, i.e., the equation Q = BγQ has a unique solution.
(2) The fixed point of Bγ is the limiting point of repeatedly applying Bγ to any Q ∈ Q.
(3) The fixed point of Bγ is an optimal value w.r.t. objective (1) if γ is the following episodic discounting function:
γ epi (s) . = 1[s 6∈ S⊥] = { 1 for s 6∈ S⊥ 0 for s ∈ S⊥ . (3)
Since we focus on optimizing objective (1), in the rest of the paper: Bellman optimality operator, denoted by B .= Bγ epi , refers to the specific operator (2) that uses the particular episodic discounting function (3); accordingly, Bellman optimal value, denoted by Q∗, refers to the unique fixed point of B; and similarly, Bellman optimality equation refers to the fixed-point equation Q = BQ under episodic discounting, or more explicitly, refers to the following system of non-linear equations:
Q(s, a) = ∑ s′∈S max a′∈A P (s′|s, a) · ( R(s′) + γ epi (s ′) ·Q(s′, a′) ) , ∀(s, a) ∈ S ×A (4)
It is worthwhile noting that although the Bellman optimal value function is unique, there can be many optimal value functions in an episodic learning problem. In particular, any value function that gives the same preference order with the Bellman optimality value is an optimal value function.

heading: 3 LAGRANGIAN DUALITY AND MINIMAX THEOREM
text: In this section we study a minimization-based variational treatment to the Bellman optimality equation (4). We will derive a practical episodic learning algorithm based on the theory presented here, and will apply the algorithm to standard machine translation benchmarks in the next section.
Our idea is inspired by the long-known linear programming re-formulation of the closely related optimality equation for state-value functions V : S → R,
V (s) = max a ∑ s′ P (s′|s, a) · ( R(s′) + γ epi (s ′) · V (s′) ) , ∀s. (5)
Both the Q-form optimality equation (4) and the V -form optimality equation (5) are nonlinear due to the max operation inside, but the V -form equation (5) admits a linear re-formulation Puterman (1994):
min V ∑ s∈S ρ0(s) ·V (s) s.t. V (s) ≥ ∑ s′ P (s′|s, a) · ( R(s′)+γ epi (s ′) ·V (s′) ) , ∀(s, a) (6)
Thanks to its linearity, (6) enjoys the standard LP duality properties, and in particular has minimax equality for its corresponding Lagrangian function, which is the basis for a recently revived thread of research on the LP approach to MDP and RL Chen and Wang (2016); Wang (2017); Cho and Wang (2017); Dai et al. (2018); Nachum and Dai (2020).
In model-free learning settings, however, the agent does not know the transition function P , thus cannot directly use a state-value function V to compare the values of different actions (as we do not know which states an action would lead to). For this reason, most value-based algorithms focus on learning the optimal Q functions Watkins (1989); Hasselt (2010); Mnih et al. (2015); Haarnoja et al. (2018). It is thus natural to ask if we can develop a variational approach directly for theQ-form optimality equations (4), similar to what we did to the V -form optimality equations.
Indeed, the Q-form optimality equations (4) can be similarly recast into a constrained optimization problem as follows:
min Q E ζ∼π
[ Q(ST , AT ) ] s.t. Q(s, a) ≥
∑ s′ max a′ P (s′|s, a) · ( R(s′) + γ epi (s ′) ·Q(s′, a′) ) , ∀(s, a) (7)
where π ∈ Π can be an arbitrary policy, and T .= inf{t ≥ 1 : St ∈ S⊥} is the termination time. Unfortunately, unlike the V -form optimality equation for which the nonlinear operation maxa can be “unpacked” into |A| linear constraints (cf. (5) and (6)), the variational formulation (7) of the Q-form optimality equation is still nonlinear, due to the maxa′ “wrapped” inside ∑ s′ . As a result, although (7) can still be written into the Lagrangian form
min Q∈Q max λ≥0 E ζ∼π
[ Q(ST , AT ) ] + ∑ s,a λ(s, a) · ( BQ(s, a)−Q(s, a) ) , (8)
it is unclear if the nonlinear Q-form Lagrangian still enjoys strong duality, a key property for designing effective and principled learning algorithms Wang (2017); Dai et al. (2018).
In the following, we give an affirmative answer to this open question by proving a minimax theorem for the nonlinear Lagrangian of the Q-form Bellman optimality equation (4). As with Theorem 1, the strong Lagrangian duality is also rooted from inherent structures of the episodic learning process. Definition. Given a finite Episodic Learning Process (S,A, P,R, ρ0), a function Lπ : Q × R|S|·|A|≥0 → R is called a Lagrangian function with conjugate policy π if
Lπ(Q,λ) . = E ζ∼π
[ Q(ST , AT ) ] + ∑ s,a λ(s, a) · ( BQ(s, a)−Q(s, a) ) (9)
where π ∈ Π can be an arbitrary policy, and T .= inf{t ≥ 1 : St ∈ S⊥} is the termination time.
Note that the conjugate policy π only determines the distribution of terminal states (and actions) in the first term of Lπ . With any conjugate policy π, the second term of Lπ always uses the Bellman optimality operator B. Let us first confirm that Q∗ is a minimax solution of the Lagrangian function (9), as Lemma 2.1 states. The proof can be found in Appendix B.1. Lemma 2.1. In any finite ELP, for any conjugate policy π, Q∗ ∈ arg min
Q∈Q max λ≥0
Lπ(Q,λ).
Now, we observe that the Lagrangian Lπ has an equivalent form when the Lagrangian multiplier vector is a special vector λπ that is proportional to the stationary distribution of the conjugate policy π (and proportional to the average episode length of π too). Lemma 2.2. In any finite Episodic Learning Process (S,A, P,R, ρ0), for any conjugate policy π, let Lπ be the corresponding Lagrangian, and let λπ be the particular Lagrangian multipliers with λπ(s, a) = ρπ(s, a) ·Eζ∼π[T ], where ρπ is the stationary distribution of π, then
Lπ(Q,λπ) = J(π) + ∑ s6∈S⊥ ∑ a∈A λπ(s, a) · ( max ā Q(s, ā)−Q(s, a) )
(10)
Proof idea: Applying a known ergodic theorem of ELP, we can transform the first term of (9) from an average over trajectories to an average over the state-action space (see Appendix B.2 for details):
E ζ∼π
[ Q(ST , AT ) ] = E ζ∼π [T ] · E S,A∼ρπ [( 1− γ epi (s) ) ·Q(S,A) ] Then substituting the above equation to (9), yields
Lπ(Q,λπ) = Eπ[T ] · E S,A∼ρπ
[ E
S′∼P (·|S,A)
[ R(S′) + γ epi (S
′) ·max a′
Q(S′, a′) ] − γ epi (S)Q(S,A) ] = Eπ[T ] · E
S,A∼ρπ
[ R(S) + γ epi (S) ·max
a′ Q(S, a′)− γ epi (S)Q(S,A) ] = J(π) +
∑ s∈S,a∈A Eπ[T ] · ρπ(s, a) · 1[s 6∈ S⊥] · ( max a′ Q(s, a′)−Q(s, a) )
In above, we have again used the ergodic theorem of ELP to transform Eπ[T ] · ES∼ρπ [R(S)] back to the trajectory space, so as to derive J(π). See Appendix B.2 for the complete proof.
The first term in the dual form of the Lagrangian, i.e. in (10), is the true performance of the conjugate policy π (in terms of objective (1)). Utilizing this fact, we can prove the strong duality property for Lagrangians conjugating with optimal policies, as the following theorem states. Theorem 2 (ELP Minimax Theorem). In any finite Episodic Learning Process (S,A, P,R, ρ0), if µ ∈ Π is an optimal policy, then its conjugate Lagrangian Lµ has strong duality property, with
min Q∈Q max λ≥0 Lµ(Q,λ) = max λ≥0 min Q∈Q Lµ(Q,λ) = J(µ) (11)
Proof idea: Let π∗ denote a Q∗-greedy policy, which is thus an optimal policy.
For any conjugate policy π, since Q∗ is a minimax solution of Lπ (Lemma 2.1), we have minQ maxλ≥0 Lπ(Q,λ) = maxλ≥0 Lπ(Q∗,λ) = Eπ[Q∗(ST , AT )] = Eπ[Qπ∗(ST , AT )]. Because J(π∗) = Qπ∗(s⊥, a) for any terminal state s⊥ ∈ S⊥ and any action a ∈ A (see Appendix A.3), we have Eπ[Qπ∗(ST , AT )] = J(π∗), and so minQ maxλ≥0 Lπ(Q,λ) = J(π∗). Again for any conjugate policy π, due to Lemma 2.2, the Lagrangian dual Lπ(Q,λπ) for the particular multiplier λπ attains its minimum when Q achieves complementary slackness with λπ in the second term of (10), in which case minQ∈Q Lπ(Q,λπ) = J(π). So now, when the conjugate policy π is an optimal policy µ, as assumed in the theorem, we have
max λ≥0 min Q∈Q Lµ(Q,λ) ≥ min Q∈Q Lµ(Q,λµ) = J(µ) = J(π∗) = min Q max λ≥0 Lµ(Q,λ).
The inequality above must actually be an equality because of the universally-held weak duality of the Lagrangian. See Appendix B.3 for a more detailed proof.
From the proof above we can also see that (Q∗, π∗), as the fixed point of Bellman optimality operator B and the corresponding Q∗-greedy policy (resp.), forms a minimax saddle point of the Lagrangian Lµ. In fact, we can derive general conditions for all saddle points of this kind by combining the complementary slackness conditions in (9) and (10). See the proof in Appendix B.4. Proposition 3. In any finite ELP, for any value functionQ ∈ Q and any policy π ∈ Π, letλπ(s, a) = ρπ(s, a) ·Eζ∼π[T ], then Lπ(Q, λ̄) ≤ Lπ(Q,λπ) ≤ Lπ(Q̄,λπ) , ∀Q̄, λ̄, if and only if
(1) BQ(s, a)−Q(s, a) ≤ 0 , ∀(s, a) ∈ S ×A (2) ρπ(s, a) · ( BQ(s, a)−Q(s, a) ) = 0 , ∀(s, a) ∈ S ×A
(3) ρπ(s, a) · ( maxāQ(s, ā)−Q(s, a) ) = 0 , ∀s 6∈ S⊥, a ∈ A

heading: 4 ALGORITHMIC APPLICATION TO MACHINE TRANSLATION
text: From last section we know that the Q-form Lagrangian Lµ has strong duality where µ is optimal policy, and that the special Lagrangian multiplier λµ forms a minimax saddle point (or minimax equilibrium) with the solution of (7). Formally,
max π J(π) = min Q max λ≥0 Lµ(Q,λ) = max λ≥0 min Q Lµ(Q,λ) = min Q Lµ(Q,λµ)
A simple idea to find such minimax saddle point is to minimize the rightmost side of the above equation, that is, to minimize Lµ(Q,λµ) over the value space Q. Although the closed form of the objective function Lµ(Q,λµ) depends on an optimal policy µ (which might appear paradoxical at a first glance as coming up with such an optimal policy was our original goal of learning), note that estimating the gradient of Lµ(Q,λµ) only requires knowledge about a “trace” of the optimal policy µ, instead of explicit knowledge about how µ is constructed. Specifically, for parameterized value function Q(s, a;w), we want to estimate∇wLµ(Q(w),λµ), that is, ∇w ( Eµ[Q(ST , AT ;w)] +Eµ[T ] E
S,A,S′∼ρµ
[ R(S′) + γ epi (S
′)max a′
Q(S′, a′;w)−Q(S,A;w) ]) (12)
in which the optimal policy µ only plays a role in data weighting – it determines the population distribution of the terminal state-actions (ST , AT ), of the terminal time T , and of the transition variable (S,A, S′). This observation inspires a general imitation learning approach, named LAgrangian MINimization (LAMIN) here, in which we try to collect some demonstration data from an optimal policy, based on which we construct an estimator of the Lagrangian gradient (12), then apply standard stochastic gradient procedures to approximate the value function that minimizes Lµ(Q(w),λµ), which corresponds to a minimax point of the original Lagrangian function (9). One may design different estimators of (12) to form different algorithms under the LAMIN idea. In the following we discuss two, and they both perform reasonably well in our validation experiment.
LAMIN1: A technical challenge of estimating (12) is to deal with the max operator in it. One idea is to relax the Lagrangian function into a smoothed version:
Lβµ(Q(w),λµ) = Eµ[Q(ST , AT ;w)]+Eµ[T ]· E S,A,S′∼ρµ E A′∼πβ
Q(w) (S′)
[ δ(S,A, S′, A′;w) ] (13)
where πβQ(w)(a|s) . =
exp ( Q(s,a;w)/β ) ∑ b exp ( Q(s,b;w)/β
) is the Boltzmann distribution with temperature β, and δ(s, a, s′, a′;w) . = R(s′) + γ epi (s ′)Q(s′, a′;w)−Q(s, a;w) is the temporal-difference error.
The smoothed Lagrangian Lβµ subsumes the original Lagrangian Lµ as the limiting case β → 0, while is readily differentiable. Thus, the LAMIN1 algorithm seeks to minimize the smoothed Lagrangian Lβµ via SGD with unbiased gradient estimator of (13). See the pseudo-code as well as more nuanced discussion on this algorithm in Appendix D.1. Among others, it turns out that the β-smoothing trick used in LAMIN1 is more than an approximation heuristic, but may potentially serve as a practical correction to an inherent bias of the minimax points of the Lagrangian that we will discuss in Section 5.
LAMIN2: Another idea is to stick to the exact LagrangianLµ but seek to construct “local” estimator of its gradient in a per-step manner. Specifically, let wt be the parameter vector of Q that is to be updated at a gradient step t, then we can estimate the value of ∇wLµ(Q(w),λµ) ∣∣ w=wt
, for this particular paramter wt, with
∇w ( Eµ[Q(ST , AT ;w)] +Eµ[T ] E
S,A,S′∼ρµ E A′∼πQ(w∗)(S ′)
[ δ(S,A, S′, A′;w) ]) ∣∣∣ w=wt
(14)
where πQ(w∗) is the Q(w∗)-greedy policy (see Section 2). Note that the greedy policy πQ(w∗) in (14) does not depend on w and thus is invariant to ∇w; in contrast, the Boltzmann policy πβQ(w) used by LAMIN1 (see (13)) will take part in the gradient computation.
The consistency of the estimator (14) is characterized by the following mathematical fact. Proposition 4. Let A be a finite action space, Q(s, a;w) a parameterized value function. If with a given parameter vector w∗, Q(w∗) suggests a unique best action amax(s;w∗) . = arg maxa∈A Q(s, a;w ∗) for state s , then
∇w max a∈A Q(s, a;w) ∣∣∣ w=w∗ = E a∼πQ(w∗)(s;w∗) [ ∇w Q(s, a;w) ] ∣∣∣ w=w∗
See the proof in Appendix D.2. In practice, the condition in Proposition 4 – i.e. Q(w∗) gives unique best actions – may be expected for large-scale continuously-valued Q functions, as it is unlikely that the real-numbered values of two actions happen to be identical under stochastically generated w.
Moreover, the local gradient estimator (14) can be combined with the β-smoothing trick by replacing the greedy policy πQ(w∗) in (14) with Boltzmann policy π β Q(w∗), forming the smoothed local gradient estimator that the LAMIN2 algorithm will use. See the pseudo-code in Appendix D.2. Empirically, we found that higher temperatures help slightly improve the performance of LAMIN2.
We now apply LAMIN algorithms to Machine Translation (MT) as a case study. Learning to translate is a highly impactful AI application Wu et al. (2016), and is also an excellent example of episodic learning problem: A translation episode starts with a given sentence in a source language, and the agent takes actions to generate translation tokens one by one in a sequential manner. The episode terminates when the agent outputs a special end-of-sentence (EOS) token, at which point the translation quality is evaluated based on the source sentence and the generated translation sentence. Note that in MT, the episode length (i.e. the length of the translation sentence) is a variable controlled by the agent policy, and the episode-wise reward (i.e. the translation quality) is generally not discounted for long episodes. Just the opposite, standard MT metrics such as BLEU Papineni et al. (2002) uses brevity penalty factor to discount the reward of short (instead of long) translations/episodes. See Appendix D.3 for the exact episodic learning formulation of MT.
Given a source sentence X , most MT metrics measure the quality of a generated translation Y by comparing the similarity between Y and some reference translation Z of X , where Z is typically provided by human expert given X . It follows that the translation policy used by the human expert (which maps X to Z) must be an optimal policy under such metric. Importantly, a trace of the optimal translation policy, in the form of a collection of source-reference sentence pairs, is indeed widely available in standard MT benchmarks, which can be readily used to power LAMIN algorithms. In general, the same idea applies to all machine learning problems with imitation reward where the performance metric is based on similarity comparison to reference/ground-truth outputs.
We tested our algorithmic ideas using the WMT English→German (en2de) dataset, one of the most influential MT benchmarks. We parameterized value function Q with the standard TransformerBase neural network Vaswani et al. (2017), and trained the Transformer-based Q-function using LAMIN1 and LAMIN2, with varying temperature β, then tested the Q-greedy policy with standard BLEU metric using the WMT’14 NewsTest data. See Appendix D.4 for details in experimentation setup.
Figure 1 illustrates the performance of LAMIN1 and LAMIN2 under a spectrum of Boltzmann temperatures, from 0.01 (in which case the algorithm is effectively minimizing the exact Lagrangian function) to 1.0 (which corresponds to the softmax distribution). Table 1 and 2 in Appendix D.4 reports the numerical scores. We see that LAMIN1 has slightly better performance than LAMIN2
under most temperatures. Interesting, higher temperatures tend to help the performance of LAMIN2 but hurt that of LAMIN1 (albeit with limited margins in both cases).
Notably, LAMIN1 with β = 0.01 attains a BLEU score of 27.4 with a greedy policy. In comparison, when standard supervised learning is used, the same neural network famously attains 27.3 only if further combined with a systematic beam search Vaswani et al. (2017). So, our algorithm achieves comparable performance with the state-of-the-art result without time-consuming search procedure at decision/translation time. On the other hand, when incorporating with the same beam search procedure, the value function trained by LAMIN1 (with β = 0.01) attains 28.7, or 1.4 BLEU score higher. Figure 2 shows the learning curves of the algorithm, with and without beam search.

heading: 5 MINIMAX VALUES VS MAXIMIN VALUES
text: The Lagrangian method we explored so far has focused on a particular class of Lagrangian saddle points, the minimax saddle points arg minQ maxλ Lπ , which correspond to exactly the set of optimal solutions for the minimization-form (or primal-form) variational problem (7). Let’s call such a value function, a minimax value function. It seems that existing research on the Lagrangian method have been exclusively focusing on studying minimax value functions (or minimax points of the Lagrangian); see Puterman (1994); Cho and Wang (2017); Dai et al. (2018); Nachum and Dai (2020) for examples. Indeed, as Lemma 2.1 confirmed, the Bellman-optimal valueQ∗, as an optimal value function, is a minimax value function. However, a minimax value function, or equivalently, a minimax solution of Lπ (for any π), is not necessarily an optimal value function. Figure 3 shows an example, where state 4 and 5 are terminal states, from which any action leads to
state 0. Choosing action 1, 2, 3 under state 0 deterministically transits to state 1, 2, 3, respectively. All actions under state 1 lead to state 4, and all actions under state 2 and 3 lead to state 5. The agent only receives non-zero rewards at terminal states, withR(4) = 1,R(5) = 2. The initial state is set to state 4. Clearly, an optimal policy of this ELP should only choose action 2 or 3 (or both), but not action 1, under state 0.
One can verify that for this ELP, the constant value function Qmin(s, a) ≡ 2 is a minimax value function. In particular, we have 2 = Qmin(0, 1) = 0 + 1 · Qmin(1, a) > 1 + 0 · Qmin(4, a) = 1, which does satisfy the constraints of (7) (that Q ≥ BQ). But the constant value function Qmin is certainly not optimal as it assigns the same value to all actions under state 0. Moreover, because Qmin(1, a) > BQmin(1, a) = 1 for all a, the λ
corresponding to Qmin needs to have λ(1, a) = 0 for all a. Such a λ cannot encode any policy.
The problem with minimax value functions is that they only guarantee optimality for optimal actions, but do not enforce sub-optimality for sub-optimal actions (such as the action 1 under state 0). This inadequacy of minimax value functions may explain our experimental observation in last section that adding a softmax temperature in the Lagrangian leads to better value functions (because the softmax averaging motivates, to some extent, the optimizer to downgrade sub-optimal actions to further lower the Lagrangian). Moreover, we remark that this is not only a problem for Q-functions or for episodic discounting, but the minimax solutions of the more popular V -form Lagrangian in discounted-MDPs Dai et al. (2018) suffer from the same issue too (see Appendix C.4 for a counterexample for the minimax V -functions in discounted setting).
Interestingly enough, it turns out that value optimality is indeed guaranteed for another class of saddle points of the Lagrangian – the maximin saddle points. Specifically, with the same argument as in Lemma 2.1 one can show that Q∗, the fixed point of B, is also the optimal solution of the following “mirrored” problem to (7). See Appendix C.1 for the proof. Lemma 5.1. In any finite ELP, Q∗ is an optimal solution of
max Q E ζ∼π
[ Q(ST , AT ) ] s.t. Q(s, a) ≤ BQ(s, a) , ∀(s, a) (15)
for any conjugate policy π ∈ Π. Equivalently, Q∗ ∈ arg max Q∈Q min λ≥0 Lπ(Q,λ).
We call an optimal solution of (15), a maximin value function (with respect to the Lagrangian Lπ). Different from minimax value functions, a maximin value function enforces sub-optimality for all (truly) sub-optimal actions, and at the same time can guarantee optimality for at least one (truly) optimal action. Consequently, a maximin value function always and only induces optimal policy. Theorem 5. In any finite ELP, for any conjugate policy π, let Qmax be an maximin value function of the Lagrangian Lπ – i.e. letQmax be an optimal solution of (15) – thenQmax is an optimal value function, in the sense that Qmax-greedy policy maximizes the episodic-reward objective (1).
Proof idea: First observe that Qmax(s, a) ≤ Q∗ at all (s, a). This is because Qmax, as a feasible solution of (15), has Qmax ≤ BQmax ≤ BBQmax · · · ≤ Q∗. Now Qmax ≤ Q∗ implies that for all actions sub-optimal to Q∗ (under a state), they can only have even lower values in Qmax. So, it is enough to prove that maxaQmax(s, a) = maxaQ∗(s, a) at every non-terminal state s that is reachable by Qmax-greedy policy – in that case the footprint of a Qmax-greedy policy will be a subset of the footprint of a Q∗-greedy policy, in which only Q∗-optimal actions are selected. Note that Qmax’s values on terminal states do not affect its footprint, due to the ELP conditions.
For an arbitrary state-action pair (s, a), let (S ×A)next denote the set of all the non-terminal (s′, a′) pairs that can directly follow (s, a) under the Qmax-greedy policy. We can prove that
Qmax(s, a) = Q ∗(s, a)
⇒ Qmax(s′, a′) = Q∗(s′, a′) and max ā Qmax(s ′, ā) = max ā Q∗(s′, ā) , ∀(s′, a′) ∈ (S ×A)next
which would enable a proof-by-induction, starting from some terminal state where Qmax and Q∗ equal to each other (such terminal state exists because both Qmax and Q∗ are optimal solutions of (15)). See Appendix C.2 for the complete proof.
In light of the symmetry breaking between the minimax-type and the maximin-type Lagrangian saddle points (in terms of optimality), we believe the latter, as well as minimax value functions and the corresponding dual-form variational problem (15), deserve more attentions from the community.

heading: 6 RELATED WORKS
text: A main challenge of this work comes from the non-linearity in both the Bellman optimality equation and the associated Q-form Lagrangian being studied. In contrast, most related research focused on linear treatments to related objects. For a linear policy-specific Bellman operator Bπ (which replaces maxa with a linear average), White (2017) proved that Bπ has unique fixed point in episodic learning setting. The linear operator Bπ leads to a LP (re-)formulation, based on which the “DICE” family of policy evaluation algorithms were developed Nachum et al. (2019); Yang et al. (2020). On the policy optimization side, an active thread of research used saddle-point optimization to solve the linear V - form Lagrangian, again relying on the generic LP duality inherited from the linear treatment Chen and Wang (2016); Wang (2017); Cho and Wang (2017); Dai et al. (2018); Chen et al. (2018); Serrano and Neu (2020); Si et al. (2004). The underlying techniques in these linear settings are not directly applicable to our nonlinear treatment in this work.
The disparity between discounted formalism and episodic learning practice is well recognized in reinforcement learning literature. The RL textbook Sutton and Barto (2018) devoted its Section 10.4 to the issue of deprecating the discounted formalism. The DP textbook Bertsekas and Tsitsiklis (1996) subsumed the discounted setting as a special case of an finite-termination setting. A special case of Theorem 1 dedicated to episodic discounting was proved by Bertsekas and Tsitsiklis (1991).
The WMT machine translation benchmark used in this paper is a fruitful driver of the rapid technical advances in Neural Machine Translation in recent years Wu et al. (2016); Koehn and Knowles (2017); Vaswani et al. (2017). MDP-based techniques have been actively studied as a promising method for this problem Ranzato et al. (2016); Edunov et al. (2018); Bahdanau et al. (2017); Wu et al. (2018), but with relatively limited effectiveness observed so far Choshen et al. (2020). To our best knowledge, the LAMIN algorithm is one of the first MDP-based solutions that is able to train Transformer-scale neural networks independently (without pretraining or ensemble learning with the aid of other techniques) to attain competitive performance on the WMT benchmark.

heading: 7 REPRODUCIBILITY STATEMENT
text: Every theorem, lemma, proposition in the main text or in the appendix of this paper has been given complete proof (unless already proved in other papers in which case the reference was given). For the experiment part, detailed experimentation setting was described in Appendix D.4. Experimentation code was attached in Supplementary Material.

heading: A PROOFS OF BELLMAN OPTIMALITY
text: In this section we prove the uniqueness and optimality of the solution of generalized Bellman equation in episodic learning setting.

heading: A.1 PROPERTIES OF EPISODIC LEARNING PROCESS
text: This section presents a series of mathematical properties of ELP; the first three is known, the rest are new. Most of our theoretical results in this paper are based on these properties.
Proposition 6. For any policy π in any ELP, the Markov chain induced by policy π is irreducible: ∀s, s′ ∈ Sπ , ∑∞ τ=1 Pπ[St+τ = s
′|St = s] > 0. (Bojun (2020), Lemma 1.1) Proposition 7. For any policy π in any ELP, the Markov chain induced by policy π is positive recurrent: ∀s ∈ Sπ , Eπ[Ts] <∞, where Ts is the recurrent time of s. (Bojun (2020), Lemma 1.2) Proposition 8. For any policy π in any ELP, let f : S → R be a real-valued function over the states, we have (Bojun (2020), Theorem 4)
E S∼ρπ
[ f(S) ] = E ζ∼π [ T∑ t=1 f(St) ] / E ζ∼π [ T ]
(16)
We write Q1 ≥ Q2 for two value functions Q1, Q2 ∈ Q iff Q1(s, a) ≥ Q2(s, a), ∀(s, a) ∈ S × A. First observe that the generalized Bellman optimality operator (2) is monotonic.
Proposition 9. For any discounting function γ : S → [0, 1], the generalized Bellman optimality operator Bγ is a monotonic operator: Q1 ≥ Q2 ⇒ BγQ1 ≥ BγQ2 , for all Q1, Q2 ∈ Q. Proof. Rewrite (2) asBγQ(s, a) = ∑ s′ ( P (s′|s, a)·γ(s′) ) ·maxa′ Q(s′, a′)+ ∑ s′ P (s
′|s, a)R(s′). As Q1(s′, a′) ≥ Q2(s′, a′) for all (s′, a′), we have maxa′ Q1(s′, a′) ≥ maxa′ Q2(s′, a′) for all s′, and thus ∑ s′ ( P (s′|s, a) · γ(s′) ) ·maxa′ Q1(s′, a′) ≥ ∑ s′ ( P (s′|s, a) · γ(s′) ) ·maxa′ Q2(s′, a′) because P (s′|s, a) · γ(s′) ≥ 0 for all s′.
Now, as a well-known special case, if the discounting function is a constant less than 1, the corresponding Bellman optimality operator is a contraction mapping with respect to the maximum-norm distance over the value space Q, which guarantees, by the Banach fixed-point theorem, that there is a special value function Q∗c which is both the unique fixed point (Q ∗ c = BcQ∗c ) and the unique limiting point of the Bellman optimality operator (Q∗c = lim n→∞ (Bc)nQ , ∀Q ∈ Q).
Unfortunately, Bγ loses the above contraction property under general discounting. Proposition 10. In any ELP where there is a single state s∗ and a single action a∗ such that doing a∗ under s∗ only goes to non-terminal states s′, i.e. ∑ s′ 6∈S⊥ P (s
′|s∗, a∗) = 1, the Bellman operator B with episodic discounting (3) is not a contraction mapping with respect to the maximum-norm distance: For some Q1, Q2 ∈ Q, maxs,a |Q1(s, a)−Q2(s, a)| = maxs,a |BQ1(s, a)− BQ(s, a)|.
Proof. Consider two value functions with constant difference everywhere: Q1(s, a) ≡ Q2(s, a)+δ, for some δ > 0. Clearly, maxs,a |Q1(s, a) − Q2(s, a)| = δ. On the other hand, for any (s, a) we have |BQ1(s, a)− BQ2(s, a)| = ∑ s′∈S P (s
′|s, a) · γ(s′) · δ ≤ δ, which equals δ at the particular (s∗, a∗) because ∑ s′∈S P (s ′|s∗, a∗) · γ(s′) · δ = ∑ s′ 6∈S⊥ P (s ′|s∗, a∗) · 1 · δ = δ.
Proposition 10 seems to be a negative result for most non-trivial ELPs – it says B is not a contraction mapping unless we always has a chance to immediately terminate an episode no matter where we are (even when we are at terminal states, at which point the episode has not effectively started yet).
But interestingly, it turns out that the episodic Bellman optimality operator B still has unique fixed and limiting point in all finite ELPs, not because of the contraction property as in discounted-MDPs, but because of a graph property dedicated to the family of ELPs, as will be shown next.
Lemma 2.1. In any Episodic Learning Process (S,A, P,R, ρ0), for any subset of states Ω ⊆ S and any policy π, let Cπ(Ω) . = { s′ : ∃s ∈ Ω, Pπ[St+1 = s′|St = s] > 0 } be the set of all successor states that are one-step reachable from Ω under π, and let Sπ be the set of states that are ever reachable under π (from initial states, in finite steps), then Cπ(Ω) ⊆ Ω only if Sπ ⊆ Ω.
Proof. For contradiction suppose Cπ(Ω) ⊆ Ω and yet there is a π-reachable state s∗ ∈ Sπ that is outside the given subset Ω. We will show that in this case, it is possible to construct a policy µ (that is possibly different from π) such that s∗ is also reachable under µ, and that µ admits an infinite trajectory that passes through s∗ and never return back to s∗ (see Figure 4 below). This would contradict with Proposition 7 above which asserts that a µ-reachable state s∗ must have finite mean recurrence time under µ.
Specifically, first observe that Cπ(Ω) ⊆ Ω means Ω is a absorbing subset under π so that once we get into Ω we would never get out.
Then observe that the existence of a π-reachable state s∗ 6∈ Ω entails that Ω cannot contain all initial states, as otherwise from any of the initial states (in Ω) we cannot go outside the absorbing subset Ω to reach s∗. Let s0 be such an initial state that is outside Ω, from which we can reach s∗ under π (as assumed) without reaching any state in Ω in the middle (otherwise we never reach s∗).
Now, pick an arbitrary state s+ in Ω, there must be some policy β under which we can reach s+ from s0 (as states unreachable under any policy should not show up in S in the first place, see Section 2). Without loss of generality we can again assume that we can reach s+ from s0 under β without going through any other state in Ω in the middle because otherwise we can simply re-define s+ to be the first state in Ω that we have encountered on the path (from s0 to the “old s+”).
So far we have obtained an initial state s0 outside Ω, from which there is an admissible path s0 π→ s∗ for policy π, and an admissible path s0 β→ s+ for policy β. Both paths only contain states outside Ω (except s+). Now we construct policy µ as follows: we ask µ to copy π on states in the path
s0 π→ s∗, and ask µ to copy β on states in the path s0 β→ s+. If a state shows up in both paths, we ask µ to be a (probability) mixture of both π and β on that state. Clearly, we can reach both s∗ and s+ from s0 under µ (note that the policy mixing only decreases the probabilities to reach s∗ and s+ but does not change their reachability).
By Proposition 6, since both s∗ and s+ are in Sµ, we must be able to go from s∗ to s+ under µ. Note that so far we have only prescribed µ’s behavior outside Ω. Our final step is to ask µ to copy π for all states in Ω, so that Ω is also an absorbing subset for µ, meaning that once we reach s+ (from s∗), we will be stuck in Ω without going back to s∗ (which is outside Ω by our assumption at the beginning of the proof). In this way, we have constructed a policy µ, under which we can first go from s0 to s∗, then go from s∗ to s+, and then be stuck in Ω forever without returning to s∗. A possibility of such an infinite trajectory under µ directly contradicts with Proposition 7.

heading: A.2 PROOF OF THEOREM 1 (1) (2)
text: Lemma 2.1 says that in ELPs, any absorbing subset of S under a policy must contain all reachable states of this policy. In particular, there cannot exist an absorbing subset outside the reachable set Sπ . Utilizing this fact, we can prove the first two statements of Theorem 1.
(Theorem 1 (1) (2)). In any ELP (S,A, P,R, ρ0) with finite state space S and finite action space A, let γ be any discounting function such that γ(s) < 1 for all terminal state s ∈ S⊥, then
(1) Bγ has a unique fixed point, i.e., the equation Q = BγQ has a unique solution.
(2) The fixed point of Bγ is also the limiting point of repeatedly applying Bγ to any Q ∈ Q.
Proof. For any two value functions Q1 and Q2, consider their L∞-distance d(Q1, Q2) . = max
s∈S ds(Q1, Q2)
where ds(Q1, Q2) . = max
a∈A |Q1(s, a)−Q2(s, a)|.
As usual, we have
d(BγQ1,BγQ2) = max s∈S max a∈A ∣∣∣ ∑ s′∈S P (s′|s, a) · γ(s′) · ( max a′1 Q1(s ′, a′1)−max a′2 Q2(s ′, a′2) ) ∣∣∣ ≤ max
s∈S max a∈A ∑ s′∈S P (s′|s, a) · γ(s′) · ∣∣∣ max a′1 Q1(s ′, a′1)−max a′2 Q2(s ′, a′2) ∣∣∣ ≤ max
s∈S max a∈A ∑ s′∈S P (s′|s, a) · γ(s′) ·max a′ ∣∣∣ Q1(s′, a′)−Q2(s′, a′) ∣∣∣ = max
s∈S max a∈A ∑ s′∈S P (s′|s, a) · γ(s′) · ds′(Q1, Q2). (17)
Traditionally, it was assumed that γ(s′) ≡ γc < 1 for all states, thus the γ(s′) term in (17) can be readily moved out of the sum, immediately yielding d(BQ1,BQ2) ≤ γc · d(Q1, Q2). When γ(s′) is not constant and is allowed to be 1 for non-terminal states, applying the operator Bγ to Q1 and Q2 cannot guarantee to reduce d(Q1, Q2), as discussed in Proposition 10.
However, by utilizing the graph property as proved in Lemma 2.1, we can show that Bγ guarantees to reduce the per-state distance ds(Q1, Q2) at some “support dimension” s, so that if we repeatedly apply Bγ , the set of “support states” will become smaller and smaller and eventually become empty at which point the overall L∞-distance gets reduced (by the composite operator of repeatedly applying Bγ). Specifically, for given Q1, Q2 ∈ Q, we will identify a sequence of proper subsets of states S = d-support(0) ⊃ d-support(1) ⊃ d-support(2) ⊃ · · · ⊃ d-support(|S|) (18)
such that
s 6∈ d-support(k) ⇒ ∀i ≥ k, ds ( (Bγ)iQ1, (Bγ)iQ2 ) < d(Q1, Q2) (19)
for all k ≥ 0. The construction of the subsets is by induction, and is based on the following insight: Lemma 2.2. Under the condition of Theorem 1 , if (19) holds for k − 1, then
∃s∗ ∈ d-support(k), such that ∀i ≥ k, ds∗ ( (Bγ)iQ1, (Bγ)iQ2 ) < d(Q1, Q2)
Proof. We first refactor (17) a little bit, which actually holds in a per-state sense, so
ds(BγQ1,BγQ2) ≤ max a∈A ∑ s′∈S P (s′|s, a) · γ(s′) · ds′(Q1, Q2)
≤ max s′∈S
ds′(Q1, Q2) = d(Q1, Q2). (20)
Recursively applying (20) gives
ds ( (Bγ)kQ1, (Bγ)kQ2 ) ≤ max
a∈A ∑ s′∈S P (s′|s, a) · γ(s′) · ds′ ( (Bγ)k−1Q1, (Bγ)k−1Q2 )
= ∑ s′∈S P (s′|s, amax(s)) · γ(s′) · ds′ ( (Bγ)k−1Q1, (Bγ)k−1Q2 )
≤ ∑ s′∈S P (s′|s, amax(s)) · γ(s′) · d(Q1, Q2) ≤ d(Q1, Q2)
(21)
where amax(s) . = arg maxa ∑ s′∈S P (s ′|s, a) · γ(s′) · ds′ ( (Bγ)k−1Q1, (Bγ)k−1Q2 ) .
Now we prove that the inequality (21) must be strict for some support-state s∗ ∈ d-support(k). In particular, we will prove∑
s′∈S P (s′|s∗, amax(s∗)) · γ(s′) · ds′
( (Bγ)k−1Q1, (Bγ)k−1Q2 ) < d(Q1, Q2) (22)
Case 1: There is an s∗ ∈ d-support(k) with ∑ s′∈d-support(k) P ( s′|s∗, amax(s∗) ) < 1. In this case it’s possible to go from s∗ to some s′ outside the subset of d-support(k). For such s′ we have γ(s′) ·ds′ ( (Bγ)k−1Q1, (Bγ)k−1Q2 ) < d(Q1, Q2) (because (19) holds for k− 1 as assumed), thus ∑ s′∈S P (s′|s∗, amax) · γ(s′) · ds′ ( (Bγ)k−1Q1, (Bγ)k−1Q2 )
< ∑
s′ 6∈d-support(k)
P (s′|s∗, amax) · d(Q1, Q2) +
∑ s′∈d-support(k) P (s′|s∗, amax) · γ(s′) · ds′ ( (Bγ)k−1Q1, (Bγ)k−1Q2 )
≤ ∑
s′ 6∈d-support(k)
P (s′|s∗, amax) · d(Q1, Q2) + ∑
s′∈d-support(k)
P (s′|s∗, amax) · d(Q1, Q2)
= d(Q1, Q2).
Case 2: For all s ∈ d-support(Q1, Q2), ∑ s′∈d-support(Q1,Q2) P ( s′|s, amax(s) ) = 1. This is equivalent to say that there exists a policy – which would choose amax(s) under the corresponding s – such that it is impossible to move from any state in d-support(k) to a state outside d-support(k) under this policy. In other words, let µ be such a policy, we have
Cµ ( d-support(k) ) ⊆ d-support(k)
which, by Lemma 2.1, entails Sµ ⊆ d-support(k), (23)
(23) literally says that the set of support-states d-support(k), as an absorbing subset under µ as assumed in case 2, must contain all reachable states under µ. By the definition of ELP, these µreachable states must in turn contain at least one terminal state (otherwise we would not have finite episode under µ at all). Let s⊥ ∈ Sµ ⊆ d-support(k) be such a reachable terminal state under µ. Since s⊥ is reachable under µ (and µ chooses amax(s) under each s), there must also be an s∗ ∈ Sµ such that P (s⊥|s∗, amax(s∗)) > 0. Because γ(s⊥) < 1 as assumed as the general condition of Theorem 1, we have∑
s′∈S P (s′|s∗, amax) · γ(s′) · ds′
( (Bγ)k−1Q1, (Bγ)k−1Q2 ) ≤
∑ s′∈S P (s′|s∗, amax) · γ(s′) · d(Q1, Q2)
= ( P (s⊥|s∗, amax) · γ(s⊥) + ∑ s′∈S\{s⊥} P (s′|s∗, amax) · γ(s′) ) · d(Q1, Q2)
< ( P (s⊥|s∗, amax) + ∑ s′∈S\{s⊥} P (s′|s∗, amax) · γ(s′) ) · d(Q1, Q2)
≤ ( P (s⊥|s∗, amax) + ∑ s′∈S\{s⊥} P (s′|s∗, amax) ) · d(Q1, Q2)
= d(Q1, Q2).
Now we have proved that ∃s∗ ∈ d-support(k), ds∗ ( (Bγ)kQ1, (Bγ)kQ2 ) < d(Q1, Q2). It is
straightforward to verify that the same proof idea applies to all i > k too (in case 1, we still have γ(s′) · ds′ ( (Bγ)i−1Q1, (Bγ)i−1Q2 ) < d(Q1, Q2) because (19) holds for k − 1; in case 2, the
existence of s⊥ is a graph property that is independent of how many times Bγ is applied).
With Lemma 2.2, we can construct each subset d-support(k) in (18) by removing the s∗ from d-support(k − 1). It’s clear that (19) will hold for the sequence of support subsets thus constructed. In particular, note that Lemma 2.2 holds for k = 0 without the inductive condition (that (19) holds for k − 1) because in this case it’s impossible to go outside d-support(0) = S as in Case 1, so only Case 2 is possible (and in this case the proof does not need the inductive condition).
Now, (18) implies that d-support(|S|) is empty set. Substituting this observation into (19), yields ds ( (Bγ)|S|Q1, (Bγ)|S|Q2 ) < d(Q1, Q2) for all s ∈ S, which means d ( (Bγ)|S|Q1, (Bγ)|S|Q2 ) <
d(Q1, Q2). In other words, the existence of the d-support sequence satisfying (18) and (19) means that the composite operator of “repeatedly applying Bγ for |S| times” (i.e. (Bγ)|S|) guarantees to reduce the L∞-distance of every value function pair in Q. Moreover, note that the initial values of Q1 and Q2 do not determine how much percentage the distance between them will reduce – the values of Q1 and Q2 only affect what amax is in (22), There are |S| · |A| · |S| possible transition probabilities in total, and |S| possible γ-values in (22), so no matter how amax (which is a policy) and arg maxd change over iterations, they just select a different subset from the |S|3 · |A| possible terms. There are a finite number of such subsets, thus when the sum of the subset is less than 1, there must be an absolute upper bound 1 − rmin for the subset sum. This upper bound ratio of distance reduction can be extremely close to 1, especially after repeating the process for |S| times, but still, it is a fixed number smaller than 1, and thus the operator (Bγ)|S| is a contraction mapping, and thus it has a unique fixed point (by the Banach fixed point theorem).
Our last step is to prove that the unique fixed point of the composite operator (Bγ)|S| is also the unique fixed (and limiting) point of the original Bellman operator Bγ . It is easy to see that Bγ cannot have two fixed points, as otherwise their distance could not get reduced by repeatedly applying Bγ for |S| times. To show that Bγ does have a fixed point, we prove the following slightly stronger result (in the following lemma we use B to denote the generalized Bellman operator for brevity).
Lemma 2.3. Under the condition of Theorem 1, let Q∗ be the unique fixed point of (B)|S|,
Q∗ = lim n→∞ (B)nQ , ∀Q ∈ Q (24)
and Q∗ = BQ∗ (25)
Proof. We first prove that (24) holds for all Q− with Q− ≤ BQ−. 3 Because B is monotonic operator, for such Q− we have
Q− ≤ BQ− ≤ (B)2Q− · · · ≤ (B)|S|Q− · · · ≤ (B)2·|S|Q− · · · ≤ Q∗ (26)
where Q∗ being the limit of the above sequence is guaranteed by the contraction property of B|S|. Recall that Q1 ≤ Q2 means ∀s, a Q1(s, a) ≤ Q2(s, a) and that d(Q1, Q2) = maxs,a |Q1(s, a) − Q2(s, a)|, we see that the value functions in the above (monotonic) sequence must have non-increasing distances to Q∗. On the other hand, as the subsequence Q−, (B)|S|Q−, (B)2·|S|Q−, (B)3·|S|Q−, . . . converges to Q∗, we know that for any > 0, there exists an i∗ such that d ( (B)i∗·|S|Q−, Q∗ ) < , and thus d ( (B)iQ−, Q∗ ) < for all integer i > i∗
due to the monotonicity, which literally means that the overall sequence (26) also converges to Q∗.
Now because Q∗ = lim n→∞ (B)nQ−, we must have BQ∗ = B lim n→∞ (B)nQ− = lim n→∞ (B)nQ− = Q∗, thus (25) holds, and that Q∗ is a fixed point of B.
3Such Q− guarantees to exist. In fact, every on-policy value function is such a Q−; see A.3 for details.
Finally, because Q∗ = BQ∗, for any Q ∈ Q (not necessarily with Q ≤ BQ this time), we have d(BQ,Q∗) = d(BQ,BQ∗) ≥ d(Q,Q∗), where the inequality is by (17). Again, d(BQ,Q∗) ≥ d(Q,Q∗) means the sequence (26) has non-increasing distances to Q∗, this time for all Q ∈ Q. So, by the same logic as above, Q∗ must be the limit of the sequence Q,BQ, (B)2Q, . . . – again, for all Q ∈ Q this time (not necessarily with Q ≤ BQ).
Note that the specific form of the γ-function does not play a role in the proof of Lemma 2.3 as presented above, so (25) and (24) apply to all Bγ that complies with the condition of Theorem 1. We thus have completed the proof of statement (1) and (2) in Theorem 1.
In comparison, the classic Bellman optimality property requires γ(s) < 1 at every state s ∈ S, while Theorem 1 only requires γ(s) < 1 at terminal states. On the other hand, the classic result applies to all MDPs, while Theorem 1 is fundamentally based on unique structures of episodic learning process. Importantly, the episodic discounting function that we use in ELP – i.e. (3) – does satisfy the condition in Theorem 1.

heading: A.3 PROOF OF THEOREM 1 (3)
text: Finally, we prove statement (3) of Theorem 1 which asserts that Q∗, as the unique fixed point of the Bellman operator under episodic discounting, is indeed an optimal value function, in the sense that a Q∗-greedy policy is an optimal policy with respect to the undiscounted objective (1).
(Theorem 1 (3)). In any finite ELP, let Q∗ be the fixed point of B (i.e. the solution of (4)), let π∗ be a policy such that π∗(a|s) > 0 only if Q∗(s, a) = maxāQ∗(s, ā), then J(π∗) = maxπ∈Π J(π), where J is the episodic-reward objective (1).
Proof. Every policy π is coupled with a (unique) on-policy value functionQπ which assigns values to (s, a) pairs according to the conditional expectations of the episode-wise cumulative reward under the policy π. Formally,
Qπ(s, a) . = E {St,At}∼π [ T∑ t=1 R(St) ∣∣∣S0 = s,A0 = a] , ∀(s, a) ∈ S ×A (27)
Comparing (27) with the definition of the episodic-reward objective J (i.e. with (1)), and by the ELP conditions, we see that for any policy π, its performance score equals its on-policy terminal values: J(π) = Qπ(s⊥, a) , ∀s⊥ ∈ S⊥ , ∀a ∈ A. (28) We will prove that for the Q∗-greedy policy π∗, we have Qπ∗ ≥ Qπ for all π ∈ Π, which would entail that J(π∗) ≥ J(π). First observe that Qπ∗ = Q∗, that is, the value function Q∗ which induced the greedy policy π∗ is also the on-policy value function of π∗. Specifically, with the episodic γ-function (3), for any (s, a), by the definition of π∗ we have
Q∗(s, a) = BQ∗(s, a)
= E S′∼P (s,a) max a′
[ R(S′) + γ(S′) ·Q∗(S′, a′) ] = E S′∼P (s,a) E A′∼π∗(S′) [ R(S′) + γ(S′) ·Q∗(S′, A′) ] (29)
= E {S1,A1}∼π∗
[ R(S1) + γ(S1) ·Q∗(S1, A1) ∣∣∣S0 = s,A0 = a] = E {S1,A1,S2,A2}∼π∗ [ R(S1) + γ(S1)R(S2) + γ(S1)γ(S2) ·Q∗(S2, A2)
∣∣∣ S0 = s,A0 = a] = E {St,At}∼π∗ [ T∑ t=1 R(St) ∣∣∣S0 = s,A0 = a]
= Qπ∗(s, a) (30)
Connecting (29) and (30) and generalizing to arbitrary π yields that for any policy π ∈ Π, we obtain Qπ ≤ BQπ; specifically,
Qπ(s, a) = E S′∼P (s,a) E A′∼π(S′)
[ R(S′) + γ(S′) ·Qπ(S′, A′) ] ≤ E
S′∼P (s,a) max a′
[ R(S′) + γ(S′) ·Qπ(S′, a′) ] = BQπ(s, a)
In other words, the set {Q : ∃π ∈ Π, Q = Qπ} is a subset of the set {Q : Q ≤ BQ}. Now, because Q∗ is a maximum value-function of the set {Q ≤ BQ} which contains all on-policy value functions as a subset, and becauseQ∗ itself is also an on-policy value function (asQ∗ = Qπ∗ ), it must follow that Q∗ is also a maximum value-function of the subset {Qπ}. Thus we have proved that Qπ∗ = Q∗ ≥ Qπ for all π ∈ Π, as desired.

heading: B PROOFS OF MINIMAX DUALITY

heading: B.1 PROOF OF LEMMA 2.1
text: (Lemma 2.1). In any finite ELP, for any conjugate policy π, Q∗ ∈ arg min Q∈Q max λ≥0 Lπ(Q,λ).
Q∗ is an optimal solution of (7) because B is monotonic, so for Q with Q ≥ BQ we have Q ≥ BQ ≥ (B)2Q · · · ≥ Q∗. The objective function of (7) is some probabilistic average over the values at terminal states (and actions), which clearly attains minimum for the per-state-action minimum value function Q∗.
Due to standard Lagrangian duality, a value function is an optimal solution of (7) if and only if it is a minimax solution of (8). In particular, only value functions with Q ≥ BQ can prevent maxλ Lπ(Q,λ) from being arbitrarily large, and for those Q’s, maxλ Lπ(Q,λ) = Eζ∼π [ Q(ST , AT ) ] under the complementary slackness condition, whose value attains minimum at Q∗ as proved.

heading: B.2 PROOF OF LEMMA 2.2
text: (Lemma 2.2). In any finite Episodic Learning Process (S,A, P,R, ρ0), for any conjugate policy π, let Lπ be the corresponding Lagrangian, and let λπ be the particular Lagrangian multipliers with λπ(s, a) = ρπ(s) · π(a|s) ·Eζ∼π[T ], where ρπ is the stationary distribution of π, then
Lπ(Q,λπ) = J(π) + ∑ s6∈S⊥ ∑ a∈A λπ(s, a) · ( max ā Q(s, ā)−Q(s, a) )
By Proposition 8, with f(s) = EA∼π(s) [ 1[s ∈ S⊥] ·Q(s,A) ] , we have
E ζ∼π
[ Q(ST , AT ) ] = E S1..T∼π [ T∑ t=1 f(St) ] = Eζ∼π[T ] · E S∼ρπ E A∼π(S) [ 1[S ∈ S⊥] ·Q(S,A) ]
So, for any Q ∈ Q, we have
Lπ(Q,λπ)
=Eζ∼π[T ] · E S,A∼ρπ
[ 1[S ∈ S⊥] ·Q(S,A) ] + Eζ∼π[T ] · E
S,A∼ρπ
[ BQ(S,A)−Q(S,A) ] =Eζ∼π[T ] · E
S,A∼ρπ
[ 1[S ∈ S⊥] ·Q(S,A)−Q(S,A) ] +
Eζ∼π[T ] · E S,A∼ρπ
[ E
S′∼P (S,A)
[ R(S′) + γ(S′) ·max
a′ Q(S′, a′) ]] =−Eζ∼π[T ] · E
S,A∼ρπ
[ 1[S 6∈ S⊥] ·Q(S,A) ] + Eζ∼π[T ] · E
S′∼ρπ
[ R(S′) + γ(S′) ·max
a′ Q(S′, a′) ] =Eζ∼π[T ] · E
S∼ρπ
[ R(S) ] + Eζ∼π[T ] · E
S,A∼ρπ
[ 1[S 6∈ S⊥] · ( max a Q(S, a)−Q(S,A) )]
=J(π) + Eζ∼π[T ] · ∑
s∈S,a∈A ρπ(s) · π(a|s) · 1[s 6∈ S⊥] ·
( max ā Q(s, ā)−Q(s, a) )
=J(π) + Eζ∼π[T ] · ∑
s∈S\S⊥
∑ a∈A ρπ(s) · π(a|s) · ( max ā Q(s, ā)−Q(s, a) )
Note that in above for Eζ∼π[T ] ·ES∼ρπ [ R(S) ] = J(π) we have again used the transformation of
Proposition 8, with f(s) = R(s).

heading: B.3 PROOF OF THEOREM 2
text: (ELP Minimax Theorem). In any finite Episodic Learning Process (S,A, P,R, ρ0), if µ ∈ Π is an optimal policy, then its conjugate Lagrangian Lµ has strong duality property, with
min Q∈Q max λ≥0 Lµ(Q,λ) = max λ≥0 min Q∈Q Lµ(Q,λ) = J(µ) (31)
Let π∗ be a Q∗-greedy policy, which is thus an optimal policy.
For any conjugate policy π, since Q∗ is a minimax solution of Lπ (Lemma 2.1), we have minQ maxλ≥0 Lπ(Q,λ) = maxλ≥0 Lπ(Q∗,λ) = Eπ[Q∗(ST , AT )]. By (30) in A.3 we have Eπ[Q∗(ST , AT )] = Eπ[Qπ∗(ST , AT )]. By (28) in A.3 we further have Eπ[Qπ∗(ST , AT )] = J(π∗). Connecting these results together gives
min Q max λ≥0
Lπ(Q,λ) = J(π∗). (32)
Again for any conjugate policy π, due to Lemma 2.2, the Lagrangian function has the dual form (10) under the particular multiplier λπ , as copied below
Lπ(Q,λπ) = J(π) + ∑ s6∈S⊥ ∑ a∈A λπ(s, a) · ( max ā Q(s, ā)−Q(s, a) )
The first term above is a constant that does not change with Q, and in the second term both λπ(s, a) and maxāQ(s, ā) − Q(s, a) are nonnegative (for any Q and π), so the sum of the two terms, i.e. Lπ(Q,λπ), attains its minimum when Q achieves complementary slackness with λπ , in which case
min Q∈Q
Lπ(Q,λπ) = J(π). (33)
So now, when the conjugate policy π is an optimal policy µ, as assumed in the theorem, we have
max λ≥0 min Q∈Q Lµ(Q,λ) ≥ min Q∈Q Lµ(Q,λµ) = J(µ) = J(π∗) = min Q max λ≥0 Lµ(Q,λ).
Due to weak minimax duality, maxλ≥0 minQ∈Q Lµ(Q,λ) ≤ minQ maxλ≥0 Lµ(Q,λ), which universally holds, thus the inequality above must actually be an equality, as desired.

heading: B.4 PROOF OF PROPOSITION 3
text: (Proposition 3). In any finite ELP, for any value function Q ∈ Q and any policy π ∈ Π, let λπ(s, a) = ρπ(s, a) ·Eζ∼π[T ], where ρπ(s, a) . = ρπ(s) · π(a|s), then
Lπ(Q, λ̄) ≤ Lπ(Q,λπ) ≤ Lπ(Q̄,λπ) , ∀Q̄, λ̄ if and only if
(1) BQ(s, a)−Q(s, a) ≤ 0 , ∀(s, a) ∈ S ×A (2) ρπ(s, a) · ( BQ(s, a)−Q(s, a) ) = 0 , ∀(s, a) ∈ S ×A
(3) ρπ(s, a) · ( maxāQ(s, ā)−Q(s, a) ) = 0 , ∀s 6∈ S⊥, a ∈ A
The “if” part is straightforward: Condition (1) and (2) immediately gives Lπ(Q,λπ) = Eζ∼π[Q(ST , AT )] = maxλ̄≥0 Lπ(Q, λ̄). On the other hand, condition (3) entails that the second term in dual-form Lagrangian (10) is zero, so Lπ(Q,λπ) = J(π). By (33) in B.3 we have minQ̄ Lπ(Q̄,λπ) = J(π), thus Lπ(Q,λπ) = minQ̄ Lπ(Q̄,λπ). Now we prove the “only if” part, for which we resort to the general saddle-point condition: Under given conjugate policy π, a (Q,λ) pair is a minimax equilibrium (or minimax saddle-point) of function Lπ(Q,λ) if and only if
(i) min Q̄∈Q max λ̄≥0 Lπ(Q̄, λ̄) = max λ̄≥0 min Q̄∈Q Lπ(Q̄, λ̄) = Lπ(Q,λ),
(ii) Q ∈ arg min Q̄∈Q max λ̄≥0 Lπ(Q̄, λ̄),
(iii) λ ∈ arg max λ̄≥0 min Q̄∈Q Lπ(Q̄, λ̄).
By condition (ii), if (Q,λπ) form a minimax equilibrium, thenQmust be a minimax value function. From B.1 we know that such minimax value function must have Q ≥ BQ (condition (1)). By condition (i) and by (32) in B.3 we know that Lπ(Q,λπ) = minQ̄∈Qmaxλ̄≥0 Lπ(Q̄, λ̄) = J(π∗) = Eζ∼π[Q(ST , AT )]. In other words, ∑ s,a λπ(s, a) · ( BQ(s, a) − Q(s, a) ) , as the second term in Lπ(Q,λπ), needs to be zero. Because λπ(s, a) = ρπ(s, a) · Eζ∼π[T ] where Eζ∼π[T ] > 0, and because BQ ≤ Q as proved, the only way to make the term zero is to have ρπ(s, a)· ( BQ(s, a)−
Q(s, a) ) = 0 for each and every (s, a) (condition (2)).
Moreover, since Lπ(Q,λπ) = minQ̄ Lπ(Q̄,λπ) as assumed, by (33) in B.3 we have Lπ(Q,λπ) = J(π), which means ∑ s6∈S⊥ ∑ a∈A ρπ(s, a) · Eζ∼π[T ] · ( maxāQ(s, ā) − Q(s, a) ) , as the second term of the dual-form Lagrangian (10), must be zero. Again, because Eζ∼π[T ] > 0 and because maxāQ(s, ā)−Q(s, a) ≥ 0 for all (s, a), the only possibility is to have ρπ(s, a) · ( maxāQ(s, ā)−
Q(s, a) ) = 0 for each (s, a) ∈ S \ S⊥ ×A (condition (3)).

heading: C MAXIMIN SADDLE POINTS VS MINIMAX SADDLE POINTS

heading: C.1 PROOF OF LEMMA 5.1
text: (Lemma 5.1). In any finite ELP, Q∗ is an optimal solution of
max Q E ζ∼π
[ Q(ST , AT ) ] s.t. Q(s, a) ≤ BQ(s, a) , ∀(s, a)
for any conjugate policy π ∈ Π. Equivalently, Q∗ ∈ arg max Q∈Q min λ≥0 Lπ(Q,λ).
The proof is by symmetric argument with the one in B.1: Because B is monotonic, for Q with Q ≤ BQ we have Q ≤ BQ ≤ (B)2Q · · · ≤ Q∗, thus Q∗ maximizes the objective Eζ∼π[Q(ST , AT )] in a per-state-action manner.

heading: C.2 PROOF OF THEOREM 5
text: (Theorem 5). In any finite ELP, for any conjugate policy π, let Qmax be an maximin value function of the Lagrangian Lπ – i.e. letQmax be an optimal solution of (15) – thenQmax is an optimal value function, in the sense that Qmax-greedy policy maximizes the episodic-reward objective (1).
As described in the proof idea, first observe that Qmax(s, a) ≤ Q∗ for all (s, a) ∈ S × A because Qmax, as a feasible solution of (15), has Qmax ≤ BQmax ≤ BBQmax · · · ≤ Q∗. Let µ be a Qmax-greedy policy, so µ(a|s) > 0 only if Qmax(s, a) = maxāQmax(s, ā). We will prove that
max ā Qmax(s, ā) = max ā
Q∗(s, ā) , ∀s ∈ Sµ \ S⊥. (34)
Note that (34) would necessarily imply that
arg max a Qmax(s, a) ⊆ arg max a Q∗(s, a) , ∀s ∈ Sµ \ S⊥. (35)
This is because Qmax ≤ Q∗ guarantees that for any action a sub-optimal to Q∗, it can only have even lower value in Qmax, so Qmax(s, a) ≤ Q∗(s, a) < maxāQ∗(s, ā) = maxāQmax(s, ā), in which Qmax(s, a) < maxāQmax(s, ā) literally says that such an a cannot be Qmax-optimal either. (35) guarantees that µ, a Qmax-greedy policy, will only choose Q∗-optimal actions at every nonterminal state it may encounter since time t ≥ 1. Such a µ is clearly an optimal policy in terms of episodic reward. Note that µ’s choices on terminal states does not matter here as state-transitions in terminal steps are action-agnostic, due to the ELP condition.
Now, to prove (34), we first prove the following induction rule: Proposition 11. Under the context of Theorem 5, let (s, a) be an arbitrary state-action pair, and let
(S ×A)next . = {(s′, a′) ∈ S ×A : s′ 6∈ S⊥ and P (s′|s, a) · µ(a′|s′) > 0}
denote the set of all the non-terminal (s′, a′) pairs that can directly follow (s, a) under the Qmaxgreedy policy µ, then
Qmax(s, a) = Q ∗(s, a)
⇒ Qmax(s′, a′) = Q∗(s′, a′) and max ā Qmax(s ′, ā) = max ā Q∗(s′, ā) , ∀(s′, a′) ∈ (S ×A)next
Proof. Because Qmax ≤ Q∗ and Qmax ≤ BQmax, we have
Qmax(s, a) ≤ BQmax(s, a)
= ES′ [R(S ′)] + ∑ s′∈S P (s′|s, a) · γ(s′) ·max ā∈A Qmax(s ′, ā)
≤ ES′ [R(S′)] + ∑ s′∈S P (s′|s, a) · γ(s′) ·max ā∈A Q∗(s′, ā) = BQ∗(s, a) = Q∗(s, a)
(36)
So, the premise Qmax(s, a) = Q∗(s, a) entails that the two inequalities in above must be equality, among which the second one – i.e. (36) – can be equality only if∑
s′∈(S×A)next
P (s′|s, a) ·max ā∈A Qmax(s ′, ā) = ∑ s′∈(S×A)next P (s′|s, a) ·max ā∈A Q∗(s′, ā) (37)
where s′ ∈ (S × A)next is a slight abuse of notation which means s′ shows up in (S × A)next with some coupled a′ (or equivalently, s′ 6∈ S⊥ and P (s′|s, a) > 0). Now observe that for (37) to hold, the only possibility is that
max ā∈A
Qmax(s ′, ā) = max ā∈A Q∗(s′, ā) , ∀s′ ∈ (S ×A)next (38)
as otherwise for those s′ on which (38) do not hold, it can only be maxā∈A Qmax(s′, ā) < maxā∈A Q ∗(s′, ā) (because Qmax ≤ Q∗); those s′ must all have positive weights in (37) (by
definition of (S × A)next), and thus will cause a real loss at the LHS of (37) (and importantly, no other state in (S ×A)next could claim a “gain” to compensate this loss, again because Qmax ≤ Q∗). Next, to prove Qmax(s′, a′) = Q∗(s′, a′) for all (s′, a′) ∈ (S × A)next (given the premise), notice that for any of such (s′, a′) we have
max ā∈A
Qmax(s ′, ā) = Qmax(s ′, a′) ≤ Q∗(s′, a′) ≤ max ā∈A Q∗(s′, ā) (39)
in which maxā∈A Qmax(s′, ā) = Qmax(s′, a′) is because a′ is by definition a Qmax-greedy action under s′, and Qmax(s′, a′) ≤ Q∗(s′, a′) is (once again) because Qmax ≤ Q∗. By (38) we know that the two ends of (39) actually equal to each other, so the inequalities in between must also be equality, and in particular Qmax(s′, a′) = Q∗(s′, a′).
Proposition 11 as proved above enables us to prove (34) by induction (which is enough to prove the whole theorem, as argued above). Specifically, because both Qmax and Q∗ are optimal solutions of (15), and because the objective in (15) is a distribution over only the terminal states (see B.1), it follows thatQmax andQ∗ must be equal on at least one terminal state s⊥. Starting from this terminal state s⊥ – as well as an arbitrary action a⊥ under it – we have Qmax(s⊥, a⊥) = Q∗(s⊥, a⊥), thus by the induction rule of Proposition 11 we obtain maxāQmax(s′, ā) = maxāQ∗(s′, ā) and Qmax(s
′, a′) = Q∗(s′, a′) for all (s′, a′) in the (S × A)next set with respect to (s, a) = (s⊥, a⊥); the latter enables us to expand the induction proof to all non-terminal states that are reachable by µ.
C.3 AN COUNTER-EXAMPLE FOR THE Q-FORM MINIMAX VALUES IN ELPS
In this subsection we elaborate more about the counter-example as illustrated by Figure 3 in Section 5 (which is copied above). In this ELP, S = {0, 1, 2, 3, 4, 5}, A = {1, 2, 3}. State 4 and 5 are terminal states, from which any action leads to state 0. Choosing action 1, 2, 3 under state 0 deterministically transits to state 1, 2, 3, respectively. All actions under state 1 lead to state 4, and all actions under state 2 and 3 lead to state 5. The agent only receives non-zero rewards at terminal states, with R(4) = 1, R(5) = 2. The initial state is set to state 4 (i.e. ρ0(s) > 0 only if s = 4).
The Bellman fixed-point Q∗ for this ELP is as follows:
• Q∗(0, 1) = 1, Q∗(0, 2) = 2, Q∗(0, 3) = 2 • Q∗(1, a) = 1, ∀a • Q∗(2, a) = Q∗(3, a) = 2, ∀a • Q∗(4, a) = Q∗(5, a) = 2, ∀a
An optimal policy of this ELP should only choose action 2 or 3, but not action 1, under state 0.
For minimax value functions, denoted by Qmin, as they are optimal solutions of (7), we have
Qmin(4, a) = 2 ≥ max  Qmin(0, 1) ≥ maxaQmin(1, a) ≥ 1 Qmin(0, 2) ≥ maxaQmin(2, a) ≥ 2 Qmin(0, 3) ≥ maxaQmin(3, a) ≥ 2
The above minimax condition only imposes tight bounds for Q∗-optimal actions (e.g. action 2 and 3 under state 0), but leaves “flexibility” for actions sub-optimal to Q∗ (e.g. action 1 under state 0) as well as for all state-action pairs that follow an sub-optimal action (e.g. all actions under state 1). The consequence is that even constant value function Qmin(s, a) ≡ 2 can be a minimax value function in this example, which is clearly sub-optimal, as discussed in Section 5.
In contrast, for maximin value functions, denoted by Qmax, they are optimal solutions of (15), thus
Qmax(4, a) = 2 ≤ max  Qmax(0, 1) ≤ maxaQmax(1, a) ≤ 1 Qmax(0, 2) ≤ maxaQmax(2, a) ≤ 2 Qmax(0, 3) ≤ maxaQmax(3, a) ≤ 2
We see that the maximin condition manages to imposes tight bounds for at least one Q∗-optimal action while at the same time can enforce all Q∗-sub-optimal actions to be still suboptimal to Qmax. For example under state 0, Qmax(0, 1) cannot exceed 1, while either Qmax(0, 2) or Qmax(0, 3) needs to be tight (i.e. Qmax(0, 3) = 2, or Qmax(0, 2) = 2, or both) so as to keep the maximum of the three no less than 2, as required.
Note that for bothQmin andQmax, the Lagrangian multiplier λ that forms equilibrium/saddle points with each of them (resp.) may not encode a policy, in general. In this example, for the constant Qmin, we have 2 = Qmin(0, 1) = 0 + 1 · Qmin(1, a) > 1 + 0 · Qmin(4, a) = 1, so Qmin(1, a) > BQmin(1, a) = 1 for all a, in which case its equilibrium multiplier λ has to have λ(1, a) = 0 for all a, due to the equilibrium condition (2) proved in Proposition 3. Such an “all-zero” λ (on state 1) cannot be normalized into a policy.
Similarly, for the following maximum value function
• Qmax(4, a) = Qmax(5, a) = 2 • Qmax(0, 1) = Qmax(1, a) = 1 • Qmax(0, 2) = Qmax(2, a) = 2 • Qmax(0, 3) = 1 • Qmax(3, a) = 1.5
we have 1 = Qmax(0, 3) < 0 + 1 · Qmax(3, a) < 2 + 0 · Qmax(5, a) = 2, so Qmax(3, a) < BQmax(3, a) = 2 again for all a, so the multiplier corresponding to this Qmax still needs to be all zero at state 3 due to the complementary slackness condition, thus cannot be normalized at state 3.

heading: C.4 A COUNTER-EXAMPLE FOR THE V -FORM MINIMAX VALUES IN DISCOUNTED-MDPS
text: Moreover, the problems with minimax value functions as demonstrated above are not limited to Qfunctions or to ELPs only, but seem to be fundamental issues rooted from the minimax structure. To see this, consider the discounted-MDP as shown in Figure 6 below.
To be strictly align with the related literature Dai et al. (2018); Cho and Wang (2017), the rewards are assigned to state-action pairs in this example. In this discounted-MDP, S = {0, 1, 2, 3},A = {1, 2}. The initial state is set to state 0 (i.e. ρ0(s) = 1 if s = 0, otherwise ρ0(s) = 0). From state 0, taking
action 1, 2 will deterministically goes to state 1, 2, respectively, with zero reward obtained in this step. From state 1, any action leads to the absorbing state 3, with reward R(1, a) = 1 obtained (for all a). From state 2, any action leads to the same absorbing state 3, but with reward R(2, a) = 2 obtained (for all a). The absorbing state 3 will loop into itself forever, with zero reward obtained. An optimal policy in this discounted-MDP should choose action 2, not action 1, under state 0. The discounting constant γ is set to 0.5, so the optimal discounted-reward performance is V ∗(0) = 1.
The V -form Lagrangian of the discounted-MDP above is: Dai et al. (2018); Cho and Wang (2017)
(1− γ) · E S0∼ρ0
[ V (S0) ] + ∑ (s,a)∈S×A λ(s, a) · ( R(s, a) + γ · E S′∼P (s,a) [ V (S′) ] − V (s) ) (40)
A minimax state-value function Vmin of the Lagrangian is an optimal solution of the Linear Programming problem (6), which has inspired some recently proposed RL algorithms (see Section 3). In this example, the LP can be more explicitly written as
min V
0.5 · V (0)
s.t. V (0) ≥ 0.5 · V (1) V (0) ≥ 0.5 · V (2) V (1) ≥ 0.5 · V (3) + 1 V (2) ≥ 0.5 · V (3) + 2 V (3) ≥ 0.5 · V (3)
for which a possible optimal solution is: Vmin(0) = 1, Vmin(1) = 2, Vmin(2) = 2, Vmin(3) = 0, which assigns the same value to action 1 and 2 under state 0, thus is not an optimal value function.

heading: D LAGRANGIAN MINIMIZATION FOR MACHINE TRANSLATION

heading: D.1 THE LAMIN1 ALGORITHM
text: As mentioned in Section 4, the idea of LAMIN1 is to minimize the smoothed Lagrangian Lβµ (with a small yet definite β) based on an unbiased gradient estimator of (13). For convenience, we copy (13) below:
Lβµ(Q(w),λµ) = Eµ[Q(ST , AT ;w)] + Eµ[T ] · E S,A,S′∼ρµ E A′∼πβ
Q(w) (S′)
[ δ(S,A, S′, A′;w) ]
where πβQ(w)(a|s) . =
exp ( Q(s,a;w)/β ) ∑ b exp ( Q(s,b;w)/β
) is the Boltzmann distribution with temperature β, and δ(s, a, s′, a′;w) . = R(s′) + γ epi (s
′)Q(s′, a′;w)−Q(s, a;w) is the temporal-difference error. Algorithm 1 gives the psuedo-code of such an algorithm.
Algorithm 1: The LAMIN1 algorithm. Input: A piece of rollout data made by an optimal policy, in the form of {st, at, rt}0,1,...,n,
where t = T1, T2, . . . , Tk are termination steps; A parameterized value function Q(w) with initial weight vector w0; Learning rate α; Boltzmann temperature β.
for gradient update i = 0, 1, 2, . . . do ∆w ← 1k ∑ t={T1...Tk}∇wQ(st, at;w) ∣∣∣ w=wi +
n k · 1 n n−1∑ t=0 γ epi (st+1)∇w (∑ a π β w(st+1, a)·Q(st+1, a;w) ) −∇wQ(st, at;w) ∣∣∣ w=wi
wi+1 ← wi − α ·∆w
Output: A Q(w)-greedy policy.
Note that Algorithm 1 samples the stationary distribution ρµ in (13) by averaging over the rollout data of a bunch of episodes, which is unbiased thanks to the ergodicity of episodic learning Bojun
(2020). The overall LAMIN1 algorithm is thus a standard unbiased SGD procedure, which shares the generic convergence property of all SGD procedures (i.e. convergence to local minimum of (13) is guaranteed under properly annealed learning rate; see Goodfellow et al. (2016)).
As an implementation trick, the gradient computation in Algorithm 1 can utilize the following fact (for brevity and clarity, we omit the argument st+1 in Q and π in the following):
∇πβw(a) = ∇ exp (
log eQ(a;w)/β∑ b e Q(b;w)/β
) = πβw(a) · ∇ ( log
eQ(a;w)/β∑ b e Q(b;w)/β ) = πβw(a) · ( ∇Q(a;w)/β − ∇ log ∑ b eQ(b;w)/β
) = πβw(a) · ( ∇Q(a;w)/β − ∑ b e Q(b;w)/β · ∇Q(b;w)/β∑
c e Q(c;w)/β ) = 1 β · ( πβw(a)∇Q(a;w)− πβw(a) ∑ b πβw(b)∇Q(b;w)
) and so
∇ (∑
a
πβw(a) ·Q(a;w) )
= ∑ a πβw(a) · ∇Q(a;w) + ∑ a Q(a;w) · ∇πβw(a)
= ∑ a πβw(a) · ∇Q(a;w) + 1 β · ∑ a πβw(a) Q(a;w)∇Q(a;w)
− 1 β · (∑
a
πβw(a) Q(a;w) ) · (∑
a
πβw(a)∇Q(a;w) )
Finally, we remark that the β-smoothing trick used in LAMIN1 is more than just an approximation heuristic, but may potentially play a role in correcting (to some extent) the sub-optimality bias of minimax value functions as discuss in Section 5. Specifically, the original Lagrangian function Lµ(Q,λµ) fundamentally cannot distinguish optimal minimax-values from sub-optimal minimax-values, as the function attains its global minimum in both cases. In contrast, the smoothed Lagrangian Lβµ(Q,λµ) tends to reach lower value at optimal minimax-values than at sub-optimal minimax-values.
As an illustration, consider the special case where there is only one non-terminal state, under which the agent can only choose between two actions, 1 and 2, and suppose action 1 is the truly optimal. In this simple case, a value function can be represented by a tuple (Q1, Q2), which indicating the value of action 1 and 2 respectively. A sub-optimal minimax-value function may have Q1 = Q2, as we showed in Section 5; in this case the smoothed Lagrangian Lβ=1µ (Q,λµ) would still equal J(µ), which can be seen from the dual form of the smoothed Lagrangian:
Lβ=1µ (Q,λµ) = J(µ) + 1 · (
( eQ1 ·Q1 eQ1 + eQ2 + eQ2 ·Q2 eQ1 + eQ2
)−Q1 )
On the other hand, an optimal minimax-value can make Lβ=1µ (Q,λµ) lower than J(µ). For example, when J(µ) = Q1 = 0, we haveLβ=1µ (Q,λµ) = e Q2 1+eQ2 ·Q2, which attains−0.28 atQ2 = −1.3. In other words, Lβ=1µ (Q,λµ) < J(µ) = 0 under the optimal minimax-value (0,−1.3), which is thus distinguished from the sub-optimal minimax-value (0, 0) in smoothed Lagrangian minimization as LAMIN1 does.

heading: D.2 THE LAMIN2 ALGORITHM
text: The idea of LAMIN2 is to minimize the original Lagrangian function Lµ based on the “local” gradient estimator (14). The consistency of the LAMIN2 estimator (with respect to∇Lµ) is characterized by Proposition 4, whose proof is given below.
(Proposition 4). LetA be a finite action space, and let Q(s, a;w) be a parameterized and differentiable value function that suggests a single best action amax(w∗) . = arg maxa∈A Q(s, a;w
∗) when evaluating the actions under a given state s with a given parameter vector w∗, then
∇w max a∈A Q(s, a;w) ∣∣∣ w=w∗ = E a∼πmax(s;w∗) [ ∇w Q(s, a;w) ] ∣∣∣ w=w∗
(41)
where πmax(w∗) denote the Q(w∗)-greedy policy.
Proof. We will prove that for any component of w,
∂
∂wi max a∈A Q(s, a;w) ∣∣∣ w=w∗ = ∂ ∂wi Q(s, amax(w ∗);w) ∣∣∣ w=w∗
(42)
which readily gives (41).
To prove (42), notice that
∂
∂wi max a∈A Q(s, a;w) ∣∣∣ w=w∗ = lim ∆→0 Q(s, amax(w ∗ + ∆);w∗ + ∆)−Q(s, amax(w∗);w∗) ∆
When there are a finite number of possible actions, there must be a non-zero gap between the best action and the second best action underw∗. On the other hand, since Q is differentiable, the change of action-values becomes infinitely small as ∆→ 0, thus the order between the two best actions will remain the same for small enough ∆, that is, amax(w∗+∆) = amax(w∗) when ∆→ 0. Therefore,
lim ∆→0
Q(s, amax(w ∗ + ∆);w∗ + ∆)−Q(s, amax(w∗);w∗)
∆
= lim ∆→0
Q(s, amax(w ∗);w∗ + ∆)−Q(s, amax(w∗);w∗)
∆
= ∂
∂wi Q(s, amax(w ∗);w) ∣∣∣ w=w∗
Note that when Q(w) is a sophisticated real-valued function, such as a deep neural network with scalar output, the chance that two actions have precisely the same value under Q(w) should be rare. Also, continuous action space can be densely quantized into a finite action space with arbitrarily small quantizing error, thus (41) should still approximately hold even for continuous action spaces.
Algorithm 2: The LAMIN2 algorithm. Input: A piece of rollout data made by an optimal policy, in the form of {st, at, rt}0,1,...,n,
where t = T1, T2, . . . , Tk are termination steps; A parameterized value function Q(w) with initial weight vector w0; Learning rate α; Boltzmann temperature β.
for gradient update i = 0, 1, 2, . . . do ∆w ← 1k ∑ t={T1...Tk}∇wQ(st, at;w) ∣∣∣ w=wi +
n k · 1 n n−1∑ t=0 γ epi (st+1) (∑ a π β wi(st+1, a)∇wQ(st+1, a;w) ) −∇wQ(st, at;w) ∣∣∣ w=wi
wi+1 ← wi − α ·∆w
Output: A Q(w)-greedy policy.
Algorithm 2 gives the pseudo-code of LAMIN2 in a further generalized form, where the greedy policy πwi is replaced with the Boltzmann policy π β wi . As mentioned in Section 4, higher temperatures, such as β = 1.0, can slightly improve performance in our experiment results (for 0.5 − 0.8 BLEU score).

heading: D.3 AN EPISODIC LEARNING FORMULATION OF MACHINE TRANSLATION
text: Many AI tasks are sequence generation problems, where we are given a context X , and are then asked to generate a sequence Y = (bos, y1 . . . yL,eos) using tokens chosen from a given token space. Machine Translation (MT) is an example of such tasks, where the token space is the vocabulary of a target language, and the context X is a sentence (or a sequence of sentences) in a source language. The choice of each token yt is conditioned on X and on the partial output Y<t . = (bos, y1 . . . yt−1). In particular, Y<1 = (bos), and Y<L+1 = (bos, y1 . . . yL), conditioned on which the algorithm will generate the first token y1 and the last token yL+1 . = eos, respectively.
The ELP formulation exactly captures the real-world MT tasks as described above. In the MT context, an episode is the translation of a given sentence. The first episode effectively starts with S1 = (X
(1),bos) where X(1) is a full source sentence. A learning agent then chooses a token A1 = y (1) 1 ∈ Σtarget ∪ {eos}, after which the environment state transits, deterministically, to S2 = (X(1), Y (1)<2 ) = (X (1),bos, y(1)1 ). The agent keeps generating actions At = y (1) t under each St = (X(1), Y (1)<t ) until it outputs AT−1 = eos at some step T − 1, leading to terminal state ST = (X(1), Y (1)) = (X(1),bos, y(1)1 . . . y (1)
T−2,eos). The agent will then make a normal action AT as in previous steps, which however makes no effect other than resetting the environment into ST+1 = (X(2),bos) from which the second translation episode begins. The process goes on episode after episode, generating a (theoretically infinite) sequence of translations (X(1), Y (1)), (X(2), Y (2)), . . . , which collectively serve as the training data for the agent to learn better translation policies.
An episode of length T as above results in a translation sentence Y = (bos, y1 . . . yL,eos) which contains L = T − 2 “normal” tokens from Σtarget. As a common and necessary practice, most realworld MT systems impose a maximum translation lengthH so that if an eos action did not show up after H steps, the environment will transit to the terminal state SH+2 = (X,bos, y1 . . . yH ,eos) even if the agent continues to output normal token AH+1 ∈ Σtarget at step H + 1. When maximum translation length is applied, the corresponding episodic learning model of MT has bounded episode length, thus satisfies the ELP Condition (3) above. Such a formulation considers the mechanism of maximum translation length as a fundamental part of learning-based MT task specification that is essential in helping learning agents (which may not master when to output eos) to escape from long and meaningless translation episodes which may otherwise lead to ill-conditioned training data.
To comply with ELP Condition (2), we prescribe ρ0 to be an arbitrary distribution over the set of terminal states, i.e. over all source-target sentence pairs (X,Y ) where Y is complete sentence ending with eos. As with other terminal steps, no matter what S0 and A0 are, the next state S1 will follow the same distribution, denoted as ρ1, which specifies the distribution of the source sentences that the agent will receive in each episode (ELP Condition (1)).
Finally, the agent receives a scalar reward R(X,Y ) ∈ [0, 100] at each terminal state, based on the translation quality of Y (with respect to X).The reward is zero at all non-terminal states (which has only partial translations). With this reward function, the expected episodic-reward objective J(π) of a translation policy π corresponds exactly to its average scores under the chosen translation metric.
The ELP formulation of MT as discussed above can be formally summarized as follows:
• S = (Σsource)H × {bos} × (Σtarget)H × { ,eos} • A = Σtarget ∪ {eos}
• R(s) = { metric ( X(s), Y (s) ) s ∈ S⊥
0 s 6∈ S⊥ , where S⊥ = {(X,Y ) : Y ends with eos}
• P (s′|s, a) =  ρ1(s
′) if s ∈ S⊥ 1[ s′ = (s, a) ] if s 6∈ S⊥ and |Y (s)| < H 1[ s′ = (s,eos) ] if s 6∈ S⊥ and |Y (s)| = H
• ρ0(s) > 0 only if s ∈ S⊥
Note that in above both S and A are finite sets, in which case the model is a finite episodic learning process. For real-world machine translation, we typically have |S| < 400002048 × 400002048 × 2 and |A| < 40000 + 1.
The experimentation code in Supplementary Material contains a faithful implementation in Python of the formulation presented here.

heading: D.4 EXPERIMENTATION DETAILS
text: We tested our algorithmic idea using the WMT’14 NewsTest English→German (en2de) dataset 4. The data was pre-processed and post-processed using the BPE tokenizer provided by YouTokenToMe 5, with shared vocabulary of size 37000. We used SacreBLEU Post (2018) as the translation metric and the standard TransformerBase neural network Vaswani et al. (2017), which is known to achieve a BLEU score of 27.3 on the WMT’14 dataset under the state-of-the-art method of MLEbased learning Vaswani et al. (2017).
We trained the model on the same 4.5 millions sentence pairs in the WMT’14 data set for 100, 000 gradient updates on a V100 GPU, with the same mini-batch size (and token-padding strategy) and learning rate schedule as recommended by Vaswani et al. (2017). A dropout rate of 0.1 is applied. The learned model is then used as search heuristic in the vanilla-beam-search decoding (e.g. see Algorithm 1 in Stahlberg and Byrne (2019)), with a beam size of 4. Empirically, we found that some more performance gain can be obtained by adding more tricks, such as modestly increasing the beam size (say, to 10), adding length penalty factor in the search heuristic (see Wu et al. (2016)), and model averaging (see Vaswani et al. (2017)), but we chose to exclude these tricks in our performance report so as to keep our algorithm simple and easy to implement. Our experimentation code and scripts can be found in Supplementary Material for reproduction.
The following tables give the numerical values of the performance scores shown in Figure 1.
4https://nlp.stanford.edu/projects/nmt/ 5https://github.com/VKCOM/YouTokenToMe

Review summaries:
In this work, the authors consider nonlinear Q-form Lagrangian function and show corresponding strong duality property. The main contributions are 1) the new proof of showing the duality gap as zero from a minmax perspective; 2) the generality of the theory with applications to machine translation tasks. A imitation learning algorithm is proposed as well and it turns out that it works well compared with the existing one.

This paper studies the Q learning in episodic learning from a Lagrangian formulation of the Q-form Bellman optimality equation.   On the theory side, this paper studies the (1) fixed point of the bellman optimality operator when the discounting factor for non-terminal states are 1; (2) strong duality of the considered constrained optimization, i.e., saddle point,  reformulation; and (3)maximin type saddle points.  On the empirical side, this paper studies the efficacy of the minimax imitation learning algorithm for a machine translation application.