how to express the performance of a policy in policy parameters Suppose a leauge of tic-tac-toe playing agents. As the league proceeds, the bad players are kicked out, and better players come in. The problem resides on how to at least approximate the better player.

One way to think of is an evolutionary approach. By random mutation possibly followed by crossovers, you may expect that slowly the players will converge to the optimum.

But I want something more deterministic. Assuming the policy function of each agent is differentiable, there are many methods to speed up the optimization. I will use the term policy as a function that takes the current board as input and ouputs the best move to play. Whatever method I choose, they need the performance as input. One obvious performance metric is the winrate, which usually works fine to approximate the performance itself, but it doesn't contain any parameter from the policy function. To optimize the policy to maximize the performance, things work best when the performance can be expressed in the parameters defining the policy, so that I can take the gradient of the performance with respect to the policy parameters, and update the policy following the gradient; that is, gradient ascent.

So back to the title, what is a good way to express the performance of a policy in policy parameters?
I suggest you study reinforcement learning, and possibly Q-learning.  They are aimed at dealing with this kind of situation. 

The short answer is that we almost never have a way to give a closed-form formula that measures how good a policy is, as a function of the policy parameters.  Rather, we use simulations: we conduct a bunch of simulations using that policy, measure how well it performs in simulation, and use that our estimate of the quality of the policy.  Then we apply stochastic gradient descent or other optimization methods to find parameter values that maximize the quality of the policy.