Tour de Heuristics: Joint Equilibrium Search (JESP)
The final stop on this heuristics tour, and the last stop for our overview of Cooperative Decision Making is Joint Equilibrium Search. This technique starts with some pre-set horizon T policies for each agent, and then cycles through each agent so that it may tweak its behaviors to maximize the response with all other policies held fixed. It continues this cycle until all trees have stabilized.
def joint_equilibrium_search(policy): curr_policy = policy do: prev_policy = curr_policy for agent in get_all_agents() : calculate_expected_values(curr_policy) curr_policy[agent] = get_best_response(curr_policy, agent) while prev_policy != curr_policy return curr_policy
Well, That’s Nifty
It seems like a slam dunk, but there are a few gotchas. From an optimality standpoint, it is only locally optimal. In order to try and mitigate this, there needs to be some sort of algorithm before this that helps select somewhat optimal trees before coming in.