Pokemon Individual Recourse A new blog post from minimallysufficient.com applies the machine learning concept of individual recourse to Pokemon battles, showing how to determine which stats to increase to beat a specific boss. The post builds on a previous neural network model that predicts battle outcomes based on stats, and uses the open-source Pokemon Showdown engine to generate 90,000 simulated battles across 730 Pokemon. The author frames the approach within the recourse literature, citing Ustun 2019 and Wachter 2018, and demonstrates how optimization methods vary based on problem structure. We’ve previously trained https://minimallysufficient.com/posts/neural-bradley-terry a neural network to predict which Pokemon will win a battle based on their stats. The motivation was tracking a Pokemon’s evolution: vanilla Bradley-Terry https://minimallysufficient.com/posts/non-transitive-bradley-terry models would invalidate themselves but our model based on stats would still generalize well. Thus as a Pokemon levels up and evolves we can see how its probability of defeating an opponent rises. This raises the natural question: what if we wanted to interfere with evolution and direct that development? In particular we might ask: which stats should we increase to have a reasonable chance of beating a particular boss? For the normal leveling-up process we can just read the stats for each level and iterate until we achieve the requisite probability. In the directed case we need to be more clever as there’s many options we can choose. There is a topic from the ML fairness literature that is helpful here: individual recourse . Individual Recourse individual-recourse The original paper as far as I can tell to introduce the idea of recourse is Ustun 2019 https://arxiv.org/abs/1809.06514 Actionable Recourse in Linear Classification . Their objective is: \ \min {r} \; \mathrm{cost} r \quad \text{subject to} \quad \hat{f} x + r = t \ That’s basically all you need to know. There’s a rather large literature 1 but they all fundamentally are variations on this theme. This is somewhat obscured as many of the subsequent papers such as Wachter 2018 https://arxiv.org/abs/1711.00399 switch to a variant of the unconstrained/penalized version \ \min {r} \; \mathrm{cost} r + \lambda \, \hat{f} x + r - t ^{2} \ This reformulation is a practical choice as it’s convenient to optimize. And of course it has a solution even when the original is infeasible. But ultimately it’s doing the same thing as \ \lambda \rightarrow \infty\ on satisfiable problems. Thus we can summarize some of the literature as such: | Paper | Objective | Optimizer | |---|---|---| | Wachter 2018 https://arxiv.org/abs/1711.00399 REVISE Joshi 2019 https://arxiv.org/pdf/1907.09615 Dandl 2020 https://arxiv.org/abs/2004.11165 DICE Mothilal 2020 https://arxiv.org/abs/1905.07697 We see that many of these papers simply modify the formula, adding some additional constraint targeting one of the -ities : sparsity 2, plausibility, diversity, or causality. This view helps make sense of the literature because the optimization algorithms are obscuring the nature of improvement. All of these choices between integer programming or gradient descent or spicier approaches like mixed optimization are more like implementation details. They fit the appropriate problem structure: like if you have neural networks gradients are cheap and easy while if everything is discrete then integer programming is the right way to go. We’ll indeed see this in our examples below. Building out the data and model building-out-the-data-and-model Last time we used a Kaggle dataset https://www.kaggle.com/datasets/terminus7/pokemon-challenge of simulated battles. That’s enough for predicting, but here we want to act on the model’s advice and then check whether the advice was any good. So we need a battle engine we can query such as the open-source Pokemon Showdown https://github.com/smogon/pokemon-showdown engine. For fights we’ll use the simulator’s built-in RandomPlayerAI . This is noisy as expected and could be improved but that’s a whole other blog post. We pit 730 pokemon against each other in 90000 battles creating a similar dataset as before. On top of this data we retrain exactly the model from the previous post: https://minimallysufficient.com/posts/neural-bradley-terry a strength network plus an antisymmetric interaction term, \ P a \text{ beats } b = \sigma\ \big \mathrm{strength} x a - \mathrm{strength} x b + \mathrm{SASNN} x a, x b \big , \ where each \ x\ is the six stats and a one-hot encoding of the primary type. Now that we have our data and our model let’s start investigating recourse Recourse for Pokemon recourse-for-pokemon We’ll build up to four different versions of the cost: | Version | What \ r\ may touch | \ \mathrm{cost} r \ | Optimizer | |---|---|---|---| | Unconstrained | any base stat, continuously | none just need feasibility | Gradient descent | | Cost-aware | any base stat, continuously | \ \lVert r\rVert 2^2\ | Gradient descent | | Diverse DICE | any base stat, continuously | + a diversity reward | Gradient descent | | Realistic | the trainer’s levers EV/IV/nat/L | money | DFS branch-and-bound | The unconstrained, cost-aware, and diverse versions share the same underlying optimization just with escalating costs. They work on the base statistics themselves which is a little unrealistic. To fix that we instead optimize on the set of levers actually available to a trainer and cost them according to the money required to buy the items causing those levers. Note that as we change the form of the problem we need to switch the optimization strategy: gradient descent works for the first two but the discrete nature of the realistic cost leads us to a depth-first search approach. For our recourse target, let’s pick Magikarp, arguably the weakest Pokemon, and pit it against Mewtwo: one of the stronger pokemon. The model gives it essentially no chance in the baseline configuration; let’s figure out what we need to do to get Magikarp to a 50-50. Unconstrained Recourse unconstrained-recourse We’ll treat the six stats as free continuous variables and fix the type can’t change that . Let’s start by figuring out how we can get a single feasible point before starting to worry about the costs. It’s actually rather easy: just projected gradient ascent on the predicted probability. The projection is there to keep us from going either negative or above a max value. function unconstrained recourse attacker, defender; t=0.5, lr=0.05, n steps=6000, on step=nothing xa = feat attacker xd = feat defender Δ = zeros Float32, N FEATURES fhat d = only predict full model, xa .+ d, xd p = fhat Δ on step === nothing || on step 0, Δ, p callback for tracing p = t && return Δ for it in 1:n steps recourse may not be possible; hence finite steps prev = copy Δ g = Zygote.gradient fhat, Δ 1 Δ 1:N STATS .+= lr . g 1:N STATS only update the things that are not fixed Δ 1:N STATS .= clamp. Δ 1:N STATS , -xa 1:N STATS , 1 .- xa 1:N STATS between 0 and 1 normalized p = fhat Δ on step === nothing || on step it, Δ, p if p = t crossed the line: bisect back to it lo = prev hi = Δ for in 1:40 mid = lo .+ hi ./ 2 fhat mid = t ? hi = mid : lo = mid end return hi end end return Δ end We get the following recourse: | Stat | Base | Change | Target | |---|---|---|---| | HP | 20 | +148 | 168 | | ATK | 10 | +57 | 67 | | DEF | 55 | +47 | 102 | | SPA | 15 | +25 | 40 | | SPD | 20 | +90 | 110 | | SPE | 80 | +28 | 108 | | P win | 0.001 | 0.5 | Thus we find that we have to increase our statistics by a huge amount over 8x-ing HP and 5x-ing SPD to survive the fight. Attack is not that emphasized which is interesting: this is more of a turtle strategy. It’s also informative to look at the path our optimization took: We started a long way away from the target and it was basically flat for almost all of the time until finally cresting at the finish. We needed the gradient information from the model to do this: if we had to increase the stats manually and actually compete to find out if progress had been made this would have taken forever. Cost Aware Recourse cost-aware-recourse So we know there’s at least a feasible solution; let’s now consider cost. We’ll use the usual L2 norm penalty: \ \min {r} \; \lVert r\rVert^2 + \lambda\, \hat{f} x+r - t ^2 \ when \ \lambda\ is large we pin the solution on the boundary and then the \ \lVert r\rVert^2\ component keeps the norm small. This preferentially chooses recourse which moves all of the stats a little rather than one stat a lot assuming both hit feasibility . function min norm recourse attacker, defender; t=0.5, λ=1000, lr=0.02, n steps=8000, clip=0.02 xa = feat attacker xd = feat defender fhat d = only predict full model, xa .+ d, xd loss d = sum abs2, d 1:N STATS + λ fhat d - t ^2 Δ = zeros Float32, N FEATURES for in 1:n steps g = lr . Zygote.gradient loss, Δ 1 1:N STATS m = maximum abs, g m clip && g . = clip / m Δ 1:N STATS .-= g Δ 1:N STATS .= clamp. Δ 1:N STATS , -xa 1:N STATS , 1 .- xa 1:N STATS end project exactly onto f̂ = t to be comparable with unconstrained for in 1:50 err = fhat Δ - t abs err < 1f-4 && break gg = Zygote.gradient fhat, Δ 1 1:N STATS Δ 1:N STATS .-= err / sum abs2, gg + 1f-8 . gg Δ 1:N STATS .= clamp. Δ 1:N STATS , -xa 1:N STATS , 1 .- xa 1:N STATS end return Δ end | Stat | Base | Change | Target | |---|---|---|---| | HP | 20 | +134 | 154 | | ATK | 10 | +52 | 62 | | DEF | 55 | +58 | 113 | | SPA | 15 | +20 | 35 | | SPD | 20 | +98 | 118 | | SPE | 80 | +36 | 116 | | P win | 0.001 | 0.5 | | | ‖r‖₂ vs ascent | 0.924 | 0.917 | Interestingly there’s not a ton of difference from unconstrained and the cost is roughly the same though a little smaller . Diverse recourse diverse-recourse Of course if you don’t want to go that particular route you’re a bit at a loss. It would be nice if we instead gave you a couple options: you could then opt for the build that matches your own preferred play style. Of course if we do this optimization a couple times we’ll get the same result. We could add a stochastic component but even then we’re likely to wind up in the same basin 3. No, to get diverse solutions we’ll need to optimize for it directly. We’ll start with k potential recourses and then maximize a pairwise distance \ \max {r 1,\dots,r K}\; \sum {k