1
$\begingroup$

What is the best practice in order to learn the optimal weight vector $W^*$? By optimal I mean the weights that will produce the agent with the highest win-rate.

I have an agent that plays a imperfect information game and I want to find the optimal weights via Reinforcement learning. Each turn, for each move $a$, the agent calculates a heuristic value, $h(a)$ that is a linear function of $n$ features. That is to say, the heuristic value for move $a$ is

$$h(a) = w_1f_1(a)+ w_2f_2(a)+...+w_nf_n(a)$$ where $\forall i, w_i \in[0,1]$

The Heuristic agent plays a distribution over the moves that is corelated to the value of the moves (moves with higher value have higher probability to be played)

  • This question might be very basic, I am new to RL.
  • Currently, the agent uses $n=13$ features.
  • I have access to daily data of $10^6$ games of agent vs human.
  • I have a game engine that allows me to run agent-vs-agent games.
  • The Heuristic agent is a bit weaker than average recreational humans (win rate of 49%).
  • The MCTS agent is a bit stronger than average human recreational (win rate of 58%).
  • I have no good reason to think that linear weights are optimal. Just thought it's an easier start.
  • The Reward is observed only at the round's end. There is no good way to evaluate the reward before the round's end.
Improve this question
$\endgroup$
14
  • 1
    $\begingroup$ It would help if there was a question-mark around the part you are asking. I see a sequence of statements, not a question. Help me out here. $\endgroup$
    – EngrStudent
    Jun 7, 2022 at 12:20
  • 1
    $\begingroup$ In a discrete game, like some versions of the knapsack problem, you have to touch every discrete state to be able to find the universal best. In this you are rounding your continuous variables, so discretization is allowed. This means that within a single "bin" the values are essentially the same, which implies there exists something like a slope. I would push in 2 ways: can you discretize more, and does gradient descent (aka slope-climbing) work. You aren't discretizing 2-way or 3-way (or 13-way) interactions. Extreme chunking: 2^13 = 8192, which is a cheap search. $\endgroup$
    – EngrStudent
    Jun 7, 2022 at 14:30
  • 1
    $\begingroup$ Consider the options shown here for gradient-free optimization: github.com/SimonBlanke/Gradient-Free-Optimizers $\endgroup$
    – EngrStudent
    Jun 7, 2022 at 14:34
  • 1
    $\begingroup$ Just to clarify, do you want to find $W$ with a reinforcement learning algorithm? Edit your post to clarify that and to further change the title to be specific. Use the tag algorithm-request, if you're looking for an algorithm. $\endgroup$
    – nbro
    Jun 7, 2022 at 20:09
  • 1
    $\begingroup$ One thing missing - what are the optimal weights for your problem? Is it the weights that have least error when predicting score, or weights that drive a policy to get the highest score? These require related but different approaches $\endgroup$
    – Neil Slater
    Jun 8, 2022 at 7:55

1 Answer 1

Reset to default
-1
$\begingroup$

My friend propose local random search:

Initialize:

  • $W_0 = (0.5,...,0.5)$
  • step = 0.1, $K < N$, MAX_ITERATIONS

Each iteration:

  1. $W_{new}$ <- $W$
  2. randomly choose up to $K$ weights, change each one step up/down.
  3. simulate 5000 games between the 2 agents: $W$ vs $W_{new}$
  4. if the win-rate of $W_{new}$ is higher than 50% then $W$ <- $ W_{new}$

Stop condition: if for 10 iterations $W_{new}$'s win rate < 50%$ or reach MAX_ITERATIONS.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ This is a very basic local random search algorithm. You tagged the question "reinforcement-learning" though, and the suggested algorithm is quite far from that. $\endgroup$
    – Neil Slater
    Jun 9, 2022 at 13:51
  • $\begingroup$ @NeilSlater, while local search is basic, I it so easy to implement that I will try it, then hill climbing. $\endgroup$
    – Cohensius
    Jun 9, 2022 at 21:36
  • 1
    $\begingroup$ Another popular option like LRS is a genetic algorithm. That's just randomly creating a lot of agents, testing them, keeping the best, then creating a new generation of agents from combinations of the best agents plus some random mutations. $\endgroup$
    – Lee Reeves
    Jun 9, 2022 at 22:10
  • 1
    $\begingroup$ And BTW, you might want to specify that the agent chooses the action with the best calculated score. I misunderstood and thought the score was something provided by the game that you were trying to estimate, which was confusing. $\endgroup$
    – Lee Reeves
    Jun 9, 2022 at 22:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .