Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: 
The 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.

The 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.

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 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.

This 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.

Here are certain points to be addressed:
1) 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 
2) 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
3) Fig.1 should have larger labels and dots. It is difficult to see currently.
4) 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.
5) p.4 The paragraph on 'self-similarity' was not clear to me. What is meant by 'chaos' or 'dimension' in this context? 
6) 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.
7) Perhaps starting with the intuitive description of v(s) (the recursive form) first before presenting the closed form solution would be easier to follow.
8) Why is there no discussion/conclusion section at the end?

There are numerous typos scattered throughout the paper. Here are some from the first page:
- abstract: "where they mention an interesting pattern of
the optimal value function with high-frequency components and repeating nonsmooth
points but without further investigation." Awkward phrase
- abstract: "With the analysis," Unnecessary phrase
- par. 1: "is described as below" -> "is described below"
- "which would hide its attractiveness." Awkward phrase
- "as an representative" -> "as a representative"
- "family of Markov decision process" -> "family of Markov decision processes"
- "the amount of bet." -> "the amount bet."
- "a round of bet." -> "a round of betting."
- "action-state value function" -> "state-action value function"
- "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.

review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: 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. 

Overall, 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. 
review_title: Official Blind Review #1

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)