0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Your best bet to find something you want would be to start at some Reinforcement Learning reference, especially since tic-tac-toe agents should be fairly commonplace among introductory RL stuff. A reference I recommend is Reinforcement Learning: An Introduction

For more advanced/general references to learn policies for a variety of problems, I recommend the following:

  1. Volume I & II of Dynamic Programming and Optimal Control
  2. Approximate Dynamic Programming: Solving the Curses of Dimensionality
  3. Neuro-Dynamic Programming

Creating/learning policies can be a challenging area for real world problems, but very exciting when things work out. Good luck!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.