Lagrangian Method for Episodic Learning
Authors: Huang Bojun
Venue: ICLR 2022 Submitted (2022)
Keywords: Reinforcement Learning
Imitation Learning
Lagrangian Duality
Machine Translation

Abstract: This paper considers the problem of learning optimal value functions for finite-time 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 almost exclusively 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 of existing works, which seeks to find minimax-type saddle points of the Lagrangian function. We 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.

Under review as a conference paper at ICLR 2022
LAGRANGIAN METHOD FOR EPISODIC LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
This paper considers the problem of learning optimal value functions for finite- time decision tasks via saddle-point optimization of nonlinear Lagrangian fune- tion that is derived from the Q-form Bellman optimality equation. Despite 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 program- ming approach RL/DD. Our paper brings new perspectives to this general ap- proach in the following aspects: 1) Inspired by the usually-used linear V-form La- grangian, we proposed 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 ap- plied to Machine Translation and obtained favorable performance on standard MT benchmark. 2) We pointed out a fundamental limit existing works which ex- clusively seeks to find the minimax-type saddle points of the Lagrangian function. We however proved that another class of saddle points, the maximin-ry -tppe 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.
INTRODUCTION
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 Al practice.
A pervasive idea of episodic learning, often called the value-based approach Sutton and Barto (0088), 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 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 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 variational (re-) Jforuultionn 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 (I.P) approach in the literature of dynamic programming Puterman (1994); Si et al. (2004); Chen and Wang (2016);
Wang (0177). 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-rewann setting, which bypass some technical difficulties Nachum and Dai (2020), but deviate from the practical settings of many (if not

---

Under review as a conference paper at ICLR 2022
most) real-world tasks. This paper fills this well-known gap between theory and practice by estab- lishing a value-based theory (and algorithm) that targets at directly learning optimal value functions and policies for the undiscounted episode-wise reward (see (I in Section
Secondly, previous works focused on linear formulations, which enjoys the strong duality property and generic LP techniques, but 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. Q- functions). 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 simple imitation learning algorithm based on the Lagrangian duality thus established, and applied the algorithm to Machine Translation (MT) case study. Transformer models trained by our algorithm achieves seam-search-leel 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 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
2 EPISODIC LEARNING PROCESS AND BELLMAN OPTIMAL VALUE
We start with introducing the mathematical formulation of episode learning problems, well as the formal definitions of related concepts.
An refiitt-horizonn MDP is tuple AS P. Pu), where S is the state space, A the action space. R(s) E [''in- mmax] is a bounded reward (possibly negative) associated to each state s E S. P(s'|s, a) specifies action-conditioned transition probabilities between states, and Po is the initial distribution with So ~ Pn- A MDP is finite if both S and A are finite sets. A policy function S x AA- - 10, 1] specifies the action selection probabilities under each state, which induces a markov chain Pa [S
S' s] = Enea P(s'|s, a) T(als). Let 11 denote the policy space, i.e., the set of all policies. Without loss of generality, we assume every state in the state space S is reachable from the initial state under at least one policy, where reachable means 3Λ E
II. Ee P= s) > O.
An Episodic Learning Process (ELP) White (017)); Bojun 2020 is an infinite- MDP that repeatedly encounters into, and reset by, a group of terminal states S1 (despite its name, a terminal state does not terminate the ELP) Formally, an infinitehhorizon MDP is an ELP if there is a non-empty subset $1 C S such that (1) all terminal states have homogeneous and action-agnostic outbound probabilities: P(s'|si, a1) P(s'(s(ss ([s'|s2,.0)) (2), Vsi, 52 E S1, Vai, a2 E A, Vs' E S, (2) the initial state is a terminal state: Po(s) = 0, Vs & S1, and (3) the average episode length is finite under any policy: VT II, E,, [T] < 0c, where T = inf 2 1 St E S1} is called the termination time. Bojun (2200) proved that in any ELP, every policy π E II has a unique stationary distribution Pm (8,
Pr (8( a) such that P [S 8, A++1 = a) = Pr (8, a) if P [S. 8, 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 3, for each step of the episodic learning process (based on data collected from
'Our state-based reward formulation follows Schulman et al. 2015) and Bojun 2020), and is equivalent to action-har hased reward formulations in terms of expressiveness. Refer to Appendix A of Bojun (2020) for details. 2 Unreachable states are irrelevant the real world whatsoever, excluded from our treatment.
2

---

Under review as a conference paper at ICLR 2022
previous steps), and the goal is to have 9i converge (as t goes to infinity) towards optimal policy that maximizes the expected episode-wing wise cumulative reward:
E R(S.)
T())
J E
where < = (So, $1, 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 [D33 for the ELP formulation of machine translation as example.
value function Q : S x A - R assigns a real number to each state-action pair (s, a) as the "perceived benefit" of doing action under state We call the set of all possible value functions, the value space, denoted by Q. A value function Q E Q is called an optimal value (any of the) ((+,a) maxa Q(s, a) is an optimal policy.
Q-greedy policy with (alas))
Bellman optimal value a special optimal value function that is characterized by the Bellman opti-
mality operator. In its general form Degris et al. (20T2); (Sutton et al. (2011) T, 2014] 2016), gener-
alized Bellman optimality operator B 2 - Q transforms a value function Q E Q into another value function B E such that for any (s,a) a) ESSxA.
1 Q(s = Σ P(s'ssa)) (R(s') + 76') max
Q(d(,a))
(2)
d'EA
J'ES
where 8 + [0, 1] is discounting function over the states.
As classic result, if the discounting function equals constant %o 1 on every state, the corre- sponding Bellman optimality operator 8 has a unique fixed point in the value space of any MDP. However, the fixed point of 8 is generally not an optimal value with respect to the undiscounted objective (T). In the following, we present 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 opti- mality are fundamentally rooted from an inherent graph property of ELP-MDPs See the proof in Appendix for detailed elaboration.
Theorem In any finite Episodic Learning Process (S,A, R. Po), let y be any discounting function such that (ss) < for all terminal state s S1, then
(1) BY has a unique fixed point, i.e., the equation Q = B has unique solution.
(2) The fixed point of B is the limiting point of repeatedly applying B any Q Q
(3) The fixed point of B is an optimal value w.rl. objective discounting function:
① if is the following episodic
7 Tapi (8) = [[sES1]= { for s S1 for s e
Since focus optimizing objective TT. in the rest of the paper: Bellman optimality operator, denoted by B 87 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 the following system of non non-linear equations:
Q(s, Σ max P(s'(s.a) (R(s') epi (s') -Q(s'aa)) V(s, ESA (4) S'ES
a'EA
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.
LAGRANGIAN DUALITY AND MINIMAX THEOREM
In this section study mwwimiiatiino-aiiiiiee based variational treatment to the Bellman optimality equa- tion (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.
3

---

Under review as a conference paper at ICLR 2022
Our idea is inspired by the long-known linear programming re-formulation of the closely related optimality equation for state- finctionss V S + R.
(s)) = max P(s'(s,,)) (R(s') + Tepi (s') V(('))
ss.
(5)
Both the Q-form optimality equation ( and the V-form optimality equation ( are nonlinear due to the max operation inside, but the V form equation admits a linear re-formulation Puterman 1994):
min Σ [Po(s)-V(s) s.t. V(5) 2 E (()))s,a) (o (d). SES
V(s,a) (6)
Thanks to its linearity, (6) enjoys the standard I.P duality properties, and in particular has minimax
equality for its corresponding Lagrangian function, which the basis for a recently revived thread of research on the LP approach to MDP and RL Chen and Wang (2016); Waag (2017); Cho and
Wang 2017 Dai al. (018); Nachum and Dai 20200.
In model-free learning settings, however, the agent does not know the transition function P. thus cannot directly use a state-value function V 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); Hasseli (2010); Mnih et al. (2013); [Haarooj et al. (2018). It is thus natural to ask if we can develop variational approach directly for the Q-form optimality equations 4 similar to what we did to the V-form optimality equations.
Indeed, the Q-form optimality equations problem as follows:
4 can be similarly recast into a constrained optimization
min Q
E S00
Q(Sr, Ar)
s.t. ((s,a) 2
Σ max P(s'(s,a) (R(s)) + Topi (()))Q(s'a'))
V(s,a)
where и E IT can be an arbitrary policy, and T = inf 2 1: S. E S is the termination time. Unfortunately, unlike the V-form optimality equation for which the nonlinear operation max, can be "unpacked" into |A|] linear constraints (cf. (5) and (6). the variational formulation ( of the Q-form optimality equation is still nonlinear, due the max.' "wrapped" inside Σ.. .. As result, although 7 can still be written into the Lagrangian form
E Ar) + EMs,a)
min QEO X
max
(8)
s,a
it is unclear if the nonlinear Q-form Lagrangian still enjoys strong duality, a key property for de- signing effective and principled learning algorithms Wang (201)): Dai et al. (2018).
In the following, give affirmative answer to this open question by proving minimax theorem
for the nonlinear Lagrangian of the Q-form Bellman optimality equation (4). As with Theorem [ the strong Lagrangian duality is also rooted from inherent structures of the episodic learning process.
Definition. Given finite Episodic Learning Process (S, P, R, po), function Ln Q x
R 11 + R is called a Lagrangian function with conjugate policy π if
(x( = E
[Q(Sr, Ar)] + >xs,,) (BQ(s, a) Q(s,a)
Coust
where π E II can be an arbitrary policy, and = inf 1: St E 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 Lx always uses the Bellman optimality operator B. Let us first confirm that Q* 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 x. Q" E aag min max L. L. A).
QEQ
A
4

---

Under review as a conference paper at ICLR 2022
Now, we observe that the Lagrangian Cx has equivalent form when the Lagrangian multiplier vector is a special vector A 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. P. R. pu), for any conjugate policy n, let f be the corresponding Lagrangian, and let Xn be the particular Lagrangian multipliers with Ar (x((8) a) - Px p=(8, a) Ec-a(TT) where Pa is the stationary distribution of n, then
(=(), J(r)
>E,((,,))) mmax -(s,,))Q((s.0)))) Q(),a))
(10)
#4S_ REA
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 (sce Appendix B.2 for details):
E
Q(ST. AT)
E
[T]
E
[[ [L1- 7pp (s) Q(S, A)
S,Ampx
Then substituting the above equation to yields
L (Q, (z)) = E [T]
E SLANPT
(R(S)) + Yepi (5") -max Q(S")((()))))) 7 7pp (S)Q(S, AD]
('MP(118A)
= [T] S.Arpe
E
R(S) + + (S) max Q(S, a') - Tei (S)Q(S, A)
= J(T) + Σ [T (s, [s c S1] max ( a') - Q(s.a))
o'
sES,aEA
In above, we have again used the engodic theorem of ELP to transform E, [T] Es-p, [R()) back to the trajectory space, so as to derive (T). See Appendix B.2 for the complete proof.
n
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 (T) Utilizing this fact, we can prove the strong duality property for Lagrangians conjugating with optimal policies, as the following theorem states.
Theorem (ELP Minimax Theorem). In any finite Episodic Learning Process (S,A,P. P, R. po), if TI is an optimal policy, then its conjugate Lagrangian by has strong duality property, with min max L,(Q, QEQ A20
max min L,(Q, = J(n
(11)
X2U QEQ
Proof idea: Let n² denote Q* greedey 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 maxa20 Cn (Q, A) maxx20 (Q A)
E Qr. ST Ar]]. Be- cause [[T)) = Qx- (s1,a) for any terminal state Ts E S and any action a E A (see Appendix A.3 we have E,, (Q. (Sr, Ar)] = J[x'') and so minQ max Lx x) = J(x").
(ST,, (ST,Ar)
Again for any conjugate policy æ, due to Lemma 2.2 the Lagrangian dual L, (Q, Ax) for the par- ticular multiplier > attains its minimum when Q achieves complementary slackness with A, the second term of (10). in which case minqee L. (Q, Am) J
So now, when the conjugate policy n is an optimal policy μs, as assumed in the theorem, we have (Q, A) 2 min (Q, = J(n ((m") = min max (Q,
max min
X20 QEQ
QEO
@ A20
The incquality above must actually be an equality because of the universally-hehe weak duality of the Lagrangian. See Appendix B.3 for 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 minimax saddle point of the Lagrangian fy. In fact, we can derive general conditions for all saddle points of this kind by combining the complementary slackness conditions in 9 and (T). See the proof in Appendix B.4 Proposition 3.
In any fimite ELP, for any value function Q E Q and any policy π E I1, let Am (8,a) Pa ()) Eq- [T), then L. (Q, < Cx(Q L. (Q,)x,, VQ, and only
(1) BQ(s, a) Q(s, 5
(s
(2) (s( (BQ(s, a) Q(s, ()) =0
((s,))E8xA
(3) (s( [maxa Q(s, - Q(s, a)) =0 V
5

---

Under review as a conference paper at ICLR 2022
4 ALGORITHMIC APPLICATION TO MACHINE TRANSLATION
From last section we know that the Q-form Lagrangian Ly has strong duality where js optimal policy, and that the special Lagrangian multiplier Ay forms a minimax saddle point (or minimax cquilibrium) with the solution of (7). Formally,
max J(T) min max Cn(Q. A) = max min (q, = min (p))) A20 Q
A20
Q
A simple idea to find such minimax saddle point is to minimize the rightmost side of the above equation, that is, to minimize (Q, > over the value space 2. Although the closed form of the objective function (Q xx depends on an optimal policy (which might appear paradoxical at first glance as coming up with such an optimal policy was our original goal of learning), note that estimating the gradient of L, (Q, A,)) only requires knowledge about "trace" of the optimal policy μ. instead of explicit knowledge about how ju is constructed. Specifically, for parameterized value function ((,, a; w)) we want to estimate V Ww (Q((), A,), that is,
V.r [Q(r,, Ar: w)] + E,, [2']
E S.A.S' <pp
R((S)) Yeu (5") max Q(S', :a';)) - Q(S, A: w)]w (12)
in which the optimal policy μ only plays role in data weighting it determines the population distribution of the terminal state-actions (Sr, Ar), of the terminal time T, and of the transition variable (S, S"). This observation inspires general imitation learning approach, named LA- grangian 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 C (Q((). A,)), which corresponds to a minimax point of the original Lagrangian function (
One may design different estimators of [22 to form different algorithms under the LAMIN idea. In the following we discuss two, and they both perform reasonably well in our validation experiment.
LAMINI: A technical challenge of estimating (12 is to deal with the max operator in it. One idea to relax the Lagrangian function into a smoothed version:
(Q)w), Xp) = E, (Q(( Ar; +)]+E
5,A,S'mp, A' (r As,,
E
E
(13)
where Th =Q(w) (als) = cxp (Q(s.a))))))
is the Boltzmann distribution with temperature B, and Ee exp (((e,(())))))/))))
ö(s, s',' = R(sss)())))))))))))) Tppi (s')Q(s', a'; w) Q(s, a; w) is the temporal- cemporal-difference error.
The smoothed Lagrangian C subsumes the original Lagrangian L, as the limiting case / - O, while is readily differentiable. Thus, the LAMINI algorithm seeks to minimize the smoothed La- grangian L via SGD with unbiased gradient estimator of (33. See the pseudo-code more nuanced discussion on this algorithm in Appendix D.I Among others, it turns out that the B-smoothing trick used in LAMINI is more than approximation heuristic, but may potentially serve as practical correction to an inherent bias of the minimax points of the Lagrangian that we
well as
will discuss Section 5
Another idea is stick to the exact Lagrangian L, but seek to construct "local" estimator of its gradient in a per-step manner. Specifically, let w. be the parameter vector of Q that is to be updated at gradient step t. then we can estimate the value of VwLx(Q(w). An) w=w,," for this particular paramter we, with
LAMIN2:
u (ES,
[T]
E -.A.S'~Pp. A' A'maq(wo; (S") A,', w=
E
(14)
where (oww") is the Q(wee)-gredy policy (see Section
2p. Note that the greedy policy TQ( in 14 does not depend on w and thus is invariant to Vwn: in contrast, the Boltzmann policy T TQ(w)
used by LAMINI (see 1 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 finite action space, Q(s, a; w) parameterized value function. If with a given parameter vector w", Q(w*) suggests a unique best action amax w²) = arg maxaEA Q(s, a; w²)) w for state s, then
Vue max Q(s, a; w)) aEA
E 10 a
V Q(s,
w=="

---

Under review as a conference paper at ICLR 2022
See the proof in Appendix D.2 In practice, the condition in Proposition i.. Q(w") gives unique best actions - may be expected for large-scale continuously-valuee Q functions, as it unlikely that the real-numbered values of two actions happen to be identical under stochastically generated
Moreover, the local gradient estimator (4) can be combined with the B-smoothing trick by replac- ing 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 case study. Learning to trans- late is a highly impactful AI application Wu et al. (2016), and also an excellent example of episodic learning problem: A translation episode starts with given sentence in 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 special end-of-sentence (EOS) token, at which point the trans- lation 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 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 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 collection of source-reference sentence pairs, is indeed widely available in standard MT benchmarks, which can be readily used to power LAMIN algo- rithms. 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 influential MT benchmarks. We parameterized value functtion Q with the standard TransformerBase neural network Vaswani et al. (2017), and trained the Transformer-basee and LAMIN2, with varying temperature B, 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.
(en2de) dataset, one of the most
Q-function using LAMIN1
27.50
corpus BLEU score
27.25
corpus BLEU score
27.00
26.75
26.50
15
26.25
lamin1 (beta=C.01, greedy pelicy)
26.00
(beta-C.01. size lamin2 (beta=t 01, greedy pulicy) (beta-1.0c, gready pelicy)
larvin (greedl policy)
25.75
lamin2 (grzedy palicy)
25.50
20000
40030
60000
80000
temperature (beta)
of gradient updates
Figure 1: Corpus BLEU scores of LAMINI and LAMIN2 under different Boltzmann temperature B. Greedy policy is used in both cases. The gray dashed line indicates the baseline performance of 27.3 achieved by a beam-search policy Vaswani al. (0017).
Figure 2:
Learning curves of some LAMIN variants. Beam search with beam size of is used for the orange line, which matches the same setting with the baseline result of 27.3 (gray dashed line). Other lines use greedy policy which is about 2x faster.
Figure I illustrates the performance of LAMINI 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 [ and 2 in Appendix [ | reports the numerical scores. We see that LAMINI has slightly better performance than LAMIN2

---

Under review as a conference paper at ICLR 2022
under most temperatures. Interesting, higher temperatures tend to help the performance of LAMIN2 but hurt that of LAMINI (albeit with limited margins in both cases).
Notably, LAMINI with 0.01 attains BLEU score of 27.4 with greedy policy. In comparison, when standard supervised learning is used, the same neural network famously attains 27.3 only further combined with a systematic beam search Vaswani et al. (2017). So, our algorithm achieves comparable performance with the state-of-the-art result withour time-consuming search procedure decision//raaslltionn time. On the other hand, when incorporating with the same beam search procedure, the value function trained by LAMINI (with 3 = 0.01) attains 28.7, or 1.4 BLEU score higher. shows the learning curves of the algorithm, with and without beam search.
MINIMAX VALUES VS MAXIMIN VALUES
The Lagrangian method we explored so far has focused on a particular class of Lagrangian saddle points, the minimax saddle points arg ming max L,, which correspond to exactly the set of op- timal solutions for the minimization-fomm (or primal-form) variational problem (7) Let's call such value function, 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 al. (2018); ;); Nachum and Dai (2020) for examples. Indeed, as Lemma confirmeed the hellman-optinen value Q", as an optimal value function, minimax value function. However, minimax value function, equivalently, minimax solution of L (for any т), is not necessarily an optimal value function.
Figure shows example, where state and are terminal states, from which any action leads to state O. Choosing action 1,2,3 under state determin- istically transits to state 2, respectively. All actions under state 1 lead to state 4, and all actions under state 2 and 3 lead state The agent only receíves non-zero rewards at terminal states, with R(4) 1, R(5) 2. The initial state set state Clearly, an optimal policy of this ELP should only choose action 2 or 3 (or both), but not action 1, under state 0.
1=1
a= 122,3
a
1
2
3
r=0
T=0
One can verify that for this ELP, the constant value func- tion Qmin a) = a minimax value function. In par- ticular, we have 2 m (0, 1) + 1- Qmin (1,a) + 0 Qmin (4, a) = 1, which does satisfy the con- straints of 7 (that Q BQ).. But the constant value function Qmin is certainly not optimal as assigns the same value all actions under state 0. Moreover, be- cause Quii (1, a) > BQmin = for all a, the X corresponding to Qmin needs to have A(),
1,2,3
1.
5
Po
r=1
Figure 3: An ELP example
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 the action 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-MDPP Dai et al. (2018) suffer from the same issue too (see Appendix C.4 for a counter- example for the minimax V Fffunctions in discounted setting).
Interestingly enough, 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, also the optimal solution of the following "mirrored" problem 7 See Appendix C.T for the proof.
Lemma 5.1. In any finite ELP, Q" is an optimal solution of
max
E
(Q(Sr,
s.t. Q(s, BQ(ssa), V(s
(15)
8

---

Under review as a conference paper at ICLR 2022
for any conjugate policy II. Equivalently, Q' arg max min Cx QEO X20
We call an optimal solution of [15 maximin value function (with respect the Lagrangian Cx). 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 S. In any finite ELP, for any conjugate policy n, let Qmax be an maximin value function of the Lagrangian L - i.e. let Quax be an optimal solution of (15) then Qmax is an optimal value function, in the sense that Qmax-greedt greedy policy maximizes the episodic- reward objective (I)
Proof idea: First observe that Q (8, a) < Q² at all (s. This is because Qmax. as a feasible solution of (15), has Qmax S BQ I BBQ max S &Q" Now Qmax S 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 max, Qs a) max, Qs a) at every non-terminal state s that is reachable by -max-greddy policy in that case the footprint of a Qmax gmeedy policy will be a subset of the footprint of Qr-greddy policy, in which only Q" -o-ptimal actions are selected. Note that Q 's values on terminal states do not affect its footprint, due to the ELP conditions.
For an arbitrary state-action pair (s,a), a). let (S x 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
Q (8', = Q"(,,a (d') and max max (8, a) = (s,a)
Qmax = max (d) V(s', d') E (S x A)next a
which would enable a proof-by-induue
starting from some terminal state where Qmax and Q" equal each other (such terminal state exists because both max and Q" 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.
6 RELATED WORKS
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 max, with a linear average), White (017) proved that B3 has unique fixed point in episodic learning setting. The linear operator B, leads to a LP (re))ooruulation, 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-pon moidee-point optimization to solve the linear V- form Lagrangian, again relying on the generic IP duality inherited from the linear treatment Chen and Wang (2016); Wang (2017); Cho and Wang (017); Dai al. (
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
setting. special case of Theorem [ dedicated to episodic discounting was proved by Bertsekas and Tsitsiklis (191).
The WMT machine translation benchmark used in this paper is a fruitful driver of the rapid techni- cal 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. (020)) To our best knowledge, the LAMIN algorithm is one of the first MDP-based solutions that is able to train Transformer-sce neural networks independently (without pretraining or ensemble learning with the aid of other techniques) to attain competitive performance on the WMT benchmark.

---

Under review as a conference paper at ICLR 2022
7 REPRODUCIBILITY STATEMENT
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.
REFERENCES
Dzmitry Bahdanau, Philemon Brakel, Kelvin Xu, Anirudh Goyal, Ryan Lowe, Joelle Pineau, Aaron Courville, and Yoshua Bengio. An actor-critic algorithm for sequence prediction. 2017.
Dimitri P Bertsekas and John Tsitsiklis. An analysis stochastic shortest path problems. Math- ematics of Operations Research, 16(3):880-595, 1991.
Dimitri Bertsekas and John N Tsitsiklis. Neuro- Neuro-dynamic programming. Athena Scientific, 1996.
D.P. Bertsekas. Reinforcement Learning and Optimal Control. Athena Scientific optimization and computation series. Athena Scientific, 2019, ISBN 9781886529397. URL https:///bbbo google co. hptpbookkssddd-21B1BAAAAAA
Huang Bojun. Steady state analysis of episodic reinforcement learning. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 9335-9345, 2020.
Yichen Chen and Mengdi Wang. Stochastic primal-dual methods and sample complexity of rein- forcement learning. arXiv preprint /12.0266 2016.
Yichen Chen, Lihong Li, and Mengdi Wang. Scalable bilinear pi learning using state and action features. In Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 834-843. PMLR, 10-15 Jul 2018.
Woon Sang Cho and Mengdi Wang. Deep primal-dual reinforcement learning: Accelerating actor- critic using bellman duality. arXiv preprint arXiv: 1712.0277 2017.
Leshem Choshen, Lior Fox, Zohar Aizenbud, and Omri Abend. On the weaknesses of reinforce- ment learning for neural machine translation. In International Conference on Learning Represen- tations, 2020.
Bo Dai, Albert Shaw, Niao He, Lihong Li, and Le Song. Boosting the actor with dual critic. In International Conference on Learning Representations, 2018. httphhtts////:peeeeee
Thomas Degris, Martha White, and Richard S Sutton. Off-policy actor-critic. arXiv preprint arXiv:1205, 4839, 2012.
Sergey Edunov, Myle Ott, Michael Auli, David Grangier, and Mare' Aurelio Ranzato. Classical structured prediction losses for sequence sequence learning. In Proceedings of the 2018 Con- ference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume 1 (Long Papers), pages 355-364, 2018.
Ian Goodfellow, Yoshua Bengio. and Aaron Courville. Deep Learning. MIT Press, 2016. http:
7/www. www..eeeeeeainnnpoo...k org
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Confer- ence on Machine Learning, pages 1861-1870, 2018.
Hado V Hasselt. Double q-learning In Advances in Neural Information Processing Systems, pages 2613-2621, 2010.
Philipp Koehn and Rebecca Knowles. Six challenges for neural machine translation. In Proceedings of the Fürst Workshop Neural Machine Translation, pages 28-39, 2017.
10

---

Under review as a conference paper at ICLR 2022
Donghwan Lee and Niao He. Stochastic primal-dual q-learning arXiv preprint arXi::1810.0822 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforeement learning, Nature, 518(7540):52--533 2015.
Ofir Nachum and Bo Dai. Reinforcement learning via fenchel-rockafellar duality, arXiv preprint arXiv:2001.01866, 2020.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Behavior-agnostic estimation of discounted stationary distribution corrections. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-uue E. Fox, and R. Garnett, editors, Advances in Neural Information Processing URL
Systems, volume 32, 2019.
www.rrireeddnnn....i............ newrips cc/ http::/:w.....eoioooccccpappp//p
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: method for automatic
evaluation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pages 311-318, 2002.
Matt Post. A call for clarity in reporting bleu scores. In Proceedings of the Third Conference on Machine Translation (WMT), pages 186-191, 2018
Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. 1994.
Marc' Aurelio Ranzato, Sumit Chopra, Michael Auli, and Wojeiech Zaremba. Sequence level train- ing with recurrent neural networks. In International Conference Learning Representations, 2016.
John Schulman, Sergey Levine, Picter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International Conference on Machine Learning, pages 1889-1897, 2015.
Joan Bas Serrano and Gergely Neu. Faster saddle-point optimization for solving large-scale markov decision processes. In Alexandre M. Bayen, Ali Jadbabaie, George Pappas, Pablo A. Parrilo, Benjamin Recht, Claire Tomlin, and Melanie Zeilinger, editors, Proceedings of the 2nd Confer- ence on Learning for Dynamics and Control, volume 120 of Proceedings of Machine Learning Research, pages 413 423, The Cloud, 10-11 Jun 2020.
Jennie Si, Andrew G. Barto, Warren Buckler Powell, and Don Wunsch. The Linear Program- ming Approach to Approximate Dynamic Programming, pages 153-178. 2004. doi: 10.1109/ 9780447054788.chh
Felix Stahlberg and Bill Byrne. On nmt search errors and model errors: Cat got your tongue? In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference Natural Language Processing (EMNLP-IJCNLP), pages 3347-3353, 2019.
Rich Sutton, Ashique Rupam Mahmood, Doina Precup, and Hado Hasselt. A new (lambda) with interim forward view and monte carlo equivalence. In International Conference on Machine Learning, pages 568-576, 2014.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Richard S Sutton, Joseph Modayil, Michael Delp, Thomas Degris, Patrick M Pilarski, Adam White, and Doina Precup. Horde: a scalable real-time architecture for learning knowledge from unsu- pervised sensorimotor interaction. In The 10th International Conference Autonomous Agents and Multiagent Systems-volume 2, pages 761-768, 2011.
Richard Sutton, A Rupam Mahmood, and Martha White. An emphatic approach the problem of off-policy -aaporal-difffrecce learning. The Journal of Machine Learning Research, 17(1): 2603-2631, 2016.
11

---

Under review as a conference paper at ICLR 2022
W Scott Temy. Learning and memory: Basic principles, processes, and procedures. Routledge, 2017.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, L ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31st Interna- tional Conference on Neural Information Processing Systems, pages 6000-6010, 2017.
Mengdi Wang. Randomized linear programming solves the discounted markov decision problem in nearly-linear (sometimes sublinear) run time. Mathematics of Operations Research, 2017.
CJCH Watkins. Learning from delayed rewards. PhD thesis, King's 's College, University of Cam- bridge, 1989.
Martha White. Unifying task specification in reinforcement learning. In Proceedings the 34th International Conference on Machine Learning- Volume 70, pages 3742-3750. JMLR. org, 2017.
Lijun Wu, Fei Tian, Tao Qin, Jianhuang Lai, and Tie Yan Liu. A study of reinforcement learning for neural machine translation. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 3612-3621, 2018
Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoe V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin John- son, Xiaobing Liu, L ukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Nishant Patil, Wei Wang, Cliff Young, Jason Smith, Jason Riesa, Alex Rudnick, Oriol Vinyals, Greg Corrado, Macduff Hughes, and Jeffrey Dean. Google's neural machine translation system: Bridging the gap between human and machine translation. CoRR, abs/1609.081 44, 2016. URL http: /tttpp//arxiv..oo org/ abs /////669. 08144
Mengjiao Yang, Ofir Nachum, Bo Dai, Lihong Li, and Dale Schuurmans. Off Off-policy evaluation via the regularized lagrangian. Advances in Neural Information Processing Systems, 33, 2020.
12

---

Under review as a conference paper at ICLR 2022
A PROOFS OF BELLMAN OPTIMALITY
In this section we prove the uniqueness and optimality of the solution of generalized Bellman equa- tion in episodic learning setting.
A. PROPERTIES OF EPISODIC LEARNING PROCESS
This section presents a series of mathematical properties of ELP; the first three is known, the rest 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: V'ss' E S.. Σx=1 (R(S s' S. = s) > 0. (Bojun) 22020), Lemma 1.1)
Proposition 7. For any policy π in any ELP, the Markov chain induced by policy π is positive recurrent: Vs S,, E,, [T.] oc, where T2 is the recurrent time of s. (Bojun (0020), Lemma 1.2)
Proposition 8. For any policy πT in any ELP, let f S - RR be veal-valed function over the states, we have (Bojun 2020). Theorem 4)
T Σ
E Smip
[(())
= E S~T
S(S))
E 5~
T
(16)
We write Q1 2 Q2 for two value functions Q1. Q2 Q iff (s 2 V(s, 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 Bthh is a monotonic operator: Q1 2 Q2 + BT B Q2Q for all Q1, Q2 E O
max, Q(s',d')+ P(s'|s, a))(s') As Qi a') 2 Q2(s',a') a') for all a'), we have max Q2(s',a') 2 max Q2(s', aa) for all s', and thus E. ((s'ls,,) ((())))))))))))))))))))))))))))) max. (i a') 2 E. (P(''1s, ())))))))))))))))))))))) maxx Q2(5',a')
Proof. Rewrite
(), E. (P()lss)
because P(s||s,a) . 7(s)) 2 0 for all s'.
Now, well-known special case, if the discounting function is constant less than 1, the corre- sponding Bellman optimality operator is a contraction mapping with respect to the maximum-nome distance over the value space 2, which guarantees, by the Banach fixed-point theorem, that there is special value function Q: which is both the unique fixed point (Q² = B,Q%) and the unique limiting point of the Bellman optimality operator (Q² lim (B.)"Q. AQ E Q).
n-*00
Unfortunately, 8 loses the above contraction property under general discounting.
Proposition 10. In any ELP where there is single state s* and a single action a" such that doing a" under s* only goes to non-terminal states s', i.e. Eves, P(s'\s",,"' aaa)= =1, the Bellman operator B with episodic discounting (3) is not contraction mapping with respect to the maximum-norm
distance: For some Q1 Q2 Q, max,,a (Qi(s,)) Q2(s,a)] max [BQi(s, (B((s,a)
Proof. Consider two value functions with constant difference everywhere: Q1 a) = Q2(s, a) +5, for some 8 > 0. Clearly, max,,a (Q1(s,)) a) Q2(s, a)l = 8. On the other hand, for any (s, a) have [BQ (s, a) BQ2(s, a) = Eves P(s"(s,) a) (ss)) 10-5 55 8, which equals at the particular (s*, a*) because Eves P(s'|s" (/6'ss,aa" a²) (s') (6))-8- == Engs, P(s'|s" a²) .1. S.
Proposition [e]seems to be a negative result for most non-trivial ELPs - it says B is not a contraction mapping unless always has chance to immediately terminate an episode no matter where 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-MDP. but because of graph property dedicated to the family of EL.ss, will be shown next.
13

---

Under review as a conference paper at ICLR 2022
Lemma 2.1. In any Episodic Learning Process (S, A. po), for any subset of states Q S and any policy n, let Cx (9)) = { { Es E Ω2 PT = s' s' = s] > 0 }} be the set of all successor states that are one-step reachable from Q under and let S be the set of states that are ever reachable under (from initial states, in finite steps), then Cx (92 C Q2 only if S C Ω
Proof. For contradiction suppose ( Ω and yet there is r--rachabble state s" S that is outside the given subset Q. We will show that in this case, it is possible to construct policy j (that is possibly different from 77) such that s* is also reachable under μ,, and that μ admits infinite trajectory that passes through 8 and never return back to 8 (see Figure $ below). This would contradict with Proposition 7 above which asserts that a p-reachable state must have finite mean recurrence time under μ.
S
M R
π
Figure 4: An p-admissible trajectory that goes through s' but never returns.
Specifically, first observe that (12) Z means Q is absorbing subset under i that get into Ω we would never get out.
Then observe that the existence of --reachable state s* & Zt entails that Q cannot contain all initial states, as otherwise from any of the initial states (in ?2) we cannot go outside the absorbing subset Ω to reach s*. Let 8o be such an initial state that is outside Ω from which assumed) without reaching any state in in the middle (otherwise we never reach s*).
reach 8* under r (as
Now, pick arbitrary state s+ in S2 there must be some policy under which so (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 st from Sp under 3 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 so to the "old s s+*).
reach s+ from
So far we have obtained an initial state sg outside Ω from which there is admissible path so 7 s* for policy n, and an admissible path Su - s+ for policy 3. Both paths only contain states outside Ω (except s*). Now we construct policy μ as follows: we ask μ to copy on states in the path
5o 3 s", and ask j to copy 33 on states in the path 4 st. If a state shows up in both paths, we ask μ be (probability) mixture of both π and on that state. Clearly, we can reach both s* and s* from 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 st are in S,,, we must be able to go from s* to st under μ. Note that so far we have only prescribed jıs behavior outside Q. Our final step ask μ to copy for all states in Ω so that Ω2 is also an absorbing subset for μ., meaning that once we reach st (from s²), we will be stuck in 52 without going back 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 sy to s", then go from 8" to st, and then stuck in Ω forever without returning to s*. A possibility of such infinite trajectory under μ directly contradicts with Proposition 7
A.2 PROOF OF THBOREM (1) (2)
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 Sz. Utilizing this fact, we can prove the first two statements of Theorem
14

---

Under review as a conference paper at ICLR 2022
(Theorem (1) (2)). In any ELP (S, R. po) with finite state space S and finite action space A, let be any discounting function such that ((s) < for all terminal state & E S1, then
(1) B has unique fixed point, i.e. the equation Q = Q has unique solution.
(2) The fixed point of B is also the limiting point of repeatedly applying B to any Q E Q.
Proof. For any two value functions QI and Q2, consider their Los distance
d(Qi, Q2) = max )2)
where
d, (Q1, Q2) max aeA
1Qi(s, a) - Q2(s,))).
As usual, we have
d(B"Q1,
Q²)) = max #ES
max
Σ P()1(s,)). > mmax Qi(s',d) max Q2(5', ab))
aEA
4
E'ES
Σ P(s (()))
max Qi(s', dd)) -max Q2(5' an)
max
max aEA
#ES
E'ES
max
max aEA
Σ
P(s'|s,0) (0 0) (65) max Q1(s', d') Q2(s',
SES
S'ES
max max
Σ
P(s||ss.)) P(s' s, a) 765) de (Q1, Q2)-
(17)
SES
AEA
'EES
Traditionally, it was assumed that 7(')) % % 1 all states, thus the 7ss)) term 177 can be readily moved out of the sum, immediately yielding (18Q,,BQ)) I Yo d(Q1, Q2). When 7(s") is
not constant and is allowed to be 1 for non-terminal states, applying the operator B to Qı and Q2 cannot guarantee reduce d(Q1, Q2), 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 d, (Q1, Q2) at some "support dimension" s, so that if repeat- odly apply 8", the set of "support states" will become smaller and smaller and eventually become empty which point the overall T. -distance gets reduced (by the composite operator of repeatedly applying B
Specifically, for given Q1, Q2 E Q. we will identify a sequence of proper subsets of states
S = (0) 3 d-support(1)) ر d- (2ppportt 5 ... 3 ((support((S)) (18)
such that
s Φ d-support(k) vi 2 k, d, ((BT)Q1, (B d(Q1, Q2)
(19)
for all k 2 0. The construction of the subsets is by induction, and is based on the following insight: Lemma 2.2. Under the condition of Theorem 7. if (19 holds for k- - 1, then
3s E d-support(k)) such that Vi 2 k d. ((B7)Q), (B)) d(Q1, Q2)
Proof. We first refactor 17 little bit, which actually holds in a per-state sense, so
d, (B B7 Q2) S max
P(s''ss, a) ())(s,))-7())) 7(s) d, (Q1,
aEA max s'ES
s'ES
(20)
(Q1, = =d(1,
Recursively applying 20) gives
(1((B))01. (( (B))
Σ P(slls, (1s)(s,a).<($5) 7(5') d. (B1))---)))
(B7)
I max
aEA
s'ES
Σ
P(s' ((8'1s, Arma (s)) 7(8)) d, (17))~1Q11 Q1, (B7)) Q2) (21)
s'ES
< Σ 3'ES
P(s (s, Amax (s)) 7(8)) d(Qi, 22) - d(),,
15

---

Under review as a conference paper at ICLR 2022
where 4max (s) arg maxo Eves a)) -(5') de (1.))-
Now we prove that the inequality 21 must be strict for some support-state s* E d d-support(A)) In particular, we will prove
P(s'ls" (max(s")) 7(s') d (187) (B7)) < <d(Q1, S'ES
Σ
(22)
Case 1: There is s* E (-support(k) with Ev'e (kp P(slss 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 (8)) de (BB))+-QQ1) (B:)) Q2) d(Q1. Q2) (because (99) holds for k assumed), thus
Σ P(Sllo,, amax) 7(6)) de (1,7) e'ES
<
Σ
P( amax) d(Q1, Q2) +
g'gd support()))
Σ
P(s'|s", amax) ,7(')) de
('Edssupport(A)
<
Σ
P(s'|s", (max) dd(1, +
Σ
P(s'l", (max) d(Q1, Q2)
s(gd-nupport(h)
s' (Ed-oupport(k)
= d2).
Case 2: For all E d-support(Qi, Q2). Ed aut.ec-uppttt...e.... P(s'|s, (max(s)) 1. This is equivalent to say that there exists a policy - which would choose 4max (8) under the correspond- ing such that it is impossible move from any state in d-support($)) to a state outside d-support( (k) under this policy. In other words, let be such policy, we have
Cy (d-support(k)) S d support(A)
which, by Lemma 2.1
entails
Sy S (dppuport)()))
(23)
literally says that the set of support-states d- d-support as an absorbing subset under ju 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 ss Sy S @-support be such a reachable terminal state under μ.. Since $ is reachable under μ (and μ chooses amax (s) under each s), there must also be an s" E Sp as assumed as the general condition of such that P(s is", (inax(s)) > O. Because 7(s1) Theorem we have
23
Σ P(s'ls" (adlls",mmxx) amax) -755) do ( EE
Σ P(s'|s", (1ss(=*,ammxx) 7(5) -d(Q1, Q2)
EE
P(slss", amax)) ((81)+
Σ P(s'|s", amax) . 7(8)) d(Q1, Q2)
P(sils", amax) +
Σ
P(s'1s", (18l))";mmax))e (m(x)) d((Q), Qz)
d'ES((FL)
P(sils", amaxx +
Σ
P(s'|s" amax)) d(Qi, Q2)
d(Q1, Q2).
16

---

Under review as a conference paper at ICLR 2022
< d(Q1, Q2). It is straightforward verify that the same proof idea applies to all i > too (in case 1, we still have
Now we have proved that 3s* E d-support(k), d (118)))0
(s') d (17T)* ((7))"/'Q.. Q Q2) d(Q1, Q2) because (99 holds for k - 1; in case 2, the existence of Ts is a graph property that is independent of how many times B is applied).
O
With Lemma 2.2 we can construct each subset d-support (k) in (8) by removing the s* from
d-support (k= 1). It's clear that (19) will hold for the sequence of support subsets thus con-
structed. In particular, note that Lemma 2.2 holds for k = 0 without the inductive condition (that [9) holds for - 1) because in this case it's impossible to go outside d- suppoort (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, (T8) implies that d -uspporr((()) is empty set. Substittting this observation into (19), yields d() for all E S, which means di ((r))(11(. (B7) $1Q
de (BBT)) Q1, (Bv)IsI
d(Q1, Q2). In other words, the existence of the d-support sequence satisfying (88) and (I9) means that the composite operator of "repeatedly applying B for |8] times" (i.e. (l) guarantees to reduce the -istaane 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 QI and Q2 only affect what Qmax is in (22)
There are |S| A|| (S] possible transition probabilities in total, and [S] possible 7-values in (2 so no matter how "max (which is a policy) and arg max d change over iterations, they just select a different subset from the |s|a.. |A|] possible terms. There are finite number of such subsets, thus when the sum of the subset is less than 1, there must be an absolute upper bound 1 - mmin 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 fixed number smaller than 1, and thus the operator (B7)) |S| is contraction mapping, and thus it has a unique fixed point (by the Banach fixed point theorem).
Our last step to prove that the unique fixed point of the composite operator (B*)Is) is also the unique fixed (and limiting) point of the original Bellman operator B It is easy to see that B7 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 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 let Q' be the unique fixed point of (B)
Q- = lim QB)"Q, VQEQ
(24)
and
Q' = BQ'
(25)
Proof. We first prove that (24 holds for all Q with Q < BQ
Because B is monotonic
operator, for such Q we have
Q < BQ < (B)²Q
(B) ... 11.
(26)
where Q" being the limit of the above sequence is guaranteed by the contraction property of B Sl Recall that QI < Q2 means Vs,a (s) < Q2(s,a) and that d(Q1, Q2) max,,a (1 a) - Q2(s, a)l. we see that the value functions in the above (monotonic) se- quence must have non- -on-increasing distances to Q". On the other hand, the subsequence converges to Q", we know that for any > 0. there
Q (
(B) Q 2 (B)3|[SQQ
exists an it such that d( (B)) Q-) and thus d (B))Q, 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 (B)"QT, we must have BQ" = B lim (B)*Q lim (B)" Q", thus 25 holds, and that Q* is a fixed point of B.
n
R
Such Q
guarantces exist. In fact, every on-policy value function is such Q see A.3 for details.
17

---

Under review as a conference paper at ICLR 2022
Finally, because Q" BQ", for any Q Q (not necessarily with Q < BQ this time), have d(BQ. = d(BQ, BQ*) 2 d(Q, Q*), where the inequality is by (17). Again, d(BQ.Q" Q*) 2 d(Q, Q") means the sequence (26) has non-increasing distances to Q", this time for all Q E Q So, by the same logic as above, Q' must be the limit of the sequence Q, BQ, (B)²Q..... again, for all
Q E Q this time (not necessarily with Q BQ).
Note that the specific form of the y-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 We thus have completed the proof of statement (1) and (2) in Theorem
In comparison, the classic Bellman optimality property requires (8)) < at every state 8 E S, while Theorem [ only requires 7ss) < 1 at terminal states. On the other hand, the classic result applies to all MDPs, while Theorem is fundamentally based on unique structures of episodic learning process. Importantly, the episodic discounting function that use E.e- (3) does satisfy the condition in Theorem
A.3 PROOF OF THEOREM (3)
Finally, we prove statement (3) of Theorem D which asserts that Q", as the unique fixed point of the Bellman operator under episodic discounting, indeed an optimal value function, in the sense that a Q" Q"-greedy policy is an optimal policy with respect to the undiscounted objective (
(Theorem T (3)). In any finite ELP, let Q' be the fixed point of B (i.e. the solution of 44)) let n² be a policy such that x² (als) > O only if (s. maxa (s, (), then J(x²) = max, (T), where J is the episodic-reward objective
Proof. Every policy æ is coupled with (unique) on-policy value function Qn which assigns values to (s, a) pairs according to the conditional expectations of the episode- wise cumulative reward under the policy æ. Formally,
T Σ
(s)
E
Ro
So s, Ao =
((s.a)
(27)
Comparing 27 with the definition of the episodic- objective J (i.e. with (.. and by the ELP conditions, we see that for any policy æ,, its performance score equals its on-policy terminal values:
( (s), a) ts SL, Va E A.
(28)
We will prove that for the Q -reedy policy x", we have QT. 2 Q for all E II, which would entail that (TT") 2 J(T).
First observe that Qn- = Q*, that is, the value function Q* which induced the greedy policy " is also the on-policy value function of n* Specifically, with the episodic y-ffnction (3), for any (s, a), by the definition of Ā² we have
Q" BQ" (s)
max [R(S") +S()) Q'
E s' P(s,a))))
E
E
[R(S") + ((("))(()))00 Q"(5" 44]
(29)
S'mP(s,a)
A d' (S')
E
R(Si) + (Si) (S( 8, Ao =a
(81.A1 Noom"
E
+ (S)) Q" A2)
So s, Ao = =a
E
R(S.) So =
(30)
18

---

B PROOFS OF MINIMAX DUALITY Under review as a conference paper at ICLR 2022
Connecting (29 and (30) and generalizing to arbitrary yields that for any policy π II, obtain Qx I BQx; specifically,
Qx(s,a)= = S(m,(s,) A'mx(S")
E
(R(S") + +(5))) Qx(5" A')
(R(5)) Qn((S d0]
E
max
S(xa())))
(s,
In other words, the set (Q 3x = is 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 subset, and because Q" itself is also an on-policy value function (as Q" = Q.-)) it must follow that Q" is also maximum value-function of the subset {Qx}. Thus we have proved that QT- Q Qn for all π E II, as desired.
B.1 PROOF OF LEMMA 2.1
(Lemma 2.1. In any finite ELP, for any conjugate policy π. Q E arg min max C, (Q,
QEC X20
Q" an optimal solution of 77) because monotonic, so for Q with Q > BQ we have Q 2 BQ 2 (B)²Q... 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 optimal solution of (7) if and only it a minimax solution of (8). In particular, only value functions with Q 2 BQ can prevent max (x(Q, from being arbitrarily large, and for those Q's, max (Q,
E Q(Sr, Ar) under the complementary slackness condition, whose value attains minimum Q" as proved.
B.2 PROOF OF LEMMA 2.2
(Lemma 2.2p. any finite Episodic Learning Process (S, (.P.PPRR.Pp for any conjugate policy m let Ey be the corresponding Lagrangian, and let An be the particular Lagrangian multipliers with An (8,88 a) = (s) (als))- Exool [T], where pn is the stationary distribution of n, then
(.(0,A=)= = J(T)+ EEA(s,)) (max (m, (((x((())))((s)a))
#gS
BEA
By Proposition with f(s) Esux(e)
[[IESS]] Q(s, A)]. we have
T = Ec [T]
E
Q(ST,
E
Σ [(S.)
E E
- (()
Srup A
t=l
19

---

Under review as a conference paper at ICLR 2022
So, for any E 2, we have
L. (Q, xx)
[T]
E S.Amp7
1[S S1] Q(5,A)) ES [
E S.Amp=
(BQ(S,A)-Q(SS))) Q(S,A)
= -E -Be [T]
E S,Ampr
Is E S1] Q(S, - Q(S, A)
E B [T]
E 8'sP(S)))
max R(S") + (S"),
Q(S", _d)]]
S,Ampx
a'
E
E
[ (1) Q(S, A)
E S'mpe
RR(S)) + 7 max Q(S',
S.AmPA
= -E [2]-
E Srupm
R(S)
+ Ec [7]
1 & S1]
[max ((5,))())) (((S,A))
S,Ampa
=J( EcCos [T].
Σ
(=(s) [(als) 1 81] maxx -((,a)
sES,aEA
=]( + Ecoo [T]
Σ
(x( x(cls) ( (max Q(s, - Q(s,a))
SESIS1
aEA
[[(S] J(x) have again used the transformation of
Note that in above for Ex-= [T]
Es-pp
Proposition 8 with S(s) = R(s).
B.3 PROOF OF THEOREM 2
(ELP Minimax Theorem). In any finite Episodic Learning Process (S,A, P, R. po). if E is optimal policy, then its conjugate Lagrangian Ly has strong duality property, with
max Ln( = max min (u(Q,A)= J(n) QEQ A20
min
(31)
X QEO
Let x²" be Q" -grredy policy, which is thus optimal policy.
For any conjugate policy n, since Q" is minimax solution of En (Lemma 2.1 D. we have
ming maxx20 Lx (Q, A) maxx2o (Q", A)
(x" Ar)]. By (30) in A.3 have
E, (ST, Ar) = Ez (Q- Ar)]- By (28 in A.3 we further have E [Q (ST, Ar)
((x)), Connecting these results together gives
min max C, (Q, A) J(T").
(32)
Q X20
Again for any conjugate policy и, due to Lemma 2.2 the Lagrangian function has the dual form 10 under the particular multiplier A,o as copied below
C, (Q, = J(T) + Σ As
mmax (max((s.a)-Q(ssaa)
SgS
REAA
The first term above is 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. C, (Q, Xx), attains its minimum when Q achieves complementary slackness with Xu in which case
min C.(Q, J(T).
(33)
QEQ
So now, when the conjugate policy π is an optimal policy μ4, as assumed in the theorem, we have
max min
(O( A) Z min QEe (Q, An) = J(p) J(=") min max (, A). X
X QEQ
Due to weak minimax duality, max mingeg (2, A) < ming maxa>o (4, A), which universally holds, thus the inequality above must actually be equality, desired.
20

---

Under review as a conference paper at ICLR 2022
B.4 PROOF OF PROPOSITION
(Proposition 3 In any finile ELP, for any value function Q E Q and any policy x E II, let (8) Per (8, a) Ee~a(T), [T], where pa Px(s,a) = p=((s) (a]s)), then
Lx(0,)) s (.( 5..
VQ.A
and only if
(1) (o(ss,)-Q((s()) 50
M(s,a)ESXx
(2) p=(
(BQ(s,a) Q(s,a)) =0
e
(3) px( (maxa Q(+ - Q( a)) =0 VagSi
The "if" part is straightforward: Condition 11) and ( immediately gives (Q, = (C>=/Q(Sr. Ar)l maxx20 (Q, A). On the other hand, condition (3) entails that the sec- ond term in dual-form Lagrangian (0) is
C, (Q, Ax) ((x). By 33 in B.3
have
ming f, )₂) = (TT) thus ( >²) = ming C (Q. A=).
Now prove the "only if" part, for which resort to the general saddle- condition: Under given conjugate policy и, (Q, pair is a minimax equilibrium (or minimax saddle-point) of function L (Q, Xj if and only if
(i) min max L (Q, A) = max min Lx (Q, Lx X20 QEO
QEQ X20
(ii) Q arg min max L. (Q,
QEO X20
(iii) À E arg max min L (Q, A). X20 QEQ
By condition
ii if (Q, A²) form minimax equilibrium, then Q must be minimax value function.
From
B.I
we know that such minimax value function must have Q 2 BQ (condition (T).
By condition i and by 32 in B.3 we know that (Q, A+) mingee max (Q,
J(x*) = E E Q(Sr, Ar In other words, Σ.o (n. (BQ(s, a) - Q(s, a)), as the second
term in C, (Q, ), needs to be zero. Because Au as) = (s a) E [T') where Eç- [7] > 0, and because BQ < Q as proved, the only way to make the term zero is to have (r(ss a). (BQ(s, (ss,a)) = 0 for each and every (s, a) (condition (2)).
Moreover, since (x, ming (Q, An) assumed, by 33 in B.3 we have (. Aa)
(T),, which means E.gs, (r, a) Eq-=(T] (maxa Q a) Q(s,a))
the second
term of the dual-form Lagrangian (10). must be zero. Again, because E [T] > and because max; Q(s, a) (s, a) for all (s, a), the only possibility have Pa (s, a) (maxa Q(s a)
Q(s,a) a)) = for each (s, a) E { S x A (condition (3)
C MAXIMIN SADDLE POINTS VS MINIMAX SADDLE POINTS
C. PROOF OF LEMMA 5.1
(Lemma 5.1
In any finite ELP, Q" is an optimal solution of
[o(Sr, Ar)] s.t. Q(s,a) S BQ(s,a), V(s,a)
max Q
E Coust
for any conjugate policy E II. Equivalently, Q' E arg max min (Q,
QEe X20
The proof is by symmetric argument with the one in B.I. Because B is monotonic, for Q with Q < BQ we have Q S BQ < (B)²Q-. < Q", thus Q' maximizes the objective Eq==IQ(S7: Ar)] per-state-action manner.
21

---

Under review as a conference paper at ICLR 2022
C.2 PROOF OF THEOREM 5
(Theorem 5). In any finite ELP, for any conjugate policy n, let Qmax be an maximin value function of the Lagrangian i.ei. let Qua be an optimal solution of [15)- then Qax is an optimal value function, in the sense that grex-y policy maximizes the episodic-reward objective Q
As described the proof idea, first observe that Qmax S Q" for (8, a) E x A because Qma as feasible solution of (5). has Qmax BQ BBQQ max Q"
Let μ be Qmax-greede policy, so plaass) s) > only if (s.a a) = maxa Qmax a). We will prove that
max Qmax (s, = max Q" (s.
V Sx SL1
(34)
Note that 34 would necessarily imply that
arg max (0max(s,4 as) S
As E Sp AS1
(35)
This is because Qmax I Q" guarantees that for any action a sub-optimal Q", can only have even lower value in Q mmxx. so Qmax(s, a) I (s(s. < max, Q*(s, @) max, Qmax (s, a). in which Qmxx (s, a) < max, Qmax((,, a) literally says that such an a cannot be maax-optiml either. 355 guarantees that 14, Emax-greddy policy, will only choose Q*-optimal actions at every non- terminal state it may encounter since time 2 1. Such μ is clearly an optimal policy in terms of episodic reward. Note that p's choices terminal states does not matter here state-transitions in terminal steps are action-aue action-agnosta 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 x Aex = {(s', a') E S x A: s' 4 S1 and P(s'(s, s. a) uuaalss) > 0}
denote the set of all the non-terminal (s',a') pairs that can directly follow (s, a) under the Q greedy policy μ. then
Qmax (s, a) = (s,a)
+ Qmax (= (s' and max Qmax a) = max Q"(s'a)) v(d,a)) (8 x A)noxt
a
Proof. Because Quaa S Q" and Quax S BQuuax we have Quax (anux(s,0) (s, BQ max (s ())
Ess(R((S)) +
Σ P(s'ls, -7(5)) aEAA
max Qmax(s', a)
s'ES
[s((R(
Σ
P(s'ls, 7(5))
max ("(s'.a)
(36)
aeA
#ES
(s,a)
(s,
So, the premise Qma (8, a) = Q" a) entails that the two inequalities above must be equality, among which the second one i.e. 336) can be equality only if
Σ
a) max Q Quaxx( (s'aa) (a)=
Σ P(s'ss,)) max Q" (s((sa)) a)
(37)
aEA
aEA
d'E(SXA)mms
where s' E (S A) next is a slight abuse of notation which means s' shows up in (S x A)next with some coupled a' (or equivalently, s' & S and P(s'(s,a) > 0).
Now observe that for 37 to hold, the only possibility is that
max Qmaxx(s a) max ('(s(a) asA
Wss E (S A next
(38)
aEA
as otherwise for those s' on which (88) do not hold, can only be maxaed Qmax(s' (s',a)
maxac Q" (s', (because Qmax Q"); those s' must all have positive weights in (37 (by
22

---

Under review as a conference paper at ICLR 2022
definition of (S x A) nex)), and thus will cause real loss the LHS of (37) (and importantly, other state in (S x Aneex could claim a "gain" to compensate this loss, again because Qmax S Q*).
Next, to prove Qmax that for any such (s', a') we have
(s', .') (''s ,') for all (s',a') E (S A)ext (given the premise), notice
max
maxx a) 1mx d') S (" S max ("(s', BEA
(39)
aad
in which m Qmax (s', @) = max a') is because a' is by definition Qmax- action under s', and mmxx (8', a') I (s',,aaa) a') is (once again) because Qiax I Q"
By (38) know that the two ends of (39) actually equal to each other, the inequalities in between must also be equality, and in particular Qmax (8', a') = (2',".a)
Proposition 11 as proved above enables us to prove (34) by induction (which is enough to prove the whole theorem, argued above). Specifically, because both Qma and Q" are optimal solutions of (15), and because the objective in (15) is distribution over only the terminal states (see B..Ip follows that Qmax and Q must be equal on least one terminal state $ Starting from this terminal state as well as an arbitrary action @ under it we have Qmax ($1, Q1) = Q (*(s1.a1)
thus by the induction rule of Proposition 11 we obtain max; Qmax (s',a) a
max; Q" ()) and
mmxx a') Q" (s', a²) for all (s', a') in the (S x A)xxx set with respect to (s,
(11,01);
the latter enables us to expand the induction proof to all non-terminal states that are reachable by μ.
1=1
1=122
R
1
2
3
==0
0
T= 0
F=
0
1,2,3
1,23
4
Po
5
F=1
T= 2
Figure 5: copy of Figure
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 Sec- tion 5 (which is copied above). In this ELP, S {0, 2, 3, 4, 5), A {1,2, State 4 and are terminal states, from which any action leads to state 0. Choosing action 1, 2,3 under state deterministically transits state 2, 3, respectively. All actions under state 1 lead state 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 state 4 (i.c. Po(s) > 0 only if 4).
The Bellman fixed-point Q" for this ELP is as follows:
(0 1, (0 2, Q" (0,
(1( 1, Va
(²( (3, a) = 2, Va
(*, = (5, a) = 2, Va
An optimal policy of this ELP should only choose action 2 or but action 1, under state 0.
For minimax value functions, denoted by Quin. as they are optimal solutions of 7 we have
Q Qmin (0,
max Qmin (1,
I WMW
(4,
max
Q min (0, 2)
max, Q min (2,a)
Q Qmin (0, (0
max, Q Quin (3,
23

---

Under review as a conference paper at ICLR 2022
The above minimax condition only imposes tight bounds for -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) 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 ()) = can be minimax value function in this example, which is clearly sub-optimal, discussed in Section
In contrast, for maximin value functions, denoted by Qmax. they are optimal solutions of
15 thus
Q maxe (0, 1)
max Q (1,a)
S
1
Qmax
2
max Q max (0, 2)
W max Q max (2 a)
2
Q mmax (0,3)
max Qax (3,a)
S
We see that the maximin condition manages to imposes tight bounds for at least one Qp-tiii action while at the same time can enforce all Q"-ssb-opttima actions to be still suboptimal to Q For example under state 0, Qmax 1) cannot exceed 1, while either Quax (0, 2) or Q (0,3) to keep the maximum of
needs to be tight (i.e. Q Qax (0, 3) = 2, or Qmax (0,2) 2) 2, both) the three no less than as required.
Note that for both Qmi and Qmax. the Lagrangian multiplier À that forms equilibrium/saddle points with each of them (resp.) may not encode policy, in general. In this example, for the constant Quin (0, 1) 0 11 (mmi((1)) a) > 0 Qmin (4, a) 1, so Qmin (1, a) >
Qmin- we have mi, a) = for all a, in which case its equilibrium multiplier À has to have A(1, a) = 0 for all a, due the equilibrium condition (2) proved in Proposition 3 Such an "all-zero" X (on state 1) cannot be normalized into policy.
Similarly, for the following maximum value function
Quxa (4, a) = Qiax (5, a) = 2
max (0, 1) = Qmax (1, a) =
Qmax (0, 2) Qmax (2 2
m (0, 3)
Quaax (3, a) 1.5
we have = Q2 max (0, 3) < 0 + 2max < 2 @m, 2, so Qmax a) < BQ (3,
2 again for all so the multiplier corresponding to this Qmax still needs to be all zero at state due to the complementary slackness condition, thus cannot be normalized at state 3.
C.4 A HOUNTER-EXAMPE FOR THE V-FORM MINIMAX VALUES IN DISCOUNTED-
Moreover, the problems with minimax value functions as demonstrated above are limited Q- functions or to ELPs only, but seem to be fundamental issues rooted from the minimax structure. To see this, consider the discounted-Mil
as shown Figure 6 below.
To be strictly align with the related literature Dai et al. (2018) Cho and Wang (2017), the rewards are assigned state-action pairs in this example. In this discounted-MDPP S =, 1,,1, 3), A = {1. 2). The initial state is set to state 0 (i.e. Po(s) if 0, otherwise Pa Pa(s) = 0). From state 0, taking
Po
F
2
2
1,2
T=U
Figure 6: An example of discounted-MDP for studying saddle points of the V-form Lagrangian.
24

---

Under review as a conference paper at ICLR 2022
action 1,2 will deterministically goes to state 1, 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 the same absorbing state 3, but with reward R(2, a) obtained (for all a). The absorbing state 3 will loop into itself forever, with zero reward obtained. An optimal policy in this discounted-MDD 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-MDD above is: Dai al. (018):
Cho and Wang (2017)
(1 (1-7)-
E Sampp
((So))
Σ
a(s,a) (R(s,a) +
E s'~P(s.a)
((S*) V(5)
(40)
(s.a)ESxA
minimax state-value function Vinn of the Lagrangian is an optimal solution of the Linear Pro- gramming problem (6), which has inspired some recently proposed RL algorithms (see Section 3 In this example, the can be more explicitly written as
min 0.5 V(0)
s.t.
V(0) 2 0.5 V(1)
V(0) 2 0.5 ((2)
V(1) 0.5 V(3)+1 +1
V(2) 2 0.5 V(3)+2 +2
V(3) 2 0.5 (33)
for which possible optimal solution is: Vuni (0) = Vmin (1) = 2, Vnna (2) = 2, Viii = 0,
which assigns the same value to action and under state 0, thus is not an optimal value function.
D LAGRANGIAN MINIMIZATION FOR MACHINE TRANSLATION
D.1 THE LAMINI ALGORITHM
the idea of LAMINI is to minimize the smoothed Lagrangian L (with a small yet definite (3) based on an unbiased gradient estimator of (13) For convenience, we copy
As mentioned in Section 4
below:
(Qww), Xn) Ar; + ET
E S.A.S' up A A (S)
E
[SSS, A, Al: w)]
where 2 =Q(w) (ala)(als)) (als) = exp (=p(Q((.a:))/)))
the Boltzmann distribution with temperature B, and Eg ezp ((s.brao)/3)
8(8, a, 8 8',' R(s') + eppi (s')Q(s', a'; w)) Q(s, a; w)) is the temporal-differen error. Al- gorithm - gives the psuedo-code of such algorithm.
Algorithm 1:
The LAMINI algorithm.
Input:
piece of rollout data made by an optimal policy, in the form of {st, a,, Tr Ju,i.....
where = Ti. T2..... ,..,.,y Th are termination steps: A parameterized value function Q (w) with initial weight vector wn; Learning rate a; Boltzmann temperature 3.
for gradient update i 0, 1,1, do Aw +- 1. E.= V a(s),
Σ Yepi (st+1) Vw
Ea (( V -Vo az; w; -(,
Wi+1 <- w; a Au
Output: ((w))-geedy policy.
Note that Algorithm [ samples the stationary distribution Pμ in (33 by averaging over the rollout data of bunch of episodes, which is unbiased thanks to the ergodicity of episodic learning Bojun
25

---

Under review as a conference paper at ICLR 2022
2020). The overall LAMINI algorithm is thus 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 GGoodfello al. (2016)).
As an implementation trick, the gradient computation in Algorithm can utilize the following fact (for brevity and clarity, we omit the argument 81+1 in Q and in the following):
e(aw))
V T (a) = V exp llo Σ, e((www))))
Ti (a). V V(10gg log Es @Q(ww)/
(a) (VQ(a: Vlog E, (((/00)//3
Es E Q(bww)/s VQ(b; w)):
= (a) (VQ(a,w)/B
Ee e((c
= =3" (a) (a) VQ(a;w) - (T) E, T (b) VQ(b: w)
and so
8 (a) Q(a; ww)
Σ f (a) VQ(a; w) + E ((a (a)
Σ t (a) VQ(a; w) +
1
Σ Tu (a) Q(a; w) (a);;w)
3
F (a) (a;:w)
(Σ Te (a) VQ(a:w)
3
Finally, we remark that the ß-smoothing trick used in LAMINI is more than just an approxima- tion 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, (n) fundamentally cannot distinguish optimal minimax-values from sub-optimal minimax-valle values, as the function attains its global minimum in both cases. In contrast, the smoothed Lagrangian (Q, Ap) tends to reach lower value at optimal minimax-valuse than at sub-optimal minimax-valuss
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 (Q),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 C% 'Q, A would still equal (p)), which can be seen from the dual form of the smoothed Lagrangian:
( -1 cl2 22.022
(()) (O,()) (14) +1.
(650) c22 e9. -
On the other hand, an optimal minimax-value can make (Q, lower than J ((4). For exam- 2a ple, when J(z) = Q O, we have ( 14e90 Q2, which attains -0.28 at Q2 = 113.. In other words, (Q, < (n) 0 under the optimal minimax-value 11.3). which is thus distinguished from the sub-optimal minimax-value (0, 0) in smoothed Lagrangian minimization as LAMINI does.
D.2 THE LAMIN2 ALGORITIM
The idea of LAMIN2 is to minimize the original Lagrangian function Cu based on the "local" gradi- ent estimator (14). The consistency of the LAMIN2 estimator (with respect to V.C,)) is characterized by Proposition 4 whose proof is given below.
26

---

Under review as a conference paper at ICLR 2022
(Proposition 41. Let A be a finite action space, and let Q(s, a: w) ) be a parameterized and differen- riable value function that suggests single best action (max(w") (w") = arg maXaeA Q(s, (,, a; w when evaluating the actions under given state with given parameter vector w", then
[ ((s,a; ())
Ve max (s,,a,w) aEA
(41)
Ro- (s:w")
where Tiax (w)) denote the )-geedy policy.
Proof. We will prove that for any component of w,
max aEA
Q(s, a; w)
Q(8, amax (w") w))
(42)
Sws
"=
Owc
which readily gives
To prove
42 notice that
((s, Omaxx (w" + A); " + +A) (ss, Omax (aommxxw")) (w=)) w= A-0
max (88 aEA
A
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 under w". On the other hand, since Q is differentiable, the change of action-values becomes infinitely small as A - O, thus the order between the two best actions will remain the same for small enough A, that amax (w= A) Omax (w") when A 0. Therefore,
(ss, Omax (w" + A); w + A) Q(s, Omax (w )) w0"
lim
A
Q(s, Amax (w") w + A)
Q(s, amax ( ( ); w
lim
0
Q(s, 0max ((s,0max("")) w)
Ow;
Note that when Q(w) is sophisticated real-valued function, such as 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 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:
piece of rollout data made by an optimal policy, in the form where = Ti, T2,.... T' are termination steps: parameterized value function Q(w) with initial weight vector wo; Learning rate a; Boltzmann temperature 3.
of {s:, a,, Tr Jo........
for gradient update i = 0, 1,2, do
Aw E1= V Q(s, (;:
w=
1.1 Tep (st+1)
Tif (6 -V aiww
t=0
w=w.
wi+1 <- w: a Au
Output: A -greedy policy.
Algorithm 2 gives the pseudo-code of LAMIN2 a further generalized form, where the greedy pol- icy Tw, is replaced with the Boltzmann policy T As mentioned in Section higher temperatures, such as B = 1.0, can slightly improve performance in our experiment results (for 0.5 0.8 BLEU score).
27

---

Under review as a conference paper at ICLR 2022
D.3 AN EPISODIC LEARNING FORMULATION OF MACHINE TRANSLATION
Many Al tasks are sequence generation problems, where we are given a context X, and are then asked to generate a sequence Y (bos, 3/1 y/ .., eos) using tokens chosen from a given to- ken 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 source language. The choice of each token y/ is conditioned on X and on the partial output Y= = (bos,): ./. 1/- In particular, Y<1 = (bos), and Y< = (bos, Y1 ..... ...)....... conditioned on which the algorithm will generate the first token y/1 and the last token V2+1 = eos, respectively.
The ELP formulation exactly captures the real-world MT tasks as described above. In the MT context, episode is the translation of a given sentence. The first episode effectively starts with S = (xa),oo) where X is a full source sentence. A learning agent then chooses a token A1 = y E Daaget U (eos), after which the environment state transits, deterministically, to S2 (X"), ) (X(), bos, ) The agent keeps generating actions A, yfth under each S. (X", Y()) until it outputs Ar-1 eos some step T I, leading to terminal state ST (X y()) (X bos, yf ... 2 eos). The agent will then make a normal action Ar as in previous steps, which however makes no effect other than resetting the environment into Sr+1 = (Xx*) from which the second translation episode begins. The process goes on episode after episode, generating a (theoretically infinite) sequence of translations (X Y (X(.)) y which collectively serve as the training data for the agent to learn better translation policies.
An episode of length T as above results in translation sentence Y (bos, // ....... VI, VV,, eos) which contains L T - 2 "normal" tokens from Mageet As a common and necessary practice, most real- world MT systems impose maximum translation length // so that if an eos action did not show up after H/ steps, the environment will transit to the terminal state S S = (X, bos, 1/1 ... VH eos) even if the agent continues to output normal token As+1 Euaget 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 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 po be an arbitrary distribution over the set of terminal states, i.e. over all source-target sentence pairs (X, where Y is complete sentence ending with eos. As with other terminal steps, no matter what So and Ay are, the next state S1 will follow the same distribution, denoted as Pt, which specifies the distribution of the source sentences that the agent will receive each episode (ELP Condition (1)).
Finally, the agent receives a scalar reward R(X, Y) E [0, 100] at each terminal state, based on the translation quality of Y (with respect to Xhe reward zero at all non-terminal states (which has only partial translations). With this reward function, the expected episodic-reward objective (xx) 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 (Exource) H x {bos} x (Eungee)) H (o,
A Enaget U {Yos}
R(s)) metric X(s),
SE s S
where S1 ((X,Y) Y ends with eos}
00
(p)())
if S1 if & S1 and (Y()) H if & S1 and (s() H
p()
1/s' (s
1| (s. eos)]
Po(s) 0 only if S1
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 x 204002048 x and |A| 40000 1.
28

---

Under review as a conference paper at ICLR 2022
The experimentation code in Supplementary Material contains faithful implementation in Python of the formulation presented here.
D.4 EXPERIMENTATION DETAILS
We tested our algorithmic idea using the WMT' 14 NewsTest English -Gemman (en2de) dataset ! The data was pre-processed and post-processed using the BPE tokenizer provided by You Tokeo- ToMe 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 BLEU score of 27.3 on the WMT' dataset under the state-of-the-ar method of MLEE based 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 V100 GPU, with the same mini-batch size (and token-padding strategy) and learning rate schedule as recommended by Vaswani et al. (217)). A dropout rate of 0.1 is applied. The learned model is then used search heuristic in the vanilla-beam-ser bea----amm--rrhhh decoding (e.g. Algorithm in Stahlberg and Bymee (2019), with a beam size 4. Empirically, we found that some more performance gain can be obtained by adding more tricks, such 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 al. (2017). but we chose 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 !
B
BLEU @ 100k
0.01
27.4
0.25
27.0
0.5
26.7
0.75
26.6
1.0
26.6
Table 1: Corpus BLEU scores of LAMINI (i.e. Algorithm) under different temperature 3.
3
BLEU@ 100k
0.01
26.0
0.2
26.2
0.4
26.8
0.6
26.2
0.8
26.3
1.0
26.8
Table 2: Corpus BLEU scores of LAMIN2 (i.e. Algorithm under different temperature 3.
29


Reviews:
[{"review_id": "lLW14rPDyDC", "reviewer": "Reviewer_1YUz", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. One motivation for this work is to work with Q-functions, rather than V-functions; the latter readily admit LP reformulations as the paper acknowledges. Usually, the advantage of having Q-functions is that one can immediately construct an (implicit) greedy policy out of it. But such an advantage is not specific to Q-functions if one has a simulator (i.e. can take samples from s' ~ s,a). Since creating a simulator on the translation task is straight-forward (dynamics are explicitly known), why is then the translation task a suitable application to demonstrate the efficacy of this approach?\n2. It is hard to make a case for the distinction in results for MDP with terminal states vs. the discounted setting. Do the results here specifically make use of this distinction? (Is Theorem 4 a part of this answer?) Theorem 1, for example, essentially follows from B^n (for large enough n) being contractive for MDP with terminal rewards, which I would argue is sufficiently similar to the disocunted case -- the same proof structure goes through. An interesting consideration here would be if only for select policies (vs. all policies currently) was termination guaranteed. \n3. The policy optimization procedure of taking gradients while replacing max_a with some heuristic (like using the behavior policy) is a bit unsatisfactory. Why is such a substitution justified? In general, granted this formulation is non-linear, when is it solvable? From my understanding, this issue is also why Nachum, Dai 2020 take the gradient on the policy evaluation lagrangian (rather than for the optimal one). \n4. Lastly, which, if any, of these results translate when the domain of Q is some restricted class of functions?", "summary_of_the_paper": "This work work in the setting of MDP with terminal states, and considers a lagrangian relaxation (really a reformulation) on the Q-values. While the fact that LP on V-functions and the occupancy measure LP are equivalent (without function approximation) follows from LP duality, the equivalent Q-value formulation is non-linear; the paper nevertheless shows that for the lagrangian strong duality holds.", "summary_of_the_review": "I'd be willing to raise my score if the above points are addressed. Otherwise, I feel the paper proves something interesting, but the translation of these ideas into either experiments or downstream theory is lacking.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Ua67dOLMbZr", "reviewer": "Reviewer_DWfZ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The theoretical results to my knowledge is new and would cover some applications. The quality of the presentation of this paper is not good. It is hard to find a clear roadmap to see what are the major contributions. My main concerns about this work are as follows:\n\n1) What are the challenges of showing the strong duality from the linear to nonlinear case.\n\n2) Why does this work focus on the episodic leaning process? Will the strong duality results be applicable to other cases? What are the unique features of ELP so that the strong duality holds?\n\n3) The organization of this paper is quite wired. Why section 5 is before the numerical section? and there is no simulation result to justify the theorem shown in section 5.\n\n4) There is no any convergence analysis of the proposed imitation learning algorithm.\n\n5) Besides algorithm1, is there a general algorithmic framework based on this nonlinear.\n\n6) Numerical results are limited. The ELP example shown in Figure 2 is rather artificial. ", "summary_of_the_paper": "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.", "summary_of_the_review": "In summary, this work indeed showed some progress regarding the nonlinear Q-function evaluation, but the quality of presenting the significance and challenges of having these results is not enough to be accepted at this stage.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JycHlrVtU2R", "reviewer": "Reviewer_fdL5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**strengths**\n\nThe theory of episodic RL recently attracted a lot of research interests in the ML community.  This paper complements the theory of episodic RL with interesting new results with good insight. \n\nThe overall presentation of this paper is well organized and follows a concentrated storyline. The authors also conducted well-designed machine translation experiments to demonstrate the usefulness of the derived learning algorithms and provide good insight connecting experiment observation and optimization theory. \n\n\n\n**weaknesses**\n\n(1) The major weakness of this paper is:  It has an implicit assumption/restriction that the reward function of the problem must solely depend on the current state.  In most MDP/RL problems, the reward function should also depend on the action (and possibly the next state.)  This weakness tremendously restricts the usefulness of this paper.\n\n(2) As a paper intending to establish new theories, it occasionally missed important points in some key steps.  Below are a few examples:\n\n(2.1) The constrained optimization reformulation (7) from (4) is abrupt.  (4) is for general MDP while (7) is specifically for episodic learning. I expected the authors to explain how T comes into play. \n\n(2.2) The complementary slackness argument above (30) seems problematic.  The complementary slackness holds only under optimal (primal, dual) pairs.  Ignoring the MDP context, consider min f(x) s.t., g(x)<=0.  For a general given \\lambda,  min f(x) + \\lambda g(x) is not necessarily attained with a x such that g(x) = 0.   In the context of (30) to prove strong duality, it does not seem we are assuming any property of the dual variables.", "summary_of_the_paper": "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. ", "summary_of_the_review": "I recommend \"6: marginally above the acceptance threshold\" by assuming the technical weakness (2) is not flaws of the paper but rather imperfectness of presentation.  However, I strongly suggest the authors conduct certain clarifications in the final version if this paper is accepted. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Although the submission studies an interesting question, many parts are not clear enough and the presentation needs to be improved. I encourage authors to revise the paper accordingly and resubmit in future venues.
Decision: Reject