I agree with you. What I am taking issue with is the article presenting a multitude of (unnecessarily) complex refutations (as if one wasn't enough) and suggesting that there is no consensus on which one should be believed. This is not how people do mathematics!
A better article would first introduce a more precise version of the switching argument and then precisely identify the flaw in it. The more advanced mathematical and philosophical discussion that explores variations of the basic argument should be separated and contextualized clearly.
I am in fact disputing this empirical fact, or at least the interpretation of it that is suggested in the article.
There is no such thing in mathematics such as an unresolved dispute over whether or not a five line proof with elementary concepts is flawed or not. The only possible situations are: 1) the proof can be checked to be correct at the level of axioms, 2) an incorrect reasoning step can be pointed to or 3) the proof is ambiguous and/or people cannot agree on what is being proved.
There isn't really a mathematical literature about the two envelopes paradox because the paradox is not really interesting from a mathematical standpoint. Or at least, making it interesting from a mathematical standpoint would require presenting a different argument than the one presented in the Wikipedia article. There may be a scholarly debate about different philosophical or linguistic aspects of this paradox. However, there is certainly no debate about where the flaw is in the presented switching argument once you make it precise enough.
(And the answer should not involve infinite series unless you are looking at a different, strong-arm version of the argument.)
This is a good comment and I believe your justification is equally valid.
The reason for the apparent disagreement is that in order to point out a logical flaw in an argument, one must make the argument formal and explicit enough first. There are several plausible ways that the Wikipedia argument can be translated into a machine-checkable formal proof (and this ambiguity is at the core of the paradox). When I make such an attempt in my head, I am not interpreting the expectation as a conditional one and the problematic step is about conflating a random variable with a fixed constant. In your attempt to formalize the Wikipedia argument, you try and use the iterated expectation theorem and the problematic step becomes different. Seeing from the comments, several people agree with my interpretation but clearly there is an ambiguity here that is part of the paradox.
Thanks for prompting me to add nuance to my comment.
I would argue that this Wikipedia article is misleading and that it confuses more than it clarifies when it comes to resolving the paradox.
In particular, I am disputing the fact that "no proposed solution is widely accepted as definitive" (exact quote). Indeed, the switching argument (or at least the argument as it is presented in the Wikipedia article) makes a clear and precise mistake that I claim any trained mathematician will immediately agree on once pointed to it.
Once you have identified it, this mistake is all but subtle. It is not about infinite series or Bayesian reasoning. It does not require a 30 minutes rebuttal talk. It is simply about misusing the very definition of an expected value in a way that could be qualified as a typing error (see linked comments). This error can only go undetected because of the ambiguity of the English language. Most of the fancy mathematical discussions I've been reading are distractions. This paradox is about language and not about any deep mathematical fact of probability theory.
I do not like this explanation. In my opinion, the fancy mathematical argument involving infinite series is an unnecessary distraction from a much more fundamental and mundane mistake (i.e. incorrectly using a variable out of its scope).
In my opinion, the Wikipedia article is making a disservice to readers by mentioning unnecessarily complex mathematical arguments involving bayesian reasoning and infinite distributions. I believe all of these are distractions from the more fundamental typing error that invalidates the switching argument.
Some excellent critiques have been provided in this thread already but I would like to offer a different perspective.
In programming terms, the switching argument (see original link) is incorrect because it does not typecheck. And it does not typecheck because variable A is used out of its scope when writing down the (5/4)*A expected value.
Indeed, variable A is tied to a specific random outcome and so it simply does not make sense to refer to it in an expected value ranging over this same outcome.
Trying to formalize the argument in a proof assistant makes the mistake clear and obvious. However, the ambiguity of the English language makes it possible for such typing errors to sneak in undetected.
As a researcher in machine learning, I wanted to explore applications of Deepmind’s AlphaZero algorithm beyond board games (such as in automated theorem proving or chemical synthesis).
However, I noticed that existing open-source implementations of AlphaZero mostly consisted in complex C++ codebases that are highly specialized for specific games (eg. Leela Zero and LC0). Accessible Python implementations could be found but they were usually too slow to do anything useful on limited computing power.
AlphaZero.jl is written in Julia and it is consistently one to two orders of magnitude faster than competing Python alternatives, while being equally simple and flexible. I just released a new version a few days ago with many new features (support for distributed computing, support for arbitrary MDPs...).
If you are a student, a researcher or a hacker curious about AlphaZero, please consider having a look!
I think that MuZero is a fascinating algorithm, but that a lot of news articles are misleading when they present it as a new, superior substitute for AlphaZero.
MuZero is solving a harder problem, in which the learning agent does not have a model of the environment from the start (e.g. it does not know the rules of the game a priori). This makes it potentially applicable to a larger number of real-world challenges.
However, I haven't seen any evidence that it is any better than AlphaZero at learning games such as Chess or Go. Although DeepMind reports that their MuZero agent "slightly exceeds the performances of AlphaZero on Go", they say nothing about the training time and tuning effort spent on each.
As far as I understand and in the absence of further data, I think AlphaZero is still the superior choice to solve games with known rules, especially if you don't have DeepMind's level of computing resources.
If anyone knows better about this, I would be happy to be proven wrong though.
I am wondering if your idea of using GBDTs in combination with AlphaZero might not be most influential in areas where no neural network architecture is known to provide the right inductive bias for the problem at hand.
I think neural models are pretty unbeatable in many classic RL environments because convolutional neural networks are REALLY good at learning visual representations. In some sense, I suspect that the great success of AlphaGo Zero comes in big part from the fact that it really makes sense to analyze a Go board as a 2D image using convolutional networks: convolutional networks provide the right inductive bias for the problem of learning to play Go.
However, there are tasks where neural network are not as good, such as symbolic manipulation tasks (I am in a good position to know this as I'm doing research in the area of automated theorem proving). I would be very curious to see how your approach fares for those tasks.
Thanks! You can easily find my email address from my github.
I am not aware of a canonical discord channel for discussing AlphaZero but the Lc0 community has a discord channel on which I had some interesting conversations.
This needs clarification indeed. As I explain in the documentation, the aim of AlphaZero.jl is not to compete with hyper-specialized and hyper-optimized implementations such as LC0 or ELF OpenGO. These implementations are written in C++ with custom CUDA kernels and they are optimized for highly distributed computing environments. They are also very complex and therefore pretty inaccessible to students and researchers.
The philosophy of AlphaZero.jl is to provide an implementation of AlphaZero that is simple enough to be widely accessible for students and researchers, while also being sufficiently powerful and fast to enable meaningful experiments on limited computing resources. It has the simplicity of the many existing python implementations, while being consistently between one and two orders of magnitude faster.
More generally, the AlphaZero algorithm is extremely general and I think it can find applications in many research domains (including automated theorem proving, which is my own research area). I have been surprised to see that, despite the general excitement around AlphaZero, very few people actually tried to build on it. One explanation, I think, is the lack of accessible open-source implementations. I am trying to bridge this gap with AlphaZero.jl.
This is interesting, thanks! Is there anything else you can tell me about the results of your experiments with small networks? I am really interested in this.
For example: did you notice than increasing or decreasing network size required significant changes in other hyperparameters? Are small networks learning faster at the beginning of training before they start to plateau?
So far, the main idea I have pulled from the Lc0 crowd is to have a prior temperature indeed. The next thing I am planning to add is the possibility to batch inference requests across game simulations instead of relying on asynchronous MCTS. In your blog series, you anticipate the problem of the virtual loss introducing some exploration bias in the search but ultimately concludes that it does not change much:
[Citation from your blog series]: "Technically, virtual loss adds some degree of exploration to game playouts, as it forces move selection down paths that MCTS may not naturally be inclined to visit, but we never measured any detrimental (or beneficial) effect due to its use."
Interestingly, it seems that the LC0 team had a different experience here. I myself ran some tests and going from 32 to 4 workers (for 600 MCTS simulations per turn) on my connect-four agent results in a significant increase in performances. This may be due to the fact that I use a much smaller neural network than yours, which is ultimately not as strong.
Related to this, there is a question I have wanted to ask you since I found your blog article series: did you make experiments with smaller networks and what were the results? What is the smallest architecture you tried and how did it perform?
Your series of blog articles has been an important source of inspiration in writing AlphaZero.jl and I cite it frequently in the documentation. Thanks to you and your team!
Multiple GPUs support definitely belongs to the TODO list. However, I am currently limited by the state of CUDA.jl on this, as it does not have a device-aware memory pool yet.
I am also looking forward to CUDA.jl supporting f16 and int8 computations, which may enable another big speedup.
I agree with the quoted numbers. As I mentioned in another comment, you have to keep in mind that AlphaZero is an extremely sample-inefficient learning technique, even for simple problems. However, it has two major strengths: 1) it is pretty generic and 2) it can leverage huge amounts of computing power.
A better article would first introduce a more precise version of the switching argument and then precisely identify the flaw in it. The more advanced mathematical and philosophical discussion that explores variations of the basic argument should be separated and contextualized clearly.