Questions Tagged With samplinghttp://www.or-exchange.com/tags/sampling/?type=rssquestions tagged <span class="tag">sampling</span>enSun, 17 Jan 2016 08:50:31 -0500Creating an "exploration vs. exploitation balance" instancehttp://www.or-exchange.com/questions/13240/creating-an-exploration-vs-exploitation-balance-instance<p>Hello everyone, </p>
<p>I am evaluating two sampling procedures for the multi-armed bandit problem. I was able to plot the allocation patterns for each of them for an artificial case where I know in advance the distributions of the arms; hence, I know which arm has the best mean. The allocation pattern is the number of samples allocated to each arm as a function of time, averaged over many replications. For each allocation pattern, I obtained the corresponding probability of correct selection curve (PCS), again averaged over many replications.</p>
<p>Studying the PCS convergence rates, method 1 has a fast rate at the beginning, but slows down afterwards. This is in comparison to method 2, which has a slower rate at the beginning, but speeds up afterwards eventually achieving a PCS = 1 much faster than method 1.</p>
<p>I hypothesized that method 1 allocates more samples than "it should" to the top arms at the beginning, and neglects the others, leading to poor estimates of the inferior arms' parameters, and eventually forcing method 1 to go back and sample the inferior ones more. I did so of course after looking at the allocation patterns of methods 1 and 2, where it is clear that method 2 "invests" more samples in the inferior arms at the beginning, leading to dropping them a bit later, but when it does, it does not go back to them. </p>
<p>All of this is based on observed performance, and is just a hypothesis as we do not know what is the "optimal" allocation pattern, or at which point should we stop exploring inferior arms, and exploit the good one(s). Base on this, I have two questions:</p>
<ol>
<li>Can we create an artificial scenario where we know what the optimal allocation pattern is so we can compare to it?</li>
<li>Is it possible to fit a regression model of the PCS vs. the number of samples each arm gets at each point in time? This might be way off as the independent variables here are constrained to have a constant sum at each point in time, and are highly correlated.</li>
</ol>
<p>Please let me know if you have any thoughts, or if you like to see the results to better understand what is happening.</p>
<p>Regards, </p>anahanaSun, 17 Jan 2016 08:50:31 -0500http://www.or-exchange.com/questions/13240/creating-an-exploration-vs-exploitation-balance-instanceallocationgroup-rankingsamplingHelp with importance sampling over HUGE sample spacehttp://www.or-exchange.com/questions/10427/help-with-importance-sampling-over-huge-sample-space<p><del>Apologies for the awful typesetting, but MathJax doesn't appear to be working, as described on the FAQ.</del> [fixed; see comment below -- <a href="/users/25/fbahr"><a href="/users/25/fbahr">@fbahr</a></a>]</p>
<p>My underlying problem is fairly simple, but the sheer size is what is causing issues. I would like to use importance sampling, but am unsure about its implementation. </p>
<p>Problem statement:</p>
<p>We have \( \text{N} \) vectors \( \mathbf{x_i} \in \mathbb{(R^+)}^{k}\) an a \( \leq\) constraint for each dimension of \( \mathbb{(R^+)}^{k}\).</p>
<p>I would like to examine all possible on-trivial subsets \(S\) of the vectors \(\mathbf{x_i}\) (there are $2^N-1$ of these) and determine, for each vector \(\mathbf{x_i}:\;\; i \in \{1...N\}\), the fraction of all subsets that satisfy the following constraints:</p>
<p>Let \(T := \{1...N\}\), \(\Omega := 2^T\setminus \emptyset\), and \(L_i>0 \;\;i \in \{1...N\}\)</p>
<p>Let \( C_i:= S \subset \Omega \) such that:</p>
<p>\( \mathbf{x_i} \in S \)</p>
<p>\( \exists ~j \in \{1...N\}: {\sum\limits_{\mathbf{x_z} \in S} ( \mathbf{x_z} )_j > L_j} \quad \text{and}~ {\sum \limits_{\mathbf{x_z} \in S \setminus \mathbf{x_i}} (\mathbf{x_z})_{j} \leq {L_j}} \)</p>
<p>My goal is to estimate \(\frac{|C_i|}{2^N-1}\) for each \(i \in \{i...N\}\)</p>
<p>Basically, sets that meet these conditions are ones whose vector sum falls outside the "box" defined by the \(L_i\) constraints, yet when the \(i^{th}\) member is removed, it falls inside the box.</p>
<p>I figured that importance sampling will help get an estimate withing a reasonable amount of time, where I preferentially select subset sizes that are more likely to meet the above constraints.</p>
<p>I would like input on how to formulate the importance sampling distribution over the subsets. My initial thought is to fit a discrete beta distribution to the vector of "reciprocal maximal exceedance ratios", which is \( \min \{\frac{L_k}{(x_j)_k},1\} \) calculated for each vector. This will approximate the distribution of required subset sizes to exceed the box constraint.</p>eupraxisMon, 13 Oct 2014 12:01:16 -0400http://www.or-exchange.com/questions/10427/help-with-importance-sampling-over-huge-sample-spacesamplingstatisticsestimationsimulationStochastic programming: sampling the VSShttp://www.or-exchange.com/questions/8011/stochastic-programming-sampling-the-vss<p>For two-stage integer stochastic problems with recourse, the Value of the Stochastic Solution is defined as:</p>
<p>VSS = EEV - RP</p>
<p>EEV = fix 1st stage, solve subproblems, take probability based weighted average (solved by N MIPs with N = number of scenarios )</p>
<p>RP = recourse problem (solved with e.g. L-shaped)</p>
<p>My question is:
"Is the VSS still valid when both EEV and RP are solved by sampling techniques?"</p>
<p>I did not find any references on this issue.</p>cvhueleWed, 15 May 2013 08:17:13 -0400http://www.or-exchange.com/questions/8011/stochastic-programming-sampling-the-vssvssstochastic-optimizationsampling