Backward Induction

Put simply, backward induction is the process of reasoning backwards in time, from the culmination of a problem or situation to the very first move, to better formulate an optimal strategy.

Dynamic programming uses backward induction as a main method for solving the Bellman equation. In game theory, backward induction is mainly used to compute subgame perfect equilibira in sequential game.

Resources

Backward induction – Wikipedia

2021-12-28

Threshold Rule: Rolling a Die
- A rudimentary application of the #Threshold Rule is when rolling a die. A general rule of thumb for solving optimal stopping problems is thinking backwards or using backward induction.¹ A standard die with a maximum roll of 6 assuming there are equal chances of rolling any face of the die at any given roll, let \(k\) equals to the remaining retry. At zero remaining reroll, we set up the base case which has an average value of a die roll of 3.5 \(((1+2+3+4+5+6)/6)\), an average of all value of the die since any value would be better than nothing since its the last roll.
  1. Algorithms to Live By by Brian Christian and Tom Griffiths - Optimal Stopping
    ↩︎
Zettel Posts
Computer Science
Book Notes

🧠 Index 🧠#