Let's say we have the following relationship between $f_1$ and $f_2$:

$$f_2(s) = \sqrt{1 + f_1(s)}$$

And $f_1$ returns a positive value. Why is it that minimax search using $f_2$ is guaranteed to the same action as using $f_1$ but is not guaranteed to return the same action as $f_1$ when used in expectimax search?

I understand that expectimax takes into account the weight of the arcs to compute the possible path. But I am still not able to understand how the aforementioned conclusion is being made.


An example for Expectimax (root node is a Max node):


(image from CSE AI Faculty / Dan Klein, Stuart Russell, Andrew Moore)

changing the evaluation function changes the action taken.

For Minimax, since $f_1(s_i) \ge f_1(s_j) \implies f_2(s_i) \ge f_2(s_j)$, the best node (action taken) doesn't change (Minimax is insensitive to monotonic transformations):

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.