# Tag Info

1

Algorithm 1, which I refer to in the question, produces a strategy that minimizes cumulative counterfactual regret. The motivation is to get a strategy which minimizes overall regret (as defined earlier in the paper). That's because such a strategy approximates a nash equilibrium strategy. In other words, cumulative counterfactual regret was designed to be: ...

1

Hint:

2

Let $A_n\subseteq \{0,1\}^{\log n}$ denote the set of binary strings of length $\log n$ with at least $c\log n$ trailing zeros on the right (here I assume that $\log n$ in an integer and $0\le c\le 1$). Note that $|A_n|=2^{\log n -\lceil c\log n\rceil}\le 2^{(1-c)\log n}$. Since $H:\{0,1\}^{\log n}\rightarrow \{0,1\}^{\log n}$ is a one to one function, $\Pr_{... 1 You need$\Omega(2^n)$samples in order to accomplish your task. Consider an algorithm that gets$m$samples from$D$and then another sample, either from$D$or from$U$, and has to guess which it is. Its input thus consists of$m+1$samples$X_1,\ldots,X_m,Y$. We will generate the distribution$D$at random by choosing a random set$V \subseteq \{0,1\}^n$... 0 You can't. Your intuition is wrong. I will give an explicit counter-example. Actually, I'll give you two: two for the price of one. Suppose$n=1$, the distribution$D$always outputs 1, and$U$is uniform on$\{0,1\}$. The following algorithm is an optimal distinguisher: Never use the black box. If the input$z$is 0, guess that it came from$U$, ... 1 Total variation distance, which is exactly half of your notion of distance, is equal to $$d_{TV}(D,U) = \frac{1}{2} \operatorname{Distance}(D,U) = \max_A \bigl|\Pr_{x \sim D}[A(x)] - \Pr_{x \sim U}[A(x)] \bigr|.$$ You can take$A$to be the indicator of$\Pr[D(x)] \geq \Pr[U(x)]$. The event$A$might be hard to compute, but it could also be easy to compute.... 1 The notation$\|x_n - \mu\|^2$stands for the squared$L_2$norm of the vector$x_n - \mu$. The squared$L_2$norm of the$d$-dimensional vector$v = \begin{pmatrix} v_1 & \cdots & v_d \end{pmatrix}$is $$\|v\|^2 = v_1^2 + \cdots + v_d^2.$$ In particular, when$d = 1$, we have$\|v\|^2 = v_1^2$. The formula you state works for the Gaussian ... 2 Here is the key. Let$A \otimes B$be the distribution corresponding to a sample from$A$and an independent sample from$B$, and denote total variation distance by$d_{TV}$. Then $$d_{TV}(A_1 \otimes A_2, B_1 \otimes B_2) \leq d_{TV}(A_1,B_1) + d_{TV}(A_2,B_2)$$ We can see this using the$L_1$formula for$d_{TV}\$: \begin{align} d_{TV}(A_1\otimes A_2,B_1\...

Top 50 recent answers are included