Answers.Body: <p>My friend propose <a href="https://en.wikipedia.org/wiki/Local_search_(optimization)" rel="nofollow noreferrer">local random search</a>:</p>
  <p>Initialize:</p>
  <ul>
  <li><span class="math-container">$W_0 = (0.5,...,0.5)$</span></li>
  <li>step = 0.1, <span class="math-container">$K &lt; N$</span>, MAX_ITERATIONS</li>
  </ul>
  <p>Each iteration:</p>
  <ol>
  <li><span class="math-container">$W_{new}$</span> &lt;- <span class="math-container">$W$</span></li>
  <li>randomly choose up to <span class="math-container">$K$</span> weights, change each one step up/down.</li>
  <li>simulate 5000 games between the 2 agents: <span class="math-container">$W$</span> vs <span class="math-container">$W_{new}$</span></li>
  <li>if the win-rate of <span class="math-container">$W_{new}$</span> is higher than 50% then <span class="math-container">$W$</span> &lt;- <span class="math-container">$ W_{new}$</span></li>
  </ol>
  <p>Stop condition: if for 10 iterations <span class="math-container">$W_{new}$</span>'s win rate &lt; 50%$ or reach <em>MAX_ITERATIONS</em>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-09T13:51:18.993Z
Answers.Text: 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.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-09T21:36:34.173Z
Answers.Text: @NeilSlater, while local search is basic, I it so easy to implement that I will try it, then hill climbing.
Answers.UserDisplayName: Cohensius
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-09T22:10:32.970Z
Answers.Text: 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.
Answers.UserDisplayName: Lee Reeves
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-09T22:16:33.597Z
Answers.Text: 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.
Answers.UserDisplayName: Lee Reeves
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-06-09T09:19:43.533Z
Answers.LastActivityDate: 2022-06-09T21:29:07.180Z
Answers.LastEditDate: 2022-06-09T21:29:07.180Z
Answers.UserDisplayName: Cohensius
Body: <p><strong>What is the best practice in order to learn the optimal weight vector <span class="math-container">$W^*$</span>?</strong>  By optimal I mean the weights that will produce the agent with the highest win-rate.</p>
  <p>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 <span class="math-container">$a$</span>, the agent calculates a <em>heuristic</em> value, <span class="math-container">$h(a)$</span> that is a linear function of <span class="math-container">$n$</span> features.  That is to say, the heuristic value for move <span class="math-container">$a$</span> is</p>
  <p><span class="math-container">$$h(a) = w_1f_1(a)+ w_2f_2(a)+...+w_nf_n(a)$$</span>
  where <span class="math-container">$\forall i, w_i \in[0,1]$</span></p>
  <p>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)</p>
  <ul>
  <li>This question might be very basic, I am new to RL.</li>
  <li>Currently, the agent uses <span class="math-container">$n=13$</span> features.</li>
  <li>I have access to daily data of <span class="math-container">$10^6$</span> games of agent vs human.</li>
  <li>I have a game engine that allows me to run agent-vs-agent games.</li>
  <li>The <strong>Heuristic</strong> agent is a bit weaker than average recreational
  humans (win rate of 49%).</li>
  <li>The <strong>MCTS</strong> agent is a bit stronger than average human recreational (win rate of 58%).</li>
  <li>I have no good reason to think that linear weights are optimal.  Just thought it's an easier start.</li>
  <li>The <strong>Reward</strong> is observed only at the round's end.  There is no good way to evaluate the reward before the round's end.</li>
  </ul>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-07T12:20:17.810Z
Comments.Text: 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.
Comments.UserDisplayName: EngrStudent
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-07T13:07:14.423Z
Comments.Text: Very broad question.  Not sure I understand where 10^36 comes from.  Are the feature weights continuous or discrete?
Comments.UserDisplayName: EngrStudent
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-07T14:15:26.373Z
Comments.Text: @EngrStudent, you right, fixed my mistake.   weights are continuous w_i \in [0,1]   The space 10^26 come from my assumption that I will discretize the space and let each weight to be a number between 0 and 1 in jumps of 0.01, thus each weight has 101 options.  Therefore, 100^13 features is equal to 10^26
Comments.UserDisplayName: Cohensius
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-07T14:30:18.040Z
Comments.Text: 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.
Comments.UserDisplayName: EngrStudent
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-07T14:34:32.190Z
Comments.Text: Consider the options shown here for gradient-free optimization: https://github.com/SimonBlanke/Gradient-Free-Optimizers
Comments.UserDisplayName: EngrStudent
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-07T20:09:05.507Z
Comments.Text: 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 [tag:algorithm-request], if you're looking for an algorithm.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-08T07:55:34.797Z
Comments.Text: 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
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-08T14:06:16.227Z
Comments.Text: @NeilSlater, the optimal weights will produce the highest win rate.  Either vs humans or vs a baseline agent.
Comments.UserDisplayName: Cohensius
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-09T13:56:45.573Z
Comments.Text: I think one reason you are not getting many answers is there is more than one thing you need to do to get to a practical self-play game-playing algorithm. Doubly so if the `reinforcement-learning` tag needs to be applied. Dealing with them all would make for a long answer, thus a lot of work for someone considering writing one.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-09T17:37:27.613Z
Comments.Text: @NeilSlater, I think that I don't know even what I don't know.  Could you explain what are those things? Currently, I have a game-playing algorithm and I have access to a game engine that can run many agent-vs-agent games.
Comments.UserDisplayName: Cohensius
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-09T18:44:05.847Z
Comments.Text: In brief, search, heuristics used with search, self-play, and for reinforcement learning how to structure  the reward, and the dozen or so RL algorithms that could be employed in your case. Also choosing between linear models with feature engineering vs non-linear models.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-09T21:18:01.800Z
Comments.Text: Thanks @NeilSlater!  I think that I know part of the material but lucking some fundamentals.  First I made a fair heuristic ~49% win-rate vs humans.  Second step was implementing MCTS (Monte Carlo Tree Search) which produce ~58% win-rate.  Now I want to further improve the the agent.  So I want to use local search or some RL-algorithm in order to find the optimal weights.  For a start I want to find the optimal linear weights.  I think that the reward structure is just win-rate vs a base-line opponent.
Comments.UserDisplayName: Cohensius
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-06-09T21:35:21.703Z
Comments.Text: @NeilSlater, can you reference some of the simple RL-algorithms that might find strong linear/non linear weights?
Comments.UserDisplayName: Cohensius
Tags: <reinforcement-learning><game-ai><algorithm-request>
Title: Which RL algorithm should I use to learn an optimal weight vector?
UserDisplayName: Cohensius
ThreadText: # Which RL algorithm should I use to learn an optimal weight vector?
  
  (Asked by: username_0 on 2022-06-07)
  
  **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.
  
  **Tags:** reinforcement-learning, game-ai, algorithm-request
  
  > **Comments:**
  > **username_1**: 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.  
  > **username_1**: Very broad question.  Not sure I understand where 10^36 comes from.  Are the feature weights continuous or discrete?  
  > **username_0**: @username_1, you right, fixed my mistake.   weights are continuous w_i \in [0,1]   The space 10^26 come from my assumption that I will discretize the space and let each weight to be a number between 0 and 1 in jumps of 0.01, thus each weight has 101 options.  Therefore, 100^13 features is equal to 10^26  
  > **username_1**: 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.  
  > **username_1**: Consider the options shown here for gradient-free optimization: https://github.com/SimonBlanke/Gradient-Free-Optimizers  
  > **username_2**: 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 [tag:algorithm-request], if you're looking for an algorithm.  
  > **username_3**: 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  
  > **username_0**: @username_3, the optimal weights will produce the highest win rate.  Either vs humans or vs a baseline agent.  
  > **username_3**: I think one reason you are not getting many answers is there is more than one thing you need to do to get to a practical self-play game-playing algorithm. Doubly so if the `reinforcement-learning` tag needs to be applied. Dealing with them all would make for a long answer, thus a lot of work for someone considering writing one.  
  > **username_0**: @username_3, I think that I don't know even what I don't know.  Could you explain what are those things? Currently, I have a game-playing algorithm and I have access to a game engine that can run many agent-vs-agent games.  
  > **username_3**: In brief, search, heuristics used with search, self-play, and for reinforcement learning how to structure  the reward, and the dozen or so RL algorithms that could be employed in your case. Also choosing between linear models with feature engineering vs non-linear models.  
  > **username_0**: Thanks @username_3!  I think that I know part of the material but lucking some fundamentals.  First I made a fair heuristic ~49% win-rate vs humans.  Second step was implementing MCTS (Monte Carlo Tree Search) which produce ~58% win-rate.  Now I want to further improve the the agent.  So I want to use local search or some RL-algorithm in order to find the optimal weights.  For a start I want to find the optimal linear weights.  I think that the reward structure is just win-rate vs a base-line opponent.  
  > **username_0**: @username_3, can you reference some of the simple RL-algorithms that might find strong linear/non linear weights?  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2022-06-09. Score: -1
  
  My friend propose [local random search](https://en.wikipedia.org/wiki/Local_search_(optimization)):
  
  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*.
  
  > **Comments:**
  > **username_3**: 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.  
  > **username_0**: @username_3, while local search is basic, I it so easy to implement that I will try it, then hill climbing.  
  > **username_4**: 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.  
  > **username_4**: 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.  
  
  ---
  
  