From a5ddd5181b959ff1d0599bf2334ab5061d28fc53 Mon Sep 17 00:00:00 2001
From: David Tolpin <david.tolpin@gmail.com>
Date: Mon, 12 Sep 2011 10:47:27 +0300
Subject: [PATCH] added letters

---
 paper/voisam/letter-a.txt | 13 +++++++++++++
 paper/voisam/letter-b.txt | 32 ++++++++++++++++++++++++++++++++
 2 files changed, 45 insertions(+)
 create mode 100644 paper/voisam/letter-a.txt
 create mode 100644 paper/voisam/letter-b.txt

diff --git a/paper/voisam/letter-a.txt b/paper/voisam/letter-a.txt
new file mode 100644
index 0000000..1c51923
--- /dev/null
+++ b/paper/voisam/letter-a.txt
@@ -0,0 +1,13 @@
+Hi Eyal,
+
+just sharing thoughts:
+
+I don't quite understand how to achieve natural PAC (that is, Pr(VOI>X)<p) bounds for VOI. Since VOI is based on probabilities, the `outer' probabilities can be intergrated into the VOI estimate, so the estimate/bound is still a single number. I'll think about that.
+
+The *upper* bound on VOI can be obtained (as I mentioned) from the Hoeffding inequality based *solely on the means*. The lower bound based solely on the means cannot be better than 0.
+
+The *lower* bound on VOI can be improved (that is, a non-trivial lower bound can be found) based on the sample distribution. If a certain arm has samples which are better than the current best, then, again, probability inequalities (like Hoeffding/Bernstein) can be used to state that VO(P)I is `at least' such and such. Thus arms who have lower variance (less samples on the other side of the best) will have smaller lower bound on VO(P)I.
+
+A next issue is ordering arms based on lower/upper bound. And proving things about algorithm performance.
+
+David
diff --git a/paper/voisam/letter-b.txt b/paper/voisam/letter-b.txt
new file mode 100644
index 0000000..7ad118b
--- /dev/null
+++ b/paper/voisam/letter-b.txt
@@ -0,0 +1,32 @@
+Hello Eyal,
+
+[a lower bound on VOI cannot be obtained unless a distribution is assumed.]
+
+GOOD NEWS: A tighter upper bound can be obtained if the sample variance is available along with the sample mean, using McDiarmid's (Bennet's, Bernstein's) inequalities, with some modifications, known in the literature.
+
+The `classical' Bernstein's inequality states:
+
+Pr(avg(X)-E[X]>t)<exp(-nt^2/(Var[X] + t/3)) (1)
+
+that is, the probability that the sample mean deviates from the expected value grows with variance, and for small variances the bound is tighter than the Chernoff bound.
+
+BUT, Var[x] is the `theoretical' variance rather than the sample variance. I found a paper (COLT 2009, http://arxiv.org/abs/0907.3740) that proves a similar inequality based on the sample variance SVar:
+
+Pr(avg(X)-E[X]>t)<2*exp(-nt^2/[SVar(X)+7nt/3(n-1)) (2)
+
+which can be used to bound the VOI when the sample variance is collected along with the sample mean.
+
+very roughly, the arms should be sorted (the smaller the better) by
+
+n*[avg(X_best)-avg(X)]^2/[SVar(X)+...]
+
+The trends are right: the closer avg(X) to avg(X_best) and the greater the sample variance, the better is the arm.
+
+I am going to write down the theoretical part formally now, with all the proper citations: we will have two upper bounds:
+
+- based on the sample mean only
+- based on the sample mean and sample variance estimate
+
+the second bound will work better in the cases when different arms have significantly different variances. Both estimates allow to specify the termination condition, since they decrease with number of pulls (samples) (exp(-An), where A is some constant).
+
+David
-- 
2.11.4.GIT