Dennis Soemers

furthermore, a fixed non-growing dataset of experience E is still more experience than if you were to have 0 experience. So you can still compare the performance of your model with that fixed dataset to the experience of a model that you give access to 0 data

just like "if I were to have more money, I could buy more things" is also a true statement, even if I don't actually have more money

that can still be true even if you don't actually have more experience

it just says that if you were to have more experience, then performance would also increase.

that quote does not mandate that in any particular instance you actually have to have a dynamically growing set of experience

"if its performance at tasks in T, as measured by P, improves with experience E"

then I think Mitchell's definition for "ML techniques" is a pretty decent one

@Marina I agree with @nbro that I don't really have a formal definition for "ML tasks" or problems. Those three families of problems you listed (classification, regression, clustering) are just informally united in that they're typical types of problems that we can generally address with "ML techniques"

@Joey MCTS generally grows its tree relatively slowly; in the most common implementation, at one node per iteration/simulation/rollout. That would require millions upon millions of iterations before it'd run out of memory, generally it's terminated due to time constraints long before that. More aggressive Expansion strategies (like, expanding all nodes encountered in a rollout) could run out of memory more quickly. Anyway, if you're not familiar with Minimax yet, all of that probably sounds rather complicated, which is why I recommend starting with basics first; Minimax.

@JohnDoucette I really don't see the similarities between A* and Quiescence search either. A* is about quickly searching in a direction as informed by a heuristic, it's about "Best-First Search", whereas Quiescence is a... "more advanced depth-selection strategy" on top of Alpha-Beta style algorithms (searching more deeply in lines of play where action is happening, less deeply in quiet / "boring" lines of play). I do like everything else in your answer, just think the A* part is confusing.

Nope MCTS doesn't first go to a fixed depth and then starting "rolling". See http://mcts.ai/about/.

A* doesn't really seem to fit in the context of two-player games like the other algorithms do? Note on MCTS: typical implementations don't "consider all moves down to some fixed depth" and then start the rollouts; instead, typical implementations dynamically, gradually grow the tree search tree, growing it more in more promising parts (parts where many rollouts are nudged towards by Selection strategy), growing it less in the less promising parts.

thanks :)

I guess it's because with the prediction problem, you're exclusively learning to predict (normally values, but I guess you could more easily extend the definition to also predicting other things, like predicting the state you end up in). You're not learning to actually interact/control anymore

I think :P

Sure could be a useful question if we don't have it already. I usually see the two being referred to as "prediction problem" and "control problem" though

which is... usually not what we want

If you have a "discount factor" of 1.1, and you received a reward of 1.0 immediately (in the very first time step), you'd only value that as 1.1^0 * 1.0 = 1.0. But if you delayed that same reward by one more time step, you'd value that same reward as 1.1^1 * 1.0 = 1.1. Hence, an agent would start preferring to delay its rewards

what about that?

I'm not sure what you're asking :)

@DuttaA Maybe someone has... I'm just not aware of it. Why would you want to do something like that though? If you have a specific domain with specific domain knowledge / heuristics that tell you that certain moments are more important than others, I'd be more inclined to factor that into the Reward function directly, or include it as yet another multiplier, but separate from the discount factor...

In practice, making it greater than 1 would cause an agent to prefer receiving the same reward later rather than earlier, as nbro mentioned. That's usually not what we want... usually we'd either want to have no preferences for time (discount factor = 1), or prefer to receive them earlier than later, because that reduces the risk of "missing out" due to stochasticity, exploration, etc. (discount factor < 1)

This is for the general case. In specific cases / specific problem settings / specific domains / specific MDPs, you could easily show that a discount factor < 1 is NOT necessary for finiteness. For example, take any game where you get a reward of 1 at the end for winning, -1 for losing, 0 for any other time step. Obviously your choice of discount factor wouldn't matter much in this setting (assuming you at least pick a nonnegative one...)

@DuttaA I'm not familiar with any work explicitly researching that... In the general case, in theoretical work, a discount factor smaller than 1 is always assumed because we need that to guarantee that infinite sums of discounted rewards are still finite. And having stuff be finite is generally nice for proofs.

@DuttaA Never read them, so can't really say anything. The Sutton and Barto book happened to be the book that my course instructors picked when I was a student, and I guess it's also the more famous one, so that's the one I'm familiar with. Nowadays I rarely read the books, mostly papers

Up until you write "Simplifying the equation by cancelling the reward terms $R_{t:t+n}$ we get:", I think it looks fine. But I find it difficult to convince myself that that particular step is correct. Not saying it isn't, but this is where it becomes too difficult for me to keep in my head exactly which parts depend on which of the $T$ trajectories, and that's important to make sure that that step is correct

Also, I think a $\gamma^n$ went missing in the definition of $G_{t:t+n}^{\pi}$. I don't mind it too much because that mistake did not carry over into the subsequent steps, but it's technically a little mistake :)

alternatively, you could include a tiny bit of randomisation in your evaluation function. Not too much, you wouldn't want it to actually affect any rankings, you'd only want the random number to provide tie-breaking. Gotta be careful though since you wouldn't want to miss out on any prunings due to such a random tie-breaker either.

that only makes sense if you don't have a more useful way of ordering your legal moves before starting the search though. If you do have more sensible ways of ordering them, that can lead to significantly more prunings in your search. For example, a very very simple trick in Chess would be to order your moves such that all the capture moves are searched before all the non-capturing moves (because usually capturing moves tend to be "better" than non-capturing moves)

@DuttaA Yes, unless you add some extra trick for randomisation. A simple thing I like to do is to simply shuffle the list of legal moves right before I start searching. If there are different legal moves that would all get identical evaluations by a full minimax search, they'll all get a chance to be selected by Alpha-Beta too if the order in which it searches them is randomised

technically some people might mean 6 "turns" = 12 "moves" when they say that... but then they're wrong unless they're really explicit about it :P I would generally read it as 6 moves, 3 per player (in a game like Chess where turns between players always keep consistently alternating)

Most people would mean looking 6 moves or plies ahead, i.e. three White moves and three Black moves

@DuttaA Err not sure, where is this? I've never heard anyone referring to search depths as "stages"...

and tree search

Artificial Intelligence, mostly focus on General Game Playing / Reinforcement Learning

owh

Maastricht University

PhD student/researcher

I know what the acronym stands for... But in my research I tend to focus on stuff that's more likely to be feasible in a shorter timeframe than... 50+ years :P

I'm not a Chess AI expert so much as general game playing though. So don't know too much of the super-chess-specific details in chess programming

@DukeZhou You liked Ludi, didn't you? We've made a pre-release version of Ludii (double "i") available today at ludii.games :) It does not (yet) generate games though, the focus so far has been on modelling and playing them.

Nope haven't heard of it (apart from seeing some retweets about the press coverage). I don't think this is the kind of stuff that I'd be paying a huge amount of attention to in my normal diggings through literature though (topic probably not close enough to what I'm directly working on).

Yeah. If the NN outputs values in [-1, 1], and we want them to be in [0, 1] for pUCT, we can always do that by just adding 1 to the NN output, and dividing by 2 afterwards

@Maybe It's about the same board games in both cases. It's just, one thing is the learning algorithm (learning values and policies in any board game), and the other thing is the tree search (again in all the same board games). They're mostly separate, and you can use different ranges of values in each of them. I suppose in the parts where these two separate components start "communicating" to each other, they'll make the translation between the two ranges. i.e. if the search uses a value in $[-1, 1]$ from the NN, it can just map that to the $[0, 1]$ range before making use of it.

@Maybe Ah right, I see. Yeah, so in Section 3 they describe their Neural Network Reinforcement Learning approach. For the purposes of this training algorithm, they use rewards of $-1$, $0$, and $1$ for losses, draws, and wins, respectively. In Appendix B they describe the tree search approach. That's a different component. And for the purposes of that part, they instead use (different) values in $[0, 1]$.

@Maybe That's what they write in the paper, right? So yes. At least for the search. Maybe for learning they use a different range, not sure, would have to check. They also actually explain why they chose that $[0, 1]$ range in the sentence after the one you quoted; it ensures that their $Q(s, a)$ values are in the same range as the $P(s, a)$ values, and both of those are combined in the pUCT rule. I suppose that keeping them both in the same range can make hyperparameters slightly more easy to tune (or interpret / understand).

@Maybe Technically you're completely right that the true, formal definition of "zero sum" would imply that losses are $-1$, draws are $0$, and wins are $+1$. Or at least that it would have to be a range centered on $0$. But the authors may have found the $[0, 1]$ range more convenient to work with for other reasons. I know that range is quite common in MCTS / bandit algorithms literature, and historically all kinds of theoretical analyses and proofs are based on that range. So also many people implemented it that way. And if they did implement it like that, its important to report in the paper

@Maybe Yes, you're right that the range selected can be very important in terms of hyperparameters. But nikos is also correct that the selected range is a fairly arbitrary choice -- in a mathematical sense. Whether we train an agent to optimise values in $[0, 1]$ or in $[-1, 1]$ doesn't really matter mathematically; exactly the same states will be winning or losing, exactly the same policy will be optimal, etc. It's an implementation detail, which mathematically does not really matter. Implementation details can be important for empirical performance though, and indeed for hyperparameters!