nips nips2008 nips2008-17 knowledge-graph by maker-knowledge-mining

17 nips-2008-Algorithms for Infinitely Many-Armed Bandits

Source: pdf

Author: Yizao Wang, Jean-yves Audibert, Rémi Munos

Abstract: We consider multi-armed bandit problems where the number of arms is larger than the possible number of experiments. We make a stochastic assumption on the mean-reward of a new selected arm which characterizes its probability of being a near-optimal arm. Our assumption is weaker than in previous works. We describe algorithms based on upper-conﬁdence-bounds applied to a restricted set of randomly selected arms and provide upper-bounds on the resulting expected regret. We also derive a lower-bound which matches (up to a logarithmic factor) the upper-bound in some cases. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 fr Abstract We consider multi-armed bandit problems where the number of arms is larger than the possible number of experiments. [sent-6, score-0.942]

2 We make a stochastic assumption on the mean-reward of a new selected arm which characterizes its probability of being a near-optimal arm. [sent-7, score-0.413]

3 We describe algorithms based on upper-conﬁdence-bounds applied to a restricted set of randomly selected arms and provide upper-bounds on the resulting expected regret. [sent-9, score-0.761]

4 1 Introduction Multi-armed bandit problems describe typical situations where learning and optimization should be balanced in order to achieve good cumulative performances. [sent-11, score-0.269]

5 The number of arms is typically much smaller than the number of experiments allowed, so exploration of all possible options is usually performed and combined with exploitation of the apparently best ones. [sent-15, score-0.827]

6 In this paper, we investigate the case when the number of arms is inﬁnite (or larger than the available number of experiments), which makes the exploration of all the arms an impossible task to achieve: if no additional assumption is made, it may be arbitrarily hard to ﬁnd a near-optimal arm. [sent-16, score-1.504]

7 When a new arm k is pulled, its mean-reward µk is assumed to be an independent sample from a ﬁxed distribution. [sent-18, score-0.331]

8 Moreover, given the mean-reward µk for any arm k, the distribution of the reward is only required to be uniformly bounded and non-negative without any further assumption. [sent-19, score-0.383]

9 That is, given µ∗ ∈ [0, 1] as the best possible mean-reward and β ≥ 0 a parameter of the mean-reward distribution, the probability that a new arm is -optimal is of order β for small , i. [sent-21, score-0.331]

10 1 Like in multi-armed bandits, this setting exhibits a trade off between exploitation (selection of the arms that are believed to perform well) and exploration. [sent-26, score-0.746]

11 The exploration takes two forms here: discovery (pulling a new arm that has never been tried before) and sampling (pulling an arm already discovered in order to gain information about its actual mean-reward). [sent-27, score-0.781]

12 Let us write kt the arm selected by our algorithm at time t. [sent-32, score-0.391]

13 We deﬁne the regret up to time n as n Rn = nµ∗ − t=1 µkt . [sent-33, score-0.18]

14 From the tower rule, ERn is the expectation of the difference between the rewards we would have obtained by drawing an optimal arm (an arm having a mean-reward equal to µ∗ ) and the rewards we did obtain during the time steps 1, . [sent-34, score-0.834]

15 We assume that the rewards of the arms lie in [0, 1]. [sent-40, score-0.759]

16 Our regret bounds depend on ˜ whether µ∗ = 1 or µ∗ < 1. [sent-41, score-0.22]

17 in cases where there are many arms with small variance. [sent-49, score-0.673]

18 Previous works on many-armed bandits: In [5], a speciﬁc setting of an inﬁnitely many-armed bandit is considered, namely that the rewards are Bernoulli random variables with parameter p, where p follows a uniform law over a given interval [0, µ∗ ]. [sent-50, score-0.372]

19 (1) The 1-failure strategy where an arm is played as long as 1s are received. [sent-53, score-0.426]

20 When a 0 is received, a new arm is played and this strategy is repeated forever. [sent-54, score-0.426]

21 (2) The m-run strategy uses the 1-failure strategy until either m continuous 1s are received (from the same arm) or m different arms have been played. [sent-55, score-0.807]

22 In the second case, the arm that gave the most wins is chosen to play for the remaining rounds. [sent-57, score-0.364]

23 Finally, (3) the m-learning strategy uses the 1-failure strategy during the ﬁrst m rounds, and for the remaining rounds it chooses the arm that gave the most 1s during the ﬁrst m rounds. [sent-58, score-0.486]

24 √ √ For µ∗ = 1, the authors of [5] have shown that 1-failure strategy, n-run strategy, and log(n) n√ learning strategy have a regret ERn ≤ 2 n. [sent-59, score-0.247]

25 They also provided a lower bound on the regret of any √ √ strategy: ERn ≥ 2n. [sent-60, score-0.2]

26 In many applications, it is important to design algorithms having the anytime property, that is, the upper bounds on the expected regret ERn have the similar order for all n. [sent-63, score-0.349]

27 Under the same Bernoulli assumption on the reward distributions, such algorithms has been obtained in [9]. [sent-64, score-0.107]

28 In comparison to their setting (uniform distribution corresponds to β = 1), our upper- and lower√ bounds are also of order n up to a logarithmic factor, and we do not assume that we know exactly the distribution of the mean-reward. [sent-65, score-0.148]

29 However it is worth noting that the proposed algorithms in [5, 9] heavily depend on the Bernoulli assumption of the rewards and are not easily transposable to general distributions. [sent-66, score-0.141]

30 Thus an important aspect of our work, compared to previous many-armed bandits, is that our setting allows general reward distributions for the arms, under a simple assumption on the mean-reward. [sent-68, score-0.108]

31 2 2 Main results In our framework, each arm of a bandit is characterized by the distribution of the rewards (obtained by drawing that arm) and the essential parameter of the distribution of rewards is its expectation. [sent-69, score-0.772]

32 With low variance, poor arms will be easier to spot while good arms will have higher probability of not being disregarded at the beginning due to unlucky trials. [sent-71, score-1.378]

33 To draw an arm is equivalent to draw a distribution ν of mean-rewards. [sent-72, score-0.381]

34 (B) the expected reward of a randomly drawn arm satisﬁes: there exist µ∗ ∈ (0, 1] and β > 0 s. [sent-76, score-0.451]

35 It gives us (the order of) the number of arms that needs to be drawn before ﬁnding an arm that is -close to the optimum1 (i. [sent-80, score-1.024]

36 However it is convenient when the near-optimal arms have low variance (for instance, this happens when µ∗ = 1). [sent-86, score-0.717]

37 Let X k,s j=1 Xk,j and Vk,s s s 1 2 j=1 (Xk,j − X k,s ) be the empirical mean and variance associated with the ﬁrst s draws of s arm k. [sent-95, score-0.387]

38 Let Tk (t) denote the number of times arm k is chosen by the policy during the ﬁrst t plays. [sent-96, score-0.358]

39 We will use as a subroutine of our algorithms the following version of UCB (Upper Conﬁdence Bound) algorithm as introduced in [2]. [sent-97, score-0.128]

40 It will be referred to as the exploration sequence since the larger it is, the more UCB explores. [sent-99, score-0.143]

41 For any arm k and nonnegative integers s, t, introduce Bk,s,t X k,s + 2Vk,s Et 3Et + s s (3) with the convention 1/0 = +∞. [sent-100, score-0.35]

42 Deﬁne the UCB-V (for Variance estimate) policy: UCB-V policy for a set K of arms: At time t, play an arm in K maximizing Bk,Tk (t−1),t . [sent-101, score-0.391]

43 We consider nondecreasing sequence (Et ) in order that these bounds hold with probability increasing with time. [sent-104, score-0.093]

44 1 UCB revisited for the inﬁnitely many-armed bandit When the number of arms of the bandit is greater than the total number of plays, it makes no sense to apply UCB-V algorithm (or other variants of UCB [3]) since its ﬁrst step is to draw each arm once (to have Bk,Tk (t−1),t ﬁnite). [sent-107, score-1.584]

45 0 0 2 3 that only K arms will be investigated in the entire experiment. [sent-111, score-0.673]

46 The K should be sufﬁciently small with respect to n (the total number of plays), as in this way we have fewer plays on bad arms and most of the plays will be on the best of K arms. [sent-112, score-0.771]

47 The number K should not be too small either, since we want that the best of the K arms has an expected reward close to the best possible arm. [sent-113, score-0.749]

48 It is shown in [2, Theorem 4] that in the multi-armed bandit, taking a too small exploration sequence (e. [sent-114, score-0.143]

49 such as Et ≤ 1 log t) might lead to polynomial regret (instead of logarithmic for e. [sent-116, score-0.347]

50 2 Et = 2 log t) in a simple 2-armed bandit problem. [sent-118, score-0.363]

51 However, we will show that this is not the case in the inﬁnitely many-armed bandit, where one may (and should) take much smaller exploration sequences (typically of order log log t). [sent-119, score-0.307]

52 The reason for this phenomenon is that in this setting, there are typically many near-optimal arms so that the subroutine UCB-V may miss some good arms (by unlucky trials) without being hurt: there are many other near-optimal arms to discover! [sent-120, score-2.146]

53 This illustrates a trade off between the two aspects of exploration: sample the current, not well-known, arms or discover new arms. [sent-121, score-0.711]

54 We will start our analysis by considering the following UCB-V(∞) algorithm: UCB-V(∞) algorithm: Given parameters K and the exploration sequence (Et ) • Randomly choose K arms, • Run the UCB-V policy on the set of the K selected arms. [sent-122, score-0.194]

55 Proof: The UCB-V(∞) algorithm has two steps: randomly choose K arms and run a UCB subroutine on the selected arms. [sent-124, score-0.833]

56 The ﬁrst part of the proof studies what happens during the UCB subroutine, that is, conditionally to the arms that have been randomly chosen during the ﬁrst step of the algorithm. [sent-125, score-0.732]

57 This enables us to incorporate the idea that if there are a lot of near-optimal arms, it is very unlikely that suboptimal arms are often drawn. [sent-133, score-0.699]

58 Taking the expectation of both sides, using a union bound and the independence between rewards obtained from different arms, we obtain Lemma 1. [sent-137, score-0.106]

59 Now we use Inequality (6) with τ = larger than 32 2 σk ∆2 k + 1 ∆k µ∗ +µk 2 = µk + ∆k 2 = µ∗ − ∆k 2 , and u the smallest integer log n. [sent-138, score-0.094]

60 2 σk +∆k where the last inequality holds since it is equivalent to (x − 1)2 ≥ 0 for x = P(Bk,s,t > τ ) ≤ P X k,s + ≤ (7) 2 − σk ≥ ∆k /4 s 2 ≤ 2e−s∆k /(32σk +8∆k /3) , where in the last step we used Bernstein’s inequality twice. [sent-144, score-0.15]

61 For Et ≥ 2 log(10 log t), this gives P(∃s ∈ [0, t], Bk ,s,t < µk ≤ 1/2. [sent-149, score-0.094]

62 Putting all the bounds of the different terms of (6) leads to 2 2 σk 1 80σk 7 ETk (n) ≤ 1 + 32 log n + + n2−N∆k , 2 + ∆ 2 + ∆ ∆k ∆k k k with N∆k the cardinal of k ∈ {1, . [sent-150, score-0.134]

63 Since ∆k ≤ µ∗ ≤ 1 and Tk (n) ≤ n, the previous inequality can be simpliﬁed into ETk (n) ≤ 50 2 σk ∆2 k + 1 ∆k log n ∧ n + n2−N∆k , (9) Here, for the sake of simplicity, we are not interested in having tight constants. [sent-154, score-0.16]

64 From (5) and (9), we have ERn = KE T1 (n)∆1 ≤ KE 50 V (∆1 ) ∆1 + 1 log n ∧ (n∆1 ) + n∆1 2−N∆1 (10) Let p denote the probability that the expected reward µ of a randomly drawn arm satisﬁes µ > µ∗ − δ/2 for a given δ. [sent-170, score-0.545]

65 1/β ≤ for C a positive constant depending on c1 and β sufﬁciently large Let us take u1 = C log K K to ensure u1 ≥ u0 and χ(u1 ) ≤ K −1−1/β . [sent-175, score-0.167]

66 We obtain Eχ(∆1 ) ≤ CK −1/β log K for an appropriate K constant C depending on c1 and β. [sent-176, score-0.167]

67 The ﬁrst term is the bias: when we randomly draw ˜ K arms, the expected reward of the best drawn arm is O(K −1/β )-optimal. [sent-182, score-0.476]

68 So the best algorithm, −1/β ˜ once the K arms are ﬁxed, will yield a regret O(nK ). [sent-183, score-0.853]

69 2 Strategy for ﬁxed play number Consider that we know in advance the total number of plays n and the value of β. [sent-187, score-0.1]

70 UCB-F (ﬁxed horizon): given total number of plays n, and parameters µ∗ and β of (1) β n2 if β < 1, µ∗ < 1 • Choose K arms with K of order β n β+1 otherwise, i. [sent-193, score-0.722]

71 The number K of selected arms in UCB-F is taken of the order of the minimizer of these bounds up to a logarithmic factor. [sent-205, score-0.828]

72 Theorem 2 makes no difference between a logarithmic exploration sequence and an iterated logarithmic exploration sequence. [sent-206, score-0.43]

73 However in practice, it is clearly better to take an iterated logarithmic exploration sequence, for which the algorithm spends much less time on exploring all suboptimal arms. [sent-207, score-0.257]

74 It is easy to check that for Et = ζ logt and ζ ≥ 1, Inequality (12) still holds but with a constant C depending linearly in ζ. [sent-209, score-0.093]

75 The next theorem shows that our regret upper bounds are optimal up to logarithmic terms except for the case β < 1 and µ∗ < 1. [sent-211, score-0.349]

76 We do not know whether the rate O(nβ/2 log n) for β < 1 and µ∗ < 1 is improvable. [sent-212, score-0.112]

77 6 β Theorem 3 For any β > 0 and µ∗ ≤ 1, any algorithm suffers a regret larger than cn 1+β for some small enough constant c depending on c2 and β. [sent-214, score-0.325]

78 If we want to have a regret smaller than cnβ/(1+β) we need that most draws are done on an arm having an individual regret smaller than = cn−1/(1+β) . [sent-216, score-0.719]

79 To ﬁnd such an arm, we need to try a number of arms larger than C −β = C c−β nβ/(1+β) arms for some C > 0 depending on c2 and β. [sent-217, score-1.398]

80 Since these arms are drawn at least once and since most of these arms give a constant regret, it leads to a regret larger than C c−β nβ/(1+β) with C depending on c2 and β. [sent-218, score-1.619]

81 For c small enough, this contradicts that the regret is smaller than cnβ/(1+β) . [sent-219, score-0.18]

82 3 Strategy for unknown play number To apply the UCB-F algorithm we need to know the total number of plays n and we choose the corresponding K arms before starting. [sent-222, score-0.79]

83 When n is unknown ahead of time, we propose here an anytime algorithm with a simple and reasonable way of choosing K by adding a new arm from time to time into the set of sampled arms. [sent-223, score-0.421]

84 Let Kn denote the number of arms played up to time n. [sent-224, score-0.701]

85 Theorem 4 For any horizon time n ≥ 2, the expected regret of the UCB-AIR algorithm satisﬁes √ C(log n)2 n if β < 1 and µ∗ < 1 β ERn ≤ (13) 2 1+β otherwise, i. [sent-232, score-0.265]

86 3 Comparison with continuum-armed bandits and conclusion In continuum-armed bandits (see e. [sent-235, score-0.272]

87 [1, 6, 4]), an inﬁnity of arms is also considered. [sent-237, score-0.673]

88 The arms lie in some Euclidean (or metric) space and their mean-reward is a deterministic and smooth (e. [sent-238, score-0.673]

89 However, if we choose an arm-pulling strategy which consists in selecting randomly the arms, then our setting encompasses continuum-armed bandits. [sent-245, score-0.108]

90 (14) d Pulling randomly an arm X according to the Lebesgue measure on [0, 1] , we have: P(µ(X) > α µ∗ − ) = Θ(P( X − x∗ < )) = Θ( d/α ), for → 0. [sent-249, score-0.355]

91 |µ(x)−µ(y)| ≤ c x − y for 0 < α ≤ 1), [6] provides upper- and lower-bounds on the regret Rn = Θ(n(α+1)/(2α+1) ). [sent-253, score-0.18]

92 On the other hand, the zooming algorithm of [7] adapts to the smoothness of µ (more arms are ˜ sampled at areas where µ is high). [sent-260, score-0.756]

93 Under assumptions (14) we deduce d = α−1 d using α ˜ the Euclidean distance as metric, thus their regret is ERn = O(n(d(α−1)+α)/(d(α−1)+2α) ). [sent-262, score-0.18]

94 Again, we have a smaller regret although we do not use the smoothness of µ in our algorithm. [sent-266, score-0.202]

95 Hence, the comparison between the many-armed and continuum-armed bandits settings is not easy because of the difference in nature of the basis assumptions. [sent-269, score-0.136]

96 Our setting is an alternative to the continuum-armed bandit setting which does not require the existence of an underlying metric space in which the mean-reward function would be smooth. [sent-270, score-0.324]

97 For the continuum-armed bandit problems when there are relatively many near-optimal arms, our algorithm will be also competitive compared to the speciﬁcally designed continuum-armed bandit algorithms. [sent-272, score-0.555]

98 To conclude, our contributions are: (i) Compared to previous results on many-armed bandits, our setting allows general mean-reward distributions for the arms, under a simple assumption on the probability of pulling near-optimal arms. [sent-274, score-0.142]

99 (ii) We show that, for inﬁnitely many-armed bandits, we need much less exploration of each arm than for ﬁnite-armed bandits (the log term may be replaced by log log). [sent-275, score-0.774]

100 (iii) Our variant of UCB algorithm, making use of the variance estimate, enables to obtain higher rates in cases when the variance of the near-optimal arms is small. [sent-276, score-0.729]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('arms', 0.673), ('arm', 0.331), ('ern', 0.317), ('bandit', 0.269), ('regret', 0.18), ('ucb', 0.163), ('bandits', 0.136), ('exploration', 0.119), ('subroutine', 0.095), ('log', 0.094), ('rewards', 0.086), ('pulling', 0.086), ('bk', 0.079), ('anytime', 0.073), ('logarithmic', 0.073), ('etk', 0.073), ('strategy', 0.067), ('tk', 0.062), ('cn', 0.055), ('nk', 0.055), ('nitely', 0.053), ('reward', 0.052), ('depending', 0.052), ('et', 0.051), ('plays', 0.049), ('inequality', 0.048), ('horizon', 0.044), ('kn', 0.044), ('audibert', 0.044), ('zooming', 0.044), ('bounds', 0.04), ('theorem', 0.04), ('assumption', 0.039), ('exploitation', 0.035), ('maxima', 0.034), ('route', 0.034), ('play', 0.033), ('certis', 0.032), ('unlucky', 0.032), ('zk', 0.032), ('satis', 0.031), ('inria', 0.031), ('bernoulli', 0.03), ('ke', 0.029), ('nondecreasing', 0.029), ('played', 0.028), ('variance', 0.028), ('draws', 0.028), ('putting', 0.028), ('otherwise', 0.027), ('ew', 0.027), ('policy', 0.027), ('suboptimal', 0.026), ('szepesv', 0.026), ('france', 0.025), ('satisfying', 0.025), ('draw', 0.025), ('dw', 0.024), ('lder', 0.024), ('randomly', 0.024), ('selected', 0.024), ('expected', 0.024), ('sequence', 0.024), ('munos', 0.023), ('auer', 0.023), ('smoothness', 0.022), ('iterated', 0.022), ('dt', 0.022), ('constant', 0.021), ('metric', 0.021), ('rounds', 0.021), ('trade', 0.021), ('holds', 0.02), ('un', 0.02), ('drawn', 0.02), ('bound', 0.02), ('paris', 0.019), ('vn', 0.019), ('proof', 0.019), ('lipschitz', 0.019), ('nonnegative', 0.019), ('kt', 0.019), ('quantities', 0.019), ('stochastic', 0.019), ('sake', 0.018), ('minimizer', 0.018), ('es', 0.018), ('know', 0.018), ('locally', 0.018), ('ck', 0.017), ('rule', 0.017), ('last', 0.017), ('continue', 0.017), ('algorithm', 0.017), ('discover', 0.017), ('setting', 0.017), ('upper', 0.016), ('happens', 0.016), ('decide', 0.016), ('algorithms', 0.016)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 1.0000001 17 nips-2008-Algorithms for Infinitely Many-Armed Bandits

Author: Yizao Wang, Jean-yves Audibert, Rémi Munos

2 0.62348837 140 nips-2008-Mortal Multi-Armed Bandits

Author: Deepayan Chakrabarti, Ravi Kumar, Filip Radlinski, Eli Upfal

Abstract: We formulate and study a new variant of the k-armed bandit problem, motivated by e-commerce applications. In our model, arms have (stochastic) lifetime after which they expire. In this setting an algorithm needs to continuously explore new arms, in contrast to the standard k-armed bandit model in which arms are available indeﬁnitely and exploration is reduced once an optimal arm is identiﬁed with nearcertainty. The main motivation for our setting is online-advertising, where ads have limited lifetime due to, for example, the nature of their content and their campaign budgets. An algorithm needs to choose among a large collection of ads, more than can be fully explored within the typical ad lifetime. We present an optimal algorithm for the state-aware (deterministic reward function) case, and build on this technique to obtain an algorithm for the state-oblivious (stochastic reward function) case. Empirical studies on various reward distributions, including one derived from a real-world ad serving application, show that the proposed algorithms signiﬁcantly outperform the standard multi-armed bandit approaches applied to these settings. 1

3 0.42334041 170 nips-2008-Online Optimization in X-Armed Bandits

Author: Sébastien Bubeck, Gilles Stoltz, Csaba Szepesvári, Rémi Munos

Abstract: We consider a generalization of stochastic bandit problems where the set of arms, X , is allowed to be a generic topological space. We constraint the mean-payoff function with a dissimilarity function over X in a way that is more general than Lipschitz. We construct an arm selection policy whose regret improves upon previous result for a large class of problems. In particular, our results imply that if X is the unit hypercube in a Euclidean space and the mean-payoff function has a ﬁnite number of global maxima around which the behavior of the function is locally H¨ lder √ a known exponent, then the expected o with regret is bounded up to a logarithmic factor by n, i.e., the rate of the growth of the regret is independent of the dimension of the space. Moreover, we prove the minimax optimality of our algorithm for the class of mean-payoff functions we consider. 1 Introduction and motivation Bandit problems arise in many settings, including clinical trials, scheduling, on-line parameter tuning of algorithms or optimization of controllers based on simulations. In the classical bandit problem there are a ﬁnite number of arms that the decision maker can select at discrete time steps. Selecting an arm results in a random reward, whose distribution is determined by the identity of the arm selected. The distributions associated with the arms are unknown to the decision maker whose goal is to maximize the expected sum of the rewards received. In many practical situations the arms belong to a large set. This set could be continuous [1; 6; 3; 2; 7], hybrid-continuous, or it could be the space of inﬁnite sequences over a ﬁnite alphabet [4]. In this paper we consider stochastic bandit problems where the set of arms, X , is allowed to be an arbitrary topological space. We assume that the decision maker knows a dissimilarity function deﬁned over this space that constraints the shape of the mean-payoff function. In particular, the dissimilarity function is assumed to put a lower bound on the mean-payoff function from below at each maxima. We also assume that the decision maker is able to cover the space of arms in a recursive manner, successively reﬁning the regions in the covering such that the diameters of these sets shrink at a known geometric rate when measured with the dissimilarity. ∗ Csaba Szepesv´ ri is on leave from MTA SZTAKI. He also greatly acknowledges the support received from the a Alberta Ingenuity Fund, iCore and NSERC. 1 Our work generalizes and improves previous works on continuum-armed bandit problems: Kleinberg [6] and Auer et al. [2] focussed on one-dimensional problems. Recently, Kleinberg et al. [7] considered generic metric spaces assuming that the mean-payoff function is Lipschitz with respect to the (known) metric of the space. They proposed an interesting algorithm that achieves essentially the best possible regret in a minimax sense with respect to these environments. The goal of this paper is to further these works in a number of ways: (i) we allow the set of arms to be a generic topological space; (ii) we propose a practical algorithm motivated by the recent very successful tree-based optimization algorithms [8; 5; 4] and show that the algorithm is (iii) able to exploit higher order smoothness. In particular, as we shall argue in Section 7, (i) improves upon the results of Auer et al. [2], while (i), (ii) and (iii) improve upon the work of Kleinberg et al. [7]. Compared to Kleinberg et al. [7], our work represents an improvement in the fact that just like Auer et al. [2] we make use of the local properties of the mean-payoff function around the maxima only, and not a global property, such as Lipschitzness in √ the whole space. This allows us to obtain a regret which scales as O( n) 1 when e.g. the space is the unit hypercube and the mean-payoff function is locally H¨ lder with known exponent in the neighborhood of any o maxima (which are in ﬁnite number) and bounded away from the maxima outside of these neighborhoods. Thus, we get the desirable property that the rate of growth of the regret is independent of the dimensionality of the input space. We also prove a minimax lower bound that matches our upper bound up to logarithmic factors, showing that the performance of our algorithm is essentially unimprovable in a minimax sense. Besides these theoretical advances the algorithm is anytime and easy to implement. Since it is based on ideas that have proved to be efﬁcient, we expect it to perform well in practice and to make a signiﬁcant impact on how on-line global optimization is performed. 2 Problem setup, notation We consider a topological space X , whose elements will be referred to as arms. A decision maker “pulls” the arms in X one at a time at discrete time steps. Each pull results in a reward that depends on the arm chosen and which the decision maker learns of. The goal of the decision maker is to choose the arms so as to maximize the sum of the rewards that he receives. In this paper we are concerned with stochastic environments. Such an environment M associates to each arm x ∈ X a distribution Mx on the real line. The support of these distributions is assumed to be uniformly bounded with a known bound. For the sake of simplicity, we assume this bound is 1. We denote by f (x) the expectation of Mx , which is assumed to be measurable (all measurability concepts are with respect to the Borel-algebra over X ). The function f : X → R thus deﬁned is called the mean-payoff function. When in round n the decision maker pulls arm Xn ∈ X , he receives a reward Yn drawn from MXn , independently of the past arm choices and rewards. A pulling strategy of a decision maker is determined by a sequence ϕ = (ϕn )n≥1 of measurable mappings, n−1 where each ϕn maps the history space Hn = X × [0, 1] to the space of probability measures over X . By convention, ϕ1 does not take any argument. A strategy is deterministic if for every n the range of ϕn contains only Dirac distributions. According to the process that was already informally described, a pulling strategy ϕ and an environment M jointly determine a random process (X1 , Y1 , X2 , Y2 , . . .) in the following way: In round one, the decision maker draws an arm X1 at random from ϕ1 and gets a payoff Y1 drawn from MX1 . In round n ≥ 2, ﬁrst, Xn is drawn at random according to ϕn (X1 , Y1 , . . . , Xn−1 , Yn−1 ), but otherwise independently of the past. Then the decision maker gets a rewards Yn drawn from MXn , independently of all other random variables in the past given Xn . Let f ∗ = supx∈X f (x) be the maximal expected payoff. The cumulative regret of a pulling strategy in n n environment M is Rn = n f ∗ − t=1 Yt , and the cumulative pseudo-regret is Rn = n f ∗ − t=1 f (Xt ). 1 We write un = O(vu ) when un = O(vn ) up to a logarithmic factor. 2 In the sequel, we restrict our attention to the expected regret E [Rn ], which in fact equals E[Rn ], as can be seen by the application of the tower rule. 3 3.1 The Hierarchical Optimistic Optimization (HOO) strategy Trees of coverings We ﬁrst introduce the notion of a tree of coverings. Our algorithm will require such a tree as an input. Deﬁnition 1 (Tree of coverings). A tree of coverings is a family of measurable subsets (Ph,i )1≤i≤2h , h≥0 of X such that for all ﬁxed integer h ≥ 0, the covering ∪1≤i≤2h Ph,i = X holds. Moreover, the elements of the covering are obtained recursively: each subset Ph,i is covered by the two subsets Ph+1,2i−1 and Ph+1,2i . A tree of coverings can be represented, as the name suggests, by a binary tree T . The whole domain X = P0,1 corresponds to the root of the tree and Ph,i corresponds to the i–th node of depth h, which will be referred to as node (h, i) in the sequel. The fact that each Ph,i is covered by the two subsets Ph+1,2i−1 and Ph+1,2i corresponds to the childhood relationship in the tree. Although the deﬁnition allows the childregions of a node to cover a larger part of the space, typically the size of the regions shrinks as depth h increases (cf. Assumption 1). Remark 1. Our algorithm will instantiate the nodes of the tree on an ”as needed” basis, one by one. In fact, at any round n it will only need n nodes connected to the root. 3.2 Statement of the HOO strategy The algorithm picks at each round a node in the inﬁnite tree T as follows. In the ﬁrst round, it chooses the root node (0, 1). Now, consider round n + 1 with n ≥ 1. Let us denote by Tn the set of nodes that have been picked in previous rounds and by Sn the nodes which are not in Tn but whose parent is. The algorithm picks at round n + 1 a node (Hn+1 , In+1 ) ∈ Sn according to the deterministic rule that will be described below. After selecting the node, the algorithm further chooses an arm Xn+1 ∈ PHn+1 ,In+1 . This selection can be stochastic or deterministic. We do not put any further restriction on it. The algorithm then gets a reward Yn+1 as described above and the procedure goes on: (Hn+1 , In+1 ) is added to Tn to form Tn+1 and the children of (Hn+1 , In+1 ) are added to Sn to give rise to Sn+1 . Let us now turn to how (Hn+1 , In+1 ) is selected. Along with the nodes the algorithm stores what we call B–values. The node (Hn+1 , In+1 ) ∈ Sn to expand at round n + 1 is picked by following a path from the root to a node in Sn , where at each node along the path the child with the larger B–value is selected (ties are broken arbitrarily). In order to deﬁne a node’s B–value, we need a few quantities. Let C(h, i) be the set that collects (h, i) and its descendants. We let n Nh,i (n) = I{(Ht ,It )∈C(h,i)} t=1 be the number of times the node (h, i) was visited. A given node (h, i) is always picked at most once, but since its descendants may be picked afterwards, subsequent paths in the tree can go through it. Consequently, 1 ≤ Nh,i (n) ≤ n for all nodes (h, i) ∈ Tn . Let µh,i (n) be the empirical average of the rewards received for the time-points when the path followed by the algorithm went through (h, i): n 1 µh,i (n) = Yt I{(Ht ,It )∈C(h,i)} . Nh,i (n) t=1 The corresponding upper conﬁdence bound is by deﬁnition Uh,i (n) = µh,i (n) + 3 2 ln n + ν 1 ρh , Nh,i (n) where 0 < ρ < 1 and ν1 > 0 are parameters of the algorithm (to be chosen later by the decision maker, see Assumption 1). For nodes not in Tn , by convention, Uh,i (n) = +∞. Now, for a node (h, i) in Sn , we deﬁne its B–value to be Bh,i (n) = +∞. The B–values for nodes in Tn are given by Bh,i (n) = min Uh,i (n), max Bh+1,2i−1 (n), Bh+1,2i (n) . Note that the algorithm is deterministic (apart, maybe, from the arbitrary random choice of Xt in PHt ,It ). Its total space requirement is linear in n while total running time at round n is at most quadratic in n, though we conjecture that it is O(n log n) on average. 4 Assumptions made on the model and statement of the main result We suppose that X is equipped with a dissimilarity , that is a non-negative mapping : X 2 → R satisfying (x, x) = 0. The diameter (with respect to ) of a subset A of X is given by diam A = supx,y∈A (x, y). Given the dissimilarity , the “open” ball with radius ε > 0 and center c ∈ X is B(c, ε) = { x ∈ X : (c, x) < ε } (we do not require the topology induced by to be related to the topology of X .) In what follows when we refer to an (open) ball, we refer to the ball deﬁned with respect to . The dissimilarity will be used to capture the smoothness of the mean-payoff function. The decision maker chooses and the tree of coverings. The following assumption relates this choice to the parameters ρ and ν1 of the algorithm: Assumption 1. There exist ρ < 1 and ν1 , ν2 > 0 such that for all integers h ≥ 0 and all i = 1, . . . , 2h , the diameter of Ph,i is bounded by ν1 ρh , and Ph,i contains an open ball Ph,i of radius ν2 ρh . For a given h, the Ph,i are disjoint for 1 ≤ i ≤ 2h . Remark 2. A typical choice for the coverings in a cubic domain is to let the domains be hyper-rectangles. They can be obtained, e.g., in a dyadic manner, by splitting at each step hyper-rectangles in the middle along their longest side, in an axis parallel manner; if all sides are equal, we split them along the√ axis. In ﬁrst this example, if X = [0, 1]D and (x, y) = x − y α then we can take ρ = 2−α/D , ν1 = ( D/2)α and ν2 = 1/8α . The next assumption concerns the environment. Deﬁnition 2. We say that f is weakly Lipschitz with respect to if for all x, y ∈ X , f ∗ − f (y) ≤ f ∗ − f (x) + max f ∗ − f (x), (x, y) . (1) Note that weak Lipschitzness is satisﬁed whenever f is 1–Lipschitz, i.e., for all x, y ∈ X , one has |f (x) − f (y)| ≤ (x, y). On the other hand, weak Lipschitzness implies local (one-sided) 1–Lipschitzness at any maxima. Indeed, at an optimal arm x∗ (i.e., such that f (x∗ ) = f ∗ ), (1) rewrites to f (x∗ ) − f (y) ≤ (x∗ , y). However, weak Lipschitzness does not constraint the growth of the loss in the vicinity of other points. Further, weak Lipschitzness, unlike Lipschitzness, does not constraint the local decrease of the loss at any point. Thus, weak-Lipschitzness is a property that lies somewhere between a growth condition on the loss around optimal arms and (one-sided) Lipschitzness. Note that since weak Lipschitzness is deﬁned with respect to a dissimilarity, it can actually capture higher-order smoothness at the optima. For example, f (x) = 1 − x2 is weak Lipschitz with the dissimilarity (x, y) = c(x − y)2 for some appropriate constant c. Assumption 2. The mean-payoff function f is weakly Lipschitz. ∗ ∗ Let fh,i = supx∈Ph,i f (x) and ∆h,i = f ∗ − fh,i be the suboptimality of node (h, i). We say that def a node (h, i) is optimal (respectively, suboptimal) if ∆h,i = 0 (respectively, ∆h,i > 0). Let Xε = { x ∈ X : f (x) ≥ f ∗ − ε } be the set of ε-optimal arms. The following result follows from the deﬁnitions; a proof can be found in the appendix. 4 Lemma 1. Let Assumption 1 and 2 hold. If the suboptimality ∆h,i of a region is bounded by cν1 ρh for some c > 0, then all arms in Ph,i are max{2c, c + 1}ν1 ρh -optimal. The last assumption is closely related to Assumption 2 of Auer et al. [2], who observed that the regret of a continuum-armed bandit algorithm should depend on how fast the volume of the sets of ε-optimal arms shrinks as ε → 0. Here, we capture this by deﬁning a new notion, the near-optimality dimension of the mean-payoff function. The connection between these concepts, as well as the zooming dimension deﬁned by Kleinberg et al. [7] will be further discussed in Section 7. Deﬁne the packing number P(X , , ε) to be the size of the largest packing of X with disjoint open balls of radius ε with respect to the dissimilarity .2 We now deﬁne the near-optimality dimension, which characterizes the size of the sets Xε in terms of ε, and then state our main result. Deﬁnition 3. For c > 0 and ε0 > 0, the (c, ε0 )–near-optimality dimension of f with respect to equals inf d ∈ [0, +∞) : ∃ C s.t. ∀ε ≤ ε0 , P Xcε , , ε ≤ C ε−d (2) (with the usual convention that inf ∅ = +∞). Theorem 1 (Main result). Let Assumptions 1 and 2 hold and assume that the (4ν1 /ν2 , ν2 )–near-optimality dimension of the considered environment is d < +∞. Then, for any d > d there exists a constant C(d ) such that for all n ≥ 1, ERn ≤ C(d ) n(d +1)/(d +2) ln n 1/(d +2) . Further, if the near-optimality dimension is achieved, i.e., the inﬁmum is achieved in (2), then the result holds also for d = d. Remark 3. We can relax the weak-Lipschitz property by requiring it to hold only locally around the maxima. In fact, at the price of increased constants, the result continues to hold if there exists ε > 0 such that (1) holds for any x, y ∈ Xε . To show this we only need to carefully adapt the steps of the proof below. We omit the details from this extended abstract. 5 Analysis of the regret and proof of the main result We ﬁrst state three lemmas, whose proofs can be found in the appendix. The proofs of Lemmas 3 and 4 rely on concentration-of-measure techniques, while that of Lemma 2 follows from a simple case study. Let us ﬁx some path (0, 1), (1, i∗ ), . . . , (h, i∗ ), . . . , of optimal nodes, starting from the root. 1 h Lemma 2. Let (h, i) be a suboptimal node. Let k be the largest depth such that (k, i∗ ) is on the path from k the root to (h, i). Then we have n E Nh,i (n) ≤ u+ P Nh,i (t) > u and Uh,i (t) > f ∗ or Us,i∗ ≤ f ∗ for some s ∈ {k+1, . . . , t−1} s t=u+1 Lemma 3. Let Assumptions 1 and 2 hold. 1, P Uh,i (n) ≤ f ∗ ≤ n−3 . Then, for all optimal nodes and for all integers n ≥ Lemma 4. Let Assumptions 1 and 2 hold. Then, for all integers t ≤ n, for all suboptimal nodes (h, i) 8 ln such that ∆h,i > ν1 ρh , and for all integers u ≥ 1 such that u ≥ (∆h,i −νnρh )2 , one has P Uh,i (t) > 1 f ∗ and Nh,i (t) > u ≤ t n−4 . 2 Note that sometimes packing numbers are deﬁned as the largest packing with disjoint open balls of radius ε/2, or, ε-nets. 5 . Taking u as the integer part of (8 ln n)/(∆h,i − ν1 ρh )2 , and combining the results of Lemma 2, 3, and 4 with a union bound leads to the following key result. Lemma 5. Under Assumptions 1 and 2, for all suboptimal nodes (h, i) such that ∆h,i > ν1 ρh , we have, for all n ≥ 1, 8 ln n 2 E[Nh,i (n)] ≤ + . (∆h,i − ν1 ρh )2 n We are now ready to prove Theorem 1. Proof. For the sake of simplicity we assume that the inﬁmum in the deﬁnition of near-optimality is achieved. To obtain the result in the general case one only needs to replace d below by d > d in the proof below. First step. For all h = 1, 2, . . ., denote by Ih the nodes at depth h that are 2ν1 ρh –optimal, i.e., the nodes ∗ (h, i) such that fh,i ≥ f ∗ − 2ν1 ρh . Then, I is the union of these sets of nodes. Further, let J be the set of nodes that are not in I but whose parent is in I. We then denote by Jh the nodes in J that are located at depth h in the tree. Lemma 4 bounds the expected number of times each node (h, i) ∈ Jh is visited. Since ∆h,i > 2ν1 ρh , we get 8 ln n 2 E Nh,i (n) ≤ 2 2h + . ν1 ρ n Second step. We bound here the cardinality |Ih |, h > 0. If (h, i) ∈ Ih then since ∆h,i ≤ 2ν1 ρh , by Lemma 1 Ph,i ⊂ X4ν1 ρh . Since by Assumption 1, the sets (Ph,i ), for (h, i) ∈ Ih , contain disjoint balls of radius ν2 ρh , we have that |Ih | ≤ P ∪(h,i)∈Ih Ph,i , , ν2 ρh ≤ P X(4ν1 /ν2 ) ν2 ρh , , ν2 ρh ≤ C ν2 ρh −d , where we used the assumption that d is the (4ν1 /ν2 , ν2 )–near-optimality dimension of f (and C is the constant introduced in the deﬁnition of the near-optimality dimension). Third step. Choose η > 0 and let H be the smallest integer such that ρH ≤ η. We partition the inﬁnite tree T into three sets of nodes, T = T1 ∪ T2 ∪ T3 . The set T1 contains nodes of IH and their descendants, T2 = ∪0≤h < 1 and then, by optimizing over ρH (the worst value being ρH ∼ ( ln n )−1/(d+2) ). 6 Minimax optimality The packing dimension of a set X is the smallest d such that there exists a constant k such that for all ε > 0, P X , , ε ≤ k ε−d . For instance, compact subsets of Rd (with non-empty interior) have a packing dimension of d whenever is a norm. If X has a packing dimension of d, then all environments have a near-optimality dimension less than d. The proof of the main theorem indicates that the constant C(d) only depends on d, k (of the deﬁnition of packing dimension), ν1 , ν2 , and ρ, but not on the environment as long as it is weakly Lipschitz. Hence, we can extract from it a distribution-free bound of the form O(n(d+1)/(d+2) ). In fact, this bound can be shown to be optimal as is illustrated by the theorem below, whose assumptions are satisﬁed by, e.g., compact subsets of Rd and if is some norm of Rd . The proof can be found in the appendix. Theorem 2. If X is such that there exists c > 0 with P(X , , ε) ≥ c ε−d ≥ 2 for all ε ≤ 1/4 then for all n ≥ 4d−1 c/ ln(4/3), all strategies ϕ are bound to suffer a regret of at least 2/(d+2) 1 1 c n(d+1)/(d+2) , 4 4 4 ln(4/3) where the supremum is taken over all environments with weakly Lipschitz payoff functions. sup E Rn (ϕ) ≥ 7 Discussion Several works [1; 6; 3; 2; 7] have considered continuum-armed bandits in Euclidean or metric spaces and provided upper- and lower-bounds on the regret for given classes of environments. Cope [3] derived a regret √ of O( n) for compact and convex subset of Rd and a mean-payoff function with unique minima and second order smoothness. Kleinberg [6] considered mean-payoff functions f on the real line that are H¨ lder with o degree 0 < α ≤ 1. The derived regret is Θ(n(α+1)/(α+2) ). Auer et al. [2] extended the analysis to classes of functions with only a local H¨ lder assumption around maximum (with possibly higher smoothness degree o 1+α−αβ α ∈ [0, ∞)), and derived the regret Θ(n 1+2α−αβ ), where β is such that the Lebesgue measure of ε-optimal 7 states is O(εβ ). Another setting is that of [7] who considered a metric space (X , ) and assumed that f is Lipschitz w.r.t. . The obtained regret is O(n(d+1)/(d+2) ) where d is the zooming dimension (deﬁned similarly to our near-optimality dimension, but using covering numbers instead of packing numbers and the sets Xε \ Xε/2 ). When (X , ) is a metric space covering and packing numbers are equivalent and we may prove that the zooming dimension and near-optimality dimensions are equal. Our main contribution compared to [7] is that our weak-Lipschitz assumption, which is substantially weaker than the global Lipschitz assumption assumed in [7], enables our algorithm to work better in some common situations, such as when the mean-payoff function assumes a local smoothness whose order is larger than one. In order to relate all these results, let us consider a speciﬁc example: Let X = [0, 1]D and assume that the mean-reward function f is locally equivalent to a H¨ lder function with degree α ∈ [0, ∞) around any o maxima x∗ of f (the number of maxima is assumed to be ﬁnite): f (x∗ ) − f (x) = Θ(||x − x∗ ||α ) as x → x∗ . (3) This means that ∃c1 , c2 , ε0 > 0, ∀x, s.t. ||x − x∗ || ≤ ε0 , c1 ||x − x∗ ||α ≤ f (x∗ ) − f (x) ≤ c2 ||x − x∗ ||α . √ Under this assumption, the result of Auer et al. [2] shows that for D = 1, the regret is Θ( n) (since here √ β = 1/α). Our result allows us to extend the n regret rate to any dimension D. Indeed, if we choose our def dissimilarity measure to be α (x, y) = ||x − y||α , we may prove that f satisﬁes a locally weak-Lipschitz √ condition (as deﬁned in Remark 3) and that the near-optimality dimension is 0. Thus our regret is O( n), i.e., the rate is independent of the dimension D. In comparison, since Kleinberg et al. [7] have to satisfy a global Lipschitz assumption, they can not use α when α > 1. Indeed a function globally Lipschitz with respect to α is essentially constant. Moreover α does not deﬁne a metric for α > 1. If one resort to the Euclidean metric to fulﬁll their requirement that f be Lipschitz w.r.t. the metric then the zooming dimension becomes D(α − 1)/α, while the regret becomes √ O(n(D(α−1)+α)/(D(α−1)+2α) ), which is strictly worse than O( n) and in fact becomes close to the slow rate O(n(D+1)/(D+2) ) when α is larger. Nevertheless, in the case of α ≤ 1 they get the same regret rate. In contrast, our result shows that under very weak constraints on the mean-payoff function and if the local behavior of the function around its maximum (or ﬁnite number of maxima) is known then global optimization √ suffers a regret of order O( n), independent of the space dimension. As an interesting sidenote let us also remark that our results allow different smoothness orders along different dimensions, i.e., heterogenous smoothness spaces. References [1] R. Agrawal. The continuum-armed bandit problem. SIAM J. Control and Optimization, 33:1926–1951, 1995. [2] P. Auer, R. Ortner, and Cs. Szepesv´ ri. Improved rates for the stochastic continuum-armed bandit problem. 20th a Conference on Learning Theory, pages 454–468, 2007. [3] E. Cope. Regret and convergence bounds for immediate-reward reinforcement learning with continuous action spaces. Preprint, 2004. [4] P.-A. Coquelin and R. Munos. Bandit algorithms for tree search. In Proceedings of 23rd Conference on Uncertainty in Artiﬁcial Intelligence, 2007. [5] S. Gelly, Y. Wang, R. Munos, and O. Teytaud. Modiﬁcation of UCT with patterns in Monte-Carlo go. Technical Report RR-6062, INRIA, 2006. [6] R. Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. In 18th Advances in Neural Information Processing Systems, 2004. [7] R. Kleinberg, A. Slivkins, and E. Upfal. Multi-armed bandits in metric spaces. In Proceedings of the 40th ACM Symposium on Theory of Computing, 2008. [8] L. Kocsis and Cs. Szepesv´ ri. Bandit based Monte-Carlo planning. In Proceedings of the 15th European Conference a on Machine Learning, pages 282–293, 2006. 8

4 0.41241208 223 nips-2008-Structure Learning in Human Sequential Decision-Making

Author: Daniel Acuna, Paul R. Schrater

Abstract: We use graphical models and structure learning to explore how people learn policies in sequential decision making tasks. Studies of sequential decision-making in humans frequently ﬁnd suboptimal performance relative to an ideal actor that knows the graph model that generates reward in the environment. We argue that the learning problem humans face also involves learning the graph structure for reward generation in the environment. We formulate the structure learning problem using mixtures of reward models, and solve the optimal action selection problem using Bayesian Reinforcement Learning. We show that structure learning in one and two armed bandit problems produces many of the qualitative behaviors deemed suboptimal in previous studies. Our argument is supported by the results of experiments that demonstrate humans rapidly learn and exploit new reward structure. 1

5 0.11954117 150 nips-2008-Near-optimal Regret Bounds for Reinforcement Learning

Author: Peter Auer, Thomas Jaksch, Ronald Ortner

Abstract: For undiscounted reinforcement learning in Markov decision processes (MDPs) we consider the total regret of a learning algorithm with respect to an optimal policy. In order to describe the transition structure of an MDP we propose a new parameter: An MDP has diameter D if for any pair of states s, s there is a policy which moves from s to s in at most D steps (on average). We present a rein√ ˜ forcement learning algorithm with total regret O(DS AT ) after T steps for any unknown MDP with S states, A actions per state, and diameter D. This bound holds with high probability. We also present a corresponding lower bound of √ Ω( DSAT ) on the total regret of any learning algorithm. 1

6 0.0745214 133 nips-2008-Mind the Duality Gap: Logarithmic regret algorithms for online optimization

7 0.0739941 123 nips-2008-Linear Classification and Selective Sampling Under Low Noise Conditions

8 0.069782525 161 nips-2008-On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization

9 0.062905937 164 nips-2008-On the Generalization Ability of Online Strongly Convex Programming Algorithms

10 0.060879104 144 nips-2008-Multi-resolution Exploration in Continuous Spaces

11 0.056117464 125 nips-2008-Local Gaussian Process Regression for Real Time Online Model Learning

12 0.052452996 22 nips-2008-An Online Algorithm for Maximizing Submodular Functions

13 0.047976397 181 nips-2008-Policy Search for Motor Primitives in Robotics

14 0.045829013 37 nips-2008-Biasing Approximate Dynamic Programming with a Lower Discount Factor

15 0.044091564 195 nips-2008-Regularized Policy Iteration

16 0.042419981 214 nips-2008-Sparse Online Learning via Truncated Gradient

17 0.036450148 40 nips-2008-Bounds on marginal probability distributions

18 0.035781551 245 nips-2008-Unlabeled data: Now it helps, now it doesn't

19 0.034746025 131 nips-2008-MDPs with Non-Deterministic Policies

20 0.032957401 2 nips-2008-A Convex Upper Bound on the Log-Partition Function for Binary Distributions

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.143), (1, 0.311), (2, -0.181), (3, -0.17), (4, -0.342), (5, -0.484), (6, -0.251), (7, 0.055), (8, 0.048), (9, 0.073), (10, 0.081), (11, -0.215), (12, -0.056), (13, 0.027), (14, -0.084), (15, -0.029), (16, -0.012), (17, 0.022), (18, -0.017), (19, -0.013), (20, 0.028), (21, 0.027), (22, -0.007), (23, -0.03), (24, 0.0), (25, 0.067), (26, -0.043), (27, 0.027), (28, -0.016), (29, -0.004), (30, 0.003), (31, -0.001), (32, -0.052), (33, 0.02), (34, 0.04), (35, 0.001), (36, -0.05), (37, 0.015), (38, -0.027), (39, -0.036), (40, -0.033), (41, 0.02), (42, 0.017), (43, -0.01), (44, -0.043), (45, 0.018), (46, -0.018), (47, -0.007), (48, -0.043), (49, -0.001)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.97486949 140 nips-2008-Mortal Multi-Armed Bandits

Author: Deepayan Chakrabarti, Ravi Kumar, Filip Radlinski, Eli Upfal

same-paper 2 0.96045494 17 nips-2008-Algorithms for Infinitely Many-Armed Bandits

Author: Yizao Wang, Jean-yves Audibert, Rémi Munos

3 0.75558138 170 nips-2008-Online Optimization in X-Armed Bandits

Author: Sébastien Bubeck, Gilles Stoltz, Csaba Szepesvári, Rémi Munos

4 0.7444821 223 nips-2008-Structure Learning in Human Sequential Decision-Making

Author: Daniel Acuna, Paul R. Schrater

5 0.30622071 150 nips-2008-Near-optimal Regret Bounds for Reinforcement Learning

Author: Peter Auer, Thomas Jaksch, Ronald Ortner

6 0.23923689 22 nips-2008-An Online Algorithm for Maximizing Submodular Functions

7 0.19642283 187 nips-2008-Psychiatry: Insights into depression through normative decision-making models

8 0.18515418 144 nips-2008-Multi-resolution Exploration in Continuous Spaces

9 0.17076592 169 nips-2008-Online Models for Content Optimization

10 0.17034982 222 nips-2008-Stress, noradrenaline, and realistic prediction of mouse behaviour using reinforcement learning

11 0.16313946 123 nips-2008-Linear Classification and Selective Sampling Under Low Noise Conditions

12 0.16302623 94 nips-2008-Goal-directed decision making in prefrontal cortex: a computational framework

13 0.16240208 149 nips-2008-Near-minimax recursive density estimation on the binary hypercube

14 0.15738513 37 nips-2008-Biasing Approximate Dynamic Programming with a Lower Discount Factor

15 0.15518859 85 nips-2008-Fast Rates for Regularized Objectives

16 0.1539028 125 nips-2008-Local Gaussian Process Regression for Real Time Online Model Learning

17 0.15043588 39 nips-2008-Bounding Performance Loss in Approximate MDP Homomorphisms

18 0.14783035 133 nips-2008-Mind the Duality Gap: Logarithmic regret algorithms for online optimization

19 0.14691927 161 nips-2008-On the Complexity of Linear Prediction: Risk Bounds, Margin Bounds, and Regularization

20 0.14233182 245 nips-2008-Unlabeled data: Now it helps, now it doesn't

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(6, 0.067), (7, 0.036), (12, 0.087), (28, 0.169), (57, 0.046), (59, 0.016), (63, 0.033), (71, 0.024), (77, 0.079), (78, 0.026), (83, 0.023), (94, 0.292)]

similar papers list:

simIndex simValue paperId paperTitle

1 0.77948886 136 nips-2008-Model selection and velocity estimation using novel priors for motion patterns

Author: Shuang Wu, Hongjing Lu, Alan L. Yuille

Abstract: Psychophysical experiments show that humans are better at perceiving rotation and expansion than translation. These ﬁndings are inconsistent with standard models of motion integration which predict best performance for translation [6]. To explain this discrepancy, our theory formulates motion perception at two levels of inference: we ﬁrst perform model selection between the competing models (e.g. translation, rotation, and expansion) and then estimate the velocity using the selected model. We deﬁne novel prior models for smooth rotation and expansion using techniques similar to those in the slow-and-smooth model [17] (e.g. Green functions of differential operators). The theory gives good agreement with the trends observed in human experiments. 1

same-paper 2 0.75475383 17 nips-2008-Algorithms for Infinitely Many-Armed Bandits

Author: Yizao Wang, Jean-yves Audibert, Rémi Munos

3 0.7408179 215 nips-2008-Sparse Signal Recovery Using Markov Random Fields

Author: Volkan Cevher, Marco F. Duarte, Chinmay Hegde, Richard Baraniuk

Abstract: Compressive Sensing (CS) combines sampling and compression into a single subNyquist linear measurement process for sparse and compressible signals. In this paper, we extend the theory of CS to include signals that are concisely represented in terms of a graphical model. In particular, we use Markov Random Fields (MRFs) to represent sparse signals whose nonzero coefﬁcients are clustered. Our new model-based recovery algorithm, dubbed Lattice Matching Pursuit (LaMP), stably recovers MRF-modeled signals using many fewer measurements and computations than the current state-of-the-art algorithms.

4 0.71320391 60 nips-2008-Designing neurophysiology experiments to optimally constrain receptive field models along parametric submanifolds

Author: Jeremy Lewi, Robert Butera, David M. Schneider, Sarah Woolley, Liam Paninski

Abstract: Sequential optimal design methods hold great promise for improving the efﬁciency of neurophysiology experiments. However, previous methods for optimal experimental design have incorporated only weak prior information about the underlying neural system (e.g., the sparseness or smoothness of the receptive ﬁeld). Here we describe how to use stronger prior information, in the form of parametric models of the receptive ﬁeld, in order to construct optimal stimuli and further improve the efﬁciency of our experiments. For example, if we believe that the receptive ﬁeld is well-approximated by a Gabor function, then our method constructs stimuli that optimally constrain the Gabor parameters (orientation, spatial frequency, etc.) using as few experimental trials as possible. More generally, we may believe a priori that the receptive ﬁeld lies near a known sub-manifold of the full parameter space; in this case, our method chooses stimuli in order to reduce the uncertainty along the tangent space of this sub-manifold as rapidly as possible. Applications to simulated and real data indicate that these methods may in many cases improve the experimental efﬁciency. 1

5 0.59220815 170 nips-2008-Online Optimization in X-Armed Bandits

Author: Sébastien Bubeck, Gilles Stoltz, Csaba Szepesvári, Rémi Munos

6 0.57515633 216 nips-2008-Sparse probabilistic projections

7 0.57299179 49 nips-2008-Clusters and Coarse Partitions in LP Relaxations

8 0.57254171 223 nips-2008-Structure Learning in Human Sequential Decision-Making

9 0.57176244 40 nips-2008-Bounds on marginal probability distributions

10 0.57155609 195 nips-2008-Regularized Policy Iteration

11 0.57113874 50 nips-2008-Continuously-adaptive discretization for message-passing algorithms

12 0.5659098 96 nips-2008-Hebbian Learning of Bayes Optimal Decisions

13 0.56564689 44 nips-2008-Characteristic Kernels on Groups and Semigroups

14 0.56473523 118 nips-2008-Learning Transformational Invariants from Natural Movies

15 0.56458473 177 nips-2008-Particle Filter-based Policy Gradient in POMDPs

16 0.56430209 205 nips-2008-Semi-supervised Learning with Weakly-Related Unlabeled Data : Towards Better Text Categorization

17 0.56393546 37 nips-2008-Biasing Approximate Dynamic Programming with a Lower Discount Factor

18 0.56389058 133 nips-2008-Mind the Duality Gap: Logarithmic regret algorithms for online optimization

19 0.56376386 162 nips-2008-On the Design of Loss Functions for Classification: theory, robustness to outliers, and SavageBoost

20 0.5635736 88 nips-2008-From Online to Batch Learning with Cutoff-Averaging