The Gambler*s Problem and Beyond
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 cite{sutton2018reinforcement}, where they mention an interesting pattern of the optimal value function with high-frequency components and repeating non-smooth points but without further investigation. We provide the exact formula for the optimal value function for both the discrete and the continuous case. Though simple as it might seem, the value function is pathological: fractal, self-similar, non-smooth on any interval, zero derivative almost everywhere, and not written as elementary functions. Sharing these properties with the Cantor function, it holds a complexity that has been uncharted thus far. With the analysis, our work could lead insights on improving value function approximation, Q-learning, and gradient-based algorithms in real applications and implementations.
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.
You are a member of the scientific community tasked with peer review. Review the following paper title and abstract.
### Title + Abstract
The Gambler*s Problem and Beyond
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 cite{sutton2018reinforcement}, where they mention an interesting pattern of the optimal value function with high-frequency components and repeating non-smooth points but without further investigation. We provide the exact formula for the optimal value function for both the discrete and the continuous case. Though simple as it might seem, the value function is pathological: fractal, self-similar, non-smooth on any interval, zero derivative almost everywhere, and not written as elementary functions. Sharing these properties with the Cantor function, it holds a complexity that has been uncharted thus far. With the analysis, our work could lead insights on improving value function approximation, Q-learning, and gradient-based algorithms in real applications and implementations.
user
<think>Okay, to do a decent peer review, I should start with summarizing what the work is about. This includes novelty, contributions, clarity, and impact. I might include suggestions to issues that I find critical to the usefulness of the work. Starting with novelty, there are different types of novelty. The first aspect of novelty is scope and scale. Is the work covering a broader perspective than previous works? The second aspect is methodology. Is the proposed methodology novel compared to previous methods? Do they provide any significant advantage over previous methodologies? The third aspect is results. Are the results different compared previous work? Does this lead to any novel theories or an extension of current theories? Next is clarity, I will be reading the work in depth and analyze if any sentences can be potentially ambiguous or misleading. If any sentences are ambiguous, I will state them and give a suggestion on how to rephrase such sentence or how to make more clear to the audience. Lastly, impact is important. I will attempt to predict how such work will impact the scientific community. This might include the applications of such work and how the work might transform the way we study a certain topic. Finally, I will might only mention issues that are critical. This is to keep the review as concise and helpful as possible.</think>



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