AIToolbox
A library that offers tools for AI problem solving.
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

◆ Result

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
AThe action space of the agents.
factorThe factor to consider for the score.
jointActionThe 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
AThe action space of the agents.
factorsThe factors to consider for the score.
jointActionThe 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
AThe action space of the agents.
graphThe graph to compute the score on.
jointActionThe 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
AThe action space of the agents.
graphThe 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
AThe action space of the agents.
graphThe graph to perform local search on.
startActionThe 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: