4

Famous example is AlphaZero. It doesn't do unrolls, but consults the value network for leaf node evaluation. The paper has the details on how the update is performed afterwards: The leaf $s'$ position is expanded and evaluated only once by the network to gene-rate both prior probabilities and evaluation, $(P(s′ , \cdot),V(s ′ )) = f_\theta(s′ )$. Each edge $...


3

You can indeed use UCB in the RL setting. See e.g. section 38.5 Upper Confidence Bounds for Reinforcement Learning (page 521) of the book Bandit Algorithms by Csaba Szepesvari and Tor Lattimore for the details. However, compared to $\epsilon$-greedy (widely used in RL), UCB1 is more computationally expensive, given that, for each action, you need to ...


3

Here is an intuitive description/explanation. $c$ is there for a trade-off between exploration and exploitation. If $c=0$ then you only consider $Q_t(a)$ (no exploration). If $c \rightarrow \infty$ then you only consider exploration term. $\frac{\ln t}{N_t(a)}$ is there to balance out exploration term. If you consider a simple case where you only have one ...


2

Isn't the distribution independent of the time the arm $i$ was chosen? Each one of the two references you describe assumes the context of the random bandit problem proposed by Robbins (1952) where the underlying reward distributions of each bandit are fixed. Therefore, yes, the underlying distributions are independent of the current time. Is it because the ...


2

Isn't the distribution independent of the time the arm $i$ was chosen? Yes, but you don't know which arm was chosen at time $t$, that is what $I_t$ represents. $v_i$ would represent the $i$th arms distribution, whereas you want the distribution of the arm that was chosen at time $t$, which is $v_{I_t}$. $X_{I_t,t}$ is used to represent the arm you chose at ...


2

The first thing to note here is that your results seem aligned with the results commonly found in the bandit literature. Second thing to note would be that the performance of bandit algorithms is usually measured in terms of regret. This is the difference between (i) the amount of rewards accumulated by an oracle policy having prior knowledge about the true ...


2

Many techniques for the exploration/exploitation dilemma that are inspired by multi-armed bandit problems, such as UCB1, assume that you can explicitly enumerate all state-action pairs; in fact, multi-armed bandit problems usually only have just one "state", and then this requirement turns into only requiring the ability to enumerate actions. In RL ...


2

First explore the nodes A,B,C once. For reference see this paper by David Silver and Sylvain Gelly, Combining Online and Offline Knowledge in UCT If any action from the current state $s$ is not represented in the tree, $\exists a \in \mathcal{A}(s),(s, a) \notin \mathcal{T},$ then the uniform random policy $\pi_{\text {random }}$ is used to select an action ...


1

Assigning a value of $\infty$ to unvisited nodes is indeed the "default" or most basic choice, and it indeed ensures that the search never visits a node for a second time if it also still has siblings that have not had any visits. But many other kinds of values have been tried in the literature too. Gelly and Wang, in "Exploration exploitation ...


1

The upper bound used here is derived from Hoeffding's inequality, which provides a symmetric, two-sided confidence interval. A good pair of blog posts on how this bound used in UCB for bandits is derived can be found here: First steps: Explore-then-Commit The Upper Confidence Bound Algorithm Indeed, in practice when using this UCB for bandits, we do not ...


1

In the PDF of the original paper for UCB1 you linked, in page 242-243 the authors proves why non-optimal machines get played much less (in fact, logarithmically less) than the optimal ones. $c$ decides whether they indeed would, and $c=\sqrt{2}$ is the minimum choice of $c$. We want to show that the number of runs for non-optimal machines ($n_i$, for non-...


1

Neil Slater's answer is very nice, but I have a couple more suggestions: You can use entropy regularization. Basically, you modify your loss function to penalize low policy entropy (so less loss for more entropy) which should prevent your policy from becoming "too deterministic" too early. You can also try maximum-entropy methods, like SAC, which employ a ...


1

I believe that if I follow the policy (sample an action from the policy) I make use of exploration because each action has a certain probability so I will explore all actions for a given state. Yes, having a stochastic policy function is the main way that a lot of policy gradient methods achieve exploration, including REINFORCE, A2C, A3C. Is it ...


Only top voted, non community-wiki answers of a minimum length are eligible