JP7248108B2 - Optimization device, optimization method and optimization program - Google Patents

Description

The present invention relates to an optimization device, optimization method, and optimization program for efficiently solving the bandit problem.

Linear optimization in the bandit problem (hereinafter referred to as bandit linear optimization) is an important problem that is widely used in many fields. Specifically, the bandit linear optimization repeats the trials described below.

At the start of a trial, the player is given a d-dimensional (trial) action vector set A⊆R ^d and T rounds of trials. At each round tε[T]:={1, 2, . . . , T}, the player chooses an action at _εA . Then, under an unknown loss vector l _t that can change from round to round, the player observes the loss l _t ^Ta _t .

A special application of bandit linear optimization is to deal with various online decision-making problems. For example, given a graph G=(V, E) and s, tεV, set A⊆R ^|E| to be the set of all feature vectors of paths between st. This allows us to view the problem as bandit shortest path, or adaptive routing. In this setup, l _t εR ^|E| corresponds to the (unknown) length of the path, and bandit feedback l _t ^T a _t denotes the length of the path between selected st.

Besides the above applications, bandit linear optimization includes, for example, combinatorial optimization problems such as minimum spanning tree, minimum cut, and knapsack problems, and bandit versions of continuous optimization problems such as linear programming and semidefinite programming. .

A player's performance is evaluated by regret R _T (a ^* ) (where a ^* εA) as defined in Equation 1 below. Equation 1 represents the difference between the cumulative loss for a player's decision {a _t } and the cumulative loss for any fixed strategy a ^* . The first priority of bandit linear optimization is to obtain a small regret for any a ^* .

Various methods are known for efficiently solving the bandit problem. For example, Non-Patent Document 1 describes a method for efficiently solving probabilistic and adversarial multi-armed bandit problems in order to obtain regret bounds on the order O ^∼ (T ^1/2 ). In the method described in Non-Patent Document 1, in a probabilistic setting under semi-bandit feedback, a problem-specific lower regret bound is derived and its scaling is treated in the dimension of the decision space. Note that O ^~ is the superscript tilde of O, and when we write O ^~ we ignore polynomial factors in d and log(T).

Also, algorithms of order O ^∼ (T ^1/2 ) are known to tolerate regrets of at least Ω(T ^1/2 ) in the worst case. This means that algorithms with regret bounds of order O ^∼ (T ^1/2 ) achieve optimal performance depending on T.

Non-Patent Document 2 describes the theory of linear programming and integer programming. Non-Patent Document 3 describes an algorithm for online linear optimization in opaque feedback, and Non-Patent Document 4 describes an efficient algorithm for sampling from an n-dimensional logarithmic distribution. there is

Richard Combes, et al., “Combinatorial Bandits Revisited”, In Advances in Neural Information Processing Systems, pp.2116-2124, 2015. A.Schrijver, “Theory of linear and integer programming”, John Wiley & Sons, 1998. B. Awerbuch, R. D. Kleinberg, "Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches", Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, pp.45-53. ACM, 2004. L. Lovasz, S. Vempala, "The geometry of logconcave functions and sampling algorithms", Random Structures & Algorithms, 30(3), pp.307-358, 2007.

However, as in the method described in Non-Patent Document 1, when the action vector set A is exponentially large or infinite, there is a computational problem. In other words, when the number of actions that can be selected by the player is exponentially large, even if the method described in Non-Patent Document 1 is attempted to be implemented using computer functions, there is the problem that it cannot be solved in a realistic amount of time. . Therefore, in order to improve the functions of computers, there is a demand for a method that can efficiently solve the bandit problem so that the regret limit that can be obtained can be made smaller.

SUMMARY OF THE INVENTION Accordingly, an object of the present invention is to provide an optimization device, an optimization method, and an optimization program capable of optimizing the bandit problem so that it can be solved efficiently.

An optimization device according to the present invention is an optimization device for optimizing a bandit problem, and includes a convex set setting unit for setting a convex set including an action set that is a set of candidate action vectors; a separation problem solver for solving a separation problem to derive a hyperplane that separates any contained vector from the convex set, and updating the convex set to a smaller convex set based on the derived hyperplane; A parameter selection unit that selects a value within the number of dimensions of a vector and a parameter indicating a positive or negative value; A decomposition problem solver that solves the decomposition problem by decomposing it into dimensional points, an action execution unit that executes the point as an action with the probability of the weight of the decomposed point, and a loss obtained by the executed action. and an estimator calculating unit for calculating an estimator of the loss vector.

The optimization method according to the present invention is an optimization method for optimizing the bandit problem, in which a computer sets a convex set including an action set, which is a set of candidate action vectors; Solve the separation problem to derive a hyperplane that separates any vector contained in the convex set from and a parameter indicating a positive or negative value within the selected number of dimensions, and the computer converts each of the elements into the number of dimensions of the action vector for the elements and convex sets determined by the values and parameters within the selected number of dimensions , the computer executes the point as an action with the probability of the weight of the decomposed point, and the computer calculates the loss based on the loss obtained by the executed action. It is characterized by calculating an estimator of a vector.

An optimization program according to the present invention is an optimization program applied to a computer for optimizing a bandit problem, wherein a convex set including an action set, which is a set of candidate action vectors, is set in the computer. Processing, solving the separation problem to derive a hyperplane that separates any vector contained in the predetermined range from the convex set, and updating the convex set to a smaller convex set based on the derived hyperplane. Separation problem solving processing, parameter selection processing for selecting a value within the number of dimensions of the action vector and a parameter indicating a positive or negative value, an element determined by the value within the selected number of dimensions and the parameter, and a convex set of the elements Decomposition problem solving processing that solves the decomposition problem that decomposes each into points of the number of dimensions of the action vector, action execution processing that executes the point as an action with the probability of the weight of the decomposed point, and the executed action It is characterized by executing an estimator calculation process for calculating an estimator of the loss vector based on the obtained loss.

According to the present invention, the bandit problem can be optimized for efficient solution.

1 is a block diagram showing a configuration example of a first embodiment of an optimization device according to the present invention; FIG. 4 is a flow chart showing an operation example of the optimization device of the first embodiment; FIG. 3 is a block diagram showing a configuration example of a second embodiment of an optimization device according to the present invention; It is a flow chart which shows an example of an optimization device of a second embodiment of operation. 1 is a block diagram showing an overview of an optimization device according to the invention; FIG. 1 is a schematic block diagram showing a configuration of a computer according to at least one embodiment; FIG.

BEST MODE FOR CARRYING OUT THE INVENTION Hereinafter, embodiments of the present invention will be described with reference to the drawings. In the first embodiment, we aim to achieve a regret bound of order O(T ^1/2 ) under the assumption that we can call it a linear optimization oracle. Oracles correspond to conceptual devices that can solve linear optimization problems for A off-line. That is, given a loss vector lεR ^d , the oracle outputs a ^* as shown in Equation 2 below.

Note that this assumption (ie, the oracle call) is known in the context of online optimization and is the minimum requirement for developing an efficient Bandit's algorithm that obtains sublinear remorse. In fact, given an efficient sublinear regret bandit algorithm, we can construct an efficient algorithm for offline problems. This means that if the offline problem is computationally hard (eg, NP-hard), then the bandit problem is also hard.

In many applications, efficient computation of the bandit algorithm relies heavily on the "oracle complexity". Here, "oracle complexity" is the number of calls to the linear optimization oracle. This trend is especially pronounced when the computational time to solve the offline linear optimization problem (ie, the time to get the answer from Oracle) is large enough to dominate other computational times. Therefore, in the present embodiment, an algorithm for efficiently solving the bandit problem by reducing the "oracle complexity" will be described.

In addition, in the first embodiment, due to the stochastic setting described later, regret of order O ^~ ((d ³ T) ^1/2 ) is achieved with high probability, and order O(poly(d We describe an algorithm with an oracle complexity of )logT).

First, the following theorem is defined. In the following description, informal theorems are also simply referred to as theorems.

<Theorem 1>
Assume l _t follows a distribution on R ^d at t=1, 2, . . . ,T. At this time, the algorithm shown below exists.
(1) The output of the algorithm satisfies R _T (a ^* )=O ^˜ ((d ³ T) ^1/2 ) with high probability for all a ^* εA.
(2) The algorithm calls the linear optimization oracle an order of O(poly(d)logT) times.
(3) Computation time, except for linear optimization oracles, is of the order of O(poly(d,T)).

Commonly known O ^∼ (T ^1/2 ) repentance algorithms require at least Ω(T) oracle complexity. Also, the algorithm shown in the first embodiment is an algorithm with a regret bound of O ^∼ (T ^1/2 ), which is quasi-linear in T, and an oracle complexity.

Furthermore, in the second embodiment, for the non-stochastic setting described below, we achieve regrets of the expected order O ^~ ((d ³ T) ^1/2 ), and achieve regrets of the order O(poly( d) Describe an algorithm with an oracle complexity of T). Therefore, the following theorems are defined.

<Theorem 2>
The following algorithms exist.
(1) The output of the algorithm satisfies E[R _T (a ^* )]= ^O˜ ((d ³ T) ^1/2 ) for all a ^* εA.
(2) The algorithm calls the linear optimization oracle an order of O(poly(d)T) times.
(3) Computation time, except for linear optimization oracles, is of the order of O(poly(d,T)).

Embodiment 1.
First, the optimization device of the first embodiment will be explained. The point in the first embodiment is to combine the gradual elimination of actions and the center of gravity spanner. Algorithms based on gradual elimination involve the process of dividing the decision-making round into phases (segments of the round). Also, at the end of each phase, possible actions are eliminated, leaving only promising actions.

In algorithms with gradual elimination, all _at selected in each phase are determined at the beginning of the phase. This means that the oracle complexity does not depend on the number of rounds, but on the number of phases. In the algorithm shown in the first embodiment, the number of phases is on the order of O(poly(d)logT), and the efficient algorithm for centroid spanners reduces the number of oracle calls in each phase to O( poly(d)). This results in an overall oracle complexity of order O(poly(d)logT).

The first embodiment also assumes a stochastic setting in the bandit linear optimization. The stochastic setting assumes that the loss vectors l _t are independent of each other and follow the same probability distribution D on W⊆R ^d in rounds t = 1, 2, ..., T. The performance of the algorithm is evaluated by the expected value of regret R _T (a ^* ) in Equation 1 above with respect to the randomness of the loss vector l _t and the internal randomness of the algorithm.

The setting of the bandit linear optimization problem will be described again below.

Before the game starts, the player has T rounds of trials, a d-dimensional action vector set A (sometimes referred to as an action set) A ⊆ R ^d , and an action vector _at (hereinafter simply action a _t .) An upper bound L>0 on the norm of εK and an upper bound R>0 on the norm of the loss vector l _t εW are given.

At each round t=1, 2, . . . , T, the player chooses an action at _εK . On the other hand, the loss l _t vector is selected by the environment, and the player observes the loss l _t ^Ta _t . Also, players can only access the linear optimization oracle _OA . In other words, it can be said that the optimization device of this embodiment controls the process of calling the device that implements the linear optimization Oracle _OA . Note that the device that implements the linear optimization oracle _OA may be implemented by the same device as the optimization device of this embodiment, or may be implemented by a different device.

The player's goal is to obtain a smaller regret R _T (a) (in other words, to maximize the reward over a period of time). Here, regret R _T (a) is calculated by Equation 3 exemplified below for any a∈K,

We also assume that the action set A is a compact subset of ^Rd . Suppose then that there exists an algorithm (oracle) to linearly optimize in A for the weight vectors in wεR ^d . Then, suppose that any input w can be given to a linear optimization oracle _OA :R ^d →A, which oracle finds points _OA (w)εA that satisfy Equation 4, exemplified below. Output.

Here we make some assumptions. First, assume that there are positive real numbers L and R that satisfy the following (a) to (b).
(a) ||l _t ||≦L for all tε[T].
(b) ||a|| ₂ ≤ R for all aεA. again,
(c) K:=Conv(A) has positive volume. That is, ∫ _K 1dx>0.

The assumptions for (a) and (b) above are common in bandit linear optimization. Also, given a linear optimization oracle on A, we can assume (c) above without loss of generality. In fact, if A is contained in a subspace of dimension less than d, it can be detected by invoking a linear optimization oracle in polynomial time, and ignoring redundant dimensions reduces K to the full can be dimensioned.

In addition, we define the size or bit length of a rational number, as shown below.

<Definition 1>
If p and q are relative prime numbers, the size of the rational number r=p/q is defined by Equation 5 exemplified below.

Also, for a rational vector x ⁼ (x ₁ , _.

Also, if the subset P is the convex hull of finite rational vectors, P is a rational polytope (hyperpolyhedron). Similarly, if P is a non-empty compact set expressed in terms of a finite set of linear inequalities expressed in terms of rational numbers, i.e., P={xεR ^d |Ax≦b}, then _P ^is _{a rational polytope} ^_ is. In this embodiment, the size size ((A, b)) of the rational inequality (A, b) is defined by Equation 7 exemplified below.

Note that for a finite set A of rational numbers such that each x ∈ A has size at most φ, if P is expressed as P=Conv(A), then P has size at most poly(d, φ) can be expressed by the linear inequality ^Also , given xεR ^d such that ||x|| can be done.

Next, a linear optimization problem LP (linear optimization problem), a separation problem SP (separation problem), and a decomposition problem DP (decomposition problem) in a compact convex P⊆R ^d are defined as follows. These are the problems that can be solved with a linear optimization oracle.

<Linear optimization problem: LP>
Given a vector ^{wεRd ,} find a vector x ^* εP such that ^{wTx *} =min _xεPwTx .

<Separation problem: SP>
Given a vector yεR ^d , determine whether y belongs to P, and if y does not belong to P, then w ^T y<min _xεP w ^T x Find the vector wεR ^d .

<Decomposition problem: DP>
Given a vector xεR ^d , find the vertices x ₀ ,...,x _d and λ ₀ ,...,λ _d ≧0 of P such that x=λ ₀ x ₀ +...+λ _d x _d do.

The well-known ellipsoid method, which alleviates the handling of the above three problems, shows the following relationship.
LP: Resolvable ⇔ QP: Resolvable ⇒ DP: Resolvable.

In Non-Patent Document 2, the following Theorem 3(a), Theorem 3( ^b ) and Theorem 3(c ) is described.

Theorem 3(a): If we have an algorithm SEP that solves the separation problem, we can solve the linear optimization problem for w∈Q ^d by calling SEP at most poly(d, φ, size(w)) times .
Theorem 3(b): If there exists an algorithm OPT that solves a linear optimization problem, we can solve the separation problem for y∈Q ^d by calling OPT at most poly(d, φ, size(y)) times. .
Theorem 3(c): If there exists an algorithm OPT that solves a linear optimization problem, we can solve the decomposition problem for x∈Q ^d by calling OPT at most poly(d, φ, size(x)) times. .

Next, definitions and theorems regarding the center of gravity spanner are given.

<Definition 2>
Let SεR ^d be the subset whose linear span is R ^d and let C>1. Now, if every xεS can be expressed as a linear combination of elements of X with coefficients in the range [−C,C], then the set X={x ₁ , . . . , x _d }⊆S is C-centroid spanner with respect to S;
Theorem 4: Let P⊆R ^d be a compact set not contained in a proper linear subspace. Given an algorithm OPT for LP for any C>1, compute the C-centroid spanner for P in polynomial time by making calls to OPT in order O(d ² log _C (d)) It is possible (see Non-Patent Document 3).

Next, the logarithmically concave distribution algorithm is described. If a probability distribution on a convex set KεR ^d has a probability density function p:K→R _>0 such that logp is a convex function, the probability distribution is called a log-concave distribution. Theorem 5 below implies that given a value oracle of a convex function f:K→R, a sample can be approximated from a log-concave distribution p(x)∝exp(−f(x)).

Theorem 5: Let P be convex with non-zero Lebesgue measure. Also, let f:P→R be a convex function and p be a logarithmically concave distribution proportional to exp(−f(x)). Furthermore, ε>0. Given access to P's membership oracle and f's value oracle, there exist algorithms that sample approximately from p as shown in (i) and (ii) below [4].
(i) The total variation distance between the generated distribution and p is at most ε.
(ii) After preprocessing for time of order O ^~ (d ⁵ ), each sample is generated for time of order O ^~ (d ⁴ /ε ⁴ ).

Note that the mean of the distribution p is described as μ(p), and the covariance of the distribution p is described as Cov(p). Theorem 5 above means that the mean μ(p) and covariance Cov(p) of a logarithmically concave distribution p can be approximately calculated efficiently.

The operation of the optimization device of this embodiment will be described with appropriate reference to the above theorems and definitions. As mentioned above, in this embodiment, we assume that l _t follows a distribution D over W for t=1, 2, . Also, l ^* is expressed as in Equation 10 below. Also, ξ _t = l _t - l ^* .

FIG. 1 is a block diagram showing a configuration example of a first embodiment of an optimization device according to the present invention. The optimization device 100 of this embodiment includes an initialization unit 10 and an optimization unit 20 .

The initialization unit 10 performs initialization processing necessary for various types of processing. Specifically, the initialization unit 10 sets a set of d-dimensional actions a that are candidates (hereinafter referred to as action set) A⊆R ^d convex hull Conv(A) (=P ₁ ). Also, the initialization unit 10 sets a parameter (δ>0) that controls the probability of obtaining a small regret.

The optimization unit 20 divides the round T into K phases=O(logT). Specifically, the optimization unit 20 divides the round T so that the k-th phase includes Θ(2 ^k ) rounds.

Also, the optimization unit 20 recursively sets the action set P _k at the start of the k-th phase. For example, when P ₁ =Conv(A) is initialized, the optimization unit 20 sets the value of l ^*T x to decrease for all x as k increases (P ₁ ⊇ P ₂ Set _Pk such that ⊇... _⊇PK .

The optimization unit 20 _{also calculates the 2-centroid spanner X k =} {x _k1 , . Note that if the actions contained in the centroid spanner X _k can be performed, then a favorable estimate of l ^* can be constructed. However, each element contained in X _k normally does not belong to A, especially if A is discrete. To address _{this, the optimizer 20 satisfies λ ki0 + . . . + λ kid = 1 and λ ki0} x _{ki0 + .} We decompose each x _ki into points {x _ki0 , . . . , x _kid }εA as follows. Then, the optimization unit 20 executes x _kij T _kij ∝λ _kij times for each j=0, 1, . . . , d. Hereinafter, an action executed in t rounds is denoted as _at .

That is, the optimization unit 20 solves the decomposition problem (DP) for each of the elements X _k and the convex hull P=Conv(A), and obtains x _ki =λ _ki0 x _ki0 + . . . +λ _kid x _kid We obtain the decompositions x _ki0 ,..., x _kid εA and λ _ki0 ,..., λ _kid . Also, in each phase k, the optimization unit 20 selects the action a _t =x _kij exactly T _kij times from the (t _kij +1)th round to the (t _ki,j+1 )th round. Note that T _kij and t _kij are calculated by Equations 11 and 12 shown below. That is, it can be said that the optimization unit 20 determines the number of actions to be selected according to the weight λ of the point.

The optimizer 20 calculates an empirical estimator of l ^* , l^ _k , based on the feedback (ie, the selected action) obtained in the k-th phase using Equation 13 below. Note that l^ is a superscript hat.

The optimizer 20 performs linear optimization for P=P _k and w=l^ _k to find the vector x ^* _k that minimizes the loss l^ ^T _k x, as shown in Equation 14 below. Solve the problem (LP). Specifically, the optimization unit 20 controls transmission of the calculated empirical estimator l^ _k to a device (not shown) that executes a linear optimization oracle, and the optimized The linear optimization problem is solved by obtaining x ^* _k elements (hereinafter referred to as optimization elements).

After calculating x ^* _k , the optimization unit 20 updates the convex hull _Pk to be smaller based on x ^* _k obtained by solving the linear optimization problem, based on Equation 15 below.

The initialization unit 10 and the optimization unit 20 are realized by a computer processor (for example, CPU (Central Processing Unit), GPU (Graphics Processing Unit)) that operates according to a program (optimization program).

For example, the program may be stored in a storage unit (not shown) included in the optimization device 100, the processor may read the program, and operate as the initialization unit 10 and the optimization unit 20 according to the program. Also, the functions of the optimization device 100 may be provided in a SaaS (Software as a Service) format.

The initialization unit 10 and the optimization unit 20 may each be realized by dedicated hardware. Also, part or all of each component of each device may be implemented by general-purpose or dedicated circuitry, processors, etc., or combinations thereof. These may be composed of a single chip, or may be composed of multiple chips connected via a bus. A part or all of each component of each device may be implemented by a combination of the above-described circuits and the like and programs.

Further, when part or all of each component of the optimization device 100 is realized by a plurality of information processing devices, circuits, etc., the plurality of information processing devices, circuits, etc. may be centrally arranged, They may be distributed. For example, the information processing device, circuits, and the like may be implemented as a form in which each is connected via a communication network, such as a client-server system, a cloud computing system, or the like.

Next, the operation of the optimization device of this embodiment will be described. FIG. 2 is a flowchart showing an operation example of the optimization device 100 of this embodiment. In this operational example, assume that the action set A⊆R ^d , δ>0, L>0 and R>0.

The initialization unit 10 sets the convex hull Conv(A) (=P ₁ ) of the action set A⊆R ^d . The initialization unit 10 also sets the number of rounds t to 0 (step S1). Henceforth, the optimization part 20 repeats the process from step S2 to step S16 about each phase k.

_The optimization unit ₂₀ sets _{X k} ={x _k1 , . The optimization unit 20 also sets the parameter ζ _k as shown in Equation 16 below (step S4).

Also, the optimization unit 20 repeats the processing from step S5 to step S12 for each d.

The optimization unit 20 solves the decomposition problem (DP) for the convex hull P=Conv(A) and x=x _ki , and the decomposition x _ki0 , such that x _ki =λ _ki0 x _ki0 +...+λ _kid x _kid , x _kid εA and λ _ki0 , . . . , λ _kid are obtained (step S6).

Furthermore, the optimization unit 20 repeats the processing from step S7 to step S10 for each d.

The optimization unit 20 calculates the number of round selections. Specifically, the optimization unit 20 calculates the number of selections T _kij and the rounds t _kij to be selected based on Equations 11 and 12 shown above (step S8). Through this processing, it can be said that the optimization unit 20 determines the number of rounds included in the phase so that the number of rounds included in the sequentially executed phase k increases in the order of the factorial of two. The optimization unit 20 selects the action at ₌ x _kij T kij times _from the (t _kij +1)th round to the (t _ki,j+1 )th round (step S9).

The optimization unit 20 updates the selected round t _kij as t _k,i+1,0 =t _ki,d+1 (step S11).

The optimization unit 20 calculates the empirical estimator _l̂k of l ^* using Equation 13 shown above (step S13).

The optimization unit 20 solves the linear optimization problem (LP) for the convex hull P=P _k and w= _l̂k in order to find the vector x ^* _k shown in Equation 14 above (step S14). The optimization unit 20 updates _Pk based on Equation 15 above (step S15). That is, the optimization unit 20 updates the convex hull P for each phase.

Next, analysis results of Regret when using the optimization device 100 of the present embodiment will be specifically described. Specifically, we show the following theorem that gives the upper regret limit achieved by the above algorithm.

<Theorem 6>
Suppose l _t is independent and _identically distributed with T≧2 and ^t ₌₁ , . In this case, with probability of at least 1−δ, regret is bounded as shown in Equation 17 below.

Next, an analysis of the oracle complexity is described.
As mentioned above, the optimizer 20 needed to compute the 2-centroid spanner X _k . On the other hand, from Theorem 4 described above, by calling the algorithm that solves the linear optimization problem (LP) for P=P _k the number of times of order O(poly(d)), You can build spanners. Furthermore, Theorem 3(a) above implies that the linear optimization problem (LP) can be solved by solving the separation problem (SP) in the order of O(poly(d)).

The separation problem (SP) for P= _Pk can be solved by the procedure shown below.

1. Determine if yεP ₁ . and if not yεP ₁ , output wεR ^d such that w ^T y<min _xεP1 w ^T x. From Theorem 3(b) above, this process can be done by invoking the LP oracle for A a number of times of order O(poly(d)). On the other hand, if yεP ₁ , the following 2. is processed.

2. ^For _j ⁼ ₁ ^, _. It means that yεP k if l̂ _j ^T (y−x _k ^* )≦LR2 ^−j for all j=1, . . . , _k −1.

1 above. and 2. In the procedure 2, the LP oracle is called the number of times of order O(poly(d)) and executed the number of times O(poly(d, K))=O(poly(d, logT)). Therefore, in step S3 shown in FIG. 2, the optimization unit 20 performs an efficient process of calling the LP oracle for K O(poly(d)) times.

Similarly, steps S6 and S14 shown in FIG. 2 can be performed by calling the LP oracle for cA O(poly(d)) times. Other steps do not require access to an oracle and can be processed efficiently. Also, since the number of iterations K relative to k is bounded, the number of oracle calls to solve LP for A is O(poly(d)K)=O(poly(d)logT).

As described above, in the present embodiment, the initialization unit 10 sets the convex hull P of the action set A, and the optimization unit 20 calculates the d dimensional elements (action vectors) included in the convex hull P. Let X be the center-of-mass spanner of its convex hull P, and the optimizer 20 solves a decomposition problem (DP) for an element X and the convex hull P that decomposes each of the elements into dimensional points. In addition, the optimization unit 20 divides the round T into phases k of log (T) order, selects points for the number of rounds divided into phases as actions, and based on the selected actions, the loss vector Compute the empirical estimator l^ _k . Then, the optimization unit 20 solves a linear optimization problem (LP) that minimizes the loss calculated by the element X and the empirical estimator l^ _k with respect to the empirical estimator l^ _k and the convex hull P. , update the convex hull P to be smaller based on the obtained optimization factor x ^* _k . Thus, the bandit problem can be optimized for efficient solution.

Further, in this embodiment, the optimization unit 20 controls the transmission of the empirical estimator _̂k calculated to the device that executes the linear optimization oracle _OA , and the optimization element x ^* Solve the linear optimization problem by taking _k . Therefore, the computation time can be reduced by reducing the number of calls to the device that executes the linear optimization oracle, thereby improving the computer's ability to solve the bandit problem. In other words, the optimization device of this embodiment can be said to be a device that appropriately controls instructions given to an oracle as a device.

Embodiment 2.
Next, the optimization device of the second embodiment will be explained. A second embodiment assumes a non-stochastic setting in bandit linear optimization. A non-stochastic setting, in contrast to a stochastic setting, is one that does not assume any generative model. For example, the possibility exists that the loss vector l _t is chosen in an adversarial manner depending on previous actions a ₁ , . . . , a _t−1 .

FIG. 3 is a block diagram showing a configuration example of the second embodiment of the optimization device according to the present invention. The optimization device 200 of this embodiment includes an initialization unit 30 and an optimization unit 40 .

The optimizer 200 of this embodiment maintains the convex set K _t ^(j) ⊆ R ^d such that A ⊆ K _t ^(j) . Note that t corresponds to a round and jε{0, 1, . . . } is an index. The optimizer 200 also updates the convex function z ^t : R ^d →R _≧0 based on the updating of the increasing weights in each round. A formal definition of ^zt will be given later.

Also, in the following description, the probability density function of the distribution on K _t ^(j) proportional to the function z ^t is denoted as q _t ^(j) . That is, q _t ^(j) satisfies the properties shown in Equation 18 below.

Also, the mean μ _t ^{(j )} ∈R ^d of q _t (j) and the covariance matrix Σ _t ^(j) ∈R ^d×d of q _t ⁽ j) are expressed by Equation 19 below.

Here, based on the assumption similar to Theorem 5 described above, a lemma is shown below.
<Lemma>
With a probability of at least 1−δ, μ^(superscripted hat of μ) and Σ^(superscript of Σ) in poly(d, 1/ε, log(1/δ)) to obtain Equation 20 shown below. with a hat). ^{It should} _be ^{noted that} ||x||

From the above lemma, optimizer 200 can compute estimators of μ _t ^(j) and Σ _t ^(j) such that Equation 21 below holds with probability at least (1−δ _t ^(j) ) . Note _that δ _t ^{( j)} ∈ (0,1) is expressed as δ _t ^(j) = 1/Tk(k+ ₁ ⁾ , where k is is incremented to

_Furthermore , let B _t ^(j) = (b _t1 ^(j) _, . . . , b _td ^{(j ) )} εR _{d ×d} be , and ε _t ^(j) ⊆ R ^d is defined by Equation 21 below.

Therefore, the optimizer of this embodiment can extract any vector y within a predetermined range (1/4e(b _ti ^(j) )) from μ (that is, a finite set ε _t ^(j) ) and a convex set Solve the separation problem to derive the hyperplane that separates . Also, _the included range of this vector is determined based on the elements of matrix B (b _t1 ^{( j)} , . .

The initialization unit 30 performs initialization processing necessary for various processing. Specifically, the initialization unit 30 sets a convex set K (=K ₁ ⁽⁰⁾ ). That is, the initialization unit 30 sets a convex set that includes the action set. Also, the initialization unit 30 may set a learning rate η>0 and an error limit ε>0. Note that in the present embodiment, T represents a target period TεN.

The optimizer 40 solves the separation problem (SP) for yεε _t ^(j) and P=K:=Conv(A) and updates K _t ^(j) . Suppose there exists a hyperplane separating K from any y. That is, the optimizer 40 solves the separation problem for deriving the hyperplane that separates the vector y and the convex set. In the following description, s _t represents the number of iterations (of the while loop), and ε _t :=ε _t ^(st) ⊆K is obtained after the iterations. Also, the mean, covariance matrix and matrix after iterative processing are respectively μ^ _t = μ^ _t ^(st) , Σ^ _t = Σ^ _t ^(st) and B _t = B _t ^(st) Write down.

Also, the optimization unit 40 randomly selects x from ε _t . Specifically, the optimization unit 40 randomly and uniformly selects a parameter σ _t ε{−1, 1} indicating a positive or negative value and a value i _{t ε} [d in the number of dimensions of the selected action vector. ]. The optimization unit 40 sets x=μ^ _t +(σ _t /4e)b _tit and calculates x based on the selected i _t and σ _t . Then, the optimization unit 40 solves the division problem (DP) for this x and the convex set P=K to obtain a division of x. _{Specifically , the optimization unit 40 performs x _} Compute _t0 ,...,xtd _? K and ? _t0 ,...,? _td ?

The optimizer 40 then performs the action a _t =x _ts with the probability of the decomposed point weight λ _ts to obtain the feedback (loss) l _t ^Ta _t . Based on the feedback, the optimization unit 40 calculates the estimated amount _l̂t of the loss vector l _t using Equation 22 below.

The optimization unit 40 calculates a function z _t from the calculated estimator ̂ _t using Equation 23 below.

Using the Lemma algorithm, Equation 20 above holds with probability at least 1−δ _t ^(j) . Here, δ _t ^(j) is represented by Equation 24 below.

Note that the initialization unit 30 and the optimization unit 40 are implemented by a computer processor that operates according to a program (optimization program).

Next, the operation of the optimization device of this embodiment will be described. FIG. 4 is a flow chart showing an operation example of the optimization device 200 of this embodiment. In this operational example, convex set K _t ^(j) ⊆ R ^d (A ⊆ K _t ^(j) ), learning rate η>0, error bound ε>0, period of interest TεN, L>0 and R>0 Suppose that

The initialization unit 30 sets the convex set K ₁ ⁽⁰⁾ ←B(0, R) (step S101).

The optimization unit 40 repeats the following steps S102 to S116 for t=1, 2, . . . , T. First, the optimization unit 40 sets j←0 (step S103).

Furthermore, the optimization unit 40 repeats the processing from step S104 to step S107 for any yεε _t ^(j) while the hyperplane wεR ^d shown in Equation 25 below exists.

The optimization unit 40 updates the contents of K. Specifically, the optimization unit 40 updates the range of K using Equation 26 shown below so as to reduce the range of K based on the hyperplane w (step S105), and sets j←j+1 (step S106). . Note that γ is a parameter. That is, the optimization unit 40 updates the convex set K to a smaller convex set based on the derived hyperplane.

After exiting the loop from step S104 to step S107, the optimization unit 40 sets st _← j (step S108) and sets Kt _{← Kt} ^(st) (step S109). The optimization unit 40 randomly and uniformly selects σ _t ε{−1, 1} and i _{t ε} [d] (step S110).

Optimizer 40 then solves the partitioning problem (DP) for P=K and x=μ^ _t +(σ _t /4e)b _tit to obtain a partition of x. _Specifically , the optimization unit 40 performs the _division such _that λ _t0 + . _. . + λ _td = 1 and λ _t0 x _{t0 +} . x _t0 , ..., x _td ∈A and λ _t0 , ..., λ _td ≥ 0 are calculated (step S111).

^The optimization unit ₄₀ executes the action at _{= xts with} a probability of _λts (where s=0, . Based on the feedback, the optimization unit 40 calculates the estimated amount _l̂t of the loss vector l _t using the above Equation 22 (step S114). Then, the optimization unit 40 updates K _t+1 ⁽⁰⁾ ←K _t ^(st) (step S115).

Next, analysis results of Regret when using the optimization device 200 of the present embodiment will be specifically described. Specifically, the upper limit of regret by the above algorithm is shown below. First, ψ is defined as shown in Equation 27 below.

Here, it is assumed that _at is given by the processing illustrated in FIG. 4 with parameters ε and η shown in Equation 28 below.

At this time, the expected value shown in Equation 29 below is obtained for all a ^* εA.

In Equation 29, S _T represents the number of updates of Kt ^(j) from t=1 to T. Note that ψ described above satisfies ψ≦log(R/r) if K contains a sphere l ₂ with radius r>0.

Next, an analysis of the oracle complexity is described. Specifically, the process illustrated in FIG. 4 indicates that the call to the linear optimization oracle is on the order of O(Tpoly(d)).

To implement the process illustrated in FIG. 4, a linear optimization oracle is required only at steps S104 and S111. At step S104, a separation problem (SP) is required to determine if there exists xεε _t ^(j) such that x is not an element of K. From the definition of ε _t ^(j) shown in Equation 21 above, the number of elements in ε _t ^(j) is equal to 2d for each t and j, so the total number of separation problems to solve is It is calculated by Equation 30.

The number of S _T can be bounded by the order O(T). As a result, the total number of orders to solve the separation problem (SP) is O(dT).

Also, in step S111, a division problem (DP) is solved in each round t. So the total number of partitioning problems (DP) to solve is equal to T. Since the linear optimization oracle can be solved by poly(T) calls to solve the separation problem (SP) and partitioning problem (DP), the linear optimization oracle is illustrated in FIG. You can implement the processing to

As described above, in this embodiment, the initialization unit 30 sets a convex set K that includes the action set A, and the optimization unit 40 sets the hyperplane w and update the convex set to a smaller convex set based on the derived hyperplane w. Further, the optimization unit 40 selects a value i _{t ε} [d] within the number of dimensions of the action vector and a parameter σ _t ε{−1, 1} indicating a positive or negative value, and selects i _t and σ _t For an element x (=μ^ _t +(σ _t /4e)b _tit ) determined by and a convex set K, solve the decomposition problem (DP) that decomposes each of its elements x into points with the dimensionality of the action vector do. Then, the optimization unit 40 executes the point as the action a with the probability λ of the weight of the decomposed point, and calculates an estimate of the loss vector based on the loss obtained by the executed action. Thus, the bandit problem can be optimized for efficient solution.

Further, in this embodiment, the optimization unit 40 controls transmission of the vector y and the convex set to a device (not shown) that executes a linear optimization oracle (an oracle that solves the separation problem). We solve the separation problem by acquiring the hyperplane w from the device. Therefore, the computation time can be reduced by reducing the number of calls to the device that executes the linear optimization oracle, thereby improving the computer's ability to solve the bandit problem. In other words, the optimization device of this embodiment can be said to be a device that appropriately controls instructions given to an oracle as a device.

Next, an outline of the present invention will be described. FIG. 5 is a block diagram showing an overview of the optimization device according to the invention. The optimization device 90 according to the present invention is an optimization device (for example, the optimization device 200) that optimizes the bandit problem, and is a convex set that includes an action set (for example, A) that is a set of candidate action vectors. (eg, K), an arbitrary vector (eg, y) included in a predetermined range (eg, ε _t ^(j) ) and the convex set Solve a separation problem (e.g. SP) to derive a hyperplane (e.g. w) that separates (e.g. K) and the convex set into smaller convex sets (e.g. , based on Equation 26 above), and a parameter indicating the value in the dimensionality of the action vector (eg, i _t ε[d]) and the positive/negative value (eg, σ _t ∈ {−1, 1}), and for the elements and convex sets determined by the values and parameters within the selected dimensionality, _A decomposition problem solver 94 (e.g. _, optimization unit 40), an action execution unit 95 (for example, the optimization unit 40) that executes the point as an action with the weight probability (for example, λ) of the decomposed point, and a loss obtained by the executed action ( For example, it includes an estimator calculator 96 (eg, the optimizer 40) that calculates an estimator (eg, l^ _t ) of the loss vector based on _lt ^Ta _t ).

Such an arrangement allows the bandit problem to be optimized for efficient solution.

In addition, the separation problem solving unit 92 derives a hyperplane that separates an arbitrary vector within a predetermined range from the average of the probability density function of the distribution of the convex set (for example, μ^ _t ) and the convex set. It may solve the separation problem.

In addition, the separation problem solving unit 92 converts the range in which the vector is included into the elements of the covariance matrix of the probability density function of the distribution of the convex set (for example, Σ^ _d ^(j) = B _t ^(j) B _t ^{(j) T} ).

In each round, the separation problem solver 92 also updates the convex function (eg, z _t (a)) based on the update of the increasing weight, and the probability density function (eg, q _t ^{(j )} ) may be calculated.

In addition, the separation problem solver 92 controls transmission of vectors and convex sets to a device that executes a linear optimization oracle (for example, an oracle that solves LP, SP, and RP), and extracts a hyperplane from the device. Obtaining may solve the separation problem. According to such a configuration, it is possible to reduce the number of calls to the device that executes the linear optimization oracle and reduce the computation time, thereby improving the computer's ability to solve the bandit problem.

Further, the parameter selection unit 93 may randomly and uniformly select parameters indicating values within the number of dimensions of the action vector and positive/negative values.

FIG. 5 is a schematic block diagram showing the configuration of a computer according to at least one embodiment. A computer 1000 comprises a processor 1001 , a main storage device 1002 , an auxiliary storage device 1003 and an interface 1004 .

The optimization device 90 described above is implemented in the computer 1000 . The operation of each processing unit described above is stored in the auxiliary storage device 1003 in the form of a program (optimization program). The processor 1001 reads out the program from the auxiliary storage device 1003, develops it in the main storage device 1002, and executes the above processing according to the program.

It should be noted that, in at least one embodiment, secondary storage device 1003 is an example of non-transitory tangible media. Other examples of non-transitory tangible media include magnetic disks, magneto-optical disks, CD-ROMs (Compact Disc Read-only memory), DVD-ROMs (Read-only memory), which are connected via the interface 1004. A semiconductor memory etc. are mentioned. Further, when this program is distributed to the computer 1000 via a communication line, the computer 1000 receiving the distribution may develop the program in the main storage device 1002 and execute the above process.

Also, the program may be for realizing part of the functions described above. Further, the program may be a so-called difference file (difference program) that implements the above-described functions in combination with another program already stored in the auxiliary storage device 1003 .

10, 30 initialization unit 20, 40 optimization unit 100, 200 optimization device

Claims (10)

An optimizer for optimizing a bandit problem, comprising:
a convex set setting unit that sets a convex set including the action set that is a set of candidate action vectors;
Separation solving a separation problem to derive a hyperplane that separates any vector contained in a predetermined range from a convex set, and updating the convex set to a smaller convex set based on the derived hyperplane a problem-solving department;
a parameter selection unit that selects a parameter indicating a value within the number of dimensions of the action vector and a positive/negative value;
a decomposition problem solving unit for solving a decomposition problem of decomposing each of the elements determined by the selected values within the dimensionality and the parameter and the convex set into points of the dimensionality of the action vector;
an action execution unit that executes the point as an action with the probability of the weight of the decomposed point;
an estimator calculating unit for calculating an estimator of a loss vector based on the loss obtained by the executed action. 2. The separation problem solver according to claim 1, wherein the separation problem solver solves the separation problem for deriving a hyperplane separating any vector within a predetermined range from the mean of the probability density function of the distribution of the convex set and the convex set. Optimizer. 3. The optimization device according to claim 1, wherein the separation problem solving unit determines the range in which the vectors are included based on the elements of the covariance matrix of the probability density function of the distribution of the convex set. 4. The separation problem solver updates the convex function based on the update of increasing weights in each round, and calculates a probability density function proportional to the convex function. The optimization device described in . The separation problem solver controls transmission of vectors and convex sets to a device that executes a linear optimization oracle, and obtains hyperplanes from the device to solve the separation problem. The optimization device according to any one of The optimization device according to any one of claims 1 to 5, wherein the parameter selection unit randomly and uniformly selects a parameter indicating a value within the number of dimensions of the action vector and a positive/negative value. An optimization method for optimizing a bandit problem, comprising:
A computer sets a convex set containing an action set that is a set of candidate action vectors,
The computer solves a separation problem for deriving a hyperplane that separates any vector contained in a predetermined range from the convex set, and converts the convex set to a smaller convex set based on the derived hyperplane. and update to
The computer selects a parameter indicating a value within the number of dimensions of the action vector and a positive or negative value,
The computer solves a decomposition problem for elements determined by the selected values in the dimensionality and the parameter and the convex set to decompose each of the elements into points of the dimensionality of the action vector. ,
the computer executing the point as an action with the probability of the weight of the decomposed point;
A method of optimization , wherein the computer calculates an estimator of the loss vector based on the losses obtained by the actions performed. 8. The optimization method of claim 7 , wherein the computer solves the separation problem to derive a hyperplane separating any vector within a predetermined range from the mean of the probability density function of the distribution of the convex set and the convex set. . An optimization program applied to a computer that optimizes a bandit problem,
to the computer;
a convex set setting process for setting a convex set containing an action set that is a set of candidate action vectors;
Separation solving a separation problem to derive a hyperplane separating any vector contained in a predetermined range from a convex set, and updating the convex set to a smaller convex set based on the derived hyperplane problem solving process,
parameter selection processing for selecting parameters indicating values within the number of dimensions of the action vector and positive/negative values;
Decomposition problem solving processing for solving a decomposition problem of decomposing each of the elements determined by the selected values within the dimensionality and the parameter and the convex set into points of the dimensionality of the action vector;
Action execution processing for executing the point as an action with the probability of the weight of the decomposed point, and
An optimization program for executing an estimator calculation process for calculating an estimator of a loss vector based on the loss obtained by the executed action. to the computer,
10. The separation problem solving process solves the separation problem for deriving a hyperplane separating any vector y within a predetermined range from the mean of the probability density function of the distribution of the convex set and the convex set. optimization program.

Images