Reinventing Policy Iteration under Time Inconsistency
Authors: Nixie S Lesmana
Huangyuan Su
Chi Seng Pun
Venue: Accepted by TMLR ()

Abstract: Policy iteration (PI) is a fundamental policy search algorithm in standard reinforcement learning (RL) setting, which can be shown to converge to an optimal policy by policy improvement theorems. However, the standard PI relies on Bellman’s Principle of Optimality, which might be violated by some specifications of objectives (also known as time-inconsistent (TIC) objectives), such as non-exponentially discounted reward functions. The use of standard PI under TIC objectives has thus been marked with questions regarding the convergence of its policy improvement scheme and the optimality of its termination policy, often leading to its avoidance. In this paper, we consider an infinite-horizon TIC RL setting and formally present an alternative type of optimality drawn from game theory, i.e., subgame perfect equilibrium (SPE), that attempts to resolve the aforementioned questions. We first analyze standard PI under the SPE type of optimality, revealing its merits and insufficiencies. Drawing on these observations, we propose backward Q-learning (bwdQ), a new algorithm in the approximate PI family that targets SPE policy under non-exponentially discounted reward functions. Finally, with two TIC gridworld environments, we demonstrate the implications of our theoretical findings on the behavior of bwdQ and other approximate PI variants.

Published in Transactions on Machine Learning Research (11/2022)
Reinventing Policy Iteration under Time Inconsistency
Nixic S. Lesmana
winiesap001 @e.ntu.edu..
School of Physical end Mathematioal Sciences Nongang Technological University
Huangyuan Su
huunngus@@andreu.ccom cww.. edu
School of Computer Science Carnegic Mellon University
Chi Seng Pun
SepunOntur edu.sg
School of Physical and Mathematical Sciences Nonyang Technological University
Reviewed on OpenReview: https:// o/pperv//penevvieeu.u net/ fermfo id= bN2UWLThhP
Abstract
Policy iteration (PI) is a fundamental policy search algorithm in standard reinforcement learning (RT) setting, which can be shown to converge to an optimal policy by policy improvement theorems. However, the standard PI relies on Bellman's Principle of Optimality, which might be violated by some specifications of objectives (also known time-inconsistent (TIC) objectives), such non-exponentially discounted reward functions. The use of standard PI under TIC objectives has thus been marked with questions regarding the convergence of its policy improvement scheme and the optimality of its termination policy, often leading to its avoidance. this paper, we consider an infinite-horizon TIC RL setting and formally present an alternative type of optimality drawn from game theory, i.c., subgame perfect equilibrium (SPE), that attempts resolve the aforementioned questions. We first analyze standard P1 under the SPE lype of optimality, revealing its merits and insufficiencies. Drawing these observations, propose backward Q-learning (bwdQ), PI family that targets SPE policy under non-exponentially discounted reward functions. Finally, with two TIC gridworld enviromments, we demonstrate the implications of our theoretical findings on the behavior of bwdQ and other approximate PI variants.
algorithm in the approximate
1 Introduction
Policy iteration (PI) has enjoyed long history of success in standard reinforcement learning (RL), which can be attributed to standard PI that combines dynamic programming (DP)-based policy evaluatior and greedy policy improvement; see Bellman classical RL algorithms, such as value iteration and the popular Q-learning (Watkins & Dayan (1992) ) and it still inspires the design of modern RL algorithms. Despite its prominence in standard RL setting, standard PI has been docmed incompatible for time-inconsistent (TIC) objectives due to non-monotonicitty and the implied violation of Bellman's principle of optimalily (BPO).
(1977 ; Howard (9600). Standard P1 has been the basis of many
Time inconsistency (also abbreviated as TIC) is prevalent in dynamic choice problems and captures well human's tendency to deviate from their current plan at future time; such deviation ariscs a plan of future course of actions that is optimal for human agent loday, may not be optömal for the same agent in the future. Tn the context of RT, TIC often arises resulting in TIC objectives upon which an RL agent is built on, and has been investigated through several major channels such as hyperbolic discounting and risk-scnsitive RL.
effort to more closely model human preferences,
For formal introduction, readers may refer Eq

---

Published in Transactions on Machine Learning Research (11/2022)
The idea of questioning the validity of standard PI under TIC was pioneered in risk-sensitive RL by Sobel (1922). In this seminal work, a counterexample to the monotonicits property (also referred to as consistent. choice, temporal persistence, or stationarity across the literature) was posted and attention was raised in how this property is commonly exploited to prove the convergence of standard policy improvement scheme to an optimal policy. Two puzzles are then left for answers:
How optimal is the termination policy (the policy obtained at the end of an algorithmic search) of standard PI?
and
Is it possible to guarantee the update monotonicity (a desirable algorithmic property that will lead to convergence) of standard PI?
In this paper, we focus infinite-horizon TIC RL problems and formally present the subgame perfect equilibrium (SPE) notion of optimality that corresponds to how sophisticated, rational agent acts in the face of TIC ie., planning consistently in terms of solving optimizations that take into account the future deviations. We will then revisit the two questions above to highlight standard Pl's merits and insufficiencies in achieving the SPE notion of optimality.
The contribution of this paper can be summarized as follows:
In terms of optimality, we establish that the termination policy of standard PT under TTC achieves SPE.
We study the failure of policy improvement theorem (Sutton & Barto 2018 and highlight some insufficiencies of standard PI update and the existing analysis tools, in the context of SPE policy search.
TIC-adjusted DP formula is established to compute nonexponentiallyddiooueedd Q-function, ad- dressing the insufficiency of standard DP formula.
Basod on the aforementioned analyses, we devise a new PI paradigm for non-exponentially discounted reward functions: backward Q-learning (bwdQ).
We design toy Gridworld examples to demonstrate the implications of our findings on the bchaviour of bwdQ and other approximate PI variants under TIC.
The analyses (in Section and 4.3 relevant to the advantage backward condilioning in bwdQ of independent interest: the characterization of its termination policy as SPE and its efficiency-relaeed desirability an SPE policy learner extend beyond general-discounting objectives.
Note that some lengthy proofs proofs/justifications of our results are deferred to Appendix.
2 Related Works
Non-monotonicity in risk-sensitive RL and solutions. In risk-related context, several follow-up works since Sobel [1982] address the non-mono con-monotonicity issue following the line of reasoning that the search for a globally-optimal policy in non-monotonic problems are computationally expensive (as one can only emumerate over the whole policy space that almost impossible in practice) and hence, new solutions are desired. For instance, Mannor & Tsitsiklis (2011) formally compares between several policy classes to reduce the search problem for globally-optimal policy (to specific policy class) and proposes several practical approximation algorithms. One important finding in their work is that randomization can improve control performance;
2A formal definition to monotonicity is provided in Eq 15 Intuitively, if decision-making problem is monotonic, then delaying the use of any two decision policies will preserve their ordering (In terms of the policies" values from any states). When this property holds, we can typically break our problem into subproblems as BPO and attain computational efficiency.
2

---

Published in Transactions on Machine Learning Research (11/2022)
this inspires Di Castro al. (012); Tamar & Mannor 2013 Prashanth & Ghavamzadeh 2013 to propose gradient-based algorithms accustommd to mean-variance criteria, which highlighted parameterized stochastic policy as manner to deal with non-monotonicity, The latter works are relevant to our case as they also use TIC adjustment terms to obtain temporal difforence (TD)-based policy evaluation (PE) that resembles the one used extended DP theory Björk et al. (2014). To distinguish our approach, we nole our focus on using SPE policy itself to deal with non-monotonicity (by modifying our optimality type) as opposod to randomization or parameterization.
Non-monotonicity in hyperbolic-discounting RL and solutions. In hyperbolie-discouniing context, non-monotonicity have also appeared, independent of Sobel (1822)'s 's work; see Kurth-Nelson & Redish (2010) for instance. In this work, several proposals towards computationally practical models are reviewed, with varying action selection strategies drawn largely from behavioral or neuroscience point of view. A recent follow- up work by Fedus et al. (2019) extends their distributed micro-agents model (i.c. p.Agents) to handle larger scale problems, utilizing deep neural network to model the different Q-values from shared representation. Though such modifications in action selection may have implicitly addressed the non-monotonicity underlying PIT failure, to the best of our knowledge, an explicit connection between the two (as in Sobel (9822 has never been made.
Timo-consistent Planning and Control. The idea of locally optimal, timo-consistent planning under TIC was pioneered by Strolz (1955); Pollak (1968). This lype of planning corresponds to a sophisticated, rational agent's behavior who, when faced with TIC, compromises with their future selves by taking future disobedience a constraint in their decision-making. The solution concept is developed
game-theoretic framework that builds on backward inductive SPE search in games, thus coining the term SPE plan or policy. This then leads to an intra-personal equilibria formalism by Björk & Murgoci (2014) which unifies several task-specific TIC sources through extended DP theory and has attracted a wide array literature in TIC stochastic control. The rise of SPE policy as a major contending solution to the globally optimal (precommitment) policy can then be attributed two reasons: (i) as controller, precommitment policy may lead to some undesirable outcomes since it may lose its optimality as time evolves (for instance, due to unpredictable change in environment dynamics), (ii) computationally, there is lack of pivotal tool to identify globally-optimal policy that generalizes naturally to different TIC tasks (for instance, due to its disconnection to standard DP that requires BPO).
SPE Policy in TIC-RL. Some works the general-discounting space have investigated TIC-RI. from a purely behavioral lens, focusing particularly on the property of target policy rather than a computational aspect. For instance, Lattimore & Hutter (2014) proposes rational agents that act according to history-dependent SPE policies. In this work, the authors cover some theoretical aspects of policies such characterization of different policy types, existence results connecting discounting and policy types, and comparative study in some example scenarios. In another work, Evans et al. (2016) proposes sophisticated agents that act according to Markovian SPE policies and are modelled with angley-e Q-learning algorithms. Though relevant, these algorithms are proposed in the context of generative models that aids human-like preference inferences; thus, algorithmic properties are not covered. A recent work by Lesmana & Pun (2021) considers the search of Markovian SPE policy under extended DP theory, the authors propose Backward Policy Iteration (BPI), which has lex mesooonotoncciyy guarantee in place of the standard policy improvement theorem. This work is the closest to ours where our backward conditioning can be viewed as an hhorite- extension to BPI. We distinguish our contribution by noting our main focus on analyzing standard PI, that motivates our infinite-horizon Markovian SPE policy formalism and the corresponding drop of time-dopendency, shifting definition of players from times to states. Relative to finite-horizon case, such formalism introduces technical challenges in both aspects of policy evaluation and improvement, which will remark on the respective sections of this paper.
rask-invarian TIC objectives. Drawing inspiration from the
3

---

Published in Transactions on Machine Learning Research (11/2022)
3 Problem Formulation and the SPE Concept
In this section, we introduce the class of TIC RL problems of our interest and formally present the solution concept of SPE policy. We then cast the general-discouniing objective as a TIC RL problem and construct a few examples in this context that we will quote frequently throughout the paper.
3.1 TIC RL Problem Formulation
We consider the policy search in an infinite-horizon TIC-MDP, which consists of the standard MDP tuple (S, A, R,) and a specific TIC source. The state space S and action spaces A, C A, Vs E S, are assumedd to be discrete and finite with stationary probabilities (-) = P[ = S,+1 = S, = - A, a] governing the transitions from a current state St = s to the next state S and reward Rc+1 for E S, given particular action A, = To define stopping criterion, it is convenient to augment a so-called absorbing state, denoted by Svoid, which incurs no reward. Then, we define slopping action ā as an action that drives a transition to Synid from any states 8 E S and boundary states 8 E S as rewarding states with specific action space As or A={aj, ie. once the boundary state is reached, we conclude with reward as there is only action a that will transit us from & to Syoid and then make us stay at Svoid forever. This setup is to complete the mathematical framework of the environment for analyses, where the problem interest has certain stopping criteria, e.g., after receiving a target reward.
Let next denote by IIP the set of all Markovian, deterministic policies π {=(s) : E S} with w : S + Ag. To aid presentation in subsequent sections, define as policy that prescribes the use of action E A for current one-step decision and policy π for all remaining decisions. Similarly, we denote by 8 क a policy that fixes the first T > 0 steps decisions to d == (ō(Sw) t S w <(+T), with a map 8: S + A, and a current time t, and follows π afterwards.
TIC reward structures and criterion We first note that by our assumption on stationary transitions, we are limiting our TIC scope those that arise from reward structures and criterion, described as follows. Let consider a general criterion V (with form not restricted this point) for any E TT and E S. Given an initial state 8o E S, a standard notion of optimality aims to solve the global problem Po.eo = max, (*(ss) and obtain the corresponding globally-optinal (precommitment policy denoted by n T". Next, let us define for each delay + > 0, the local problem Pr.,,, - max V* (*+),, where 8, represents any realization of S, following the sequence policies { ( (S)) :0 stttrr T 1 = 5p), and denote by π (*77)) its solution. Bellman's Principle of Optimality (BPO) then states that
VT, 8r, क (** = =x (s7)
(1)
By the BPO definition above, the standard RL criteria belong to the time-consistent (TC) class that does not violate T While in this paper, we consider criteria (*)(s) that violate [ these include general-discountin
risk-related, and more (cf. Björk & Murgoci (2014)). ). Given any critoria (s), one can vorify whether it
belongs to the TIC class through a counterexample (which will be illustrated with Example 3.7 below).
It is noteworthy that our way in defining TIC criterion is unlike most MDPs that specify the criterion V (s) up to the expectation of cumulative rewards. We aim to maintain generalities up to the formalism of SPE optimality (in Section 3.2) that is valid for different forms of TIC reward structures and criterion. For instance, while gemeral-discoutting objectives still admit an expectation form, risk-sensitive objectives involve non-linearity in expectations. That said, to fully define a TIC-MDP, we need the exact specifications of reward structures R and the corresponding TIC sources. We will further discuss on this topic in Section 3.3 with general--iscoontinn specifications.
3.2 SPE Notion of Optimality
In the previous subsection, we have established our focus on the objectives that violate BPO in ① Once BPO is violated, -=0 + π * for some T, s, and we will have a collection of competing optimization problems (Pr.,, : VT E [0, oo). s, E S} to solve. We then have two options. Firstly, we can focus on only a single agent corresponding to (0, so), denoted by Agent-sp, and solve for globally optimal or so-called
4

---

Published in Transactions on Machine Learning Research (11/2022)
precommitment policy. However, we have noted in Section 2 this is expensive to obtain in general and more importantly, it has been known to suffer from the two puzzles in Section Secondly, we can consider {Pri, : VT E [0, 00), , E {} as a multi-agent problem, where each Agent-s, is associated with the problem Pr,,,; and solve for the Nash equilibrium of this (sub-)game, i.. SPE.
In this subsection, we will formalize such SPE notion of optimality in an infinite-horizon setting. Let us consider any TIC criterion (*))) and define the corresponding action-value Q-function (* a) (s) Our aim is then to find an (stationary) SPE policy A, defined follows.
Definition 3.1 (SPE Policy). A policy # I is an SPE policy if it satisfies
Qa (*)) Q* (s, Va E As,
(2)
In other words, our game consists of Players, indexed by the states S, and we search for SPE, where Player takes into account the strategies of other Players s' E S {s} in its decision making as will be transited to an s'. In particular, Definition 3.1 implies that any state s' does not have incentive to deviate from its strategy f(s") when everyone else plays म; note that this is how SPE takes into account future deviations, as we mentioned in Section [
Remark 3.2. It is important to note that in standard RL, the policy that realizes Definition 3.1 (or so-called non-positive advantage) is the optimal policy. However, such equivalence draws on BPO, which does not apply in TIC RL. Once BPO is violated, the optimal policy (one that solves Po..o == max V*(s0), that we refer lo as globally-optimal/ peppimal/precommmmmenn policy π πー) is no longer equivalent to the one that realizes non-positive advantage (one that solves the game induced by competing local optimizations Pr,,, == max V* (s7)), that
we refer to as SPE policy Ø). As we will see later in Section 3.3 an SPE policy (cf. Figure I(c)) can be
neither equal equivalent in value to the globally-optimal//rees precommmmmteemmmmmemtt policy (ef. Figure [bb).
Throughout this paper, we will adopt several technical assumptions to address the technical challenges of such infinite-horizon SPE, particularly those that arise from the derivations of TIC-adjusted DP Section
4.2 and backward conditioning update in Scction 5.1
Assumption 3.3. Ys E S, Ve > 0, there cxists truncation step T < 00 s.t. VT E MD , : A
(TT())
((6)-v>'' v= * (8) c
(3)
Denote by Ts.c the smallest such T. Assumption 3.4. Eso E S s.t. I.. < <0
Fu V S (so).3m MD
Σ
PIST s/S, sol 0.
Intuitively, Assumption 3.3 asserts that starting from any s and following any policy π. any rewards generated after T steps are negligible as the policy मे incurs 0 rewards Then, Assumption 3.4 ensures the existence of at least one state sy from which all other states s S {56} can be reached in finite time, with positive probability. Combining these two, we fix 80 and set T. max (T., T, to obtain our last assumption.
Let us define s = {5o} and Vt E (0,
Assumption 3.5.
S S
{s E S: E (0,t), s, S. s.t. 3π E MD PIIST =|So s7] > 0}
(4)
Then, Ve > 0, V (0, T.). Vs, E Sy MD and VT MD with P[S sc|so] 0, 3x(e) k(E, t, St. ग. s0)
s.t. (TT(s)) y* th - (st) x and lim x(e) 0.
"We note one important implication of Assumption 3.3 bounded value functions, which proof can be found in Appendix
A.2
5

---

Published in Transactions on Machine Learning Research (11/2022)
Intuitively, Assumption 3.5 ensures the negligibility of rewards under from any intermediate states 8t E (.... &S when there is a path connecting to So under the same policy и. In Appendix A.1 we show that these assumptions are reasonable in practice through a set of sufficiency conditions (in general-discounling context, in terms of restrictions on MDP and discounting function).
3.3 General-discounting Criterion
As major concern of this paper, we consider the following infinite-horizon criterion
8r) = E Σ ((t-7))(ST x {(T)) 8r
(5)
defined for any 2 O, with general discounting function o : - (0, 1]. The intermediate (possibly random) reward function R: S x A Rt follows the standard MDP formulation, with emphasis on its boundedness and non-negativity. We further note our use of notation ST for the (random) state visited at time / on a trajectory generated by following policy π and initialized at S = 87.
Next, we define action-value or Q-function that relates to the value function in 5
Definition 3.6 (Q-function). For each state-action pair a) E S x A and fixed policy π E II we define Q-function as
(" E
(()) (T((TT)) So
(6)
Note that to emphasize on the stationarity of our problem, we have avoided any explicit appearance of т in the Definition 3.6 above by performing a simple change of variable drawn from the Markov property P[ST = S, = s, P[ST- = St|S, = sy]. Later Section 4.2 r will be re-introduced as our RL agent's parameter that keeps track of nonstationarity changes.
We may now revisit the TIC concept by witnessing how criterion 5 violates BPO through Gridworld counterexample.
Ezample 3.7 (BPO Violation). Consider a Gridworld environment as deseribed in Figure 1(a) and a byperbolically-diccommm criterion, i.e, setting g - r) = 1/(1 + A(t - 7)) in (5) Given 8g = 21, we can compute (by trajectory enumcration) the globally-optimal, procommitment policy π -0 as in Figure (bb) After applying delay
and following the delaying policy 8 π we reach 8, at which the locally-optimal policy suggests nT = {9)) { and accrues rewards V (s,) 10/ 1) 19/(1 +3) V (s,); see Figure 1(d). This violates BPO at 3 and s, = 9.
TIC value function and Q-unction as defined in 5 - for any appearance of V*(s) and (s a), unless specified otherwise. We then denote by (i and QTc s, a) the exponential-discouniii (i.e., (tl)= = 7²) Lime-consistent (TC) value function and Q-lunction to exemplify any standard RL formulations in the subsequent sections.
Here onwards, we will use the
4 An Analysis of Standard Pl
In this section, we analyze standard PI under the SPE optimality type, revealing its merits and insufficiencies.
4.1 SPE Optimality of Termination Policy
We first present the standard PI update.
T' (()) f- arg max aE
(s.
(7)

---

Published in Transactions on Machine Learning Research (11/2022)
(a)
+11
3,4
(b)
W
W
10
A
A
12
13
15
12
13
L
15
16
19
16
19
20
21
22
23
20
21
22
23
2
Ayb
(d)
W
W
11
A
11
15
12
15
19
16
19
23
Figure 1: (a) Deterministic, Hyperbolic 1I Gridworld. S comprises absorbing states $ (2, emitting rewards R(2) 19, R(8) 10. Each action in A {t. 1,,,,,+7 +-} drives transition through deterministie P; transitions to WALL outside the grid will spawn the agent back to its original location. (b) Globally-optimal, precommitment policy - and its corresponding path, accruing accumulated rewards V* (so) T+6 This path exhibits TIC at J and 8,
shown in Example 3.7 (c) SPE
policy # and its corresponding path, accruing rewards V (80) I+8
19 V=* (so). One could refer back to
Definition 3.1 and verify that states Sy this path have the incentive to deviate from its current policy *(s,). (d) Delusional policy 8 x and its corresponding path, with т, o, and "- specified in Example 3.7. accruing rewards of 188 " (so) = I+4 < V*(s)). The term 'delusional' is used to reflect how state 21
19
presumes will go up, unaware the TIC issue.
where n', represent new (at current iteration) and old policies (at previous iteration) in any two consecutive iterations. Next, will show the merit of standard PI in Proposition its termination policy achieves SPE optimality.
Proposition 4.1. If n' = and update follows the rule in 7. then TT' are SPE policy.
Proof. By 7 and nt we obtain that Va E As, Vs ES
(s, (')) 2 (s. = (=({x((s)) 2 (s,a))
Thus, by Definition 3.1 n, n' are SPE policy.
4.2
Policy Evaluation
The update rule requires the computation the TIC Q-function QT a), which is not straightforward. In standard RL setting, there DP formula to efficiently compute TC Q-function,
QTo(s): = ER R(st. a) + (VV))
(8)
where (s) (itcratively) solves { after substituting (s;)) into a, Under general discounting as in no longer holds. In this subsoction, we present a recursive formula satisfied by our TIC Q-function (scc below) by leveraging the extended DP theory (Björk al. 2014)).

---

Published in Transactions on Machine Learning Research (11/2022)
TIC-adjusted DP Noting that in Section 3.2 we have assumed access to fixed T. < co, introduce reward adjustment (or r-function) that our agent will use it to track the nonstationary changes (due to TIC) in Q-function.
Definition 4.2 (r-function). For each {O,... TeJ, m E (T...., T.). s SES, a A, and a fixed policy π E IIMP, we define r-function as
y p (8, a) E [mpm - T)ll (S (S)))) =s]
(9)
where and fixed parameters.
Next, we will use the adjustment function above to obtain a formula that recursively computes our Q-function Theorem 4.3. For any fired π ITMD, (0, Te), m (r,...,Tehh TT], E ESS, E As, r-function satisfies form= m
TT (s, Eu
(10)
and for m 2 r T 1,
m0mm - T) (p(mm - (T (5.
(s, (8,0) = Est
(11)
Moreover, for any flxed π E II t t0.... Tch, E at E Asi under some technical conditions (see Assumption B.1 Q-function satisfies for st and a E A,
(" = ERpP"
(12)
and for s, E S\S and a E Ase
(1),)))))) ss ERapsE
+ Eginp: (S" (0() Art,
(13)
where Ar7 Em=u41 (Esi~pht ( (S',
- - (se, an)
Remark 4.4. Both the proof of Theorem 4.3 and the technical conditions for are provided Appendix We note that Theorem 4.3 is an analog Proposition 11 in Lesmana & Pun (2021) and our main technical novelty lies in the approximation and limejo x(e)
('=") part of [13; here, zs b denotes the existence of <<c) s.t. |a la-b) x(e) i 4 Intuitivoly, this result ensures that our approximation error can be made arbitrarily small by choosing sufficiently large Tc.
Remark 4.5. Theorem 4.3 has used the specific properties of general-discounting TIC source. For other types of TIC sources, recursive formulas need be re-derived. In risk-sensitive case, for instance, readers may refer to Tamar & Mannor
(2013); Sobel 1982).
1992 are drawn from Standard TD-based approximation algorithms such as Q-learning Watkins & Dayan
the standard formula. (5) and thus, are insufficient for general-discounting factor. Theorem provides formula that addresses insufficiency of standard formula (8), which we will later use to reinvent new approximate PT algorithm for general-discounting objectives.
4.3 Policy Improvement (Update Monotonicity)
In this subsection, we will highlight some insufficiencies of the standard PI's update and analysis tools in the face of TIC by revisiting the unprovable policy improvement theorem. To start off, we present the following proof (ef. Sutton & Barto 2018)) of the theorem: Vs S,
VTc(s) S QTc(s i = R + x VTT =
s E RE + a ('S =... S
< vTs(s).
(14)

---

Published in Transactions on Machine Learning Research (11/2022)
'=' Note that in each alternating step 'f' and 's', two operations performed: (i) recursive expansion of TC Q-function, and (ii) substituting the monotonicity relation:
E E S, Via (s) 2 (s) = E S, " 2 ViC (s)
(15)
for all delays T and 8 = { < Let us pay attention to the monotonicity relation, particularly
about how 11 fails under TIC criterion. To this end, recall Example 3.7 and focus the states along the precommitmentt path in Figure [bb). We can then counter
15 follows:
Set π = T== 3. = T (9) = +; then,
19 I+3
=
VT
(9) S V (9)
I+I
10 holds. However,
19 V8 (21) g [V (9) Eg V * (9) V x (21) 1+4
10
(16)
1 1+0
showing that at 21, the monotonicity relation
15 does not hold.
We make two observations here: (i) defining improvement as in policy improvement theorem (i.c.,
Vs E S, V- (s) 2 (*)))) might be too strong as this definition targets optimal policies not SPE policies, (ii)
the counterexample 16 suggests the existence of priority ordering over S (i.e. 9 holds priority over 21) such that unordered (i.e. Vs E S) update as may not suffice. To further probe on these issucs, we will consider the following example.
Ezample 4.6 (Inefficiency of Standard PI). Let us refer back our Hyperbolic Gridworld in Figure [a). Wo will keep our deterministic transition and reward functions, but restrict our stale-space to:
$ = f1,2, 8, 9. 11, 13, 15, 17, 19, 21, 22,
and action-spaces
Ån {t, +}
Ag = (t,+},
A3 = {-}
A, {+},
Ys E (1,22),
A, (t). Vs (17, 5, 7, 11, 19,23)
A =a], Vs (2,8).
Letting = 22 = 0, = { E MD | + Á.}, we have a priority-ordering on S, S 3
So = (21), ; $
(1,,2)), 82 = 113, 23), 8, (9, 84 15,8,
8 (1, 8. = (2,7), 8, = (3), Sg 12)-
(17)
To apply standard P1 for SPE policy search from so = 21, we choose initial policy (() illustrated in Figure aa) Following the standard PI's rule
policies at all states are updated conditional to the policy at previous iteration. Let us now focus on the two important states = 9, 21, in which decisions need to be made (i.e., [A.] > 1). First, note that after updated conditional to the previous policy x (00)(9) =t, we obtain x (21) =f that incurs a higher reward; see Figure 2 (b). Following the same rule, we also obtain T (() +. When combined, the current iteration ends up in T that corresponds a delusional path; see Figure ().. We contend that such ilerative update is inefficient as would have found the desired SPE path if state 21 has anticipated (9) = when making its update. We will see how achieve this in
Section 5.1 by leveraging known priority-orlering in [17
5 Backward Q-learning Algorithm
Drawing on the analyses and observations in Section family that. targets SPE policy under a general-discount ing criterion.
4
we propose new algorithm in the approximate PI
"y either the sophisticated agent's strategy Strotz 1955
its SPE formalism Björk al. 2014 higher priority here
corresponds to later order visitation in trajectory

---

Published in Transactions on Machine Learning Research (11/2022)
(a)
(b)
+9
(c)
+9
10
10
11
B
A
11
16
19
20
23
20
22
23
Figure 2: 2-Layered Correction with Standard PI. (a) Policies at initialization. (b) Policies after state
21 updates. (c) Policies after state 9 (and all other states) updates.
5.1 Backward Conditioning
To mitigate the insufficiencies surrounding update monotonicity, we build on recent result in Lesmana & Pun (2021) and propose backward condilioning: to perform update backward from Sp. to So and conditioning the update of states with lower priority (happens earlier) the new policy x' of states with higher priority
(happens later). We formalize the above in the following update rule.
Definition 5.1 (Backward Conditioning Rule). For any > 0, set = Te and let Sor == S priority-orderiig on S. Then, for / = TT- 1:00:
be a
U:T
Vs Se, (s) arg max (s,
(18)
aEAr,
Remark 5.2. Note that in the Definition 5.1 we have assumed the existence of a priority-orderian whatever actions the states in Sa:-1 are taking are assumed have no effect on the choice of states in S, This justifies (18: : its backward order and conditioning the update of any S (with highest priority) the old policy æ. We note however that even without such priority-ordering the worst that can happen is St S = St [0, TT, which is equivalent to performing standard PI in (7 times.
Next, we will show that the backward conditioning rule preserves the SPE optimality of termination policy.
Proposition 5.3. If nt = π and update follows the rule in equation 18 then n, x are SPE policy-
Proof. First, we will show that
Vs S, E Saa.11
(19)
0.7-1
Since T. - 12 Pay, by definition of Pag, Vs E
1-11
3F E IT MD
P(S = s|sol > >0 31 E [0, T. - s.t. 3r E MT ,ISTT = =s|so] > 0
1=0
3 E [0,
s.t. S.
8 E S S -1-
Now, let us consider arbitrary s E S. By Ya E A.,
19
3 E [0, - 1] s.t. s E Sz. Using such t, by
18
we have
QiT')
(s)) 2 ( - (s,
which by T², implies
(s, 2 Q (s.a).
10

---

Published in Transactions on Machine Learning Research (11/2022)
Example 5.4 (Efficiency of Backward Conditioning). To illustrate the difference between
18 and let
reconsider the setup in Example 4.6 Given the same ini initialization (see Figure B a))), backward conditioning rule (18) asserts state 9 E S3 to update earlier than state 21 E So, in one current iteration. This necessarily mcans that by the time state 21 updates, it will have anticipated state 9's current policy (() = +- (see
Figure b)) and directly obtain the desired x (21) = + (see Figure 3 3(c)). When combined, such current the target SPE path मे note how the path extending from s0 21 in Figure 3( overlaps with the one in Figure [c.. In contrast to (7), backward conditioning imposes that the choice of later states are directly propagated to earlier states in each policy iteration and
iteration ends up in π (1) that corresponds
correspondingly prevents inefficient movement of policies (i.e., away from SPE policy in Figure 2
(a)
+18 S45
(b)
+19
(c)
19
W
10
10
12
12
13
15
12
13
15
16
10
16
20
Figure 3: 2-Layered Correction with Backward Conditioning. (a) Initialization. (b) State 9 updates first. (c) State 21 updates last, after 9, 13, make their updates.
Remark 5.5. Through Example 1.6 and Example 5.4 we have concluded that relative to standard PI, backward conditioning mitigates inefficient movement of policies (cf. Figure 2 by propagating information about future players' "optimal" policies (as soon as it is found) directly to carlier players (cf. Figure 3 To see how this phenomenon transfers to a TIC "Q-learning" setting, readers may refer to Table 1 in Section 6.1 and
Appendix D.4.3 particularly to (i) the reduced delusionality in earlier episodes under backward conditioning
(cf. Figure ) as compared standard forwardly-ordered version (cf. Figure ((c),, and (ii) the improved stability of F Figures [e)-(() relative to Figures (()-((). We would like to remark that our observations are consistent with the results of related literature under non-TIC motivations, e.g., sample efficiency (Lin) 1991
Lee et al. (2 consistent uncertainty propagation (Bai et al. (2021)), where they have similarly concluded backward update's power in information propagation.
Remark 5.6. In Theorem 25 of Lesmana & Pun [202]], finite-horizon analog to the update rule 18 has been shown to exhibit. lex-monotonicity (i.e. a weaker update monotonicity than PIT that reflects closer to SPE), by leveraging a policy-independent ordering on time-extended state-space due to T < 00 (i.e. players are times). This prevents the cycling of policics, implying convergence. In T oc, we lose this order (i.c. players are states) and resort to using visitation order on trajectory. This results in a lex-mono analog: Vt, if TT'S, is closer to SPE As., than , and S3,- 137, Convergence thus remains open complications may arise when S. Sp + for some tt.
is T''.- It discussed through Example 5.4 when St {21}
5.2 Approximate Backward Conditioning
In this subsection, we are interested in deriving an approximate version to the backward conditioning rule in Definition 5.1 This can be done in two steps. Firstly, we will replace the exact computation of QT (x,a) with prediction. To this end, we will use our results in Theorem 4.3 and derive TIC-adjusted TD targets for
predicting x az) from 10 11 and (T((s, az) from 12 -11).
((0) at);
m t
& (m)
(20)
20m-1h +1m (S411 1aa1,'((S (((+1))), m
(1n-((+1))
11

---

Published in Transactions on Machine Learning Research (11/2022)
((0)R(s), ae) + 7( max(O, Ard), t 65 2 (0))
6
(21)
t= and 8t E E
where År, = Em
a.). Then, we can incorporate the backward conditioning simply by reordering update from the end of sampled trajectory t t= T to 0. Note that here, we have replaced T with T < T to account for the variable length of trajectories encountered in practice. We summarize this section with pseudocode in Algorithm 1 where lines 11, 18 20 capture our backward conditioning and lines 12 - 17 capture the TIC-adjusted TD evaluation
5
Algorithm Backward Q-learning (bwdQ)
1: Parameters: exploration rate e, episode length T, learning rates aqq Cr
Init:
Q(s, a) Ys 8 A;
((s,a) R(,) S,a A;
as 0, VT, m. S A;
6: <s(s) + arg max, Q(s, S t
7: repeat
8:
π + =²;;
Choose So randomly;
10: Sample Sg. ............ 1, Ar- ST,, Ar- nT';
11:
for L T to 0 do
12:
for +
t to T do Compute (m) according to 20
13:
14:
(St, At) + (S, A,) + +a, (e((())
15:
end for
Compute & according to 21
16:
17:
Q(S,, A, + Q(,,, A₂) + ( if Q(S,, (S,)) < max, QS,, a) then
QS,, A,));
18:
19:
n' (S,) t- arg max. ()
20:
else
21:
T't) n (St) end if
22:
23:
end for
24:
until stable (T' # T
Remark 5.7. While Algorithm I can be considered as a Q-learning's variant, standard convergence analysis such as in Bertsekas & Tsitsiklis (9966) does not apply to our case. Even more recent analysis techniques on coupled iterations such those done for double Q-learning (Hasselt) (2010); Xiong al. (2020): Zhao et al,
(2021)) do not apply to case for the fully-coupled dynamics of the iterated r-functions and Q-function. Formal convergence analysis of backward Q-learning is thus left for future study.
6 Learning Performance: An Illustration
In this section, illustrate the behaviour of bwdQ in two TIC Gridworld environments: (i) Deterministic (D), by reusing our motivating example in Figure | which has been shown to exhibit future deviations, and (ii) Stochastic (S), by injecting some random noise into state 9's transition in (D). For our comparative study, we consider as benchmarks two approximate PT variants that also target SPE policy under general-discounting objectives, namely standard PI with Monte Carlo (MC) and sophisticated EU (sophEU) from Evans et al.
(2016). Pscudocodes and training specifications are provided Appendices D.2 D.3
For detailed derivations of Algorithm readers can refer Appendix
12

---

Published in Transactions on Machine Learning Research (11/2022)
6.1 Results
Our results and evaluation be segregated into three components: efficiency, value prediction, and termination policy, all of which are summarized into Table ! and Figure !
Efficiency In Section 5.1 we have provided an intuition on the desirability of bockward conditioning. From Table 1 we can its implication to actual learning instances with approximation. In particular, we can observe that bwdQ demonstrates higher learning efficiency in both (D) and (S): it has significantly shorter Ai in average (mean) with lower standard deviation compared to the others.
Table 1: Delusional period Ai = 16 - اgو statistics, presented as mean(stdev) (in thousands). This
metric relates to the 2-layered correction illustrated in Figures 2 and 3 Ai quantifies how many iterations 21 needs to reflect 9's move to SPE. Episode indexes ig and 12 represent the first overtaking episodes of mean SPE Q-value at states and 21, respectively; see Appendix D.4.1 for illustrative Q-value curves. For each algorithm and environment, 10 experiments are conducted and each consists of 50 random seeds.
MC
SophEU
BwdQ
(D)
(3.39
(9.97
2.37 (0.73)
(4.55(4.83)
97.56
(..5
Deterinistooo (D)
Deterministic (D)
(a)
(b)
+
25
t
W
+
1.0
2
0.0
Epeodos
Srachaetc
Stochastic (S)
f
W
23
f
1.3
43
L
6
f
Figure 4: (a) Value learning curves of sp 21. (b) Termination policies. For each algorithm in (a), the dark line and the shaded rogion each refers to the mean and standard deviation of 50 experiments, where in one experiment, we record the values Vi(sa) Q*(sn, T (so)) at the end of each training episode i. In (b), we record the termination policies r'(s), Vs S after the policies at all states stabilize training episode I; note that here may differ across algorithms and experiments as only want to show the asymptotic performance of each algorithm in learning SPE policy. Groundtutth 'TRUE' in (a) is then computed as the value of analytical SPE policy in (D), and the value of termination policy in (S).
13

---

Published in Transactions on Machine Learning Research (11/2022)
Value prediction From Figure a), we observe that in (D); the mean value of bwdQ matches closely the groundtruth (manually computed) upon convergence. On the contrary, sophEU and MC both converge at. value strictly smaller than the groundtruth. Similar conclusion can be drawn in (S), despite bwdQ produces higher variance than the rest; see Appendices D.4.2 D.4.3 for more results and discussions on value biases.
Termination policy In both (D) and (S), all algorithms (i.e. MC, sophEU, and bwdQ) converge and the termination policies are plotted Figure [b). While all algorithms converge to the same policies in (S), this is not true in (D): at & 13, 17, MC and sophEU converge to {1, t) when bwdQ converges to {t, } or (+, Thus, in Figure [b, we present together these three different termination policies. For the termination policies in (D), we can verify that they correspond to the groundtruth SPE policies (by Definition 3.1 and Q* computed manually from the reward specifications in Figure 1j. This is consistent with our results in Propositions 4.1 (MC) and 5.3 (bwdQ) that guarantee SPE optimality if converged. For the termination policies in (S), we can see how the noise injected to 9 affects the SPE policy: #(13) shifts from {+,1} in (D) to {{- in (S) as Q* (13, 1) in (S) is pulled down by random transitions of 9 - and + 13.
7 Conclusion and Future Works
Prior to this paper, was unclear how policy iteration performs and whether is sufficient in TIC RL settings under which BPO or DP becomes inaccessible. Through this paper, we demonstrated how introducing SPE optimality can shed lights on the two fundamental questions surrounding the use of PI in TIC RL setting. While this paper TIC RL is of theoretical nature, managed to demonstrate our findings. In particular, we obtain positive results on PT in the sense of both standard PT and backward conditioning's capability to characterize SPE policies. Though we could not close the convergence of either standard PI or backward conditioning, we have made progress towards it by verifying the importance of ordered policy iteration and improvement criteria. From the perspective of policy evaluation, SPE optimality recovers the use of DP-like formulas. This has resulted in familiar forms of algorithms, such as our backward Q-learning, that is also important towards closing the analysis of SPE policy search.
toy Gridworld example to
From our current paper, closing the convergence analysis of Pl, backward conditioning, and their approximate variants under SPE optimality (i.e., in particular, addressing the fully-coupled iterations that arise with TIC adjustments) is an important future direction. Secondly, noting our recovery of DP-like formulas and Q-learning like algorithms, we see promise in adopting the use of function approximations and scaling up to more general models such as linear MDP (Jin et al. (2020)) or more complex domains such as Atari Bellemare al. (2013). Finally, will be interesting apply the analysis of this paper to other TIC sources such risk-sensitive objectives and compare across different. TIC sources the extent of future deviations, TIC-adjustment techniques, and the control performance of PI (as proxy for SPE policy). On broader exlent, hope that our first allempl can inspire more works on TIC RL towards closing the gap between progress in standard RL and TIC RL.
14

---

Published in Transactions on Machine Learning Research (11/2022)
References
Chenjia Bai, Lingxiao Wang, Lei Han, Jianye Hao, Animesh Garg, Peng Liu, and Zhaoran Wang. Principled exploration via optimistic bootstrapping and backward induction. In International Conference on Machine Learning, pp. 577-587777 587. PMLR, 2021.
Marc G Bellemare, Yavar Naddal, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253-2755 2013.
Richard Bellman. Dynamic Programming. Princeton University Press, Princeton, NJ, USA, 1 edition, 1957.
Dimitri P. Bertsekas and John N. Tsitsiklis. Newro-dynamicc progrumming, volume 3 of Oplimization and neural computation series. Athena Scientific, 1996. ISBN 1886529108.
Tomas Björk and Agatha Murgoci. theory of Markovian time-inconsistent stochastic control in discrete time. Finance and Stochastics, 1833)5545-592, June 2014. doi: 10.1007/500730-014400444
Tomas Björk, Agatha Murgoci, and Xun Yu Zhou. Mean-variance portfolio optimization with state-dependent risk aversion. Mathematical Finance, 24(1):1 24, January 2014. doi: 10.1111/j.1467-9955. 00......1...1......
Dotan Di Castro, Aviv Tamar, and Shie Mannor. Policy gradients with variance related risk criteria. ar. preprint Xr0:::126.. 6404, 2012.
Owain Evans, Andreas Stuhlmüller, and Noah D. Goodman. Learning the preferences of ignorant, inconsistent agents. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30 of AAAI'1,, pp- 323 329, Phoenix, Arizona, February 2016. URL https://dl.acnn acm /tt..///..///1110056600011111111 3015880
William Fedus, Carles Gelada, Yoshua Bengio, Mare G. Bellemare, and Hugo Larochelle. Hyperbolic discounting and learning over multiple horizons. arXiv: 1902.06865, February 2019. URL httpss//arxiv oTg/abs/1902.0688
Hado Hasselt. Double q-learning, Advances in newral information processing systems, 23, 2010.
Ronald A Howard. Dynamic programming and markov processes. 1960.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137 2143. PMLR, 2020.
Zeb Kurth-Nelson and A. David Redish. A reinforcement learning model of precommitment in decision making. Frontiers in Behavioral Newroscience, 4:184, 2010. ISSN 1662-5153. doi: 10.3389 10.3389/fubeh.23 /ft.ch..010.0008....... URL https://www frontiersin
http:::///....rriieeriii..cm wwt.eeorrrr/a///.e.eeee 3389/fnbeh. 2010.00184
Tor Lattimore and Mareus Hutter. General time consistent discounting. Theoretionl Computer Science, 519:
1541 2014.
Su Young Lee, Choi Sungik, and Sae- Young Chung. Sample-efficient deep reinforcement learning via episodic backward update. Advances in Neural Information Processing Systems, 32, 2019.
Nixie $ Lesmana and Chi Seng Pun. A subgame perfect equilibrium reinforcement learning approach to time-inconsistent problems. Available at SSRN 3951936, 2021.
Long Ji Lin. Programming robots using reinforcement learning and teaching. In AAAI, pp. 781-786, 1991.
Shie Mannor and John N. Tsitsiklis. Mean-variance optimization in markov decision processes. CoRR, abs/1104.5601, 2011. URL http:://axxxt aatt:://arxiv.org/bbb////// wttpi//orrr/abbb/1..50500
Robert A. Pollak. Consistent planning. The Review of Economic Studies, 35(2):201, April 1968. doi: 10.2307/2296548.
LA Prashanth and Mohammad Ghavamzadch. Actor-critic algorithms for risk-sensitive mdps. In Advances in neural information processing systems, pp. 252 260, 2013.
15

---

Published in Transactions on Machine Learning Research (11/2022)
Matthew J Sobel. The variance of discounted Markov decision processes. Journal of Applied Probability, pp- 794 794-802, 1982.
Robert H. Strotz. Myopia and inconsistency in dynamic utility maximization. The Review of Economic Studies, 23(3):165-180, December 1955. doi: 10.2307/229572
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Aviv Tamar and Shie Mannor. Variance adjusted actor critic algorithms. ArXiu, abs/ 1310.3677 2013.
Christopher J.C.H. Watkins and Peter Dayan. Q-learning. Machine learning. 8(3-4):279 292, May 1992.
Huaqing Xiong, Lin Zhao, Yingbin Liang, and Wei Zhang, Finite-time analysis for double q-learning, Advances in neural information processing systems, 33:16628- 166668888688,,,, 2020.
Lin Zhao, Huaqing Xiong, and Yingbin Liang. Faster non-asymplolic convergence for double q-learning. Advances in Newral Information Processing Systems, 1177442-7253 2021.
16

---

Published in Transactions on Machine Learning Research (11/2022)
A Additional Details on Assumption 3.5
A.1 MDP Examples under Ceneral-Discountii Criterion
In this section, we derive several sufficient conditions for our assumptions in Section 3.2 in the form of restrictions on MDP (S, A, or discounting function g(-).
Definition A.1 (Boundary-only Rewards). The reward function R x - R+ is boundary-only if it is non-zero only at boundory states, i.e. R(s, > 0 only if E S.
Lemma A.2. Any MDP that has boundary- only rewards satisfies Assumption 3.3
Proof. Let Tgls defines the minimum hitting time of any boundary states S when initiated at s and following л.. Thus, Vs s, VT E MIDD
vT < 00,
T Σ
(s)=
Σ RT) s
P T|$]E
Σ p(t)
=
Σ (c)
T=T+1
r"
*
E
R(t)
1==
f
Σ
PITS' #
Σ
( $13 + Σ
PIT 2
= T|s]E
(1) R2 ?
5
0=0
7=
Σ
PITg = =|
(()) RT
(since Vr 2 T + 11, Evoid = P(TT"" r|s] 0.)
By bounded reward function,
Rman == :s
(22)
exists. Then, Vc > 0, As E S, we can set T < 00 s.t.
Rmax (T(T + +1) Sc
(23)
and the following holds,
sup V / FETTT(S (8) Va *s)]|= (**+(()]== MEILDD
sup HEILDD
P[T = 7 ss]
(by boundary-only rewards)
00
sup EIIAD
Rmaxx
Σ
P = =())
(by 22
T=1+1
sup EDTAD
|mmxx + 1)P(TT > T|s]
(by (p(-) decreasing)
Rmax (TT 5c
(by 23
Lemma A.3. Suppose an MDP has boundary-only rewards, 3o that satisfies Assumption 3.4 such that To,.0 00, and discounting factor N. + (0, 1] that satisfies
1I 2 0, ppT ((T+ +1) (p())
is increasing in T,T 2 1.
(24)
Then, Assumption
3.5 holds.
17

---

Published in Transactions on Machine Learning Research (11/2022)
Proof. Suppose otherwise, 36" > 0,1 E [0, T-]), E St Sta. t. E ITMD s.1.
PTST = s0|so| > 0
(25)
and Vx O,
(s* ym -t #(
Σ
PITS [T))) 107
(26)
T-T,.-t4
Let us fix = and set
K²* = PlS s* s'lsu] + +1
(27)
Note that Λ²¹ > 0 by 25 and Te < 00 (by Assumption 3.3 Ton.e- < 00, and by Assumption 3.4 T < 00). Then,
(80) - VT. 2o # ((80)
P(T = =T -
((s())
r= ==
(by boundary-only rewards; see Lemma A.2 proof)
Σ r=
PIT S = [[s)) [s0]
(by Tag.r- S Tx-)
Σ
PIS = 8) s/50 s0] = - - -
+ SES
> P(S 8* [sl
P E|s + R7 1s*]
T-T,---+1
(by non-negative rewards and probabilities)
2 PIS = =0/so]/[TT +1)
Σ
PIT = r| (77 [s"]
T
(by 24 and t" E [0, T.-))
PIST =s solp(TT + 1) e
(by 26 and 27
This contradicts definition of T (see Assumption 3.3 implying that our supposition is false.
With nle,t, St, so) = P[ST = solsole(TT. + 1), we will now show that
lim - PIST se|soly((Te +1) 0
(28)
For any fixed <> 0, let us define
G(TT; 80) = min = so/5o] 00:0E (0, 8, E
(29)
Then, VT E MD Vt Te), Vs, I1
(30)
PiST = selsolp(Te +1)
so) +1)
Since Tag.0 < 00, we have
To = max max Tog <
(31)
18

---

Published in Transactions on Machine Learning Research (11/2022)
Let us fix arbitrarily л IMD ( [o, Tol, st E St S.o. By (31, lim G(T G(To: > and
lim,-o (pT. + 1) = (To + 1) 0. Thus, we can take lim on the upper and lower bound in (30) and have shown
lim PIST se +1)
Finally, it's straightforward to verify that our hyperbolic Gridworld in Figure I has boundary- only rewards and so 21 that satisfies Assumption 3.4 Moreover, due to the existence of T" max
E
[ < oo by its deterministic transition and | < x0, we have VT 2 T",
(V*(so) sup *El
=
V (~ -* * (so))
(by boundary-only rewards)
TEIMP PE
(b VT T 2 5 VT E II with T co, = r|s 0)
and thus, T Ton < T' < co. For concrete example, refer to the restricted Hyperbolic Gridworld
in Example 4.6 where we can compute manually i. and T s0.0
A.2 Implied Bounded Value Functions
Through the following lemma, we can link Assumption 3.3 to the standard well-posedness condition of bounded value functions that ensures the existence of optimal policy.
Lemma A.4. If Assumption 3.9 holds, then vs E Sy E II V* < 00.
Proof. Suppose Im., So s.t. VT (s.) 00. Then, we can 8, 8,, n. and arbitrary e" s.t. VT oo, ] ! (s.) - (s.)l e since V=! * *ss) < co.
B Theorem 4.3
B.1 Technical Assumptions
Assumption B.1 ('Relevant at t under π²). If 0,
PIST solso] = 0, Vt 2 1A P[S = So so, Ao ao]
(32)
If > 0, 3(s:-1, 'relevant at f- under s.t.
PlS. = St|S.-1 = 8t-1, Ar-1 = =0--)> 0na = =s())-
(33)
Intuitively, for t 0, 33 exhausts the use instances of (st, az) in PE updates (3--1, B(QTT(s. ((s)) +... and thus, it must hold. Whereas for t = 0, some restrictions on the MDP
(o.g., VE' # S. n S IIDD = as in Example 4.6) can be imposed to ensure that 32 holds
Yn ITDD 8080 E S (S)), Asp- Note however that in actual use instances, 432 only need to hold for the encountered in the PI updates (instead of VT E ID. This may relax the need for such MDP restrictions:
observe from our experiments (see Section 6 algorithm still performs plausibly
well even when A + Soo n = 01 does not hold. In what follows, we present several intermediate results that link the conditions in Assumption B.I to the 'approximation" [13 in Theorem 4.3
Lemma B.2. Al any 2 0, if (st,at) az) is "relevant at I under π then Iso, 'relevant at 0 wnder s.L.
P0 se|so] OA a; Too (8t)
19

---

Published in Transactions on Machine Learning Research (11/2022)
with a0 defined follows
ao.
s =
Tag (8)
(34)
क (s); otherwise
Proof. (Base case: t = 0.) Note that for any (so. ao) that 'relevant under π²,, we have P P
|so]
0. Moreover, ag ao (8a) holds by definition in (3/.
(t > 0.) Proof by induction. Suppose that the relation holds at t= 8' - 1, will show that it also holds at = t'. By (sp, I's'ss 'relevance at t' under πτ' [(s -1) 'relevant at t' - under x s.t.
P[S = se Se|Sp-11 = 1 A ar-1) > 0 A or = x88e)
(35)
Moreover, by assumption (that at t' the relation holds), the above (s ar satisfies: Esp, 4g 'relevant at under π s.t.
P| 000000 = =sp-1[so] 0 av-1 T0 (s
(36)
Therefore,
PIST ssr
2 P 00000 =y S sy sy-1|P(S m0 s1-o
P[Se se Sp 8 Ar-1 = av PP -1-11880 >
(by (36
Moreover, by (Sp, ao)'s 'relevance at under '¹ and t' 0, we must have sy # so which then implies
ag a0 (8x)
(by 35
Lemma B.3. For any MTD., 1 0, and (st, az) "relevant at t under T²; 3x s.l.
V8s41 pit V (S(+1) - v ui ((s+(((ss))))))))))(()) S
(37)
and lim,jo x =0 O.
Proof. Let us first fix arbitrarily (st, ae T). By Lemma B.2 Bsp ag and के = x0. s.t.
PlS se|so] > >0 #(st)
(38)
Next, for any arbitrary choice of 8441 ~ ph, we have
PPS = S141|S: 8t, Ar = ar) > 0
(39)
Therefore,
PiS 1601
P 8141 St sr]P[S sc|s0]
P[S = 8141 St = 8t, Ar = a. a.)p[ss = se|so]
(by 38
(by 38 and 33
which by Assumption 3.5
implies
6
2
** (*(++)) 2 12-11111)1100
(81+1)
<<c, t + 8141, #: 8o)
(*T(+++) pm (st+1)
(by (so, ao)'s 'relevance at 0 under TT and t 1 0, se+1 + so.)
20

---

Published in Transactions on Machine Learning Research (11/2022)
and
lim <0
0.
(40)
x(e, t + 1, S141, n; 30)
Now, let us choose x = min + 1,441, #;80) 8841 ~ p..). Note that 37 directly holds. thus remains show the following,
lim
lim
</0 K
<00 mine 1 1, 8841, T; 80) ) : 8141 ~ psi
lim max <40
8641 Pei
(x(c, 1 + 1, 8141, 80)
0
(by 40 and at most finitely many choices of 81+1 E ES)
B.2 Proof of Theorem 4.3
For any m 2 T 1, we can derive r-function recursion as follows
p T. (s, a) E [sp(m
R (S (T(mm²) Ss, =
(41)
Es rpp
E (m - T)R(S m. ((S))) [S,+1]]
(42)
( - T)
Es.
E [sp(m - (r + 1)) (5 (( S++11]
(43)
(m (T + 1}}
(m - T)
E Es.rrop
x.., (1
(44)
(m(m - (T + 1]]
For m T, by Definition 4.2
we have
n: (s, Emp(m r) (S
((())))))))))))))))))))))(())))) " =
(45)
ERapo (s(0)
(46)
Next, derive Q-function recursion,
QT at) = (000::00000000000000000000011110 + T T(5+2)))
(47a)
= =ER-D%: +
+...|1... = st]
T (
+ (S((22 + st]
E [ ( +(())))))))))))))++)))))) ( n (a..T)
+... Se. s(] 0:)l + E S (5 (S,1)))
(S
(47b)
-ERnD% (p(()))())))))))))))))))) R( ((())
{ E
E ((S) T 1) + +...)))))........ Stt1]
ES
E (I(R))(ST))) n + (SH+2) +.+]|+++1]] [S+1]]]
(47c)
ER~P% (s()) ut)] + Eg ppp
(S
Esu at
E
Σ
f +t 1)) R(S TAST,TTSST ( St+1
Lm=++1
-Eg
E
p(m t) R(S π (S (Sm S1+1
(47d)
Lm=++1
21

---

Published in Transactions on Machine Learning Research (11/2022)
On the 2nd line, apply Vstt1 pss
Tr
E
Σ
p - (t 1)
S4+1
S1+1
E
Σ
f
(t +
1m S sc+1
m==++
m=(+1
(1+1)
E
( m Rm Su = S1+1
-E E
Σ
= 8671
m
VZ (11)) (sc+1)l ($(+))
(by using x from Lemma B.3
K
On the 3rd line, apply 1sst1 por
T,
E
(m
t) S = 82+1
EE
Σ
( - t) St+1
S1+1
m==+1
m=1+1
T
oc
p R -150 = 84+1
E
(m R 1 = s1+1
m
m
o
<
p 1) = 88+1
5 1) = 8141
(by sp()) decreasing)
V (8(+1) V- / (c++1))
(sL+1)
(by
5
(by using k from Lemma
B.3
Therefore, continuing from 47d,, we can perform approximation with T. < oo as follows, x E ER (s())) ar)l + i0 (Q++ π (S:+1))
Te
E Es di
E Blp(m - (t R(S ((
m=t+1
(m 1)
Es
(m - (t (t+ E (p((m (1+ I)) क (( Set1)
(by sctting k(e) = k/2 which directly implies lim x(द
0)
By applying 46 Definition 4.2 and on the 1st, 2nd, and 3rd line, respectively, we can then obtain
E Rnps (sp R[ a:)] + B (S
Espiippy Caattll.(Srrm T m. (st (st, ai)
(47e)
m==+1
Finally, based on the Definition 3.6 we will set our boundary conditions (when are at some boundary states),
Q" ar) Bn (((0) a.),, e S. A
(48)
C Backward Q-learning Algorithm
In this section, detail the derivations of Backward Q-learning in Section 5.2 from Theorem 4.3
22

---

Published in Transactions on Machine Learning Research (11/2022)
C.1 r-table Update
Based on the r-function recursion, i.e. 44 and 46 we obtain bootstrap targets that corresponds to the main paper,
20 in
(m) + R(0) at),
for m =
(49)
(m) + f(m - t)
1 at 7 (Si+1)), for m = m=t+1:
(50)
f (t + 1))
Then, updates r-table are made as follows,
pl. ar) + (1 a,) ) (s, am), for =
(51)
given learning rate a, 0.
C.2 Q-table Update
Based on the Q-function recursion, i.e. 47e and we obtain bootstrap targets that corresponds to in the main paper,
c R()) at), for T and 8t E
(52)
C - (0) ai) + Q(S(+1,(S(' 7' (( - max(0, Art), for t -
(53)
where Ar, Em=14 / 1l. (81+1, T' (8(+1)) A. (8) u.). Then, updates to Q-tbll can be done as follows, (() + (1 ag)Q(ss, at) tagg for L 5 7
(54)
given learning rate aq 0.
Truncation from T to T For our implementation, instead of keeping track of all values up to T, we use the variable length T of each trajectory sampled following a current policy л. However, we will still set a sufficienlly large T as a proxy for Te to ensure that all trajectory terminates.
Clipping of adjustment terms. Let us denote by ArT the adjustment terms in the 2nd row of (47e) in the main paper. Referring to (53) note that the clipped function max(0, Ar,) has been used in place of Ar.. This is done to slow down the accumulation of error relevant to Ar; ArT. In particular, nole that ArT 2 0:
T-1
ArT
E Esinpi
(S', 7.
m=t+1
T-1
Eginpit (1--00 mpmm - (t + 1))
plm-t) -t
1.. (S',
(by
m=t+1
20 0
(by v(-) discount factor and R: S A R s.t. is nog-negaaive)
But without clipping, Ar. < 0 may happen subsequent iterations, inflating Q-values at some states past a certain threshold such that their neighboring states prefer transition to these inflated states than moving towards goal states, when the latter clearly results in fewer steps. This then creates looping behaviour which eventually lead to divergence.
C.3 Policy-table Update
We note of policy-table separate from the arg max of Q-table to represent greedy policy. This is due to the possibilities of non-unique actions realizing arg max, Q(s, a) for some E S which may cause non-unique r-function related values, i.c. the components Emmm4 Art", after substituting different global optima actions. Specifically, we follow the consistent tie-break rule proposed in Section 3.3 of Lesmana & Pun (202]); line 18-22 in Algorithm
23

---

Published in Transactions on Machine Learning Research (11/2022)
Algorithm On-policy Monte Carlo Control (MC)
Input: Hyperbolie (k =) Gridworld, Hyperparameters (e, 7)
Output: Approximate SPE Q-function (*, S,
3: Initialize: ((s,a) t 0, vs S S, A: Q(s,a) t R(0))(s S, a A; Returns(s, a) t 0, Vs
S. E A(s); (s) - arg max, Q(,,a), Vs S: + 0;
4: repeat
5: Update π f- TT'
Choose So randomly
Generate Irajectory wo.7 = So Aos... .. ST., Ar- following n
Set + for to T do
10:
if the pair Ai) does not appear in Wha-11 then
11:
Compute G + ( R(Sr,, Ar.)
12:
Append to Returns A²)
13:
Update QSS,, Ax) & average Returns(S,, As)) Update T' (St) arg max, ()
14:
15: end if
16:
end for
17:
until stable (TT' # π
D NUMERICAL EXAMPLES
This section provides some missing details on Section
D.1 Environment Setup
We review 3 important considerations in our Gridworld designs: (i) existence of actual future deviations (i.e. if states like (su, 8,) 9) exist, where the optimality of 21's action is constrained by 9's action such that we have priorily ordering on S), (ii) n= (sp) # #ss) where the value of following SPE path A is strictly less than following precommitment path T and (iii) initialization to TIC, precommitment policy (that is necessary to invoke the insufficiency of standard Pl as illustrated in Example 4.6h. For our stochastic (S) example, we inject noise to the deterministic transitions p.(.) of state 9 in (D) such that
.9,
pg(() in (D)
Va ( P(slls = 9,a)
1 3
1-.9
else
D.2 Benchmark Algorithms
Following, we describe the two benchmark algorithms that we use in our experiments: MC and sophEU, For our MC implementation, we use the fist-visit variant on-policy MC contro as described Algorithm 2 For the sophEU, adapt the sophEU algorithm proposed in Evans et al. (2016) by modifying the exploration technique e-greedy; Algorithm This is done for fair comparison with the other two methods, i.e. MC and bwdQ.
D.3 Training Setup
For cach pair of algorithm and environment, hyperparamoters are informally selocted from the sets a, ag E {.2, 3, 4,-5,,a, ar E {-7,.8,99 1.0), E (00,,.03, 000,0,,0 07,.1) with the following criteria in mind: (i) small overtaking-mean 121 (ii) small stdev-shade the Q-value learning curves = 9, 21, and (iii) identifiable ig in (i.e. reducing the overlapping frequencies between two contending actions' mean Q-value learning
We refer the sourcecode in https:/ http:////tthbboommm///////ttteee modification.
prior hypeeballe-ddsccontinng
24

---

Published in Transactions on Machine Learning Research (11/2022)
Algorithm Sophisticated Exxpected-Utility Agent (sophEU)
Input:
Hyperbolie (k 1) Gridworld, Hyperparameterss(,
Output: Approximate SPE Q-function Q (s,a) a, S.
3:
Initialize: Q(s, a, d) t 0, vd, 8 S.a E A: a( + ((0) S, E A: r'((s) t arg max, Q(s, a, d), vd. S, + 0
4: repeat
5: Update π f- n²'
Choose Su randomly
for 0~ to - do Sample action A, m
Observe reward R++1 = R(S,, Ar) and next state S
10:
Set t
11:
Compute utility U + ((d) . At)
12:
Compute expectation + Ea'nd ( d', 1) Update Q(S,, A,, d) + A,, auU - Q(+,, A,, Update (S,) + arg max, a,
13:
14:
15:
end for
16:
until stable (Tg + mi)
curves): see Figure [a)-(b) for relatively bad instances. For all environments and algorithms, we set T = 100; larger episode truncation does not affect much our experiment results. We summarize our final choice of hyperparameters in Table 2
Table 2: Hyperparameters
(c, a,)
MC
sophEU
bwdq
(D)
(.07, 100, -.-)
(.07, 100, .4.
(.07, 100, .4, 1.0)
SS)
(.07, -00,-.-)
(.07, 100, -)
(.07, 100, .4, .9)
D.4 Additional Results and Evaluation
This subsection expands the results and evaluation subsection in the main paper.
D.4.1
Q-value Learning Curves
illustrate how we record the overtaking indexes ig. 22 used to compute Ar in Table 1 we plot Figure the Q-value learning curves that correspond Figure
D.4.2 Terminal Policies vs Groundtruth Value Comparisons
In Figure (b) of the main paper, we have shown that all algorithms will evelt terminate at SPE policy # (so) for So = 21. However, Figure Afa shows that both MC and sophEU do not flatten to the groundtruth SPE value function (**ss) Q* (so, A (sa)). Now that we have Q-value learning curves Figure it becomes clearer that the source of this discrepancy lies on the mis-evaluated Q-values; see Q(21, in Figure a) for instance. This is explainable for few reasons. Firstly, in the case of MC, the magnitude of exploratory rate causes Q-values to evaluate the exploratory policy n' consisting paths of extended lengths, which correspondingly lead to an underestimated cumulative discounted reward. In the case of sophEU, similar undervaluation ion of π happens due to the action-taking probabilities being included in the Q-table updates; see line 12-13 in Algorithm 3 While making e smaller intuitively fixes this issue, learning performance deteriorates (i.c. highly variable across scods) once we decrease up to certain threshold; our final choice of .07 has taken this into consideration. Secondly, observes some kind of smoothening effect across updates, which if combined with the delayed reflecting of information (i.e. prolonged Ai") exacerbate the
25

---

Published in Transactions on Machine Learning Research (11/2022)
(X--27) MCSE UC7 I00
Uy-M) DC7 100) Cetanrmene
(a)
25
24
0300
1000
500
2000
300
500
1000
1600
2000
2003
(2w221) (0w.21)).eeeU111100 St 07 4,7= Eetermmatic
OEsn9) SoptEU Ju 100)
40
(d)
25
20
0.
00
Q19n211 Bard
1001 Detoministi
Ogentin Bead 07.477.4.0 0.077 1..11.0F Deterr
(e)
1.5
RG-T
LEFT
30
Orgidic at 2561
20
Dreitdo
1.5
0.9
00
Figure 5: Q-value Learning Curves for MC, sophEU, and bwdQS at = 21, 9 in (D).
early flattening of policy values. Such smoothening concurrently explains how MC appears to have lesser variance compared to bwdQ sophEU at later iterations; Figure Tumee 4aa)-Stcchastic (S) in the main paper.
D.4.3 Ablation Study: Reversed Backward Q-learning
Since both benchmark algorithms suffer from similar undervaluation of policy issue, construct additional benchmark: Reversed Backward Q-lcarning (bwdQ-rev), that is basod on our own algorithm budQ. Here, we only retain the exlended DP-based policy evaluation component of bwdQ (that resembles TD-based methods in standard RL literature) and apply standard conditioning by reversing the backward order of policy update in line 11, Algorithm 1 This benchmarking can also be seen as an ablation study see how backward conditioning alone can reduce delusionality and improve learning performance. Figure 9 displays the value and Q-value learning curves of budQ-rev against budQ in both (D) and (S), under the same learning rates.
26

---

Published in Transactions on Machine Learning Research (11/2022)
Qp+21)) MC +. or. Tw 103) Stesheati
Oge33 Ju- DV. ICO) Elecnaaie
(8)
UP
10011
L171
14
08
2230
2000
30000
0003
19000
3000
(gye21) 1g (+ 07 you 4 T= 100) Rindhwehh
Qje je 07.0m 4.7 Srodwwll
(c)
(d)
35
R
1.0
00
1000
Oge-211 Bwd A.p 100) Stochasic
Olen &
25
RG IT
08
Figure 6: Q-value Learning Curves for MC, sophEU, and budQ at 21,9 in (S).
Value learning curves. From Figure I(a,, can be scen that bwdQ-rev also manages match the groundtruth values at about the same speed of bwdQ. However, we can observe a large swing at earlier iterations which indicate budQ-rev's degree of delusionality. In particular, such swing is caused by 21's late update about 9's strategy of going 't', resulting in delusional prediction targets Q(21, 1; (9) =f) and an inflation of Q-values. BwdQ-rev's speed of correction towards the groundtruth here is then made possible by its large learning rates which we will show to have some disadvantages next.
Some comparisons be made with KC's degree of delusionality in Figure 4(a) of the main paper, that is milder for its smaller (smoothened) learning rate. It then natural to ask how sophEU does be explained by sophEU's dclay-ang,ontaaion, in which the rate of value propagation from delays d 0 the speed of delusionality correction. illustrate, can observe how Figure c). sophEU's ((21, 1) climbs up slowly from instead of jumping near 2.0 like most others.
to exhibit such (Q-)value inflation. This
may match
27

---

Published in Transactions on Machine Learning Research (11/2022)
Sge-21) Septil 07 - IC0) Detemmnsatc
Q3-3] EoptcU 07.-47 100 Detemenate
(b)
UP
M001
LE3
12
08
20000
2000
10000
0000
10000
Figure 7: Q-value Learning Curves for sophEU (Ext.) at 8 = 21, 9 in (D).
(2o011) (1w-21 St 27 pa 100 Strehell
Spe-0iS jo- 07 pr 100) Stodhakl:
(a)
(b)
30
15
2000
0090
2000
2000
1000 2003
<034
0000
0000
TX000
Figure 8: Q-value Learning Curves for sophEU (Ext.) at 8 21,9 in (S).
Q-value learning curves. From Figure 9 D(e) while 12 of badQ-rev seems to match bwdQ, we observe wide stdev-shades for two contending actions " and "f" that overlap throughout training episodes, indicating indecisive bchaviour i.c. high variability of trained policy at convergence across random soeds. We note that this phenomenon happens in 5 out of 10 bwdQ-rev experiments we conducted under (S) setup, while never happening in bwdq. Moreover, in Figure f), the mean Q-curves of the two contending actions 'r"' and 't' are relatively unstable and overlap frequently; see how bwdQ behaves in Figure ((f) for comparison. These evidences suggest that reversing backward conditioning standard impedes learning, particularly impairing bwdQ's ability to handle larger learning rates. The results for both algorithms under (D) setup largely similar, except for bwdQ-rev's inflated Q-valucs at earlier iterations that has been covered previously.
28

---

Published in Transactions on Machine Learning Research (11/2022)
Defarmannti: 101
Stectantc
(a)
Epecde
(d)
35
RIGH
1577
0.
Qpe211 Bad mete
103) Stedhasti
Ope5)
Stachaatic
30
25
24
30
0
200
300 2000
1000
Figure 9: Value and Q-value Learning Curve at s 21, 9 bwdQ-rev in (D) and (S). Experiment ID for budQ-rev similarly set to the one exhibiting slowest. termination at 21 as indicated by the largest 12-
29


Reviews:
[{"review_id": "SuatOTcWxp", "reviewer": "Reviewer_bU9Q", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I have read the whole paper and part of the proofs. Overall, this paper considers the interesting Time Inconsistent setting and propose backward Q-learning for handling the challenges. I have the following questions for the authors to address. \n\n1. What is the definition of $\\bar{T}$ in Assumption 3.2? The missing definition makes it hard to grasp what 3.2 is about. \n\n2. The discounting criterion $(5)$ has $\\varphi(\\cdot)$ inside and might not be well-defined for $\\varphi$ equals to constant $C$. When $\\varphi\\equiv 1$m shouldn't your result simply give $\\infty$?\n\n3. The Assumption 3.4 is quite hard to parse, which makes the result not easy to understand, in particular, why it is reasonable to assume $\\lim_{\\epsilon\\rightarrow 0} \\epsilon/\\kappa=0$? \n\n4. I am not sure about the Time inconsistency utilized in Algorithm 1. While I can see the TIC-adjusted TD evaluation is used in line 12-17, the hindsight for using backward conditioning remains lacking. Maybe I missed some point, but could you please explain more about the power of the design for Algorithm 1 and why this overcome the hurdle in standard PI?\n\n5. May I ask what is the main technical novelty of Theorem 4.3? It seems you provide a Bellman style equation (14) for the TIC setting, how hader is it compared to the standard Bellman equation besides that the reward uses general discounting?\n\n6. Currently, there is no convergence analysis for Algorithm 1, which seems necessary for theoretical validation of the proposed algorithm. In addition, the work would be more complete if the finite sample regret analysis can be conducted since due to the randomness in the trajectory sampling (Line 10 of bwdQ). Note such a result has been conducted for standard Q learning [1].\n\n[1] Is Q-learning provably efficient? NeurIPS 2018.\n\n7. Lastly, the whole work (especially the experiment) focuses on the Tabular setting (Gridworld), which limits of the power of the proposed algorithm. Could you propose similar algorithm for the general setting like Linear MDPs? Having discussion on those aspects would make the contribution of this paper more clear. \n", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the policy iteration problem for the challenging time-inconsistent (TIC) setting. The paper proposes backward Q-learning (bwdQ), a new algorithm in the approximate PI family that targets SPE policy under general (non-exponential) discounting criteria. They also demonstrate the implications of our theoretical findings on the behavior of the bwdQ and other approximate PI variants via experiments.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Please see the above section.", "broader_impact_concerns": "Not applicable. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "IQH0KcY3ve", "reviewer": "Reviewer_PRKT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* as I said in the introduction, I love the problem at stake and I would encourage the authors to continue on this topic.\n* the work seems well-rounded: all the elements I would expect from an article are present. Obviously more ambitious experiments would be a plus, but this is not a requirement in my eyes.\n\nWeaknesses:\n* The exposition mainly, under various forms:\n  * concepts are often not properly defined:\n    * abstract: *time inconsistent (TIC) objective* => the authors introduce PI, but do not explain what TIC is precisely.\n    * introduction: *monotonicity* => equivalent terminology is provided, but the concept is not defined.\n    * introduction: *termination policy* => I am still unsure what it is.\n  * acronyms are sometimes not introduced:\n    * abstract: *SPE* => we do not understand it refers to subgame perfect equilibrium at this point.\n    * introduction: *PIT* => I thought it was a typo for PI, but it's actually PI theorem. Maybe this acronym is not necessary.\n    * introduction: *DP* => not introduced.\n    * section 3.1: *BPO* => recall what it stands for.\n  * some English language needs proof reading:\n    * abstract: *subgame perfect equilibrium* => there is a sentence trying to explain it but it is not understandable.\n    * section 2: *problems are computationally intractable such that new tractable solutions are required* => if a problem is intractable, it means that we know that there is no tractable solution. I don't understand what the authors mean here.\n    * section 3.2: *when initiated at any intermediate states $s_t$ against $s_0$* => I don't understand.\n  * some mathematical imprecisions:\n    * definition 3.1: the action space has been assumed to be countable earlier, which somehow does not guarantee the existence of an SPE policy. Indeed, consider a stateless MDP that grants a reward of $1-\\frac{1}{a}$ with $a\\in\\mathcal{A}=\\mathbb{N}$.\n    * definition 4.2: $m$ was previously defined as $t-\\tau$, so it should be from $0$ to $T-\\tau$ in this definition. The same remark applies many times again after.\n    * equation 11: $\\phi$ was defined to be in $[0,1)$, if it's exactly equal to 0, then (11) is not defined.\n    * equation 13: it is incomplete. Therefore, I don't know where the terms in eq (14) come from.\n  * the authors do not really help the reader to follow the train of thought:\n    * Assumptions should be names so that we understand in a glimpse what they intend to say.\n    * Assumption 3.4: it is not explained. What does it say and how constraining it is? I have doubts about this one, see my technical concerns.\n    * Assumption 3.4: it's a recursive definition, usually the initial definition (for t=0) is written before the recursion. It helps the reader to parse the definition.\n* I also have a few technical concerns which I'll ask the authors to address:\n  * Assumption 3.4 seems to defeat a large part of the impact of the work. Indeed, it looks like this assumption enforces a discounting that is below-geometric. In particular, I don't think it works with the hyperbolic discounting, and Lemma A.3 seems to confirm my intuition.\n  * Section 3.3: *general discounting function* => is this work limited to general discounting function, because it seems to claim that it can be any TIC? Does not this discounting need to be monotonously decreasing?\n  * What about the solution used by Fedus consisting of using a family of discount factor as basis functions for any discounting scheme \\phi? It would only work for diminishing discount factors, but that looks powerful to me, more than the approximate solution proposed by the authors. So I would like to hear their arguments against this approach.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The submission tackles the problem of optimizing a policy under time inconsistency*: *i.e.* when decision optimality varies across time. This happens when the objective function (which devises optimality) is not expressible as the standard expectation of the geometrically discounted sum of rewards: $\\mathcal{J}(\\pi)\\doteq \\sum_t \\gamma^t R_t$. The Bellman's principle of optimality does not hold anymore which compromises the policy iteration monotonous improvement. The authors derive an alternative optimality definition called the subgame perfect equilibrium. They analyze policy iteration under this optimality criterion and propose an algorithm called backward Q-learning. Finally, they validate their work on two small gridworld environment.\n\n\\* Example 3.6 is quite informative on the phenomenon and allows also to relate to human decisions. I believe it should be presented as soon as the introduction. Indeed, the gridworld is like choosing to follow a longer path to avoid the temptation of buying croissants on the way to work. It also reminds me of a friend that uninstalled video games in order not to be tempted to play them: you make sure that the distractions never yield immediate reward, you need to plan to access them. These examples show a lack of personal focus if you ask me, but it is clear that we all regularly succumb to immediate distractions of our long term goals. For these reasons, I am quite hyped by the subject of research.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I request two things from the authors:\n1- solve the exposition issues\n2- answer my technical concerns", "broader_impact_concerns": "I do not have impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "0xNFLrgjWT", "reviewer": "Reviewer_agjL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n* [Setting] The paper addresses a setting, the one of TIC objectives, that is of interest in my opinion and seems motivated by the observation of the human behavior that \"tends to deviate from the plan\".\n\n* [Novelty] The proposed approach is novel, in particular, the employed updated rules for defining backward Q-learning (bwdQ).\n\n**Weaknesses**\n\n* [Subgame Perfect Equilibrium] I have some concerns about the role of the SPE in this context. First of all, SPE is a solution concept from game theory, and, at a general level, I do not understand why this is actually employed in (what I believe is) a single-agent problem. I have to admit that I am not an expert on the TIC RL literature, and, therefore, I might be missing some central points. Furthermore, if I look at Definition 3.1, the inequality is basically requiring that the current policy $\\hat{\\pi}$ has non-positive advantage, i.e., in the standard RL language, that $\\hat{\\pi}$ is the optimal policy. Can the authors elaborate on the role of SPE? Nevertheless, my feeling is that the authors could have made a better effort in trying to introduce the role of SPE in TIC RL, even for a non-expert reader. \n\n* [Assumptions] As the authors aknowledge, Assumptions 3.2, 3.3, and 3.4 are technical. The first two are briefly explained and their meaning is clear, while Assumption 3.4 remains obscure to me. I would appreciate it if the authors could provide a more detailed explanation of the meaning of these assumptions. Furthermore, and most importantly, are these assumptions reasonable in practice? For instance, are these assumptions verified in the grid world example?\n\n* [Theorem 3.4] I had trouble evaluating the meaning of Equation (14). What does the approximation symbol exactly mean? Are you approximating and ignoring any term in the expression? In my opinion, this should be clarified.\n\n* [Experimental Evaluation] The experimental evaluation is limited since it is conducted in just two versions (stochastic and deterministic) of the same grid world. I do not see this necessarily as a problem since the main purpose of the paper is to provide a theoretical contribution. Nevertheless, I think that the discussion in Section 6 could be improved. In particular, the results of the experimental evaluation are described in a very synthetic way. For instance, it is interesting to observe that the proposed approach is able to converge to the true value function while the others display a bias. In my opinion, the authors could elaborate on why this happens. Why do the baselines display a bias? Furthermore, I couldn't find the number of runs for generating the plots in Figure 4 and whether the shaded areas represent standard deviation or confidence intervals (if so, with which confidence?).\n\n**Minor Issues**\n* The acronym SPE appears in the abstract, but it is never defined before.\n* In the introduction, the authors say that \"Standard PI has been the basis of many classical RL algorithms, such as the popular Q-learning\". In my view, Q-learning can be thought of as the sample-based version of Value Iteration rather than PI.\n* Assumption 3.2, Equation (3) should contain an absolute value, not a norm. The same is in Assumption 3.4, for the second line after Equation (4).\n* Sometimes, in full-line equations, the punctuation is missing.\n* The plots in Figure 4 (a) are non-vectorial.\n* [Notation] The used notation seems quite non-standard and not immediate to understand. In particular, I am referring to the notation $\\pi_1^T \\cdot \\pi_2$ to denote the execution of policy $\\pi_1$ for the first $T$ steps and then $\\pi_2$ (like in Equation (3)). This is not really a weakness of the work, in my opinion, but it seems to me that everything could be formulated in terms of non-Markovian policies.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper tackles the Reinforcement Learning (RL) problem in the presence of time-inconsistent (TIC) objective functions, i.e., the case in which the usual Bellman optimality principle is violated (e.g., hyperbolic discounting instead of exponential one). The goal of the paper is to extend Policy Iteration (PI) to this setting and eventually propose a sample-based approach named backward Q-learning (bwdQ). To this end, the notion of optimality is rephrased in terms of the Subgame Perfect Equilibrium (SPE). Finally, a numerical validation on a grid world environment is proposed in comparison with some baselines.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "**Critical**\nAddressing the concerns related to [Subgame Perfect Equilibrium], [Assumptions], [Theorem 3.4], [Experimental Evaluation].\n\n**Non-Critical**\nFixing minor issues.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers found the problem studied in the paper interesting and the paper of good quality. They initially had questions and asked for some changes (mostly minor) and clarifications. The authors properly addressed all the questions and revised their paper according to the reviewers' suggestions. I vote for the acceptance and strongly recommend the authors to ensure that they address all the reviewers' comments in the final version of the paper. 
Decision: Accept (poster)