AIToolbox::Factored::Bandit::LocalSearch Class Reference

This class approximately finds the best joint action using Local Search. More...

#include <AIToolbox/Factored/Bandit/Algorithms/Utils/LocalSearch.hpp>

Public Types
using	Result = std::tuple< Action, double >
using	Graph = FactorGraph< Vector >

Public Member Functions
	LocalSearch ()
	Basic constructor. More...
Result	operator() (const Action &A, const Graph &graph)
	This function performs the actual local search process. More...
Result	operator() (const Action &A, const Graph &graph, Action startAction)
	This function performs the actual local search process. More...

Static Public Member Functions
static double	evaluateGraph (const Action &A, const Graph &graph, const Action &jointAction)
	This function evaluates the full score of a given joint action. More...
static double	evaluateFactors (const Action &A, const Graph::FactorItList &factors, const Action &jointAction)
	This function evaluates the score for a subset of factors in a Graph. More...
static double	evaluateFactor (const Action &A, const Graph::FactorNode &factor, const Action &jointAction)
	This function evaluates the score for a single factor in a Graph. More...

Detailed Description

This class approximately finds the best joint action using Local Search.

The Local Search algorithm is a simple routine that maximizes each agent in turn, selecting its local action that maximizes the overall reward.

We iteratively go over all agents (each time in random order to avoid adversarial inputs), optimizing each one in turn, until no optimizations can be done. In this way we are guaranteed to find a local optima, but there is no guarantee that Local Search will be able to find the global optima, which is why this is an approximate method.

On the other hand, this method is quite fast, as each individual optimization is simple and quick to do.

Member Typedef Documentation

Graph

using AIToolbox::Factored::Bandit::LocalSearch::Graph = FactorGraph<Vector>

Result

using AIToolbox::Factored::Bandit::LocalSearch::Result = std::tuple<Action, double>

Constructor & Destructor Documentation

LocalSearch()

AIToolbox::Factored::Bandit::LocalSearch::LocalSearch

(

)

Basic constructor.

Member Function Documentation

evaluateFactor()

static double AIToolbox::Factored::Bandit::LocalSearch::evaluateFactor ( const Action &  A, const Graph::FactorNode &  factor, const Action &  jointAction  )

static

This function evaluates the score for a single factor in a Graph.

Parameters

A	The action space of the agents.
factor	The factor to consider for the score.
jointAction	The current full joint action.

Returns

The score of the joint action within the input factor.

evaluateFactors()

static double AIToolbox::Factored::Bandit::LocalSearch::evaluateFactors ( const Action &  A, const Graph::FactorItList &  factors, const Action &  jointAction  )

static

This function evaluates the score for a subset of factors in a Graph.

Since we only optimize a single agent at a time, there is no reason to re-evaluate the whole graph at each optimization step. This function evaluates only the factors that are needed in the Graph, given the current joint action.

Parameters

A	The action space of the agents.
factors	The factors to consider for the score.
jointAction	The current full joint action.

Returns

The score of the joint action within the input factors.

evaluateGraph()

static double AIToolbox::Factored::Bandit::LocalSearch::evaluateGraph ( const Action &  A, const Graph &  graph, const Action &  jointAction  )

static

This function evaluates the full score of a given joint action.

Parameters

A	The action space of the agents.
graph	The graph to compute the score on.
jointAction	The current full joint action.

Returns

The score of the joint action.

operator()() [1/2]

Result AIToolbox::Factored::Bandit::LocalSearch::operator()	(	const Action &	A,
		const Graph &	graph
	)

This function performs the actual local search process.

This function optimizes over a single randomly sampled initial action.

See also

operator(const Action &, Graph &, Action)

Parameters

A	The action space of the agents.
graph	The graph to perform local search on.

Returns

The pair for best Action and its value given the internal graph.

operator()() [2/2]

Result AIToolbox::Factored::Bandit::LocalSearch::operator()	(	const Action &	A,
		const Graph &	graph,
		Action	startAction
	)

This function performs the actual local search process.

We randomly iterate over each agent. Each agent is set to take the action that maximizes the value of the full joint action. We repeat this process until no agent can modify its action to improve the final value.

Note that this process is approximate, as it can converge to a local optimum.

This function optimizes over the input joint action.

Parameters

A	The action space of the agents.
graph	The graph to perform local search on.
startAction	The initial action to optimize.

Returns

The pair for best Action and its value given the internal graph.

---

The documentation for this class was generated from the following file:

• include/AIToolbox/Factored/Bandit/Algorithms/Utils/LocalSearch.hpp