Is the minimax algorithm model-based?

Question

Trying to get my head around model-free and model-based algorithms in RL. In my research, I've seen the search trees created via the minimax algorithm. I presume these trees can only be created with a model-based agent that knows the full environment/rules of the game (if it's a game)? If not, could you explain to me why?

Answer 1

Minimax is a planning algorithm, and all planning algorithms need access to a model of the environment in order to look ahead or simulate possible future states and results.

Technically this does not need to be 100% accurate or complete. It could even be a learned model. However, in the case of applying minimax to classic two player games, such as chess or Connect 4, then usually the game rules are used to create perfect predictions.

This difference between planning and learning is not quite the same as model-free vs model-based RL, but the ideas do overlap considerably. You can for instance consider the experience replay approach used in DQN as a form of "background planning" where the model used is the memory of previous events, whilst the core Q-learning algorithm used inside DQN is normally considered model-free.