26
votes
Accepted
What is the difference between First-Visit Monte-Carlo and Every-Visit Monte-Carlo Policy Evaluation?
The first-visit and the every-visit Monte-Carlo (MC) algorithms are both used to solve the prediction problem (or, also called, "evaluation problem"), that is, the problem of estimating the value ...
- 41.1k
15
votes
Accepted
How does "Monte-Carlo search" work?
Monte Carlo method is an approach where you generate a large number of random values or simulations and form some sort of conlusions based on the general patterns, such as the means and variances.
As ...
7
votes
Accepted
Why does TD Learning require Markovian domains?
The Markov assumption is used when deriving the Bellman equation for state values:
$$v(s) = \sum_a \pi(a|s)\sum_{r,s'} p(r,s'|s,a)(r + \gamma v(s'))$$
One requirement for this equation to hold is that ...
- 32.9k
7
votes
Why do we need importance sampling?
Importance sampling is typically used when the distribution of interest is difficult to sample from - e.g. it could be computationally expensive to draw samples from the distribution - or when the ...
- 5,000
6
votes
Accepted
What does the term $|\mathcal{A}(s)|$ mean in the $\epsilon$-greedy policy?
This expression: $|\mathcal{A}(s)|$ means
$|\quad|$ the size of
$\mathcal{A}(s)$ the set of actions in state $s$
or more simply the number of actions allowed in the state.
This makes sense in the ...
- 32.9k
6
votes
Why is the target called "target" in Monte Carlo and TD learning if it is not the true target?
It is our "current" target. We assume that the value we get now is at least a closer approximation to the "true" target.
We're not so much moving towards a wrong value as we are ...
5
votes
How do temporal-difference and Monte Carlo methods work, if they do not have access to model?
The main idea is that you can estimate $V^\pi(s)$, the value of a state $s$ under a given policy $\pi$, even if you don't have a model of the environment, by visiting that state $s$ and following the ...
- 202
5
votes
Accepted
What is the intuition behind TD($\lambda$)?
TD($\lambda$) can be thought of as a combination of TD and MC learning, so as to avoid to choose one method or the other and to take advantage of both approaches.
More precisely, TD($\lambda$) is ...
- 41.1k
5
votes
Accepted
What is the typical AI approach for solving blackjack?
Blackjack is usually modelled using Monte Carlo (MC) Methods. There is a lot of literature on MC methods which is interesting on its own right but here is a paper describing how MC is applied to ...
- 3,847
5
votes
Accepted
In MCTS, what to do if I do not want to simulate till the end of the game?
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'$ ...
- 2,554
4
votes
Accepted
Why is GLIE Monte-Carlo control an on-policy control?
In this case, $\pi$ has always been an $\epsilon$-greedy policy. In every iteration, this $\pi$ is used to generate ($\epsilon$-greedily) a trajectory from which the new $Q(s, a)$ values are ...
- 562
4
votes
Accepted
MCTS: How to choose the final action from the root
By far the most commonly used strategy is to select the child with the highest number of visits. This is as described in the 2008 paper you linked. It's also what's referred to as the "robust child" ...
- 10.4k
4
votes
Accepted
Into which subcategories can reinforcement learning be divided?
Your two suggestions are not mutually exclusive. If you go by this process, you'll have to do a "Cartesian product" of a bunch of different RL categorizations which would get out of hand. I ...
- 1,136
4
votes
Accepted
Action-value estimation of deterministic policies with Monte Carlo method
But, in a real application under a given deterministic policy $\pi$, how can you choose the initial action $a$ arbitrarily at state $s$ because it is already fixed by the policy $\pi$: $a=\pi(s)$?
...
- 32.9k
3
votes
In what RL algorithm category is MiniMax?
I think you are looking at it from the wrong direction, min-max is just a planning algorithm, decision strategy, in the sense that you are describing other algorithms/methods it does not have a ...
- 77
3
votes
Accepted
How can we compute the ratio between the distributions if we don't know one of the distributions?
The rationale behind importance sampling is that $q(x)$ is difficult to sample from but easy to evaluate. Or at least you can easily evaluate some $\tilde{q}$ such that:
$$
\tilde{q}(z) = Zq(z)
$$
...
3
votes
Accepted
Do we need the transition probability function when calculating the importance sampling ratio?
There is one thing I don't particularly understand. Why do we need the state-transition probability function when calculating the importance sampling ratio for off-policy prediction?
It is not needed ...
- 32.9k
3
votes
Accepted
In Monte Carlo learning, what do you do when an end state is reached, after having recorded the previously visited states and taken actions?
I am assuming you are asking about Monte Carlo simulation for value estimates, perhaps as part of a Monte Carlo control learning agent.
The basic approach of all value-based methods is to estimate an ...
- 32.9k
3
votes
What is the relation between Monte Carlo and model-free algorithms?
In Reinforcement Learning (RL), the use of the term Monte Carlo has been slightly adjusted by convention to refer to only a few specific things.
The more general use of "Monte Carlo" is for ...
- 32.9k
3
votes
Monte-Carlo, every-visit gridworld, exploring starts, python code gets stuck in foreverloop in episode generation
Your implementation of Monte Carlo Exploring Starts algorithm appears to be working as designed. This is a problem that can occur with some deterministic policies in the gridworld environment.
It is ...
- 32.9k
3
votes
How can we compute the ratio between the distributions if we don't know one of the distributions?
It is common in Bayesian statistics to only know the posterior up to a constant of proportionality. This means that we can't directly sample from the posterior. However, using importance sample we are ...
- 5,000
3
votes
Accepted
What is the bias-variance trade-off in reinforcement learning?
The bias-variance trade-off that you're referring to has to do with the return estimator. Any RL algorithm you choose needs some estimate of the cumulative return, which is a random variable with many ...
- 1,136
3
votes
Accepted
Why are state-values alone not sufficient in determining a policy (without a model)?
why is it not possible to suggest a policy solely on the basis of state-values; why do we need state-action values?
A policy function takes state as an argument and returns an action $a = \pi(s)$, or ...
- 32.9k
3
votes
Accepted
Why does Monte Carlo policy evaluation relies on action-value function rather than state-value function?
In Model Based Reinforcement learning, state and state-action values for all states can be calculated based on the bellman equations. The equations are taken from Andrew Ng's Algorithms for Inverse ...
- 1,291
3
votes
Accepted
Is the expected value we sample in TD-learning action-value Q or state-value V?
However, from the blogs and texts I read, the equations are expressed in terms of V and NOT Q. Why is that?
MC and TD are methods for associating value estimates to time step based on experienced ...
- 32.9k
3
votes
With Monte Carlo off-policy learning what do we correct by using importance sampling?
We estimate a value using sampling on whole episodes, and we take this values to construct the target policy.
The crucial bit that you are missing is that there is no single value of $V(s)$ (or $Q(s,...
- 2,554
2
votes
Why is Monte Carlo used as the tree search algorithm for AlphaGo?
The paper that introduced AlphaGo, Mastering the game of Go with deep neural networks and tree search, motivates the use of MCTS
Monte Carlo tree search (MCTS) uses Monte Carlo rollouts to estimate ...
- 41.1k
2
votes
Accepted
Why Monte Carlo epsilon-soft approach cannot compute $\max Q(s,a)$?
If $\pi$ is a random policy, and after running through this algorithm, and for each state take the $\max Q(s,a)$ for all possible actions, why would that not be equal to $Q_{\pi^*}(s, a)$ (optimal Q ...
- 32.9k
2
votes
Accepted
How is the incremental update rule derived from the weighted importance sampling in off-policy Monte Carlo control?
By definition of $V_{n+1}$, we have:
$V_{n+1} = \frac{\sum_{k=1}^{n} W_{k} G_{k}}{\sum_{k=1}^{n} W_{k}} \; \tag{1}$
Then, taking the $n^{th}$ term out of the sum in the numerator, we have:
$V_{n+1} ...
- 722
2
votes
Accepted
Understanding the W term in off policy monte carlo learning
The pseudocode you have copied looks incorrect to me, and I think it is from the first edition.
The main issue is at the end of the loop. Where the book has
$\qquad W \leftarrow W \frac{1}{\mu(A_t|...
- 32.9k
Only top scored, non community-wiki answers of a minimum length are eligible