2
$\begingroup$

Game wordle got fame in January 2022 on Twitter (now knows as X).

Rules are pretty simple.

  • Player has to guess a word of length 5
  • Player can make at most 6 guesses
  • If player guesses the correct word or when 6 guesses are exhausted, game ends.
  • Once player guesses any word, he/she gains information regarding the actual word using colors. If a character is placed at correct position, it is denoted by green color. If a character is in the actual word but at a different position, then it is denoted by yellow color.

I want to describe this as a reinforcement learning problem. My question is: Can we describe this as a multi armed bandit problem ?

Edit-1: I have found these two research papers which address wordle as reinforcement learning problem. None of them has talked about seeing wordle as a bandit problem.

  1. D Bertsimas et al.
  2. S Bhambri et al.
$\endgroup$

1 Answer 1

2
$\begingroup$

Is it possible to describe wordle as a multi armed bandit problem?

Yes, although the data management to present the current choice would involve constructing a state much like a reinforcement learning (RL) version of the same problem.

An agent that attempted to solve Wordle with a multi-armed bandit approach would likely be less efficient than the RL version, since the reinforcement learning version would be able to select an answer with a lower immediate chance of winning, but that gave more information and thus a higher chance of solving. You can intuitively see that is the case since a bandit version would learn to equally select any one of the few thousand possible start words (assuming they are equally likely to be chosen by the problem setter) for a 1-in-2390 probability of winning, whilst it is a proven strategy that some start words are more informative when they fail. Bandit algorithms however do not consider "next state".

A multi-armed bandit version would be a contextual bandit, with the input state being known letter information from previous attempts - e.g. an array of 26 x 5 x 2 with the known results of placing each letter in each position so far. The output could be the possible class values - e.g. all allowed words, one-hot encoded. Other structures are possible. You could also make the agent's life slightly easier by ruling out words logically - although that's 90% of the work so there's not much learning to do at that point. A bandit's best strategy assuming the target word was chosen randomly, is simply to choose from available valid words completely at random*.

The reinforcement learning version could use identical structures, but in its Q table it would be able to learn about the advantages to reducing the space of valid words through careful choice in early guesses.

An optimal play of Wordle assuming random pick of target word is also entirely possible using a logical look-ahead search. By choosing test words that are guaranteed to split the remaining valid words into the smallest groups (probabilistically) depending on the results, you can dramatically reduce the search space in only a few steps. This resolves to minimising the mean square size of each group (the frequency of ending up in the group times the remaining size). You could probably write this optimal search just as easily as writing a bandit or RL agent to solve the problem. However, that only makes sense if you want an optimal agent by any means - if you want to use Wordle as a way to try out RL or bandit algorithms, then there is no need to write this "expert" agent.


* You could use reward shaping to reward the bandit for reducing the remaining candidate words. At that point you have almost implemented the full reinforcement learning version by proxy though.

$\endgroup$

You must log in to answer this question.

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