Questions tagged [monte-carlo-methods]
For questions related to the Monte Carlo methods in reinforcement learning and other AI sub-fields. ("Monte Carlo" refers to random sampling of the search space.)
83
questions
1
vote
1
answer
45
views
Please help me understand constant-α Monte Carlo method
This is my understanding thus far about Monte Carlo method for approximating value function:
Instead of using a recursive Bellman equations and knowledge of environment dynamics, Monte Carlo methods ...
- 39
1
vote
1
answer
35
views
Understanding the policy improvement theorem for Monte Carlo Control without Exploring Starts
I am currently studying the equations 5.2 in Reinforcement Learning An Introduction By Sutton and Barto on page 101.
I want to comprehent the proof by a simple example:
Having only one State with two ...
- 13
2
votes
1
answer
40
views
Why is there the potential problem of "learning only from the tails of episodes" in off-policy MC control?
Sutton-Barto page 111, first paragraph (Off-policy Monte Carlo Control):
A potential problem is that this method learns only from the tails of episodes, when
all of the remaining actions in the ...
- 974
1
vote
1
answer
274
views
Confused about Monte Carlo first visit algorithm
I'm really confused about understanding the Monte Carlo first visit algorithm as presented in the Sutton & Barto's book in chapter V. Here is the pseudocode:
The reason is that I'm trying to ...
- 204
0
votes
0
answers
64
views
Finding a value at which TD(lambda) and Monte Carlo Are Similar
Let's say that I'm trying to find a value of lambda for which running a TD(lambda) method will produce the same results as a Monte Carlo method (within a small margin or error, of course). One of the ...
- 1
3
votes
1
answer
237
views
How does Monte-Carlo Tree Search Compare to MCMC?
Monte-Carlo Tree Search was the method used for AlphaGo my understanding is: it would randomly search the state space of possible moves where the probability of choosing a move was proportional to the ...
- 434
2
votes
1
answer
285
views
How does off-policy Monte Carlo weighted importance sampling bias converge to zero (Sutton & Barto Section 5.5)
On Section 5.5 (page 105) of Sutton & Barto's "Reinforcement Learning: An Introduction", they discuss the off-policy Monte Carlo method for learning the value function of a target policy ...
- 248
1
vote
1
answer
237
views
In off-policy MC learning, why is the probability of sampling a trajectory the same as having a return?
In Sutton and Barto's RL book, in the section for off-policy learning, we would like to find the expected value of the random variable $G_t$, given $S_t = s$ under our target policy: $$\mathbb{E}_{\pi}...
- 13
3
votes
0
answers
60
views
How does off-policy monte carlo explore and converge? [duplicate]
Premises to question:
Behavior Policy: e-greedy (stochastic)
Target Policy: greedy (deterministic)
Importance Sampling Included
In off-policy Monte-Carlo control, the behavior policy chooses actions ...
- 31
2
votes
1
answer
77
views
Comparing Reinforcement Learning models
I am currently completing my thesis on optimising combinatorial problems, and we decided to utilize reinforcement learning. The problem is that I am not sure which algorithm to choose. Is there a ...
- 31
1
vote
2
answers
65
views
Given a set of trajectories produced by a fixed policy, what is the the standard approach to estimate Q?
Let's say that I have a set of trajectories $\mathcal{D} = \{\tau_1, \dots, \tau_n\}$ produced by an agent acting in a (episodic) MDP with a fixed policy $\pi$. I would like to estimate the $Q$ ...
- 183
0
votes
1
answer
217
views
Action-value estimation of deterministic policies with Monte Carlo method
In Monte Carlo-based action value estimation problem for a deterministic policy (estimation of $q_{\pi}(s,a)$),the estimation problem seems not to be well-defined because $q_{\pi}(s,a)$ by ...
- 199
2
votes
1
answer
662
views
How to code an $\epsilon$-soft policy for on-policy Monte Carlo control?
I was trying to code the on-policy Monte Carlo control method. The initial policy chosen needs to be an $\epsilon$-soft policy.
Can someone tell me how to code an $\epsilon$-soft policy?
I know how to ...
- 23
2
votes
1
answer
352
views
How does the learning rate $\alpha$ vary in stationary and non-stationary environments?
In Sutton and Barto's book (Chapter 6: TD learning, 2nd edition), he mentions two ways of updating value function:
Monte Carlo method: $V(S_t) \leftarrow V(S_t) + \alpha[G_t - V(S_t)]$.
TD(0) method: ...
- 379
1
vote
1
answer
90
views
In the cross-entropy method, should I select state-action pairs by their immediate reward or by the episode reward?
I am trying to understand the code mechanics when selecting the elite states and elite actions. It appears clear to me that they are those that appear in the episodes with the rewards bigger than the ...
- 221
2
votes
0
answers
112
views
Doubt in Sutton & Barto's off-policy Monte Carlo control algorithm
The algorithm is described as below:
My understanding: In the third last step, we act greedily w.r.t $Q$. Since we use importance sampling, this $Q \approx Q_\pi$. However, in the next step, whenever ...
- 379
1
vote
0
answers
82
views
What is the sample complexity of Monte Carlo Exploring Starts in RL?
We can use a model-free Monte Carlo approach to solving an MDP $(S,A,R,P,\gamma)$ with transition dynamics $P$ unknown by estimating Q-values by rolling out trajectories starting from random states $...
- 225
0
votes
1
answer
167
views
GLIE MC control (reinforcement learning): how the policy affects evaluation?
In his lecture 5 of the course "Reinforcement Learning", David Silver introduced GLIE Monte-Carlo Control.
I understand that we do policy evaluation for one step and then policy improvement....
- 101
2
votes
2
answers
290
views
In off-policy MC control algorithm by Sutton & Barto, why do we perform a last update when sample action is inconsistent with target policy?
I have a question about the $W$ term in the off-policy MC control algorithm on Page 111 of Sutton & Barto. I have also included it in the figure below.
My question: shouldn't the check $A_{t} = \...
- 123
1
vote
1
answer
91
views
When showing that the policy improvement theorem applies to MC control, why is $q_{\pi_{k}}\left(s, \pi_{k}(s)\right) \geq v_{\pi_{k}}(s)$ true?
When discussing why the policy improvement theorem is true, when we do Monte Carlo control by updating greedily, it says on page 98 of Sutton and Barto's book (2nd edition) that:
$$
\begin{aligned}
...
- 225
0
votes
0
answers
251
views
Comparison between TD(0) and MC ( or GAE )?
I'm getting started with DRL and have trouble distinguishing TD(0), MC, and GAE; and which scenarios one's better than others. Here is what I understand so far:
TD(0): increment learning, can learn ...
- 3
2
votes
2
answers
314
views
With Monte Carlo off-policy learning what do we correct by using importance sampling?
I do not understand the link of importance sampling to Monte Carlo off-policy learning.
We estimate a value using sampling on whole episodes, and we take these values to construct the target policy.
...
- 221
6
votes
1
answer
615
views
In MCTS, what to do if I do not want to simulate till the end of the game?
I'm trying to implement MCTS with UCT for a board game and I'm kinda stuck. The state space is quite large (3e15), and I'd like to compute a good move in less than 2 seconds. I already have MCTS ...
- 63
1
vote
1
answer
1k
views
How exactly is Monte Carlo counterfactual regret minimization with external sampling implemented?
I have read many papers, such as this or this, explaining how external sampling works, but I still don't understand how the algorithm works.
I understand you divide $Q$, which is the set of all ...
- 11
0
votes
1
answer
403
views
What are the popular approaches to estimating the Q-function?
I need the q-value for my RL training, there are some approaches:
Brute-force the action sequence (this won't work for long sequence)
Use a classic algorithm to optimise and estimate (this ain't much ...
- 1,293
3
votes
0
answers
516
views
How can I use Monte Carlo Dropout in a pre-trained CNN model?
In Monte Carlo Dropout (MCD), I know that I should enable dropout during training and testing, then get multiple predictions for the same input $x$ by performing multiple forward passes with $x$, then,...
- 31
6
votes
1
answer
1k
views
Why do we need importance sampling?
I was studying the off-policy policy improvement method. Then I encountered importance sampling. I completely understood the mathematics behind the calculation, but I am wondering what is the ...
1
vote
1
answer
230
views
When updating the state-action value in the Monte Carlo method, is the return the same for each state-action pair?
Referring to this post, in the following formula to update the state-action value
$$ Q(s,a) = Q(s,a) + \alpha (G − Q(s,a)),$$
is the value of $G$ (the return) the same for every state-action $(s,a)$ ...
- 221
2
votes
1
answer
669
views
Unclear definition of a "leaf" and diverging UTC values in the Monte Carlo Tree Search
I have two questions regarding the Selection and Expansion steps in the Monte Carlo Tree Search Algorithm. In order to state the questions, I recall the algorithm that I believe is the one most ...
- 123
0
votes
0
answers
492
views
Is my pseudocode titled "Monte Carlo Exploring Starts (with model)" correct?
Reinforcement Learning: An Introduction second edition, Richard S. Sutton and Andrew G. Barto:
We made two unlikely assumptions above in order to easily obtain this guarantee of
convergence for the ...
0
votes
1
answer
130
views
When we have multiple traces, do we average over traces or the total number of times we have visited that state?
I am confused about the workings of the first- and every-visit MC.
My first question is, when we have multiple traces, do we average over traces or the total number of times we have visited that state?...
0
votes
0
answers
514
views
Suppose every-visit MC was used instead of first-visit MC on blackjack. Would you expect the results to be different?
This is a question from page 94 of Sutton and Barto's RL book 2020.
I read in someone's compiled GitHub answers to this book's exercises their answer was: "No because each state in an episode of ...
- 805
3
votes
1
answer
218
views
Is the expected value we sample in TD-learning action-value Q or state-value V?
Both MC and TD are model-free and they both follow a sample trajectory (in the case of TD, the trajectory is cut-short) to estimate the return (we basically are sampling Q values). Other than that, ...
- 155
1
vote
1
answer
464
views
Why does Monte Carlo policy evaluation relies on action-value function rather than state-value function?
Here is David Silver's lecture on that. Look at 9:30 to 10:30.
He says that, since it is model-free learning, the environment's dynamics are unknown, so the action-value function $Q$ is used.
But ...
- 155
4
votes
2
answers
320
views
Why is the target called "target" in Monte Carlo and TD learning if it is not the true target?
I was going through Sutton's book and, using sample-based learning for estimating the expectations, we have this formula
$$
\text{new estimate} = \text{old estimate} + \alpha(\text{target} - \text{old ...
- 125
6
votes
1
answer
540
views
Why does TD Learning require Markovian domains?
One of my friends and I were discussing the differences between Dynamic Programming, Monte-Carlo, and Temporal Difference (TD) Learning as policy evaluation methods - and we agreed on the fact that ...
- 1,161
4
votes
1
answer
493
views
Why are state-values alone not sufficient in determining a policy (without a model)?
"If a model is not available, then it is particularly useful to estimate action values (the
values of state-action pairs) rather than state values. With a model, state values alone are
sufficient ...
- 1,161
4
votes
1
answer
159
views
What does the term $|\mathcal{A}(s)|$ mean in the $\epsilon$-greedy policy?
I've been looking online for a while for a source that explains these computations but I can't find anywhere what does the $|A(s)|$ mean. I guess $A$ is the action set but I'm not sure about that ...
- 95
1
vote
0
answers
182
views
Monte Carlo Exploring Starts broke for 2048 game AI
I implemented a MCES for 2048 (the game), with a quality function implemented as a neural net of a single layer.
The starts are created with 6 cells filled with values between 64 and 1024, two cells ...
- 227
1
vote
1
answer
52
views
If the transition model is available, why would we use sample-based algorithms?
Sample-based algorithms, like Monte Carlo Algorithms and TD-Learning, are often presented as useful since they do not require a transition model.
Assuming I do have access to a transition model, are ...
- 2,990
1
vote
0
answers
90
views
Should the importance sampling ratio be updated at the end of the for loop in the off-policy Monte Carlo control algorithm?
I'm studying RL with Sutton and Barto's book. I'd like to ask about the order of execution of a statement in the algorithm below.
Here, $W$ (importance sampling ratio) is updated at the end of the <...
- 11
2
votes
1
answer
114
views
Into which subcategories can reinforcement learning be divided?
In the course of a scientific work, I will discuss the different types of reinforcement learning. However, I have difficulties to find these different types.
So, into which subcategories can ...
- 23
1
vote
0
answers
115
views
Why do bootstrapping methods produce nonstationary targets more than non-bootstrapping methods?
The following quote is taken from the beginning of the chapter on "Approximate Solution Methods" (p. 198) in "Reinforcement Learning" by Sutton & Barto (2018):
reinforcement ...
- 121
2
votes
1
answer
2k
views
What is the bias-variance trade-off in reinforcement learning?
I am watching DeepMind's video lecture series on reinforcement learning, and when I was watching the video of model-free RL, the instructor said the Monte Carlo methods have less bias than temporal-...
- 33
6
votes
2
answers
638
views
How can we compute the ratio between the distributions if we don't know one of the distributions?
Here is my understanding of importance sampling. If we have two distributions $p(x)$ and $q(x)$, where we have a way of sampling from $p(x)$ but not from $q(x)$, but we want to compute the expectation ...
- 343
3
votes
1
answer
531
views
How is the incremental update rule derived from the weighted importance sampling in off-policy Monte Carlo control?
Here's the approximated value using weighted importance sampling
$$
V_{n} \doteq \frac{\sum_{k=1}^{n-1} W_{k} G_{k}}{\sum_{k=1}^{n-1} W_{k}}, \quad n \geq 2
$$
Here's the incremental update rule for ...
3
votes
1
answer
1k
views
In what RL algorithm category is MiniMax?
Q-learning is a temporal-difference method and Monte Carlo tree search is a Monte Carlo method. In what category is MiniMax?
- 623
3
votes
0
answers
48
views
Why do we update $W$ with $\frac{1}{\mu (A_t | S_t)}$ instead of $\frac{\pi (A_t | S_t)}{\mu (A_t | S_t)}$ in off-policy Monte Carlo control?
I had the same question when I am reading the RL textbook from Sutton Bartol as posted here.
Why do we update $W$ with $\frac{1}{\mu (A_t | S_t)}$ instead of $\frac{\pi (A_t | S_t)}{\mu (A_t | S_t)}$?...
- 53
1
vote
0
answers
138
views
When does Monte Carlo linear function approximation converge?
In this Stanford lecture (minute 35:47 and 37:00), the professor says that Monte Carlo (MC) linear function approximation does not always converge, and she gives an example. In general, when does MC ...
- 882
1
vote
1
answer
463
views
Monte Carlo epsilon-greedy Policy Iteration: monotonic improvement for all cases or for the expected value?
I was going through university slides and this particular slide is trying to prove that in a Monte Carlo Policy Iteration algorithm using an epsilon-greedy policy, the state Values (V-Values) are ...
- 562