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.)

Filter by
Sorted by
Tagged with
1 vote
2 answers
51 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$ ...
user avatar
  • 163
0 votes
0 answers
14 views

Given a dataset with columns $x_1, x_2, \dots, x_n, y$, which algorithm can tell me which $x$ values had the biggest impact on $y$?

I have a set of data that is generated from a monolithic Monte Carlo-based program. I've set up a way to monitor the calculations of this program and output values correlating to those calculations, ...
user avatar
0 votes
1 answer
78 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 ...
user avatar
2 votes
1 answer
109 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 ...
user avatar
  • 23
2 votes
1 answer
38 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: ...
user avatar
0 votes
0 answers
18 views

In the original GAN paper, why is it claimed that variational inference is used in deep undirected models for inference?

In the original GAN paper (table 2), why is it claimed that variational inference is used in deep undirected models for inference? I was under the impression that they used Gibbs Sampling, MCMC-based ...
user avatar
1 vote
1 answer
45 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 ...
user avatar
2 votes
0 answers
43 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 ...
user avatar
1 vote
0 answers
27 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 $...
user avatar
  • 203
0 votes
1 answer
57 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....
user avatar
2 votes
1 answer
101 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} = \...
user avatar
1 vote
1 answer
54 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} ...
user avatar
  • 203
0 votes
0 answers
47 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 ...
user avatar
2 votes
2 answers
189 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. ...
user avatar
5 votes
1 answer
137 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 ...
user avatar
  • 53
1 vote
1 answer
310 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 ...
user avatar
0 votes
1 answer
110 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 ...
user avatar
  • 1,183
2 votes
0 answers
189 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,...
user avatar
  • 21
5 votes
1 answer
243 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 ...
user avatar
1 vote
1 answer
78 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)$ ...
user avatar
2 votes
1 answer
225 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 ...
user avatar
  • 123
0 votes
0 answers
187 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 ...
user avatar
0 votes
1 answer
74 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?...
user avatar
0 votes
0 answers
87 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 ...
user avatar
3 votes
1 answer
132 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, ...
user avatar
1 vote
1 answer
220 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 ...
user avatar
3 votes
2 answers
228 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 ...
user avatar
5 votes
1 answer
182 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 ...
user avatar
4 votes
1 answer
190 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 ...
user avatar
4 votes
1 answer
117 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 ...
user avatar
1 vote
0 answers
134 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 ...
user avatar
1 vote
1 answer
41 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 ...
user avatar
1 vote
0 answers
41 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 <...
user avatar
  • 11
2 votes
1 answer
99 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 ...
user avatar
1 vote
0 answers
63 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 ...
user avatar
  • 121
2 votes
1 answer
799 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-...
user avatar
5 votes
2 answers
374 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 ...
user avatar
  • 313
3 votes
1 answer
152 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 ...
user avatar
2 votes
1 answer
270 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?
user avatar
  • 573
3 votes
0 answers
46 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)}$?...
user avatar
  • 53
1 vote
0 answers
77 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 ...
user avatar
1 vote
1 answer
233 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 ...
user avatar
  • 522
1 vote
1 answer
67 views

Understanding the W term in off policy monte carlo learning

In Sutton and Barto's RL textbook they included the following pseudocode for off policy Monte Carlo learning. I am a little confused, however, because to me it looks like the W term will become ...
user avatar
2 votes
2 answers
1k views

How does Monte Carlo Exploring Starts work?

I'm having trouble understanding the 5th step in the flowchart. For the 5th step, the 'update the Q function by taking the average of returns' is confusing. From what I understand, the Q function ...
user avatar
  • 113
1 vote
1 answer
115 views

MCTS moves with multiple parents

I'd like to develop an MCTS-like (Monte Carlo Tree Search) algorithm for program induction, i.e. learning programs from examples. My initial plan is for nodes to represent programs and for the search ...
user avatar
2 votes
1 answer
314 views

How to apply hyperparameter optimization on Monte Carlo Tree Search?

I have a basic MCTS agent for the game of Hex (a turn based game). I want to tune the parameters of UCT (the Cp parameter) and the number of rollouts parameter. Where do I have to begin? The problem ...
user avatar
4 votes
1 answer
223 views

How does policy evaluation work for continuous state space model-free approaches?

How does policy evaluation work for continuous state space model-free approaches? Theoretically, a model-based approach for the discrete state and action space can be computed via dynamic programming ...
user avatar
  • 1,211
3 votes
1 answer
455 views

How does Monte Carlo have high variance?

I was going through David Silver's lecture on reinforcement learning (lecture 4). At 51:22 he says that Monte Carlo (MC) methods have high variance and zero bias. I understand the zero bias part. It ...
user avatar
2 votes
1 answer
172 views

What does the figure "Blackjack Value Function..." from Sutton represent?

I came across this graph in David Silver's youtube lecture and Sutton's book on reinforcement learning. Can anyone help me understand the graph? From the graph, for 10000 episodes what i see is ...
user avatar
6 votes
2 answers
3k views

What is the intuition behind TD($\lambda$)?

I'd like to better understand temporal-difference learning. In particular, I'm wondering if it is prudent to think about TD($\lambda$) as a type of "truncated" Monte Carlo learning?
user avatar
  • 115