Efficient Multivariate Bandit Algorithm with Path Planning
Authors: Keyu Nie
Zezhong Zhang
Ted Tao Yuan
Rong Song
Pauline Berry Burke
Venue:  (2020)
Keywords: Multivariate Multi-armed Bandit
Monte Carlo Tree Search
Thompson Sampling
Path Planning

Abstract: In this paper, we solve the arms exponential exploding issues in multivariate Multi-Armed Bandit (Multivariate-MAB) problem when the arm dimension hierarchy is considered. We propose a framework called path planning (TS-PP) which utilizes decision graph/trees to model arm reward success rate with m-way dimension interaction, and adopts Thompson sampling (TS) for heuristic search of arm selection. Naturally, it is quite straightforward to combat the curse of dimensionality using a serial processes that operates sequentially by focusing on one dimension per each process.  For our best acknowledge, we are the first to solve Multivariate-MAB problem using graph path planning strategy and deploying alike Monte-Carlo tree search ideas. Our proposed method utilizing tree models has advantages comparing with traditional models such as general linear regression. Simulation studies validate our claim by achieving faster convergence speed, better efficient optimal arm allocation and lower cumulative regret.

Under review as a conference paper at ICLR 2020
EFFICIENT MULTIVARIATE BANDIT ALGORITHM WITH PATH PLANNING
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we solve the arms exponential exploding issues in multivariate Multi-Armed Bandit (Multivariate-MAB) problem when the arm dimension hi- erarchy is considered. We propose a framework called path planning (TS-PP) which utilizes decision graph/trees to model arm reward success rate with m-way dimension interaction, and adopts Thompson sampling (TS) for heuristic search of arm selection. Naturally, it is quite straightforward to combat the curse of di- mensionality using a serial processes that operates sequentially by focusing on dimension per each process. For our best acknowledge, we are the first solve Multivariate-Man MABB problem using graph path planning strategy and deploy- ing alike Monte-Carlo tree search ideas. Our proposed method utilizing tree mod- els has advantages comparing with traditional models such as general linear re- gression. Simulation studies validate our claim by achieving faster convergence speed, better efficient optimal arm allocation and lower cumulative regret.
INTRODUCTION
Multi-Armed Bandit (MAB) problem, is widely studied in probability theory and reinforcement learning which dates back to clinical trial studies by Thompson Thompson (1933). Robbins Rob- bins (1952) formulated the setting in 1952: it includes leamer having K arms (options/choices) to explore given little knowledge about the properties of each arm. At each step / in [1,T]. the learner chooses an arm i and receives a reward X from the choice under the purpose to minimize the regret as well as maximize cumulative reward. Binomial bandit is the most common bandit formats by restricting the rewards being binary (X* E (0, 13). The solution of MAB problem volves balancing between acquiring new knowledge (exploration) and utilizing existing knowledge (exploitation), to make arm selection each round t based on the state of each arm. The upper confidence bound (UCB) algorithm was demonstrated as optimal solution to manage regret bound the order of O(log(T) Lai Robbins (1985 Lai et al. (1987 Agrawal (1955) Auer et al.) (2002). In online experiment, Thompson Sampling (TS) algorithm attracts a lot of attention due its sim- plicity at implementation and resistance in batch updating. TS algorithm for binomial bandit could achieve optimal regret bound as well Kaufmann et al. 2012).
Many modern online applications (e.g. UT Layout) have configuration involving multivariate dimen- sions to be optimized, such font size, background color, title text, module location, item image etc., each dimension contains multiple options Hill et al. (2017) Nair et al. (2018). In this paper, we call it MuAti problem. The exploring space faces exponentially exploding number of possible configurations as dimensions are added into the decision making. TS algorithm is reported convergences slowly to the optimal solution Hill et al. (2017) when dealing with Multivariate- MAB problem. To speed up convergence, one common enhanced TS solution is to model the ex- pected reward as general linear model (TS-GLM) Chu et al. 2011 Bubeck et al. (2012 Scott (2010) by probit/logit link function with m-way dimension interaction features. TS-GLM gives up the ability to certain complex interactions. exchange for focusing on lower-dimensional parame- ter space and achieves better solution. However, updating derived posterior sampling algorithm in TS-GLM demands imputing the multivariate coefficients and creates computation burden at each iteration Scott 2010 Scott 2015 Hill et al. (2017). To release such burden, Daniel et. al. Hill et al. (2017) proposed Hill-climbin multivariate optimization Casella & Berger (2002) for TS- TS.GLM, and recognized it obtained faster convergence speed with polynomial exhaustive parameter space.

---

Under review as a conference paper at ICLR 2020
Different from TS-GLM, our proposal framework called "Path Planning" (TS-PP) is quite straight- forward to combat the curse dimensionality by a serial processes that operates sequentially and focuses dimension at each component process. Further more, it treats reward naturally with m-way dimension interaction by m-dimensional joint distribution. Our novelty includes: (a) modeling arm selection procedure under tree structure. (b) efficient arm candidates search strategies under decision graph/trees. (c) remarkable convergence performance improvement by straightfor- ward but effective arm space pruning. (d) concise and fast reward function posterior sampling under beta-binone ti--iinomial even with m-way dimension interaction consideration. Compare to TS-GLM, TS-PP avoids deriving complex and slow posterior sampling in GLM, while still effectively leveraging the m-way dimension interactions and achieving even better performance by reducing arm space with efficient search strategies.
This paper is organized as follows: We first introduce the problem setting and notation; then we explain our approach in details, and further discuss the differences among several variations; we also examine the algorithm performance in simulated study and concludes at the end.
2 MULTIVARIATE-MAL PROBLEM FORMULATION
We start with the formulation of contextual multivariate MAB: the sequential selection decision of layout (e.g. web page) A, which contains template with D dimensions and each dimension con- tains N options, under context C' (e.g. user preference) for the purpose of minimizing the expected cumulative regret (Rt).
For each selected layout A, a reward X shall be received from the environment. Here only binary reward (X E {0, 1)) is discussed, but approach be extended to categorical/numeric rewards as well. In the layout A template, there exists N, alternative options for dimension and f. is de- noted as the selected option. We further assume N; N in our following description for simplicity purpose. The chosen layout A can be denoted as [fi...., fol E (1,.... .ND,, and it utilizes the no- tation A[i] referring ft. Context C' includes extra environment information that may impact layout's expected reward (e.g. device type, user segments, etc.).
At each step = ,,....?7 T. the bandit algorithm selects arm A' from ND search space with the consideration of the revealed context Ot in order to minimize the cumulative regret over T rounds:
R Σ (E(XIA E(XIA,,, E=
where A stands for the best possible arm at step t. Generally, Ry is on the order O(VT) under linear payoff settings Dani al. 2008|Chr al. (2011 AAArAAaaa & Goyal (2013). Although the optimal regret of non-contextual Multivariate MAB is on the order O(logT") Lai & Robbins 1985). In this paper, we focus on categorical-conter variables. By solving multivariate MAB independently for each combination of C' (assuming not too many), it is trivial show that the optimal regret bound of R still (T)) Without loss of generalization, we set context feature as constant and ignore C' in the following discussion.
multivariate MAB where C are purely categorical
3 RELATED WORK
3.1 PROBABILISTIC MODEL FOR MULTIVARIATE-MAB
To model the multivariate bandit reward of layout A', denote the features combining A and interactions within A (possibly non-linearly as B E RM with length M. The BA could involve only upto m-way dimension interactions of (O(N")) instead of capturing all (O(ND) possible interactions. The linear model with pairwise interactions is as follows:
D (
D D
B BJ== = nO + + +
i=1==++
where y are fixed but unknown parameter coefficients. In above function, it contains common bias term y." weights for each dimension of layout μ!! (A) and 2-way dimension interactions of layout n (A). The sub-indexes and j referring dimension and j correspondingly.
2

---

Under review as a conference paper at ICLR 2020
Under the GLM setting, g(P(X = 1|Ba)) g(p) BT where p is the success rate of re- ward X and g is the link function that can either be the inverse of normal CDF $ (p)(p) as a pro- logit model. For given BA, the likelihood of reward X would be
bit model the In( p (mpp
(B(BA)))* - $ (B] or (exp(- ( + 1) (exp(BAx) + 1) 1)(+++ for probit or logit model respectively. The posterior sampling distribution of reward is its likelihood integrates with some fixed prior distribution of weights μ.. Updating the posterior, at step i, requires solving GLM for j from cumulative historical rewards H [(X A A?), (X (x A), which is disturbing and creates computation burden with time.
Daniel et. al. Hill et al. (2017) proposed MVT2 by assuming probit model with interactions between dimensions (Equation and employing Hill-climbing multivariate optimization to achieve faster convergence speed.
3.2 THOMPSON SAMPLING
Thompson sampling (TS) Russo et al. (2018) is widely adapted in solving bandit and reinforcement learning problems to balance between exploitation and exploration. It utilizes common Bayesian techniques to form posterior distribution of rewards, hence allocates traffic to each arm proportional to probability of being best arm under posterior distribution.
Normally we handle binary response as binomial distribution with Beta prior Beta(ag. 36) to form posterior distribution Beta(ay, + Cig, 3x + 9n), where ag and 3₁ are the number of successes and failures it has been encountered so far at arm k, as well as Onp and 9o are prior parameters and would been set 1 for uniform prior. At selection stage in round it implicit allocates traffic as follows: simulates a single draw of 02 from posterior (Beta(a) + oko, 3k + ().)) for each arm k and the arm k. arg max, (0x) out of all arms will be selected. At update stage, collects reward X {0, 13 and the reward is used to update hidden state (ax+, BBx)) ) of selected arm.
Practically, to solve Multivariate-Man MAB problem, algorithm ND MAB directly adopts TS in selec- tion out of No arms, while algorithm D-MABs decomposes Multivariate-MA MAB into D (dimensions) sub-MABs and implements TS in selection out of N arms for each MAB (dimension) independently. We would discuss more details of the two algorithms in following sections.
3.3 MONTE-CARLE TREE SEARCH
Monte-Carle Tree Search (MCTS) Browne et al. 2012 Chaslot et al. (2008a) is best-first heuristic search algorithm to quickly locate the best leaf node in a tree structure. In game tree problem, achieves great success especially when the number of leafs is large. Generally, each round of MCTS consists of four steps Chaslot et al. (0088): selection, expansion, simulation and back paekk-ropagation. Essentially, a simplified case only need selection and back-propagation steps. At selection step of MCTS, it starts from root of the tree and adopts a selection policy to select successive child nodes until Icaf node L is reached. The back- propppropngntion step of MCTS involves using the reward to update information (like hidden states) in the nodes on the path from selected Icaf to root. In artificial intelligence literature, the most successful (MCTS algorithm) UCT utilizes UCB Koesis & Szepesvári (2006) as its node selection policy. Applying TS node selection policy in MCTS (TS- MCTS) is not well investigated in literature Imagawa & Kaneko (2015) from our best knowledge.
By introducing the hierarchical dimensional structure of bandit arms, we can build tree structure over bandit arms and deploy MCTS with TS techniques for arm selection. We prefer TS node selection policy due to its resistance in performance for batch update situation. Inspired by this idea, we establish TS Path Planning algorithm to solve Multivariate-MAN problem.
4 APPROACH
In this paper, we propose TS path planning algorithm (TS-PP) for Multivariate-MAB problem to overcome the exponential explosion arm searching space of ND_ MAB algorithm. Stimulated by MCTS idea, we utilize similar heuristic search strategy to locate best arm under a tree structure. We call such tree structure as "decision tree" which is constructed purely by D dimensions. Notably there are D! decision trees constructed in different sequential dimension order over same leaf nodes
3

---

Under review as a conference paper at ICLR 2020
and they assemble "decision graph". Under decision tree/graph, the arm selection procedure is decomposed into serial processes of decision making that operates sequentially and focuses on value selection within one dimension per each process. At each sequential decision process, would apply TS as successive child nodes (dimension value) selection policy. The sequential order of dimensions ("decision path") is determined by the path planning strategy.
Figure D shows an example of decision graph, decision tree as well as decision path. Without loss of generality, we assume that dimensions are tagged in order of [d] : dp), which is an arbitrary order of [,,...,D) DJ. Decision tree in Figure Ib compactly represents the joint probabilities of all arms [fd, (leaf nodes) and internal nodes. Here we borrow notations in Kochenderfer (2015). [d] : :dp and [fd, are compact ways to write idj....,dp and [fd...... fdol respectively. The sub-index d, fa; refers that this dimension value f+ comes from dimension d, The structure of decision tree consists of nodes and directed edges. Each level of the decision tree represents dimension d, and each node at that level corresponds to value fa, for dimension d,. Directed edges connect parent node to child node where the arrow represents conditional (jointly) relationship. Associated with each node fa, is a jointly probability P(f,, prePath( fa,)). where prePath(fa, represents all predecessor nodes of fa, in red arrows (Figure lb.. We denote prePath( fa.) as fai:d- in our example, and fath(fa,) ) as fd,:d, Based on the cham rule, the likelihood of arm [fd, is P(fár:d,) ITp=1 P(fa, (fd;:d;-)) be represented by hidden states () from Beta distribution (binary rewards) for node fa, (given its prePath(fa,, )) and node's states could be updated in back-propagation stage (like in MCTS). As TS, the chance of arm fdy:d being the best arm depends on P(Jaldd)) hence it is also partially related with P(fd.:d,): ). Instead of sampling directly from posterior distributions of N arms, sampling from distribution associated with each node fa, could also provide guidance on value selection for dimension d, Figure Ta utilizes decision graph compactly represent D! decision trees. Once decision path (red arrow in Figure Tab is determined, decision graph is degenerated decision tree for detailed view. With such abstraction, we further extended the naive MCTS idea with several other path planning strategies.
P(fa, (ffaalld x P(fdy:d.). ). In practice, P(fá,:d, could
Root
d
d
4
d
d
d
r
A
levels
d
d
4
Aid 1-f,
A= (f",, Cy r.)
d
d W
d Paroii
W/
(b) Decision
Tree
under
dimensions
order
(a) Decision Graph
(di...., dD)
Figure 1: Path Planning Overview
4.1 TS-PP TEMPLATE
Algorithm [ provides TS-PP template for better understanding of our proposal over big picture. The proposed path planning algorithms utilize different path planning strategies to obtain candidate arm, by navigating the path from one node to next node originating from start to destination of the decision graph and applying TS within selected node (dimension) to pick the best value per each dimension, condition on fixing selected multivariate options in predecessor nodes unchanged. This conditional posterior sampling distribution as mentioned previously would rely on the hidden states of dimension values within current node given predecessor nodes dimensional value choices.
4

---

Under review as a conference paper at ICLR 2020
Algorithm TS-PP Template
1: Input N. E R', ag = = Bg
2:
for step = 1,2,... do
3: for search
do
D Candidates Construction Stage
4: A < Path Planning Procedure
5:
Sample 0 + Sample (A9))
6: Select Arm A < arg max, 1- (00))
7:
Update History Rewards H' < U
8:
function SAMPLE(Pah=(/4444)
9: Get a, 3 from Node fddddrr
10: Sample 0 ~ Beta(a + ao. 8 + -b)
Return e
We understand that searching candidates in this way might be stacked in sub-optimal arms. To address this issue, we intentionally repeat candidate searching for (S) times and re-apply TS tricks among these candidates for final arm selection. Once the arm is chosen at step t. we would back- propagate the collected reward X to update the hidden states of nodes (Node(fa,, (fandd within all the possible paths from selected leaf to root in decision trees. Here the notation Node fay Iddi-dz .) is used load the node fá= 's (with prePath fdy:dı 1) hidden states in to mem- ory, which corresponds the joint density P(fá,:dz). It worth to note that any relative order of [fd,adz] represents the same joint distribution (with same hidden states). In practice, Node( fázz (dd.:d=-)) requires O(1) computation complexity. But it could also be implemented in O(T) computation complexity for lazy back sock-propagation with eache memory saving.
4.2 PATH PLANNING PROCEDURE
We propose four path planning procedures for candidates searching: Full Path Finding (FPF), Par- tial Path Finding (PPF), Destination Shift (DS) and Boosted Destination Shift (Boosted-DS). To construct arm-candidate under decision graph (figure [aa), FPF starts from the root and sequentially optimizes dimensions one-by-one a completely random order, which utilizes the depth-first search (DFS) strategy. With sticking with top-down flavor while extending the D-MABs, PPF utilizes the breath-firs ferst search (BFS) strategy with m m dimensional joint distribution independence (explained later) for all m-sub dimensions out of D. Finally, inspired by hill-climbing Casella & Berger (2002) Hill et al. (017). which start from a random initial arm (bottom node in decision graph) and opti- mize value for one dimension with all other dimension value fixed, such bottom-up flavor DS and the advanced version Boosted-DS would be discussed. The following explains four methods in details.
Full Path Finding FPF is the direct application of MCTS and describes DFS algorithm in graph search. Starting from top. FPF randomly picks a permutation of D dimensions denoting as [din) with equal chance construct a decision tree, and recursively applies TS policy from nodes on the path from root to leaf in that decision tree. It follows dimensions order to sequentially op- timize value fū, for each dimension d,. The upper index refers the optimized value for target dimension d:- 'Since we repeat FPF S times, each iteration picks different decision tree (per- mutation of dimensions) and construct one candidate A The computational complexity for full path finding is O(SN D) with S times searching and space complexity is O(NP). For lazy mack-propagation implementation, the computation and space complexity could improved to O(SNDT) and O(SDT) separately.
Partial Path Finding In contrast, PPF describes a kind of BFS algorithm. A m th -partial path finding (PPFm) recursively applies TS policy from nodes pre-path [d1:(m-1)] up to level in decision graph, then it simultaneously visits the remaining (D m + 1) dimensions (un-visited nodes) in parallel at level m and apply TS policy correspondingly. Specifically, the D-MABs method is equivalent to PPF1, which adopts the dimension independent assumption. The Pseudo code in Algorithm 2 between line 5 and 10 illustrates a PPF2 algorithm, which assumes pairwise joint distribution independence. Mathematically, variables A and B are conditionally independent give C' (A 1 B(C) if and only if P(A, B(C) = P(A P(B('), and would call joint distribution of (A, C) and (B, C) are independent. So pairwise dimensional joint distribution independence means
5

---

Under review as a conference paper at ICLR 2020
Algorithm 2 Path Planning Procedures
1: procedure FULL PATH FINDING
2: for index = - D in (random order) [d1.D] do
3: fā. TitttDDim=d, prePath=[/aa,d_. and A'dd.] f3.
4: Constructed Candidate A
5: procedure PARTIAL PATH FINDING
6: Random Pick Dimension d: E [d1.D]
fá, f- TSI (tgt d,, prePath= 0) and A'dd.] = fā:
8: for index (j = D) and (j * i) do
9: få, - TStggDimmddd prePath=lfaj and Ar[ds] = fäj
10: Constructed Candidate A
11: procedure DESTINATION SHIFT
12: Initial A random layout A
13:
for k = + K do
14:
Random Pick Dimension di [d
J7 f TSigtDiim=dd, prePath=AA (-<d]) and [ddd]] fā,
16:
Constructed Candidate A
17:
procedure BOOSTED DESTINATION SHIFT
18:
Initial A random layout A
for k + do
20:
Random Pick Dimension d, E dd..]]
21: fá, f bittSStgtDii=dd; ArePath=A"[ddd)] and A9d,) = fā.
22:
Constructed Candidate A
23:
function TS(tttDiim = dr. prePath-[faaidd.-1
24:
for f = do
25:
4- S-Saaple(Pauh-//aa s(ay))
26:
Return fāg arg arg (01)
27:
function BSTTS(tgtDim de, prcPath= 1)
28:
for f = 1 do
29:
Hdd, <- -aaaple(Path-[fa.]]] L do
30:
for index i
31:
W0,,ez Sample(Path- (uz))
32:
0f t- Mly, Ei=1 pdi
33:
Return fā, +- arg sorgmax11i (0')
that d(I:D)-, T ld, for Vi E (1 D). where d( 1 stands for all dimensions are independent except for dimension d, Intuitively, PPF2 assumes pairwise interactions between dimensions, as draws samples from pairwise dimensional joint distribution. Generally PPFm maps up (m)- interactions regression model. The optimal computational complexity of PPF2 is O(SND) with S times searching and space complexity is O(ND)), if we only load all hidden states from top levels of decision graph into memory.
Destination Shift DS randomly picks an initial (bottom node in decision graph) and performs Hill-climbing method cycling through all dimensions for K rounds. At each round k, we randomly choose an dimension d; optimize and return the best dimension value fū, based on posterior sampling distribution condition on the of the dimension values prefixed (A4[-d:)- We then use fū, to generate A(x; from A1 by 1n(d1 = få.- The computational complexity is O(SNK) and space complexity is O(N
Boosted Destination Shift Boosted-DS utilizes bstTS instead of TS function for value optimiza- tion on each target dimension node d. extends our previous intuition that sampling from m- dimensional joint distribution is 1-to-1 mapping to m-way interaction weights in regression model. Pseudo code Algorithm between line and 22 describes 2nd -Bosstedd-- (Boosted-DS2) sam- pling strategy which follows equation [ with pairwise (2 - way) interaction assumption. Instead of single draw from arm P(A Já.). at round with target dimension d, it sums samples drawing from 1-way joint density (P(f.) and all pairwise (2 way) joint distributions with fa, (P(fa, fa.) for all sub-index E [1: D] and + d:). Generally, m th -Boosted-DS (Boosted- would take the sums of drawing samples upto dimensional joint distributions. The computa-

---

Under review as a conference paper at ICLR 2020
tional complexity of Boosted-DS2 is O(SKND) and space complexity is O(ND²) if we store all needed hidden states instead.
In summary, FFP utilizes hidden states from same decision tree each iteration; PFP and Boosted- DS only utilizes hidden states on top levels of decision graph; DS utilizes hidden states on Icaf nodes. DS and Boosted-DS randomly pick layout A to start and keep improving itself dimension by dimension till converge, while FFP and PFP do not randomly guess other dimension values. All four algorithm approximate the process of finding best bandit arm by pruning decision search trees and greedy optimization of sequential process through all dimensions. As the greedy approach sig- nificantly reduce search space, hence the converge performances are expected beat the traditional Thompson sampling method ND MAB.
5 EMPIRICAL VALIDATION AND ANALYSIS
We illustrate the performance of our algorithm (FPF, PPF, DS and Boosted-DS) on simulated data set, comparing with MVT et al. (2017). ND MAKHill et al. (017) and D-MABsHill et al. (2017) base models mentioned before. Specially, we evaluate (a) the average cumulative regret, (b) the convergence speed and (c) the efficiency of best optimal arm selection among these models under same simulation environment settings. To access fairly appreciative analysis, the mechanism and parameters for generating the simulation data set are completely at random. We would also replicate all algorithms multiple (H) times and take the average to eliminate evaluation bias due to TS probabilistic randomness. Furthermore, we extensively exam the cumulative regret performance of proposed algorithms by varying (1) the relative strength of interaction between dimensions and (2) complexity arm space (altering N and D) to gain comprehensive understanding our model.
5.1 SIMULATION SETTINGS
Simulated reward data is generated in Bernoulli simulator with success rate being linear with m-way dimension interactions:
D
D Σ
(())= = ww +a Σ (A)+
Omm
Σ
Pd dm (A)
d==1
dm=dm-1t1
where 3 is scaling variable and We intentionally generate weights μ independently from N(,, 1), and set B m and am control the overall signal noise ratio as well related strength among m-way interactions.
are control parameters. It is trivial to set μ = 0.
m9 ((D-I)..(0-m:
In this paper, we set m = 2 (pairwise dimension interaction). D = 3 and N 10 in above simu- lator settings, which yields 1000 possible layouts. To observe the convergence of each model and eliminate the randomness, our simulation is generated with T = 100, 000 time steps and H/ 100 replications. On each simulation replica and at time step t, layout and binary reward X' is sampled from Bernoulli simulator with success rate 8, which is coming from Equation 2 with pre-generated randomly weights μ.. We choose S = 45 and K = 10 as the same Hill climbing model parameter settings compare between FPF, PPF2, DS, Boosted-DS2 and MVT2 methods.
is chosen by each algorithm,
5.2 NUMERICAL. RESULTS
Figure 2 shows the histograms of arm exploration and selection activities for 7 algorithm as well as distribution of success rate for arms in our simulator. The horizontal axis is the success rate of selected arm, while the vertical axis is the probability density in histogram. The success rate density of Bernoulli simulators is symmetrically distributed, which coincides with our simulation setting. However, the severity of right skewness reveals the efficiency and momentum algorithms recog- nizing bad performance arms and quickly adjusting search space to best possible arms. Although ND-MAD B is theoretically guaranteed to archive optimal performance in the long run, the histogram graph might empirically explains why MVT2, FPF, PPF2 and Boosted-DS2 outperform NP-MAB in many ways. It worth to mention that the search behavior (performance) DS is similar to N MAB, but DS consists simpler computational complexity (O(SNK)). This concludes us that DS
7

---

Under review as a conference paper at ICLR 2020
strategy itself starting path planning from bottom has limited improvement arm heuristic search than N The underline reason could be that only small fraction of arms is explored at early stage and little information is known for each arm, starting from top strategy resemble dimen- sional analogues and learn arm's reward distribution from other arms with similar characteristics. In turns, it helps rapidly shift to better performed arms. The proposed Boosted-DS2 overcomes DS's issue by using TS samples from top levels. The heavily right skewness in Boosted-DSS histogram confirms our suspects.
probabiltty densiyy
FPF
probabiltt density
PPF2
DS
MVT2
20
10
SUccess
probabillty densiey
Boosted-DS2
grobabiigg Willity density
N MAB
Aishon by Creaaa
D-MABs
Aysuap Anieeooi
Distribution of Simulator
10
success rale
Success rele
SUCCeSS rale
0.0
0.5
1.0
Figure 2: Histogram of expected reward for historical arm search.
Algorithm
FPF
PPF2
DS
Boosted-DS2
MVT2
Iteration Speed (it/s)
7.04
22.39
2.01
1.38
0.25
Table Algorithm Speed Comparison
To recognize the effectiveness of optimal selection, we leverage the average regret, convergence rate and best arm rate. We define convergence rate as proportion of trials with the most selected layout over a moving window with batch size (f, - to =) 1000. We further specify best arm rate as the proportion of trials with the best possible layout in one batch.
E(XA.) X
t (A-(A')
Average Regret
Σ
Convergence Ratelto, f.]
Σ h=1
H
T
H 4 I=to
to
h=1
1=1
H
6
LA-(A)) 1-
Best Arm Rate|to, 41]
Σ
Σ
h=1
where A and A stand for most often selected layout and best possible layout respectively within a batch. Ideally, we prefer convergence rate and best arm rate both approaching to I, which means the algorithm converges selection to single arm (convergence) fully converged batch trials almost surely select the same layout (sub-optimal) but not necessarily the global optimal layout.
well as best arm. In practice,
Simulated performance results are displayed in FigureBwhert x-axis is the time steps. Path planning algorithms demonstrate advantages base models, especially for FPF, PPF2 and Boosted-DS? We see that PPF2 and Boosted-DS2 quickly jump to low regret (and high reward) within 5000 steps, followed by FPF and MVT2 around 10000 steps. Although Boosted-DS2 and MVT2 share fastest convergence speed followed by PPF2 then FPF, but FPF holds the highest best arm rate. FPF performance in cumulative regret (and reward) catches up for longer iterations well. The intuition behind these is that FPF includes the most complex model space with considering full dimension interactions. in which it not only look from top level of decision graph quickly eliminate bad performed dimension values but also drill down to leaf arms to correct negligence from higher levels. our concern of
The exponential space complexity or computational complexity proportional FPF compared with PPF2 and Boosted-DS2.
In our experiment, PPF2, Boosted-DSS DDS2 and MVT2 assume models with pairwise interactions in one way or the other, and it happens be simulator setting, In practice extra effort is needed for correct modeling the reward function, which out of this paper's scope. PPF2 and Boosted-DS2 both efficiently achieve lower regret comparing with MVT2. However, PPF2 carries better best arm rate than Boosted-DS2. Our take-away from this is that Hill-climbing strategy contains two drawbacks. First, is equivalent to bottom-up path planning strategy in framework, which
8

---

Under review as a conference paper at ICLR 2020
0.3
0.4
0.3
0.32
23030
40C04
500000
82003
130330
40
60
batch 19 2002)
(a) Average Regret.
(b) Convergence Rate
0.3
0.4
0.3
0.1
batch
(c) Best Arm Rate
Figure 3: Performance on simulated data with = 3, N =0 3, aj = and a2 = 3-
not as efficient as top-down strategy as discussed before. Boosted-DS2 combats such weakness using TS samples top levels mimic sample draw from lower level. Second, Hill-climbing starts with randomly guess other dimension values which easily ends up with good enough arm selection (low regret and high convergence) but always the best (low best arm rate). In the meanwhile, D-MABs struggles in performance as its assumption of independence between dimensions doesn't t match with our simulator.
Although PPF2, Boosted-DS2 and MVT2 all share simplified model complexity (both in compu- tation and parameter space), however MVT2 takes longer time period per iteration compared with the other two. Table [1 shows the iteration speed of these algorithms in our implementation. In fact, MVT2 the slowest algorithm as the heavy computation burden when updating regression coefficients in posterior sampling distribution.
further extend our simulation results of average cumulative regret by varying 02 to change the strength of interactions well varying N and D to change space complexity in Fig 4 We skip MVT2 due to the time limitation (MVT2 takes 5 days per experiment). As 0g varies from 1 to with step size 6 we see the pattern consists with prior result at Fig 4a The only exception is D-MABs gets dominant regret when interaction strength is weak (0 = d. as D-MABs's 's no inter- action assumption close the truth at that time. D-MABs is equivalent with PPF1. So D-MABs should perform similarly with PPF2 when interaction strength is weak. Next we analyze the im- pact on performance with model complexity. We systematically swap N in (2, 4, 6, 8, 10, 12) and D in (2, 4, 5) at Fig 4b and 4c respectvelly We observe that the relative performance still holds: FPF PPF2 > Boosted DS DS N--MAB > D-MABs. Based on these extensive experiments, assert that proposed method is superior consistently.
In summary, our simulated results suggest that TS-PP has good performance overall for multivariate bandit problem with large search space when dimension hierarchy structure exists. FPF accom- plishes the best performance, however PPF2 attracts implementation attention due to its computa- tion efficiency with comparable performance.

---

Under review as a conference paper at ICLR 2020
N:10 11112/1/2 T-100/000
MOMA
(a) Performance when dr varies
(b) Performance when D varies
21=1// T=100,000.
340
(c) Performance when N varies
Figure 4: Cumulative Averaged Regret over number of iterations when D, N and 02 varies.
6 CONCLUSIONS
In this paper, we presented TS-PP algorithms taking advantage of the hierarchy dimension structure of bandit arms to quickly find the best arm. It utilizes decision graph/trees to model arm reward success rate with m-way dimension interaction, and adopts TS with MCTS for heuristic search of arm selection. Naturally, it is quite straightforward to combat the curse of dimensionality using serial processes that operates sequentially by focusing on one dimension per each process. Based on simulation results, it achieves superior results in terms of cumulative regret and converge speed comparing with MVT, ND-MAB and D-MABs on large decision space. We listed variations of algorithm, and concluded that FPF and PPF conduct the best performance. We highlight PPF due to its implementation simplicity but high efficiency in performance.
It is trivial extend our algorithm contextual bandit problem with finite categorical context features. But how to extend our algorithm from discrete to continuous contextual variables worth us further exploration. We notice some related work of TS-MCTS Bai et al. (2014) dealing with continuous reward in this area. Finally, fully understanding the mechanism of using heuristic greedy approach (in our method) to approximate TS from N arms is still under investigation.
REFERENCES
Rajeev Agrawal. Sample mean based index policies by (log n) regret for the multi-armed bandit problem. Advances in Applied Probability, 10544 1995.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International Conference on Machine Learning, pp. 127-135, 2013.
Peter Auer, Nicolo Cesa-Bianchi and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-256, 2002.
Aijun Bai, Feng Wu, Zongzhang Zhang, and Xiaoping Chen. Thompson sampling based monte- carlo planning in pomdps. In Twenty-Fourth International Conference on Automated Planning and Scheduling, 2014.
10

---

Under review as a conference paper at ICLR 2020
Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. A survey of monte carlo tree search methods. IEEE Transactions Computational Intelligence and Al in games, 4(1):1-43, 2012.
Sébastien Bubeck, Nicolo Cesa-Bianchi, al. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends(E) in Machine Learning, 5(1):1-122, 2012.
George Casella and Roger Berger. Statistical inference, volume Duxbury Pacific Grove, CA, 2002.
Guillaume Chaslot, Sander Bakkes, Istvan Szita, and Pieter Spronck. Monte-carlo tree search: A new framework for game ai. 2008a.
Guillaume M JB Chaslot, Mark HM Winands. H JAAP VAN DEN HERIK, Jos WHM Uiterwijk, and Bruno Bouzy. Progressive strategies for monte-carlo tree search. New Mathematies and Natural Computation, 4(03):343-357, 2008b.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff func- tions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pp. 208 214,222 2011.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit. feedback. 21st Annual Conference on Learning Theory, pp. 355-366, 2008.
Daniel N Hill, Houssam Nassif, Yi Liu, Anand Iyer, and SVN Vishwanathan. An efficient bandit algorithm for realtime multivariate optimization. In Proceedings of the 23rd ACM SIGKDD In- lernational Conference on Knowledge Discovery and Data Mining, pp. 1813-1821. ACM, 2017.
Takahisa Imagawa and Tomoyuki Kaneko. Enhancements in monte carlo tree search algorithms for biased game trees. In 2015 IEEE Conference on Computational Intelligence and Games (CIG), pp. 43-50. IEEE, 2015.
Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. pp. 193-213, 2012.
Mykel Kochenderfer. Decision making under uncertainty: theory and application. MIT press, 2015.
Levente Koesis and Csaba Szepesvári. Bandit based monte-carlo planning. In Proceedings of the 17th European Conference on Machine Learning, ECML'OK pp. 282-293, Berlin, Heidelberg, 2006. Springer-Vertiee Verlag. ISBN 3-540-45375-X, 978-3-540-45375--8 doi: 10.1007/11871842.29
URL
doi 10..
29.
Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules, Advances in applied mathematics, 6(1):4-22, 1985.
Tze Leung Lai et al. Adaptive treatment allocation and the multi-armed bandit problem. The Annals of Statistics, 15(3):009111114 1987.
Vivek Nair, Zhe Yu, Tim Menzies, Norbert Siegmund, and Sven Apel. Finding faster configurations using flash. IEEE Transactions on Software Engineering, 2018.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527-533, 1952.
Daniel Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, al. A tutorial on thompson sampling. Foundations and Trends in Machine Learning, 11(1):1-96, 2018.
Steven L Scott. A modern bayesian look at the multi-armed bandit. Applied Stochastic Models in Business and Industry, 26(6):639-66 6588, 2010.
Steven L Scott. Multi-armed bandit experiments in the online service economy. Applied Stochastic Models in Business and Industry, 31(1):37-45, 2015.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-295 1933.


Reviews:
[{"review_id": "SyghGtcCKS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes to use path planning on the tree structure for multivariate MAB problem. The idea is to model the hierarchical structure in the decision space, thus tree search idea can be applied to improve the efficiency of learning.\n\nIn general the trend of the paper is easy to follow. However, the proposed method is a bit ad-hoc and I don’t think the paper provides enough justification for it. \n1. FPF is not really practical in that it needs to main D! decision trees, each one with N^D leaves. On the other hand, other approximation methods like PPF, relies on some independence assumption. However, this paper provides not analysis about such independence even in simulations. For example, when these independence assumptions are strongly violated, what the performances would be.\n2. There is no experiments on real data. The simulation in the this paper is very specific and I am not sure how representative it could be. The simulation results don’t provide a clear message too.\n\nOther comment\n1. On page 4, why would P(f_{d1:d_D}) be propotional to P(f_{d1:d_i})? \n\n\n=========================\nAfter Rebuttal\nI don't think the rebuttal addresses my concern: the proposed method is not well justified and its performance is not really analyzed nor with convincing evidence.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Ske0qdxJ5H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper approaches the problem of exploding arms in multivariate multi-armed bandits. To solve this problem, the authors suggest an approach that uses Thompson sampling for arm selection and decision trees and graphs (inspired from Monte-Carlo tree search) to model reward success rates. They propose to versions of this path planning procedure and 2 version inspired from Hill-climbing methods. They validate their claims on a simulation showing better performance and faster convergence, and providing an extensive analysis of the results. \n\nThe idea seems novel. The paper is well structured, but the writing can be improved, and some parts are hard to read and follow (See minor comments below). \n\nHere are few questions:\n- The authors claim that the approach can be extended to categorical/numeric rewards. Can they give more details on how? \n- The experiments are done only with D=3 and N=10. How easy would it be to scale to higher dimensions?\n- In the curves of Figure 3, N^D-MAB and DS seem not converged yet contrarily to the other methods. Have the authors tried to let them run for longer to see to which values they converge? \n\nMinor comments (non-exhaustive examples): \n- Punctuation issues: \n    *Multi-Armed Bandit (MAB) problem, is widely ...\n    * Generally, RT is on the order O( T) under linear payoff settings Dani et al. (2008)Chu et al. (2011)Agrawal & Goyal (2013). Although the optimal regret of non-contextual Multivariate MAB is on the order O(logT ) ...\n\n- Imprecise statements:  ... for each combination of C (assuming not too many), ...\n\n- Sentences to rewrite: \n     * The posterior sampling distribution of reward is its likelihood integrates with some fixed prior distribution of weights μ.\n     * ..., and would call joint distribution of (A, C) and (B, C) are independent. \n     * ..., which means the algorithm converges selection to single arm (convergence) as well as best arm. \n\n- Typos: Jointly distribution/relationship -> joint ,It worth to note -> it is worth to note, extensively exam -> extensively examine, a serial processes -> process, would been -> be ...\n ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BkxkW9Yu9r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors address the curse of dimensionality in Multivariate Multi-Armed Bandits by framing the problem as a sequential planning problem.\nTheir contributions are the following:\n1. They propose to solve the Multivariate MAB sequentially across each dimension, which I think is a reasonable and not very common approach in the literature compared to e.g. structured bandits, even though the authors themselves call this approach \"natural\" and \"quite straightforward\".\n2. They propose a framework based on a Monte-Carlo Tree Search procedure to solve this sequential decision problem.\n3. They introduce several approximations and heuristics to avoid traversing the entire tree and trade-off performance for computational complexity, which they evaluate empirically.\n\nThe obtained results seem to support their original claim: the tree-based approaches (e.g. FPF) perform better than the considered baselines. However, this claim is at the same time contradicted by the fact that a depth-one planning procedure with heuristic leaf evaluation (PPF2) reaches similar performances, which indicates that the underlying problem can be solved greedily and does not involve long-term (m-way) interations and limits the interest of the main idea in this paper. This is probably due to the design of experiments which only model pairwise interactions, but then this questions the relevance of the proposed empirical evaluation with respect to the claim.\nGenerally, though several good ideas were presented, I felt that they were not properly motivated and that the paper generally lacks rigor and clarity. The many variants and modeling decisions proposed seem quite arbitrary, and in the end fail to provide any valuable insight. \n\nSeveral aspects of the proposed approach and algorithms were not clear or justified. I will list some of them, grouped by the corresponding contribution:\n\n1. Multivariate MAB framed as a planning problem.\nNo intuition is provided regarding why it is expected to perform any better than classical N^D-MAB. In this absence of assumption regarding additional structure to the problem considered (such as, say, the independence assumption in D-MABS), is there any reason to think so? (for instance, all the N^D arms are present at the leaves of the tree) The authors only mention in their conclusion that they leverage a \"hierarchy dimension structure\", but this claimed structure was is never defined nor formalized in the paper. I can only guess that such a structure would involve a particular ordering of dimensions such that shallow ones have more influence on the payoff than the deeper ones? But then, it would be unknown in practice, and the choice of the particular ordering used in TS-PP is expected to have a crucial influence on its performance. Yet, the sensitivity of their algorithms to the ordering is never discussed by the authors -they choose it arbitrarily-  nor evaluated in their experiments.\n\n2. The proposed TS-PP framework\n- The authors propose using MCTS with TS instead of UCB as a sampling rule, which they claim is quite novel: \"Applying TS as node selection policy is not well investigated from our best knowledge\". However, the authors do not mention important reference (Bai et al, 2014) until the very end of the paper in their conclusion: \"We notice some related work dealing with continuous rewards in this area\". Yet, Bai et al. also consider Bernoulli rewards in their experiments and use conjugate Beta priors, exactly like the authors of the present work do. Moreover, the choice of TS rather than UCB is not properly motivated, and the UCT algorithm is not considered as a baseline in the experiments. Hence, there is no basis to assess whether TS is particularly relevant or not for this problem.\n- They also propose to repeat S times the candidate searching procedure in Algorithm 1 in order not to be \"[stuck] in sub-optimal arms\". This property is normally ensured by optimistic sampling rules, it is not clear why it is required here. More importantly, the sensitivity of the Algorithm 1 to S is not evaluated.\n- I did not fully understand the Candidates Construction Stage in Algorithm 1. For instance, in the case of FPF, for each search c=1..S (l3) there is a call (l4) to Full Path Finding() to generate a candidate A^c. From what I understand, a random ordering is chosen (Algorithm 2, l2), and a single rollout is performed (l2, the dimensions 1->D are iterated from root to leaf) to return a candidate. When we move to the next search c -> c+1, since a new ordering d_1:D is chosen then the previous tree storing the models for p(fd_i | fd_1...fd_i-1) is not relevant anymore and must be discarded. Does that mean that the priors at the nodes are recomputed for each search/ordering/tree given the entire history, instead of being maintained and updated? The authors do state that \"FFP utilizes hidden states from the same decision tree\", but I do not see how this is feasible when the dimensions ordering changes at each iteration. \n- This confusion is related to the fact that the update of the Beta posterior does not appear anywhere in Algorithm 1 and 2. This is unfortunate, especially considering that contrary to TS in a normal MAB setting, the observations for an internal node are not i.i.d. since they depend on the underlying planning procedure, which induces a distributional drift as more sample are collected and probably make the derived posterior invalid. Has this issue been considered by the authors?\n\n3. The variants of FPF\nThe idea behind Partial-PF-m is common in the tree-search literature: to stop at early depths and use a heuristic to estimate the value at the leaf. Here, the suggestion in the particular context of Multivariate-MAB to use TS with an independence assumption (D-MABs) is interesting and sound. However, It requires the knowledge the degree m of interactions, whereas the idea of MCTS is precisely to avoid using such heuristics for leaf evaluation by replacing them without random rollouts. Other methods such as DS start at a leaf and move locally which rather resembles Hill-climbing more closely than actual Tree-Search, and I do not really see how they fit in the TS-PP framework?\n\nFinally, I found the manuscript difficult to read due to many language mistakes and typos.\n\nMinor comments:\n- The citation style is incorrect.\n- What is the point of introducing contextual MABs in the problem formulation when the context is not going to play any part whatsoever in the presented work? This only brings unnecessary complexity and impedes clarity.\n- In the experiments, H=100 replications are performed, which is appreciated, but unfortunately the corresponding confidence intervals or standard deviations are not shown, only the mean performance.\n- I found the section 3.1 unclear. Is B_A^T \\mu a dot product? Where do the coefficients of B_A or its length M appear in (1)? How is M chosen, how is B_A obtained?\n- Figure 1.a is also unclear, the graph seems to be used to define permutations/orderings of dimensions 1..D. But all paths are not valid (eg. d1 -> d2 -> d1), ad random orderings are used in Algorithm 2, so where is this graph used exactly?\n\n\n=============\nAfter Rebuttal:\nOn one hand, some of the points mentioned are now clearer (e.g. 1 & 2.2, 2.3).\nOn the other hand, most of my concerns remain valid, and some were not addressed.\nTypically, the dependency to an unknown (and undefined...) optimal ordering and the underlying optimization procedure (random search) are not properly discussed, whereas they seem central to justify the tree-based approach.\nOther remaining concerns are more generally the lack of justification and clarity of the proposed framework and implemented variants, and the inadequacy of the experiments with respect to the claim (using m=2 basically means only the first depth of the tree is useful). Therefore, I will maintain my initial score.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles the multivariate bandit problem (akin to a factorial experiment) where the player faces a sequence of decisions (that can be viewed as a tree) before obtaining a reward. The authors introduce a framework combining Thompson Sampling with path planning in trees/graphs. More specifically, they consider four path planning strategies, leading to four approaches. The resulting approaches are empirically evaluated on synthetic settings.

Unfortunately, the proposed approaches lack theoretical justification and the current experiments are not strong enough to support the claims made in the paper. Given that most of reviewer's concerns remained valid after rebuttal, I recommend to reject this paper.
Decision: Reject