The Gambler's Problem and Beyond
Authors: Baoxiang Wang
Shuai Li
Jiajin Li
Siu On Chan
Venue:  (2020)
Keywords: the gambler's problem
reinforcement learning
fractal
self-similarity
Bellman equation

Abstract: We analyze the Gambler's problem, a simple reinforcement learning problem where the gambler has the chance to double or lose their bets until the target is reached. This is an early example introduced in the reinforcement learning textbook by Sutton and Barto (2018), where they mention an interesting pattern of the optimal value function with high-frequency components and repeating non-smooth points. It is however without further investigation. We provide the exact formula for the optimal value function for both the discrete and the continuous cases. Though simple as it might seem, the value function is pathological: fractal, self-similar, derivative taking either zero or infinity, not smooth on any interval, and not written as elementary functions. It is in fact one of the generalized Cantor functions, where it holds a complexity that has been uncharted thus far. Our analyses could lead insights into improving value function approximation, gradient-based algorithms, and Q-learning, in real applications and implementations.

Published as a conference paper at ICLR 2020
THE GAMBLER'S S PROBLEM AND BEYOND
Baoxiang Wang
Shuai Li
Department of Computer Science and Engineering The Chinese University of Hong Kong bxwang@cse cuhk. edu. hk
John Hoperoft Center for Computer Science Shanghai Jiao Tong University Chuaili8@f jtu. edu.cn
Jiajin Li
Department of SEEM The Chinese University of Hong Kong jjlißse. cuhk. edu. hk
Siu On Chan
Department of Computer Science and Engineering The Chinese University of Hong Kong
si siuonêcse, cuhk. edu. hk
ABSTRACT
We analyze the Gambler's problem, a simple reinforcement learning problem where the gambler has the chance to double lose their bets until the target is reached. This is an early example introduced in the reinforcement learning text- book by Sutton & Barto (2018), where they mention interesting pattern of the optimal value function with high-frequency components and repeating non- smooth points. is however without further investigation. We provide the exact formula for the optimal value function for both the discrete and the continuous cases. Though simple as it might seem, the value function is pathological: fractal, self-similar, derivative taking either zero or infinity, not smooth on any interval, and written elementary functions. is in fact one of the generalized Cantor functions, where it holds complexity that has been uncharted thus far. Our anal- yses could lead insights into improving value function approximation, gradient- based algorithms, and Q-learning, in real applications and implementations.
INTRODUCTION
We analytically investigate a deceptively simple problem, the Gambler's problem, introduced in the reinforcement learning textbook by Sutton & Barto (2018), on Example 4.3, Chapter 4, page 84. The problem setting is natural and simple enough that little discussion was given in the book apart from an algorithmic solution by value iteration. A close inspection will however show that the problem, as a representative of the entire family of Markov decision processes (MDP), involves a level of complexity and curiosity uncharted in years of reinforcement learning research.
The problem discusses gambler's s casino game, where they places multiple rounds of betting. The gambler gains the bet amount if they win round or loses the bet if they lose the round. The probability of losing each round is p 2 0.5, independently. The game ends when the gambler's capital reaches either their goal of N O. each round, the gambler must decide what portion of the capital to stake. In the discrete setting this bet amount must be integer, but it can be real number in the continuous setting. To formulate it as an MDP, we denote state s be the current capital and action the bet amount. The reward is +1 when the state reaches N, and zero otherwise.
Our goal is to solve the optimal value function of the problem. We first give the solution to the discrete Gambler's 's problem. Denote N the target capital, state the discrete setting), p > 0.5 as the probability of losing a bet, and 7 as the discount factor. The special case of N 100, 7 corresponds the original setting in Sutton and Barto's 's book.
the current capital (which is the

---

Published as a conference paper at ICLR 2020
p- 0.6, gamma-1.0
p=0.6, gamma=0.95
0.7, gamma=1,0
p= 0.7, gamma-0.mm..mmmmm
Figure I: The optimal state-value function of the discrete Gambler's problem.
Let & S and 0.5. The optimal value function z(n)) is v(n/N) in the discrete setting of the Gambler's problem, where v(.) is the optimal value function under the continuous case defined in Theorem 12.
Proposition 1.
The above statement amounts the discrete problem to the continuous problem by a uniform dis- cretization. The rest of the discussion will be the general continuous setting. In the setting, the target capital 1, the state space is [0, 1], and the action space < a S min(s, s, 8} at state meaning that the bet can be any fraction of the current capital long the capital after winning does not exceed 1. We state the optimal value function below and intuitive description the value function later in this section.
Theorem 12. Let 0 S 7 and p > 0.5. Under the continuous setting of the Gambler's 's problem, the optimal state-value function is v11 = L, and
u(s)
p)> b
f=1
for 0 S s < 1, where = 0.b, be (2) is the binary representation of the state s.
Next, we solve the Bellman equation of the continuous Gambler's 's problem. In the strictly discounted setting Y 1. the solution the Bellman equation f(0) = 0, f(1) 1,
f(s) (cc
max (1
aa)
is f()) = o(s) the optimal value function (Proposition 21).
This uniqueness does not hold in general. If the rewards are not discounted, the solution of the Bellman equation is either the optimal value function, or a constant function larger than 1.
Theorem 22, Let = 1, > 0.5, and f(.) be real function on [0, 1]. f(s) solves the Bellman equation and only if either
f(s) is u(s) defined Theorem 12, or
f(0) = 0, f(1) = L, and f(s) = for all 0 < a < for some constant C' 2
Under the corner case 7 = 1, p = 0.5 (where the gambler do not lose capital in bets expec- tation), the problem involves the midpoint concavity (Sierpifíski, 1920a;b) and Cauchy's functional equation. The measurable function that solves the Bellman equation is uniquely f(s) = C' s + B' on E (0, 1), for some constants C" B' 2 1. Additionally, under Axiom of Choice, f() can also be some non non-constn constructive, non Lebesgue measurable function described by a Hamel basis (Theorem 27 and its lemmas).
2

---

Published as a conference paper at ICLR 2020
p- 0.6, gamma-1.0
p=0.6, gamma=0.95
0.7, gamma-1.0
p= 0.7, gamma=0.mp
Figure 2: The optimal state-value function of the continuous Gambler's problem.
Though the description of the Gambler's problem seems natural and simple, Theorem 12 shows that its simpleness is deceptive. The optimal value function is fractal and self-similar, and non-rectifiable (see Corollary 14 and Lemma 8). It is thus not smooth on any interval, which can be unexpected when significant line of reinforcement learning studies is based on function approximation like discretization and neural networks. The value function (1) can neither be simplified into formula of elementary functions, which introduces difficulties in understanding The function is monoton- ically increasing with e0)) 0 and v(1) 1, but its derivative is O almost everywhere, which is counterintuitive. This known as singularity, famous pathological property functions. v(s) is continuous almost everywhere but not absolutely continuous. Also when is strictly smaller than 1, it is discontinuous on a dense and compact set of infinitely many points. These properties indicate that assumptions like smoothness, continuity, and upproximability In general, it is reasonable to doubt if these assumptions can be imposed in reinforcement learning. To better understand the pathology of u(s), known in analysis as a counterexample of many seemingly true statements (Dovgoshey et al., 2006). In fact, vss) generalized Cantor function, where the above descriptions are true for both v(s) and the Cantor function.
not satisfied in this problem.
analogize it to the Cantor function, which is well
Intuitive description of v(s). All the statements above require the definition of v(s). In fact, in this paper, v(s) is important enough such that its definition will not change with the context. The function cannot be written as combination of elementary functions. Nevertheless, we give an intuitive way to understand the function for the original, undiscounted problem. The function can be regarded generated by the following iterative process. First we fix v(0) and u(1) 1, and compute
( - =op0) (1- (1-0)++(-ppu()) (1 (1-p).
Here, o())) is the weighted average of the two "neighbors" v(0) and v(1) that have been already evaluated. Further, the same operation applies to v(1) and v(2). where v(2) po(0) (1 p)u(H) 2)2 and v po((t) + (1 p)v(1) (1 p) p(1 p), and forth to e()), ())), etc. This process evaluates v(s) on the dense and compact set Up21 G3 of the dyadic rationals, where G2 = {k2- / h E {1...., 2 1}}. With the fact that v(s) is monotonically strictly increasing, this dyadic rationals determines the function v(s) uniquely.
This iterative process can also be explained from the analytical formula of v(s). Starting with the first bit, bit of will not change the value, while a bit of will add (1-p) (1--))
to the value. This term can also be written as (1 - (11 p) #0 bits n bits), where the number of bits is counted over all previous bits. The value (1 p) #F bits p hits decides the gap between two neighbor existing points the above process, when we insert a new point in the middle. This insertion corresponds to the iteration on G3 over &.
3

---

Published as a conference paper at ICLR 2020
We provide high resolution plots of 2(n), NN 100 and e(s) in Figure 1 and Figure 2. respectively. The non-smoothness and the self-similar fractal patterns can be clearly observed from the figures. Also, us)) is continuous when y = 1 while v(s) is not continuous infinitely many points when < 1. fact, when y < 1, the function is discontinuous on the dyadic rationals U221 G2 while continuous on its complement, as we will rigorously show later.
Self-similariyy. The function v(s) on [s, 8 + 2 2 for any =0.byb... bE(2). e 2 1 is self-similar the function itself on [0, 1]. Let 0.b1b2 b2 ... be (2) [s,5 +-5+255
2 2- this can be observed by
(s))
p)> b;
( 1)bb)
i-1
p) (2p 1)bb) + +7
((1 +2 1)b;))
i=1
j=1
i-1
x
Σ
(1- - p)7
beei
(2p
i=1
j=1
= v($)+ +
II - (2p- 0(2 -8)).
The self-similarit can be compared with the Cantor function (Dovgoshey et al., 2006; Mandelbrot, 1985), which uses the ternary of s instead in the formula. The Cantor function self-similar to itself on [s, + 3- when uniquely described by their self-similarity, the monotonicity, and the boundary conditions.
0.b, b2 ... bL(3) and be * 1. Both v(s) and the Cantor function can be
Optimal policies. It is immediate by Theorem 12 and Lemma 8 that
π (s) m s}
one of the (Blackwell) optimal policies. Here, Blackwell optimality is defined as the uniform optimality under any 0 < S 1. This policy agrees with the intuition that under game that is in favor of the casino (p > 0.5), the gambler desires to bet the maximum to finish the game in as little cumulative bet possible. In fact, the probability of reaching the target is the expected amount of capital by the end of the game, which is negative linear to the cumulative bet.
The optimality is not unique though, for example, π 15) the original, undiscounted setting, small amount of bets can also be optimal. Namely, when s can be written in finite many bits by by ... be(y) in binary (assume by 1), (s)) = 2-f is also an optimal policy. This policy is by repeatedly rounding the capital to carryover the bits, keeping the game be within most rounds of bets.
32 is also optimal (for any 7). Under
1.1 PRELIMINARIES
We use the canonical formulation of the discrete-time Markov decision process (MDP), denoted as the tuple (S, A, T, r. Pu. Pu. That includes S the state space, AA the action space, T : S x A x S B the transition probability function, r S - IR the reward function, Po S + R the initial state distribution, and 7 E (0, 1] the unnormalized discount factor. deterministie policy क : + A is map from the state space to the action space. In this problem, T(s, (,, a) and T(s, a, + a) are p and 1 - respectively for s E S, a E A, and T is otherwise
Our goal is to solve the optimal value function of the Gambler's problem. In this problem, the state- value function is the probability of the gambler eventually reaching the target capital from a state. The definition of the state-value function of an MDP with respect to state and policy π is
(*)
Σ I''ro = s, = ((s)), 8141 T(s,, az), Tr ~ r(st), 0,
When n² is of the optimal policies, fr (s) is the optimal state-value function. Despite that there may exist more than one optimal policies, this optimal state-value function is unique (Sutton & Barto, 2018; Szepesvári, 2010).
4

---

Published as a conference paper at ICLR 2020
1.2 IMPLICATIONS
Our results indicate hardness on reinforcement learning (Papadimitriou & Tsitsiklis, 1987; Littman al., 1995; Thelen & Smith, 1998) and revisions of existing reinforcement learning algorithms. is worth noting that similar patterns of fractal and self-similarity have been observed empirically, for example in Chockalingam (2019) for the Mountain Car problem. With these characterizations being observed in simple problems like Mountain Car and the Gambler's problem, our results are expected to generalized variety of reinforcement learning settings.
The first implication is naturally on function value function approximation, which is developed topic in reinforcement learning (Lee al., 2008; Lusena al., 2001). By the fractal property of the optimal value function, that representation of such function must be inexact (Tikhonov, 2014). When discretization is used for value function representation, the approximation error is at least OLL/N), where N is the number of bins.
Proposition 19. When N E N N 2 is a power 2, let (8) be piecewise constant on any of the intervals E (k/N, (k 1)/N), O,.... N then
J. (e()) (s)) ds
p)7 + +ol N. N 1-
1 (2 -1
1
Alternatively, when a subclass of I--Lipschitz continuous used represent e(s), this error is then at least (1/L) (1 (1-p) (1 - -7)3/(4 worth remarking that despite this specific lower bound diminishes when 7y is 1, the approximation error is nonzero for arbitrarily large L under = 1, the derivative of us)) can be infinite (Fact 16).
(phy) by the discontinuity of v(() (Proposition 20). It is
Notably, neural networks are within this family of functions, where the Lipschitz constant L, is determined by the network architecture. By the proposition, it is not possible to obtain the optimal value function when a neural network is used, albeit the universal approximation theorem (Csáji, 2001; Dovgoshey et al., 2006; Levesley et al., 2007).
The second implication is by Theorem 12 and Fact 16 that the derivative of v(s) is
u(s + As) O, lim o(s + As)
too, if = 0r s E U2z1 Gt
lim 48-0+
As
As
0,
otherwise.
This imposes that the value function's derivative must be exactly obtained, it is 0 almost ev- erywhere, except on the dyadic rationals G5, where it has a left derivative of infinity and right derivative of O. Algorithms relying on Ov(s) and 0Q(s, a)/aa (Lillicrap al., 2015; Gu al., 2017: Heess et al., 2015; Fairbank & Alonso, 2012: Fairbank, 2008; Pan et al., 2019; Lim et al., 2018), where Qss, a) is the action-value function (Sutton & Barto, 2018), can suffer from the esti- mation error even have unpredictable behavior.
In practice, the boolean implementation of float numbers can further increase this error, as all points implemented are in G2 for some f. A precise evaluation requires all these derivatives to be infinity when Leabague derivative is used (the average of left and right derivatives), which cannot be obtained a computer system.
The third implication is on Q-learning (Mnih et al., 2015; Watkins & Dayan, 1992: Baird, 1995), by Theorem 22 and its supporting lemmas. It is proved that when 7 1, Q-learning has multiple converging points, as the Bellman equation has multiple solutions, namely v(s) and
ʃ(0) = 0, ((1) 1, and [()) C' for all 0 < <,
for some constant C 2 1. Therefore, even when the Q-learning algorithm converges, it may not converge to the optimal value function v(s). In fact, as the solution can be either the ground truth of the optimal value function, or a large constant function, is easier to approximate a constant function than the optimal value function, resulting in relatively lower Bellman error when converging the large constant.
This challenges Q-learning under 1 when the return (cumulative reward) is unbiased. Though the artificial y is originally introduced to prevent the return from diverging, it can be also necessary to prevent the algorithm from converging large constant in Q-learning, which is not desired.
5

---

Published as a conference paper at ICLR 2020
2 DISCRETE CASE
The analysis of the discrete case of the Gambler's problem will give an exact solution. will also explain the reason the plot on the book has a strange pattern of repeating spurious points.
The discrete case can be described by the following MDP: The state space is ,
NN,,,N,; Nr; the action {0 a V min(n, (n, N :) the transition from state and action a is and n + a with probability p and - P, respectively; the reward function is r(N) 1 and r(n) 0 for 0 < n N 1. The MDP terminates
space at n is A(n)
{0, N). We use time-discount factor of 0 S < L, where the agent receives y r(N)) rewards if the agents reaches the state = N at time
Let z(n). E N, n S N, be the value function. The exact solution below of the discrete case relying on Theorem 12, our main theorem which describes the exact solution of the continuous case. This theorem will be discussed and proved later in Section A.
Proposition 1. Let 0 < < 1 and p > 0.5. The optimal value function z(n) is v(n/N) in the discrete setting of the Gambler's problem, where v(-) is the optimal value function under the continuous case defined in Theorem 12.
Proof. We first verify the Bellman equation. By the definition of v(-) we have
2(n) v(n/N)
max Ocogmin(n/N..o (I., BY vln/N a) + (1 - p)> v(n/N + aa) pro(n/N - a) + (1 - phy un/NN / + a)
max (Co5min(x//.11nn/AAAA.
max
P7 z(n a) + (1 - p)7 =
Meanwhile let a= = min(n, N - n.. Corollary 13 suggests that
=(n) v((nN)
-n -4=
a')N) py -y ==n==a)) (1- (1-1)7 +(n+aa)
max Ocasmin(x,NNn)) P7 z(n a) + (1 p)y x + a).
Therefore =(n) = maX0ocoogmiu(n..--no..... 1n x(n - a) + (1 - p)7 =(v2 + a) as desired.
We then show that =nn)= = v(n/N) the unique function that satisfies the Bellman equation. The proof is similar to the proof of Lemma 2, but the arguments will be relatively easier, both the state space and the action space are discrete. Let (n) also satisfy the Bellman equation. We desire to prove that (n) is identical (n))
f(m) - z(m). This maximum must exists as there are finite many states. Then define the non-empty set S {n f(n) z(n) 6, S n N - For any n' S and a' E angmax (N N' f(n' a) +1 (1-p)) f(n' + a), we have
Define 8 = max SagN-1
f(n') p7 s(n' d') (1 p)- f(n' + aa)
S py (=(n' - d') + + (1 p1> (z(n' + +a') + 8)
$ py 2(n' - d') (1 +n' +5
S =nn')+8
f(n').
As the equality holds, by the equality of we have n'' a' E S and ni + a' E.
17 s(no a) + (1 p)y f(no + a). Then, we have nip do E S. Denote ni = no ag and, recursively, py ( Since a, 2 1 and n, E N, there must exist 7 such that ny = Therefore, 5 f(nr) ( = 0.
Now we specify some no E and ap argmax SagnnaxggsmmimnoNNN-o
a argmax, argmax
f( and and1 n4 n4-44 ar, t = 1,2, ...

---

Published as a conference paper at ICLR 2020
By the same argument 8 maxigngN-1 2(n)- - fn() = 0. Therefore, 2(n) and fn) are identical, as desired.
As ((n) is the unique function that satisfies the Bellman equation, it is the optimal value function of the problem.
Proposition I indicates the discretization of the problems yields the discrete, exact evaluation of the continuous value function 0, 1/........ If we omit the learning error, the plots on the book and by the open source implementation (Zhang, 2019) are the evaluation of the fractal uss) at 0, 1/N...... 1. This explains the strange appearance of the curve the figures.
3 SETTING
We formulate the continuous Gambler's problem as Markov decision process (MDP) with the state
space S = [0, 1] and the action space A(s) = (0, min {s, 1 - 8}}. E (0, 1). Here s E S represents the capital the gambler currently possesses and the action a A(s) denotes the amount of bet. Without loss of generality, we have assumed that the bet amount should be less or equal to 1 a and
avoid the total capital to be more than 1. The consecutive state s' transits to with probability 2 0.5 and 1 - p respectively. The process terminates if s E {0, 1) and the agent receives an episodic reward
at the terminal state. Let 0 S 7 S be the discount factor.
Let f [0, 1] + R be real function. For f(s) to be the optimal value function, the Bellman equation for the non- -en-telminal and terminal states are
f(s) = max py f(s - + (1-p)) f(s+ + a) for any s E (0, 1), aEA(s)
(A)
and
f(0) = 0, f(1)=1. 11
(B)
can be shown (later in Lemma 2 and Lemma 3) that a function satisfying (AB) must be lower bounded by 0. A reasonable upper bound is 1, the value function is the probability of the gambler eventually reaching the target, which must be between 0 and 1. It is also reasonable to assume the arbitrary small amount of starting capital
continuity of the value function at 8 O. Otherwise will have at least a constant probability of reaching the target 1.¹ Consequently the expectation of capital at the end of the game is greater than the starting capital, which contradicts p 0.5. The bounded version (X) of the problem leads to the optimal value function.
0 < 7 < 1, p> 0.5, (()) < for all 8, f(s) is continuous on 0.
(X)
Respectively, the unbounded version (Y) of the problem leads to the solutions of the Bellman equa- tion.
0 S 1, p 0.5.
(Y)
The results extend for = 0.5 in general, except an extreme corner case of = 1, = 0.5, where the monotonicity in Lemma 3 will not apply. This case (Z) involves arguments over measurability and the belief of Axiom of Choice, which we will discuss at the end of Section A.
= 1, 0.5, f(s) is unbounded.
We are mostly interested in two settings: the first setting (ABX) and its solution Theorem 12, discuss a set of necessary conditions of f() being the optimal value function the Gambler's s problem. As we show later the solution of (ABX) is unique, this solution must be the optimal value function. The second setting (ABY) and its solutions in Proposition 21 and Theorem 22 discuss all the functions that satisfy the Bellman equation. These functions are the optimal points that value iteration and Q-learning algorithms may converge to. (ABZ) is interestingly connected some foundations of mathematics like the belief of axioms, and is discussed in Theorem 27.
'This continuity assumption is only for hetter organization of the settings. The more general problem (AB) is solved in Section A.2 without this assumption.
7

---

Published as a conference paper at ICLR 2020
4 ANALYSIS
The analysis section rigorously supports the statements on the Gambler's problem and its Bellman equation with proofs and discussions. It deferred the appendix due the page limit.
CONCLUSION AND FUTURE WORKS
We give complete solution the Gambler's problem, simple and classic problem in reinforce- ment learning, under a variety of settings. We show that its optimal value function is very compli- cated and even pathological. Despite its seeming simpleness, these results are not clearly pointed out in previous studies.
Our contributions are the theoretical finding and the implications. It is worthy to bring the cur- rent results to start the discussion among the community. Indicated by the Gambler's problem, the current algorithmic approaches in reinforcement learning might underestimate the complexity. We expect more evidence could be found in the future and new algorithms and implementations could be brought out.
It would be interesting to see how these results of the Gambler's problem generalized to other MDPs. Finding these characterizations MDPs in general an important step understand reinforcement learning and sequential decision processes.
ACKNOWLEDGEMENT
We thank Richard S. Sutton and Andrew Barto for raising the Gambler's problem in their book, and Rich Sutton for the discussions on our theorems and implications. We thank Andrej Bogdanov for pointing out the connection to the Axiom of Choice, namely, Theorem 27, and Chengyu Lin for the discussions on the properties of o(s), namely, Lemma 6, 8, and 9. This paper was largely improved by the reviews and comments. We especially would like thank Csaba Szepesvári, Kirby Banman, and ICLR 2020 anonymous reviewers for their helpful feedback.
REFERENCES
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pp. 30-37. Elsevier, 1995.
Valliappa Chockalingam. The role of interest in prediction and control, 2019. URL https: youtu. be/ tee/aFxdpCDAG22g 3t=395 The plot of the empirical optimal value function of the Mountain Car problem first appears at 6:35. Some follow-up discussions start at 33:20.
Balázs Csanád Csáji. Approximation with artificial neural networks. Faculty of Sciences, Etvs Lornd University, Hungary, 24:48, 2001.
Oleksiy Dovgoshey, Olli Martio, Vladimir Ryazanov, and Matt Vuorinen. The cantor function. Expositiones Mathematicae, 24(1):1-37, 2006.
Michael Fairbank. Reinforcement learning by value gradients. arXiv preprint arXiv:0803.3539, 2008.
Michael Fairbank and Eduardo Alonso. Value-gradient learning. In The 2012 International Joint Conference Newral Networks (ICCN). pp. 1-8. IEEE, 2012.
Shixiang Shane Gu, Timothy Lillicrap, Richard Turner, Zoubin Ghahramani, Berharr Schölkopf, and Sergey Levine. Interpolated policy gradient: Merging on on-policy and off-policy gradient esti- mation for deep reinforcement learning. Advances neural information processing systems, pp. 3846-3855, 2017.
Mance E Harmon and Leemon C Baird III. Spurious solutions to the bellman equation. Technical Report, Wright-Patten Patterson Air Force Base Ohio: Wright Laboratory, WL-TR-96 9-- To Be Assigned",, 1996.
8

---

Published as a conference paper at ICLR 2020
Nicolas Heess, Gregory Wayne, David Silver, Timothy Lillicrap, Tom Erez, and Yuval Tassa. Learn- ing continuous control policies by stochastic value gradients. In Advances in Neural Information Processing Systems, pp. 1944-29522 2015.
Thomas Jech. The axiom of choice. Courier Corporation, 2008.
Takashi Kamihigashi and Cuong Le Van. Necessary and sufficient conditions for a solution of the bellman equation to be the value function: A general principle. Documents de travail du Centre dÊconooie de la Sorbonne 2015.07, 2015. ISSN: 1955-611X.
Peter Latham. Bellman's equation has a unique solution, 2008. URL ucl.ac uk/ "mandama /RRG// be Lman_converreeeeeeeeooooooo p.f.
Wee S Lee, Nan Rong, and David Hsu. What makes some pomdp problems easy to approximate? In Advances neural information processing systems, pp. 689-696, 2008.
Jason Levesley, Cem Salp, and Sanju I. Velani. On a problem of k. mahler: Diophantine approxi- mation and cantor sets. Mathematische Annalen, 338(():97-118, 2007.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint www.:iv:10000000
2015.
Sungsu Lim, Ajin Joseph, Lei Le, Yangehen Pan, and Martha White. Actor-expert: A framework for using action-value methods in continuous action spaces. arXiv preprint arXiv:1810.09103. 2018.
Michael L Littman, Thomas L Dean, and Leslic Pack Kaelbling. On the complexity of solving markov decision problems. In Proceedings of the Eleventh conference Uncertainty in artificial intelligence, pp. 402-402. Morgan Kaufmann Publishers Inc., 1995.
Christopher Lusena, Judy Goldsmith, and Martin Mundhenk. Nonapproximability results for par- tially observable markov decision processes. Journal of artificial intelligence research, 14:83- 103, 2001.
Benoit B Mandelbrot. Self-affine fractals and fractal dimension. Physica scripta, 32(4):257, 1985.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529-533 2015.
Yangchen Pan, Hengshuai Yao, Amir-massoud Farahmand, and Martha White. Hill climbing on value estimates for search-control in dyna. arXiv preprint arXiv: 1906. 07790,
arXiv:1906.00
Christos Papadimitriou and John Tsitsiklis. The complexity of markov decision processes. Mathematics of operations research, 12(3):4414455 1987.
MJ Pelling. Formulae for the arc-length of curve in m. The American Mathematical Monthly, 84 (6):465466, 1977.
Wactaw Sierpiński. Sur l'équation fonctionnelle f (x+ y)= f (x)+ f (y). Fundamenta Mathematicae, 1(1):116-122, 1920a.
Wactaw Sierpiński. Sur les fonctions convexes mesurables. Fundamenta Mathematicae, 1(1):125- 128, 1920b.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Csaba Szepesvári. Algorithms for reinforcement learning. Synthesis lectures on artificial intelli- gence and machine learning, 4(1):1-103, 2010.
Esther Thelen and Linda B Smith. Dynamic systems theories. Handbook of child psychology, 1998.
Yu V Tikhonov. On the rate of approximation of singular functions by step functions. Mathematical Notes, 95(3-4):530-543 2014.

---

Published as a conference paper at ICLR 2020
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-22) 22077999991111 1992.
Shangtong Zhang. troduction, 2019.
Python
implementation of Reinforcement learning: An in- URL https: //gp:////ghhhb///////h/pp /agg//ghgngtttthgggg/g
A ANALYSIS
A.1 ANALYSIS OF THE GAMBLER'S PROBLEM
In this section we show that u(s) defined below is a unique solution of the system (ABX). Since the optimal state-value function must satisfies the system (ABX), v(s) is the optimal state-value function of the Gambler's s problem. This statement is rigorously proved in Theorem 12.
Let 0 7 and p > 0.5. We define v(1) 1, and
1-1
u(s) =
phy by j=1
(1- (11-p)
(2p
(1)
for 0 S < 1, where 0.b b2 ... be (2) is the binary representation of It obvious that the series converges for any 0 S 8 1.
The notation u(s) will always refer to the definition above in this paper and will change with the context. We show later that this v(s) is the optimal value function of the problem. We use the notation (s) to denote general solution of system, which varies according the required properties.
Let the set of dyadic rationals
G. G== le E {I,.... 2 1}}
(3)
such that G, is the set of numbers that can be represented by at most & binary bits. The general idea verify the Bellman equation (AB) is prove
vss)
max aEGinAte
- (1- v(s + a + u(s a) for any Ge
by induction of = 1,2, and generalize this optimality to the entire interval s E (0, 1).
It then suffices show the uniqueness of u(s) that solves the system (ABX). This is proved by assuming the existence of solution f(s) and derive the identity f(s) = v(s), condition on the Bellman property that us)) satisfies (AB). For presentation purposes, the uniqueness is discussed first.
As overview, Lemma 2, 3, and 4 describe the system (ABX). Claim 5, Lemma 6, 8, and 9 describe the properties of v(s).
Lemma (Uniqueness under existence). Let f(s): : [0, - IR be a real function. u(s) and f(s) both satisfy (ABX), then u(s) = f()) for all 0 < 1.
Proof. We proof the lemma by contradiction. Assume that f(s) is also a solution of the system such that ((s) is not identical with v(s) some Define å supn< f(s) v(s). As f(2 f(2-1)
(1 (1-p)7 f11 p7 f(0) (1 p)7 v(2-)), we have 5 2 0.
We show that 8 cannot zero by contradiction. I is zero, as vss) and f(s) are not identical, there exists such that f(s) < u(s). In this case, let 8 suPuce<1 vos) f(s). Then choose
غ (1 p7)6 and specify so such that v(so) f(o) 5 ट. Let ag min 1 so), have
v(0) (1 p)7 v(so ao) + py v(so ao)
$ (1 p)> f(0o ao) py f( + an) + p7d
< f(so) + p75.
10

---

Published as a conference paper at ICLR 2020
The above inequality is due to at least one of so du 0 and Su + do = 1 must hold. Thus least
one of ((sy - 0o) - f(su - ag) and v(s + - -
f(u + ao) must be zero. The inequality contradicts v(so)= f(a) > 8 E. Hence, ò cannot be zero. We discuss under ò 0 for the rest of the proof.
Case (1): 7 < 1. In this case, we choose e = (1 - 7)o. By the definition of ó we specify so In fact, the existence of so is by the condition y < 1. Let ao E argmax, (EA(o)) PY f(80- - a) + - phy f(8o + a), we have
such that (80) v(80) + 6
f(5o) = py f(0 on) + (1 - p)7 f(3o + ao)
S py (u(se on) + 5) + (1 p)y (u(s0 + ao) + 6)
My u(s0 - -a)) + (1 - p)y us5 + an) + +
I (so) +
The inequality f(v) S vso) + 5 - c contradicts f(so) > u(s)) + 8 - Hence, the lemma is proved for the case 7 < 1.
Case (II): = 1. When there exists an s' such that f(s') v(s') = ô. we show the contradiction.
Let S = [s]s(s) v(s) = 6,0 < }} # Ø. For any E S and a' E arl) P7 J(
a) + (1 11 7)7 f(s' + a), we have
1(6' vi 0(8' d') + (1- - p)7 f(8 +a))
p s(s - a') + (1 p) f(8' +d)
- S D (u(s' d') +0) +1 (1-
(u(s' + +a') +
=pr(s' - d') + (1 p) v(s' + +0)
S 0(8')+8.
Thus, the equality in and must hold. We specify so S, and by the equality of we have f - ao) = uSs - on) + + thus So 1--ag ag E S. Let $1 = so ag. and we recursively specify an arbitrary 0 E or (1-))11p))))))))) f(s: + +a) + py f(s a) and $1+1 8, a, for t= 1,2,.... .... until sT 0 for some T, or indefinitely if such an sT does not exist. If ST exists and the sequence { terminates at ST = 0, then f(ST) = v(ST) + 8 by the boundary condition f(x)) f(0) = O.
which contradicts
We desire to show the existence of T. When there exists / and such that 8, E Ge, by Corollary 7 we have $1+1 E Ge and inductively Sy Ge for all t' 2 t. Consider that {sc] } is strictly decreasing and
there are finite many elements in Gr, {st] cannot be infinite. Otherwise 8 & G2 for any t, 2 1. Then by Corollary 10 the uniqueness of optimal action we have 81+1 28; 1 if 8t 2 2- and
8141 - 0f s, S } After finite many steps of 8t+1 2s, we will have 8t = 0 for some t.
It amounts to show the existence of s' such that fs') - v(s')
6. By Lemma we have the
continuity of uss). Lemma 3 indicates the monotonicity of f(s) on [0, 1). The upper bound f(s) < f(1) in (X) extends this monotonicity to the closed interval [0, 1]. Then by Lemma 4 we have the
continuity of (s) on (0, 1]. By (X) this extends to (0, 1). Thus we have the continuity of fs) (s)) and consequently the existence of maxogs'1 f(s') u(s'). As f(0) v(0) f(1) - c(1) 0
and 8 >0 0, this maximum must be attained at some s' E (0. Therefore we have the existence of maxo-co'< <1 f(+)) v(s'), which concludes the lemma.
Lemma 3 (Monotonicity). Let 7 = 1 and p > 0.5. If a real function f(s) satisfies (AB) then f() monotonically increasing on [0, 1).
Proof. We prove the claim by contradiction. Assume that there exists 81 < 82 where f(x1) > f(22).
Denote As = 82 - $1 > 0 and A = f(11) - f*2) > 0. By induction we have
f(s2 - 2 - f(>2) Af
for arbitrary integer l 2 1. Then when 82 + < 1, by f(22) 2 pf(s2 - 2ssAss + +11- f(2 + 2ss))
f(82 + 2- - 1- p
1
f(22)
p p
f 2 2'As)
11

---

Published as a conference paper at ICLR 2020
= = + p (f(1)) 1-p ([(ss) - [(02 - As))
- f(02) + f(22) - f(82 - -2-
This concludes + - f(x) f(22) - f(s -2 By induction have
f(s2 + + - f(2 + (1: 1 As) 5 f + (k - 10)-1) - f( - (k - 22)2
for 1 = 1,2,...... when $2 - < 1. We sum this inequality over k and get
422 K2 A f(22) - k<f(s2) f(s2 2 As)) 2 kp Af.
By letting k: = 2 and kkp Aʃ + -0. The arbitrarity of n indicates the non-existence of [( + k2- As), which contradicts the existence of the solution f(.).
No. 82 + 2 As < 1, and +00, we have 82 + 12- <
Lemma 4 (Continuity). Lety = and 2 0.5. I real function (() is monotonically increasing on (0, 1] and it satisfies (AB), then [(s) is continuous (0, 1).
Proof. We show the continuity by contradiction. Suppose that there exists point s' E (0, 1) such that f (s) is discontinuous s', then there exists c, > where f(s + f(s' - (2) 2 for any
+ = c. Then, by
1 70) 2 2
1(6
1(8 - + (1--)) 1(8 + ())
have
1 f(s' 70) f(s' -) 2 (1 (1- (1-p)ppp
Similarly, for h: 1.2.....
1
11 / f(8' 1 (1 p)0/p.
Let k > (11-))/p) we have fss +) f(s' > 1. This contradict with the fact that f(s is bounded between 0 and 1. The continuity follows on (0, 1).
If the function is discontinuous on s = 1, then there exists e, where f(1) - f(1 e1) 2 8 for any 6 S c. The same argument holds by observing
1 f(1 2 2
J(1
24 2 S(1.
The lemma follows.
When f(s is only required to be monotonically increasing on (0, 1), the continuity still holds but only (0, 1).
For simplicity define
(x(s,a)= = o(s -(--))a-- +1 p)y v(s + a).
(4)
As u(s) is the optimal state-value function (to be proved later in Theorem 12), (x, is in fact the optimal action-value function (Sutton & Barto, 2018; Szepesvári, 2010).
Recall that G2 is the set of dyadic rationals {k-2- k E (1,...,,2_ - 1}}.
Claim 5. for any & = 0.b2b2 fa.bb...bbpp be(() E G. G (0).
0 u (8+2- (8+2-((+)))- v(s) = (1- ph 81
II ((1 - p) + (2p - 1)b,) s (11 (1- pip (5)
j=1
12

---

Published as a conference paper at ICLR 2020
For any 0.b1b2......... ..)) ..bbb...bb((3)))
Ge with by 1 and s k Se E
p) ++1 k-1
v(8) - (s-22 (--2-(+t))) 2 2p
(11
(6)
Also,
((1) - (1-22((t1))
1 11t1lett1 2 2x
The equality of (6) and (7) holds if and only if = 1.
Proof. Inequality (5) and (7) are obtained by the definition of o(s). To derive inequality (6), denote
k = max {1 is L: b 0} and then
vss) 2-2
k-1
= - n)
II
((1 -p) + (2p- - 1)br)
/=1
8+1
k-1
Σ -h-ph
p) + (1 p)
II p
+=++1
j=k+1
(1- (1-)
1+1
=1 p)
(L
Σ
i=k+1
k-1
1 (1 (1p 1 (xp)
(1 p)n
+
1 1-7p
1=1
k-1
2 (1 - p)
((1 - (2p (1- (1- ()x))=**)))
k-1
(1 - p)p
((1 p) + (2p 1)b,).
j=1
The arguments are due to the fact that 2 (e+1) 0.b1b2 11-10x1 ... l441(2) and the inequality is by (1 - p)7 < pp.
Lemma 6. Let > 1,0 < - 1,0.5 S << 1. For any E Ga.
Qu(s,a) S max aEGenA(s)
Qs(s.)).
max eE(Gr.1 (G)
Proof. Case (I): First we prove that for > any Gr Gen 2 s < 1,
Qu (s,a-2-((4t)) < max (Q. Qu (s, -
Note that in this case, a 2-(1+) E G n A(s) and a - 2- E A(s)).
Let 0.0102 .e.02...coe CE(2) 0..1022.... 0,1001 ... [[()) where k max (1gig(:q=0)
is the index of the last ( bit in a. Such k must exist since 0 < s a < <1-3x2'<1
Similarly, let s + a 0.d1d2 ... de(2) O.did2.... ... (x) where k = max [1sis4:4=1]
is the index of the last bit in + a. Such W/ must exist since 3 x 2- sstakl 1. Also, + 2 (f+1) (f+11) 0.d,d2... ... 1w+1 ... let1ey)
To prove Qu (s, 2 (e+))) & (o a), it equivalent to prove
((s + a) v (s s (-(tt)) 2
p (u 2-((11) u(s - a)).
= 1-p
13

---

Published as a conference paper at ICLR 2020
Then by applying inequality (6), (7) and inequality (5) in Claim 5 on the LHS and RHS respectively, suffices to prove
k
p² k (1 p)
II ==1
((1 p) +2 (2p- 1)d)) 2 II ((1-() pp) + (2p (2p-1)00 1)c;)
==1
A-1
= p² (1 - p)
II /=1
p) (2p-1)cs)
Let M, 144-,,Ma-00 Ma = d1+.... de--1 be the number of Is (cl,..., (00].....,)..] :dl,.... dr
respectively. Then Qu (8,a 2--1)) 1 Qu(s, holds when = 0.5 or > 0.5, Me + 2
Mo + K..
To prove Qr (s,u 2 (+++)) S S a - 2--). it is equivalent to prove
0(s (Is-a+222) - v (s - a + 2 (-(tl) 2
1 1 (u (u(s (uss a 1--t--2-0--0 2-((tt) - v a
Note that 8 - + 2- 0,0 ... (2) and 8 + a 2 0.d1d2... ... 0g 1x+1 ... 1 Then by
inequality (6). (7) and inequality (5) on the LHS and RHS respectively, suffices to prove
k-1
W-11
p
2
(11 - p) + (2p - 1)0,) 2 (1 p)3p* R-
II
((1 p) + -pp-pppp)))) - 1)d,).
j=1
1=1
Then Qu a (++1)) 1 Qu (s.a 2 holds when p = 0.5 0.5, M +k' +2 Ma-h.
k and Ma+h 2 M&+ holds, thus Q (s, 2 2-(1+1)) < As at least one of Me h +12 +
max (Q)(s, Qu (s, a..a-2 )-
We cover two corner cases for the completeness of the proof.
Case (II): Next we prove for 2 1, any E Gt, a E G. n A(s) and s +a = 1.
Qu (s,a-2-((+))) s (s)aa)).
Similar to above, it is equivalent prove
p (u a a 2 2-(11) -u(s- -a)) (11 v (1 2 2- (e+1)
2 1-p
v1s
Note that by Claim 5,
o(1) v 2 > pptlgeth
p (1 p)p'
1-p p
P (u(s a + 2 2-+(1))) -iss -1s -a)
2 1-p
which concludes the proof.
Case (III): Last we prove for l > 1, any s E G2 and a = 2-, < x1-2-
When s = 0.b b... 0m 1m11m+1-- ... 16(2) with 1 S m < f, to prove Qu (s,2-(e+1) s Q (s,2-), is equivalent to prove
v (s+22 - 1 (s+2-
p 1 (s (-- (s-aa2-
v(s -i)
1-p
In this case, s + = 0.b ... 1..) 2 - 0.b,b.... ... On 1m+1 ... 1c-1(2) and M.
Ma, k' m. thus Ma + k 2 Mc + k', which concludes the proof similar to the first part of the ()) case.
When s 0.b1b2 ... Im 0m/+1 ... 00(2)) with 1 S ml < l, let Mo b1 +... bnc Then,
Qn (8,2-m²) Qu (s.2-(e+1)
14

---

Published as a conference paper at ICLR 2020
= (1 - ph(ppp++++221
+2
(1- u(s - -(s-2-))))) - (1-p)(u(ss)
v(s - -2 2-
- - (1-philu(+222
+ + -(s)) - p) - - 0(8 2- ))
2 (1 p))(m)) Me ((1 p))) 22 p)7
p)7 Mr ((1 p) p)y
- (1 (1-p)y (1-p)y +1 (11 (
p)7
- -p7(17) (0 ((1 p)7) Mo (1
-Mb + (17) + (17)8-11 )1 - -p
= =1 - p)m NMoN m² - p No (1 p) )m +1 M m +1 - p Mot1(1 p) - Mogeth e+1
n
-pMot1( (1 p) 3
Mo 7m +2 (1 (p7) 8- m )/(1 /p)
2 p Mo - p)) n "M?' -p p My (1 p) 1-11M M ym m'+1 - pp Mo+1 (1 p) c- Moalti
meg
-pNbt1( (1 p) MM m (pr)
++ 2 p Mb+ --M M
p Mb+ (1 - p)m - Mo +1 (pp))
2 0.
The arguments in the proof that either M + k: 2 Ma + W' + 1 or Ma + 2 Me + k must
hold is tight for integers Mc and Ma. This is the case for a E Ge+1 \ Gt. When Ge+1, this sufficient condition becomes even looser. The lemma imposes Ge to be the only set of possible optimal actions, given E Ge.
Corollary 7. Let 2 1. For any & E Gb,
argmax Qo(s,a) S Ge. aEA(s)
Now we verify the Bellman property on Utz1 Ge.
Lemma 8. Let 2 1. For any E Ge+1.
min s, s}
argmax Qu(s,a). eEGr+inA(s)
Proof. We prove the lemma by induction over l. When & 1, it is obvious since G1 has only one element. The base case = 2 is also immediate by exhausting we assume that for any s E G2, min(s, - $} E argmax Qo a). We aim to prove this lemma for ++11 1.
20-2 for 2-1 Now
For Ge, by Lemma 6,
(o( S Ge. Then by the induction assumption, min(s, 1 --s] s} argmax Qu(s,a) a) C argmax holds for E Gg. We discuss under 8 Ge+1 \ G5 for the rest of the proof.
(s) Hence, the lemma
We start with two inductive properties of v(s) to reduce the problem from E Ge+1 to s' E G where s' is either 2s or 2s- 1. For any s 2 2-1, that is, 02 ... C(+1(2) ..2+11())) E Ge+1 with Cj = 1,
(1)) Σ
p) &
II ((1 p) + (2p 1)cz)
/=1
= (1 - p)7 +
(1 p)y's c
II ((1 p) + (2p - 1)c;)
i=2
f=1
{-1
= (1- - p)7 +
(1 - p)7
i+l
Ci+1 ((1 p) + (2p 1)c1)
((1 - p) + (2p 1)c(+1)
1=1
f=1
(1 - p)7 + p7 (0012g...((11)))) (2)
... (1 p)7 + p. v22s 1).
Similarly, for any 8 2-1 that is, s =
E G441 with ej = 0.
ا-ع
v(s) Σ
p)
+
II
((1 p) + (2p 1)cz+1)
c+1
/=1
15

---

Published as a conference paper at ICLR 2020
-1- p2yr(2s).
Armed with the properties, we split the discussion into four cases 2-1 + S 1,2 s 2- + - <
s 2 2-1 and 0 < s S 1 -
When s 2-2-++2 a - 8, we have s 2- and + 2-1 Hence, the first bit after the decimal of s - and + a is 1. Hence,
Qu(s,a) p7 v(s - + (1-11) u(s
=(1 -11 11- py (py v(2s 2a 1)) + (1 pyy u(2s + 2a -1) 1)
(1 1--)> p7 (py 0((2s -) 1 2a) + (1 7)7 u 1) + 2a))
(1 p)>² py Q2s 1,2a).
As 2s 1 E G. and 2a Gg, by the induction assumption the maximum of Q. 1, 1,2a) is obtained at a = 1 - 8. Hence, 1 E argmaxxeGG+.nnAte (u a) as desired.
2 if 8 2 2-1, then first bit after the decimal of - a and s + is and the lemma follows the same arguments as the above case. Otherwise, if s a < 2-1, have Qu(s, a) = py v(s a) (1 (1- u aa)
When 2-1 < 8 < 2 + 2
(1 - =11-p)??²
- + p(1 - p) u2s 2a 20-1)
= (1 (1-p)7 (p7
- v(2s
(2u 1 ( 2)
+ (1 v(2s - ) + (2a - 2-))))
+ (2p - u22+ 1) p1-
= (1 - p)7 Qu - 2- 22
- (2p 1)7² 22 1) + +1 p)
As 2s 2-1 E Ge and 2a 2- E Ge whenever / 2 2. by the induction assumption (2s
2-1 2a - 2-1 obtains its maximum at = 8. By Claim 5, u(s) is monotonically increasing on Ge for any 823 2. Hence, r(2s 2a- 1) obtains the maximum the maximum feasible o, which i = 8. Since both terms takes their respective maximum at a = 1 8, we conclude that 1-s s argmax (s, as desired.
The other two cases, 2-1 < s < 2-1 and -- 2- - follow similar arguments. The lemma follows.
Lemma 9. Both v(s) and vs) max Qr(s, a) are continuous at 8 if there does not exist an l such that s Gt.
Proof. We first proof the continuity of us). For s = b by .bb........................... .b..................... (2)) & Ge indicates that for any integer there exists n 2 N such that bn = and no 2 such that bno = 0. The monotonicity of v(s) is obvious from Equation (1) that flipping 0 bit to a 1 bit will always yield greater value.
no, For any s 2- N < s' < + 2-N, we specify nı and no such that s 2 m I s' I s 2 By the monotonicity of v(s) we have
v(s) v(8') < us)) v(s 2 2-1)
n1
-(1-p) m)
II ((1 -) (2p (2p-1111) 1)b;) (1+
Σ m
m- d.p
II
((1 (1-p)) + (2p 1)b,))
j=mi+1
(1-p)y" (2p
i m1 b
(2p
Ø=1
j=
n1 -1
= (1-p)" m
((1 - p) + 12p-1)6;)) (1
j=1
i-mi by (2p 1)
II
((1 - p) (2p- 1)6;))
i=
j=mi+1
20
S p) 21 12
2 x- R1 (2p 1) 1
i=
16

---

Published as a conference paper at ICLR 2020
I 2 p)
And similarly,
u(s) - v(s') 2 u(s) - v(ss + +2 20)
8
2 -1 p (1+
Σ i
n
1)p 1)p
2 221 - p pM-1
Hence, (o(s) u(s')l is bounded by 2(1 p) pN-1 for s 2- S S As 2(1
p)> p² converges to zero when N approaches infinity, v(s) is continuous as desired.
We then show the continuity of t'(s) maxae.A(s) Qe We first argue that vs) is monotoni- cally increasing. In fact, for s' 2 and 0 S min s), either 0 < S min(s', 8') or O < a + s I min(s', 8 1 - 8 must be satisfied. Therefore a E A(8) indicates at least one of s' A(s').
a E A(s') and a
Let a' be a or a + s - 8 whoever is in A(s'), we have both s' + + 2 + a and 5' -a 2 Specify a such that (s) Qu a), we have
o' e'(s') 2 Qu(s',)) 2 dss).
The monotonicity follows.
Let b1b2 ... be. -2)). Similarly, for any N, specify n1 N such that bn. 1 and no 2 N + 2 such that bno = 0. Also let 80 = b, (2)- Then for the neighbourhood set 80 2N(+1) < vs)) for both the ends of the interval G [t'(s) ('ss)) | is then bounded by 2 (N++((+))-) - +2 -2-------- (N+)))
s' S so 2 (N+1) ('(s)
2 2-(++1)) so + 2 (N++1
According to Claim 5, this value converges to zero when N approaches infinity. The continuity of es(s) follows.
The continuity of v(s) extends to the dyadic rationals U1z1 Ge when ? = 1, which means that (()) continuous everywhere on [0, 1] under 7 = 1. It worth note that similar to the Cantor function, vss) is not absolutely continuous. In fact, e(s) shares more common properties with the Cantor function, as they both have a derivative of zero almost everywhere, both their value go from 0 to 1, and their range is every value in between of 0 and 1.
The continuity of (s) = maxae.A(s) Q., a) indicates that the optimal action is uniquely min(s, 1 1-s) 3} on s & Ge. This optimal action agrees with the optimal action we specified on s G in Lemma 8, which makes (T)) = min(s, 1 1- 3} an optimal policy for every state (condition on that v(s) is the optimal value function, which will be proved later).
Corollary 10. If s & Gefor any é 2
argmax Qu(s,a)= (min (s, s}} aEA(s)
Lemma 11. v(s) is the unique solution of the system (ABX).
Proof. Let (s)) = max Qu(s, a). As per Lemma 8 we have u(s) = v'(s) on the dyadic rationals Uc21 Ge- Since U121 Ge is dense and compact on (0, 1), v(s) = ds() holds whenever both v(s) and (s) are continuous at By Lemma 9 v(s) and 0s() are continuous for any s if there does not exist an
such that Ge. which then indicates v(s) v'(s) on the complement of U2 Ge. Therefore u(s) = e((s) is satisfied on (0, 1), which verifies the Bellman property (AB). The boundary conditions (X) holds obviously. Finally as per Lemma 2, v(s) is the unique solution to the system of Bellman equation and the boundary conditions.
Theorem 12. Let 0 < Y S and p > 0.5. Under the continuous setting of the Gambler's problem, the optimal state-value function is v(1) = 1 and v(s) defined in Equation for 0 S < 1.
Proof. As the optimal state-value function must satisfy the system (ABX) and v(s) is the unique solution to the system, v(s) is the optimal state-value function.
17

---

Published as a conference paper at ICLR 2020
Corollary 13. The policy x(s) min(s, s} is (Blackwell) optimal.
It is worth noting that when = and E Ge \ Ge-1 for some E, then r'(s) 2- optimal policy at s.
f is also an
Theorem 12 and the proof of Lemma 8 and also induce the following statement that the optimal value function v(s) is fractal and self-similar. The derivation of the corollary is in the introduction.
Corollary 14. The curve of the value function v(8) on the interval [k2- (k 1)2-9 is similar (in geometry) to the curve of v(s) itself on [0, 11, for any integer 2 and S k s 2 1.
Some other notable facts about E(5) are as below:
Fact 15. The expectation
S v(s)ds = (1 (1-p)7 = ((2)
Fact 16. The derivative
u(s + As)
0(s As)
+00,
= U221 Ge.
lim At
O, lim
(8)
As
A--00
As
0,
otherwise.
Fact 17. The length of the are y = v(s),
S equals 2.
In fact, any singular function (zero derivative a.c.) has an are length of (Pelling, 1977) if it go from (0, 0) to (1, 1) monotonically. This can be intuitively understood as that the curve either goes horizontal, when the derivative is zero, or vertical, when the derivative is infinity. Therefore the are length is the Manhattan distance between (0, 0) and (1, 1), which equals 2. Fact 18.
2 argmin v(s) - ( 05
It is natural that by the fractal characterization of v(s) the approximation must be inexact. The following two propositions give quantitative lower bounds on such approximation errors.
Proposition 19. When N E N+, N is a power of 2, let in (s) be piecewise constant any of then
the intervals s E (k/N, (k 1)/N). k .....,N N-
J. (o(s) 10()) (s)
1 (2 7)(1 - phy
+ o N
N 1 1-p7
Proof. When N is a power of 2, for E (O....,NY N - 1}. the curve of v(s) on each the intervals (k/N, (k 1)/N) self-similar to v(s) itself (0, 1). We consider this segment of the curve. By Equation (2),
v(s) = 08) + II
(11 p) + (2p - 1)b3) u(2 8)),
j=1
where l = log, N, 3 = k/N and = 0.b, ... be...(2) E (3, )-
Let As = 1/N, Ay = v((k + 1)/N) v(k/N), we have for 0 < s < As
(5 + 5) v(s) + uss/As)yy
As u(s) is monotonically increasing every interval (k/N, (k + 1)/N), the minimum over
[0()) - øl ds
is obtained when Vs v(8 + 1 As) (intuitively, the median of v(s) on the interval). This results in an approximation error of
A+ (o(s) 5/ ds
min
18

---

Published as a conference paper at ICLR 2020
8+ As
1 As) r(s) ds +
3+4s
0($ + 2
JamatAa v(s) - -((+ As) ds
v(s) ds +
v(s) ds
sm3
1
As
b(3) + (0(3 +
As) - v(3))u(s) ds
2
2
==0
1
1 As) + (u(3 As) v( + 1 As))e(() ds
As
2
===
1
5s((11 (1- - ()))( + As) v()) - (1 - p) () + Ao) - u($ + 1 As)))..
1
=
2
2
This error is then summed over á = 0, 1/N, , (N - 1)/N such that
(N-1)/N
N - 1/4
Σ
(0(8) - 5zl ds 2
2N (11 (1 - 11)))))
+ (1 -1-p) (1) - rl 2N
22 1))
N
O0N
2N ((1 (1 - p)7) (1 p)7 (1 (pry) N+1)
1 py
+ +(1-p)(1 - ((1 | N+11)
N-1 (2 7) - -p) NNI++oRg my (1 (1- (1 p)))ppp1 - p)y?
1 p-py
2(1 - -p7)
N 1+10g (1-p) (1 - -p)
2
(2- (1 p)y
+ o N)
N 1-P7 Py
An error bound in O(1/N) can be generated to any integer N, as we can relax N to 2 NJ-1 so that at least one self-similar segment of size 1/N is included in each interval.
For Lipschitz continuous functions like neural networks, the following proposition shows an ap- proximation error lower bound in (L)LL), where L is the Lipschitz constant.
Proposition 20. Let L 2 (1 - p)1(1 (1 - pr). (2()) is Lipschitz continuous on E (0, where L is the Lipschitz constant, then
J. (u(s)) (s) ds 2
1 (11 (1 - 7)2
L 4(1 m))
Proof. We consider v(}) = (1 p)y and
(1 - p)?
lim v(s) =
1 - Py
When 0 < < 1, we have
0(2)
1 lim vss)
(1 p)r(1 - 7) 0. 1-py py
Denote h = (1 (1-p)>' (1 - /) 17). By the monotonicity of v(s). using 02()) to approximate v(s) has an error at least /, ([())
- Ez (x)] ds, where {(x) denotes the step function on [0, 1].
(0
s5s<b 27
E(s)
h 1 1.
In this case, the optimal (s) is
0
05 1 2
(2
L(s ( (
2. <
2L
h
1 1 I <
+
19

---

Published as a conference paper at ICLR 2020
Hence, we have
1.1 (10())-b2()) ds)) 2 (E(s) - (2( ds 2
112
4L
as desired.
A.2 ANALYSIS OF THE BELLMAN EQUATION
We have proved that v(s) is the optimal value function in Theorem 12, by showing the existence and uniqueness of the solution of the system (ABX). However, the condition (X) is derived from the context of the Gambler's problem. It is rigorous enough to find the optimal value function, but we are also interested in solutions purely derived from the MDP setting. Also, algorithmic approaches such Q-learning (Watkins & Dayan, 1992; Baird, 1995; Mnih et al., 2015) optimize the MDP by solving the Bellman equation, without eliciting the context of the problem. Studying such systems will help to understand the behavior of these algorithms. In this section, we inspect the system of Bellman equation (AB) of the Gambler's problem. We aim to solve the general case (ABY) where p 0.5 and the corner case (ABZ) where p p= 0.5.
When p > 0.5, the value function v(s) is obviously still a solution of the system (ABY) without condition (X). The natural question is if there exist any other solutions. The answer is two-fold: When y < 1, [() = u(s) is unique; when 7 = 1, the solution either vi(s) or a constant function least 1. This indicates that algorithms like Q-learning have constant functions
their set of converging points, apart from vs)). As v(s) is harder to approximate due to the non-smoothness, constant function in fact induces smaller approximation error and thus has better optimality for Q-learning with function approximation.
is immediate to generate this result to general MDPs, as function of large constant solves MDPs with episodic rewards. This indicates that Q-learning may have more than one converging points and may diverge from the optimal value function under y 1. This leads to the need of 7 which is artificially introduced and biases the learning objective. More generally, the Bellman equation may have continuum of finite solutions an infinite state space, even with 7 < 1. Some studies exist on the necessary and sufficient conditions for solution of the Bellman equation to be the value function (Kamihigashi & Le Van, 2015; Latham, 2008; Harmon Baird III, 1996), though the majority of this topic remains open.
The discussions above are supported by series of rigorous statements. We begin with the following proposition that when the discount factor is strictly less than the solution toward the Bellman equation is the optimal value function.
Proposition 21. When y < 1, v(s) is the unique solution of the system (ABY).
Proof. The uniqueness has been shown in Lemma 2 for the system (ABX). When < 1 it corre- sponds case (I), where neither the upper bound f(s) < 1 nor the continuity
in condition (X) is used. Therefore Lemma 2 holds for (ABY) under y < 1, so follows Lemma 11 the uniqueness as desired.
This uniqueness no longer holds under ? =
Theorem 22. Let & = 1, p > 0.5, and f() be a real function on [0, 1]. f(s) satisfies the Bellman equation (ABY) if and only if either
f(s is v(s) defined in Theorem 12, or
f(0) f(1) L, and f(s) C for all 0 < 1, for some constant C'
Proof. It is obvious that both f(s) defined above are the solutions of the system. It amounts to show that they the only solutions.
Without the bound condition (X). the function f(s) is not necessarily continuous on s = 0 and s = and is not necessarily monotonic on 1. Therefore the same arguments in the proof of Lemma will not hold. However, the arguments can be extended to (Y) by considering the limit of f(s) when approaches 0 and 1.
20

---

Published as a conference paper at ICLR 2020
By Lemma the function is continuous the open interval (0, 1). Let
Co = lim f()), C1 lim f(s). s0001
s-1
Then by Lemma 3, 0 S Co S f(s) S Ci for 8 E (0, 1). Here we eliminate the possibility of
Co +oo and C1 +o0. This is because if there is a sequence of 0 such that f(s)) > t,
then we have f(5) 2 p f(s)) + (1 -1-P8 p) f(1 151 si) 2 (1 - p)t for any t. Then f(ž) does not exist.
Similar arguments show that C1 cannot be +o0.
Now specify a sequence a + 2 at < 2. such that Co S f(2 as) S Co + and C1 s [ + 0x) v C. Then we have
1
1 o1) (1) - +0)
/ 1 2
CpC + +1 (1-p) -
As is arbitrary we have (( pC + c). By induction on & it holds E Up21 G2 that
f(s) 2 Co+ + (C, - Co)u(s).
By Lemma 4 the continuity of f(s) and us) under 7 1. this lower bound extends beyond the
dyadic rationals to the entire interval (0, 1). Define fs) C. + (C1 Co)u(s) for s E (0, 1),
f(0) = Co. (1) = C₁. It is immediate to verify that for any C1 Co 2 0. f(s) solves the system (AY) (without (B) the boundary conditions).
If Ci Co + 0, by Lemma 2 Case (II) f(s) on (0, 1) is the unique solution of the system (AY), given monotonicity, continuity, and the lower bound f(s)- With the boundary conditions (B), have 0- f(0) Co and 1 = f(1) C1, therefore (() = v(s). This case C₁ - Co * 0 induces the first possible solution.
amounts to determine f(s) when C1 Co O, that is, when 0- < Co f(s) C₁ for
E 10, (by Lemma 3). It suffices to prove that Co < 1 is not possible. In fact, if Co < 1 then
f()) < f()) +1 (1)) (1), which contradicts (A). Then, f(s) = Co for some Co 1 is the only
set of solutions when C1 Co = 0, as desired.
The fact that a large constant function can also be a solution toward the Bellman equation can be extended to a wide range of MDPs. The below proposition lists one of the sufficient conditions but even without this condition it is likely to hold in practice.
Proposition 23. For an arbitrary MDP with episodic rewards where every state has an action to transit to non-terminal state almost surely, f(s) for all non-terminal states is a solution of the Bellman equation system for any C greater or equal to the maximum one-step reward.
Proof. The statement is immediate by verifying the Bellman equation.
The rest of the section discusses the Gambler's problem under p = 0.5, where the gambler does not lose capital by betting in expectation. In this case, the optimal value function is still v(s) by similar arguments of Theorem 12. is worth noting that when = 1, Thcorem 12 indicates v(s) = s. This agrees with the intuition that the gambler does not lose their capital by placing bets in expectation, therefore the optimal value function should be linear to s. Proposition 21 also holds that v(s) the unique solution of the Bellman equation, given 7 < 1. The remaining problem is to find the solution of the Bellman equation under 7 1 and 0.5. This corresponds to the system (ABZ).
When p 0.5, condition (A) implies midpoint concavity such that for all A(s).
1 2 f(s a) + f( 1 a
f(s) 2
where the equality must hold for a. As Lemma no longer holds, solution fs) may have negative values for some s. Though, it does not have a negative value, must be concave, and thus linear by condition (A) (will be proved later in Theorem 27). It suffices to satisfy s(s) for any
21

---

Published as a conference paper at ICLR 2020
Therefore the non-negative solution is f(0) = 0. f(1) = 1, and f(s) C's B' <n for some constants C' +B' 2 1.
If f(s) does have negative value at some s, then the midpoint concavity (9) does not imply con- cavity. In this case, by recursively applying (9) we can show that the set {(s, f(s) I E (0, 1)} is dense and compact on (0, 1) R. Then the function becomes pathological, if it exists. Despite this, the following lemma shows that f(s) need to be positive on the rationals Q
Lemma 24. Let f()) satisfies (ABZ). If there exists 0 I & < <+ I and a constant C. such that f(s f(st) 2 C, then f() 2 C for all s {s- + w(s - -s) w E 0,0
Proof. The statement is immediate for w E {0.1]. For 0 < w < we prove the lemma by contradiction. Let f( + w(s s }} C for some w E Q while 0 < w < 1. We define so = s + w - ) and S(+1 2s, - s for < 2 + and S1+1 = 2s, - s for st > 1s + +.). respectively. S++1 will be undefined if s, + let w- = m/n where m and n are integers and the greatest common divisor ged n) 1. Then (st-s)) --) me/n, where my 2' m'm mod n. As Z,, is finite, {s heo only take finite many values. Thus either the sequence {sa} J is periodic, or it terminates at some 8t 2 + +st).
Since E Q.
Then we show that f(st) is strictly decreasing by induction. Assume that f(sg) > ... > f(s)). +s*), ). by (9) we have fst) 2 ==( (sr4()) which indicates that f(s++1) When 8t < (5=
(s))) $ (s) - [(s < f(00) ʃ(x)) < 0. When 8 [ +s+), ). by (9) we have [(x) 2
( + (s+). which indicates f($++1) - f(s)) S ((t - f(*)) < fso) - f(st) 0.
The base case f(81) < f(0o) holds as least one of [(00) 2 [1(0))) + [ and ((00) Z
[s1) + (s+) must be true. Thus we conclude that (8x) is strictly decreasing.
If the sequence terminates at some = (5 + s+), then [(*) < [x1) < C, which contradicts fs.) f(2 (s- + +)))
)) 2 ((())++ + ff((s))) 2 C. Otherwise is periodic and indefinite. Denote
the period T we have (8:+T) < fst). which indicates (s;) < fsr) as contradiction.
Lemma 24 agrees with the statement that the midpoint concavity indicates rational concavity, The below statements give some insights into the irrational points.
Lemma 25. Let f() satisfies (ABZ). If there exists an á E R RR)0 such that f(ø) 2 0, then f(s) 2 0 for all s E {ww + u w,u Q S w, u, 1, w + a S 1}.
Proof. Specify 8- = a and 8- = 1 in Lemma 24, we have f(# + -4, - -)) 2 0 whenever u 0 Σ wtn S 1 and u
wit E Q. This is satisfied when 0 I w, u I 1, w + u > 0, w, u E Q
Specify s = 0 and st = 3 -4 (1- 8) in Lemma 24, we have fww + u) = f((w + (3
(1 8))) > 0 whenever + u < 1. Thus f(w5 + u) 2 for 0 w,u < 1, w, Q.
and 0 < w + u < 1. Since the case w = u = 0 is immediate, the statement follows with s E (w8 + u w, Q. w, u, S 1, w 13.
Corollary 26. Let fs) satisfies (ABZ). If there exists B RR Q such that f(3) O, then fww) is monotonically decreasing with respect to w for w E Q 1 15 w < 1/8.
Lemma 25 and Corollary 26 indicate that when there exists a negative or positive value, infinitely many other points (that are not necessarily in its neighbor) must have negative or positive values as well. It is intuitive that the solution with a negative value, if it exists, must be complicated and pathological. In fact, Sierpinski has shown that midpoint concave but non-concave function is not Lebesgue measurable and is non-constructive (Sierpiński, 1920a;b), so does fs) if it solves (ABZ) while having negative value.
Such an (s) exists if and only if we assume Axiom of Choice (Jech, 2008; Sierpiáski, 1920a;b). We consider the vector space by field extension R/Q. With the axiom specify basis B = {1) (g) hez. known as Hamel basis. With this basis B every real number can be written uniquely as a linear combination of the elements in B with rational coefficients. Therefore, denote a real number s uniquely as a vector (w, w;)izz w, w; E Q such that s w + Σiez Wig.. We correspond each f(s) f'(w, (wi]err uniquely to defined QIEI and use the two spaces interchangeably.
22

---

Published as a conference paper at ICLR 2020
The solution fs) to (9) is any concave function f' on the vector space R/Q. Based on this solution
we extend the system (9) to (ABZ). To this end, f(s) need to attain the equality in (9) at every 8, which holds if and only if for every w + Sjez Wig; there exists s w +iez w 9. and 5²
w² + Ever wfg: such that f'(X=* +1 {>w (1 - A)u ) Hizz) (1-
for any 0 < A < 1 (intuitively, local linearity of f on at least one direction everywhere). By a(w,) + 3(w,) for some wy E {w} U {w; i E I). where is linear function, 3 is concave function, and w denotes {w} U {w; E 2} {wz}. When wy is w, f(s) is in fact w + 3([w: hezz) for some concave function B. This is equivalent to specifying a function w(s) R + Q such that w maps reals to rationals additively (88 + 82) = w(s)) + w(x2) and w is not constantly zero, and then write f(s) as w(s) + (s (s)) for some concave real function S1. Otherwise if wy not w, f(() is in the aforementioned form with the boundary conditions (B).
specifyyng B, the condition can be met if f(s) = fw, (wi)ez))
While we have shown that under Axiom of Choice f(s) = a(w,) + B(w,) set of solutions
that can be described by the infinie-diimensioaal vector space IR /Q and its basis, we do not know if they are the only solutions. Nevertheless, combining our analysis and the literature we conclude the following statement about the system (ABZ).
Theorem 27. Let y 1 and p 0.5. A real function f(s) satisfies (ABZ) if and only if either
f(s) = C's + B" on s E (0, 1), for some constants C' + B3' 2 L, or
f(s) is some non-constructive. not Lebesgue measurable function under Axiom of Choice.
Proof. The first bullet correspond to the function f(s) that non-negative on [0. 1]. By the midpoint concavity (9) and the fact that f(s) is non-negative, f()) is concave on [0, 1] (Sierpinski, 1920a;b). We specify 8o = 1.2 By (A) we have
f(00) = 2 [( - an) + 2 f(50 + aa))
for some Since f() is concave, f(s) must be linear on the interval (so Qo, so + ao). Consider the nonempty set
A A1-f00 A(so) ((00) 5 ao) [ + ao)
1
1
We show by contradiction that sup is 1 If a1 = sup A1 < 2. ity as Ai, where the continuity is impfied by the convexity. This indicates that f(s)
1 then by the continu-
fso) + [(ente))-(eooau1/
5o) when so - aj S s S so + a1 But as aj is the maximum element of Ai, on at least one of the intervals [0, 80 a1) and (so + ai] we have by the convexity ((f=+o))f((00--- (s su). Therefore, for at least one of {so a1, a1} 20g
20:
f(s) < <f(so)
we have f(s) > f/f(s - a) f + a) for all a, which contradicts condition (A). Hence sup sup is 7, which implies that [((s is linear on (0, 1). Writing (s) as C's + B', by the boundary condition
verify that f(s) C's + B' with C" + B' 2 1 is sufficient to satisfy the system (ABZ), and is thus the non non-negative solution of the system.
(B) we have C" + B' 2 1. It is immediate
If f(s) is negative some s, then by (9) and (B) f(s) must not be concave. By Sierpiński (1920a;b) such an f(s) exists only if we assume Axiom of Choice, and is non-construetive and not Lebesgue measurable if it exists (some discussion on this function is given above the statement of this theo- rem).
23


Reviews:
[{"review_id": "ryeJ7a_TYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper revisits the Gambler's problem. It studies a generalized formulation with continuous state and action space and shows that the optimal value function is self-similar, fractal and non-rectifiable. That is, it cannot be described by any simple analytic formula. Based on this, it also deeply analysis the discrete case. \n\nOverall, the paper is extremely well written. I must admit that i have really enjoyed reading it. However, the discussion of the implications falls too short. There are a number of complexity results for MDPs and POMDPS, see e.g. (Papadimitriou, Tsitsiklis 1997; Lusena et al. JAIR 2001; Lee at al NIPS 2007). Indeed, the paper does not hide this and provides references. However, for an informed outsider such as the reviewer it does argue how exactly it extends our knowledge here. ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rkecKYVccH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThe paper gave a very detailed analysis of the value function of the gamblers problem. In this problem, the agent decides how much to bet in each step, doubling or losing the chosen amount. There is a chance of loss of greater than 0.5 and as a result the agent would like to minimize the number of steps. While one optimal policy is extremely simple (just bet the maximum), this paper shows that the value function is deceptively complicated due to its fractal structure. In particular, the value function is continuous only when there is no discounting and does not have well behaved derivatives. The exposition is clear and well structured. The author argues such behaviors have consequences for valued function based RL such as value iterations or Q-learning, since one of the simplest RL problem has a weird value function.\n\nThe paper presented both an interesting issue and a clear analysis, and should be accepted. The major issue is that any implications for RL seems unverified. For example, I would be very surprised if a tabular method will not solve the problem given a reasonable update order. The author also did not provide any analysis on how a parameterized method will actually behave, given that is the likely implication. So it is a bit unclear if the pathology is due to taking the continuous limit or if it is present in discrete cases as well. The final part relying on the axiom of choice is too mathy for the problem motivation (since it applies to the rather boring p=0.5 case). The paper would be more valuable to the ML community if that part is replaced with some analysis/evidence of how the issue shows up when actually running one of the solution methods.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "S1xIYUHRKH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper derives the optimal value function for the continuous and discrete versions of the Gambler's problem. It also explores certain properties of this value function and finds that it has many fractal-like qualities.\n\nThis paper focuses on an unconventional but intriguing topic, bringing more insight into the possible shapes of value functions. The main result, which describes the value function for the gambler's problem, seems surprisingly complex and could have some practical implications for value-learning. Unfortunately, I find the paper is difficult to follow due its organization and the presence of many typos and unclear phrases. In summary, while I believe the topic is interesting and the work seems sound, the presentation would need to be improved significantly for me to recommend acceptance.\n\nHere are certain points to be addressed:\n1) On p.2, \"The optimal value function presents its self-similar, fractal and non-rectifiable form\". It is not clear from Thm. 11 that these properties hold. Some further explanation would be helpful \n2) I think it would be helpful to include some descriptions of certain concepts that may be less familiar to the reader in the appendix. E.g. the Cantor function\n3) Fig.1 should have larger labels and dots. It is difficult to see currently.\n4) p.3 \"the similar fractal patterns observed empirically in other reinforcement learning tasks.\" Certain concrete examples would be helpful here since I was not aware that this was common.\n5) p.4 The paragraph on 'self-similarity' was not clear to me. What is meant by 'chaos' or 'dimension' in this context? \n6) p.5 \"Otherwise an arbitrary small amount of will have a fixed probability of reaching the target 1.\" I am unsure what this sentence means.\n7) Perhaps starting with the intuitive description of v(s) (the recursive form) first before presenting the closed form solution would be easier to follow.\n8) Why is there no discussion/conclusion section at the end?\n\nThere are numerous typos scattered throughout the paper. Here are some from the first page:\n- abstract: \"where they mention an interesting pattern of\nthe optimal value function with high-frequency components and repeating nonsmooth\npoints but without further investigation.\" Awkward phrase\n- abstract: \"With the analysis,\" Unnecessary phrase\n- par. 1: \"is described as below\" -> \"is described below\"\n- \"which would hide its attractiveness.\" Awkward phrase\n- \"as an representative\" -> \"as a representative\"\n- \"family of Markov decision process\" -> \"family of Markov decision processes\"\n- \"the amount of bet.\" -> \"the amount bet.\"\n- \"a round of bet.\" -> \"a round of betting.\"\n- \"action-state value function\" -> \"state-action value function\"\n- \"n as the starting capital (n denotes the state in the discrete setting),\" The phrase is a bit confusing as it suggests n denotes both the discrete state and the starting capital.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the optimal value function for the gambler's problem, and presents some interesting characterizations thereof. The paper is well written and should be accepted.
Decision: Accept (Poster)