# how to approximate a very complex optimal policy when the distance function is unknown

A policy $P$ is defined as a set of parameters. We want to know the optimal policy $O$, which certainly exists but unfortunately unknown.

$D(P)$ shows how far $P$ is from $O$. The function $D$ itself is unfortunately not known. However, $D(P) - D(Q)$ is known. That is, one can always know which among $P$ and $Q$ is closer to $O$.

What kind of approach can be done for such problem?

In my setting, a policy is in a form of a (convolutional) neural network. $D(P) - D(Q)$ is approximated by a simulation involving an agent with policy $P$ and an agent with policy $Q$. We repeatedly play a two-player game with a clear win/loss where $P$ plays against $Q$. The value of $D(P)-D(Q)$ is equal to the number of times $P$ wins against $Q$, divided by the number of games we play.

• OK, thanks, that helps! Check my edit to see if it accurately represents your situation. – D.W. Feb 2 '17 at 21:17

Let me start with some basic material that covers the case where you know how to compute $D(P)$; then speculate on some methods that might be applicable to your particular situation, where we only know how to compute $D(P)-D(Q)$.

Gradient descent. One reasonable approach is to use gradient descent to optimize the parameters. If we have an objective function $\Phi(P)$ that tells us the penalty or loss associated with policy $P$, we use gradient descent to try to find parameters $P$ that minimize $\Phi(P)$. This requires that $\Phi(\cdot)$ be continuous and differentiable. Ideally, we'd have a way to compute the partial derivatives (the gradient) of $\Phi$ at any point; but if we don't, one possibility is to use standard methods to approximate the partial derivative, e.g.,

$${\partial \over \partial x} \Phi(P) = {\Phi(P+\epsilon x) - \Phi(P-\epsilon x) \over 2 \epsilon}.$$

Stochastic gradient descent. In your situation, stochastic gradient descent is an important optimization that provides significant speedups. The basic idea is that, if we can decompose the objective function as a sum

$$\Phi(P) = \sum_i \Phi_i(P),$$

then we can speed up gradient descent. In each step, we evaluate the gradient of $\Phi_i$ (rather than of $\Phi$, as ordinary gradient descent would do) and take a small step in the direction given by that gradient. This can be a lot more efficient, if computing the gradient of $\Phi_i$ is more efficient than computing the gradient of $\Phi$.

In your situation, $\Phi(P)$ is defined to be

$$\Phi(P) = \sum_{i=1}^n {w_i(P) \over n},$$

where $w_i(P)$ is 1 if $P$ wins in the $i$th game and 0 otherwise. Therefore, $\Phi$ has the required form to allow you to apply stochastic gradient descent, and you can expect this method to give significant speedups. Effectively, you do only one game simulation per step of (stochastic) gradient descent rather than $n$ game simulations per step.

As a practical matter, there are many further improvements on stochastic gradient descent that are well-studied, including momentum, rmsprop, and many others. Personally, I'd recommend trying the Adam solver; it seems to be state of the art.

So if you knew how to compute $D(P)$, the above would give you a reasonable method for optimizing $P$: simply define $\Phi(P)=D(P)$ and then apply stochastic gradient descent. But you don't... so now we need a way to adjust.

Your situation. Your specific situation is more challenging, but there are still some avenues you could explore. For instance, here is one approach you could consider. Fix a reasonable policy $Q_0$, and define

$$\Phi(P) = D(P) - D(Q_0).$$

Apply stochastic gradient descent to try to minimize $\Phi(P)$, i.e., to find $P$ that makes $\Phi(P)$ small. Do that for a little while. Then, pick a new policy, call it $Q_1$, and define

$$\Phi(P) = D(P) - D(Q_1)$$

and continue iterating. Every so often, you replace $Q_i$ with a new (better) policy $Q_{i+1}$ that hopefully is closer to $O$. This might work.

How do you choose $Q_{i+1}$? One way would be to let $Q_{i+1}$ be the best policy seen so far. So, effectively, you are constantly trying to find a policy that beats the best policy seen so far. You'd need to tune how often you change $Q$ and play with some parameters.

Caveats. However, I suspect that if you're actually dealing with a two-player game, things won't be this simple. In particular, I suspect that your model of the situation is not accurate: that, for several reasons, the fraction of times that $P$ wins against $Q$ is not actually an estimator of $D(P)-D(Q)$.

• The relationship between "fraction of wins" vs $D(P)-D(Q)$ is probably not linear. For example, Magnus Carlsen (world chess champion; rated about 2800) will beat me 100% of the time in chess. He will presumably also beat Arnold Schwarzenegger (rated about 1500) 100% of the time. But Arnold will probably beat me 100% of the time, too, because I suck at chess. Letting $P_M =$ Magnus Carlsen, $P_A =$ Arnold Schwarzenegger, and $P_D =$ me, it can't be simultaneously true that $D(P_M)-D(P_D)=1$, $D(P_M)-D(P_A)=1$, and $D(P_A)-D(P_D)=1$, yet that is what your assumption implies.

• Strategies usually aren't totally ordered. Sometimes we have situations where one strategy is especially effective against another strategy (more than you'd expect based on their overall strength). For instance, we can have situations where Alice usually beats Bob, Bob usually beats Charles, and Charles usually beats Alice. Your framework doesn't take this into account.

You'll probably need more sophisticated methods to deal with these challenges. For instance, one possibility is to build a small collection of different baseline strategies $Q_1,Q_2,\dots,Q_k$. Then, evaluate $P$ according to how well it does against all of these: e.g., have $P$ play $n/k$ games against each $Q_i$, count the total number of wins for $P$, and divide by $n$.

This leaves open the question of how you select the baseline strategies $Q_1,\dots,Q_k$. You might want each $Q_i$ to be as strong as possible, but also want to have some diversity in the pool, so $Q_i,Q_j$ are as different as possible for all $i,j$. That requires a way to measure how similar two strategies $Q_i,Q_j$ are. One way might be to play a game between $P$ vs $Q_i$; at each board position reached, compare how often $Q_i$ would select the same move as $Q_j$. To select a collection of baseline strategies, you could try to solve an optimization problem where you select among the s policies you've explored so far, while maximizing some objective function that rewards selecting strong strategies but penalizes similarity between selected strategies.

There are probably many challenges here, but hopefully this gives you some ideas you can try out.