nips nips2010 nips2010-196 knowledge-graph by maker-knowledge-mining

196 nips-2010-Online Markov Decision Processes under Bandit Feedback

Source: pdf

Author: Gergely Neu, Andras Antos, András György, Csaba Szepesvári

Abstract: We consider online learning in ﬁnite stochastic Markovian environments where in each time step a new reward function is chosen by an oblivious adversary. The goal of the learning agent is to compete with the best stationary policy in terms of the total reward received. In each time step the agent observes the current state and the reward associated with the last transition, however, the agent does not observe the rewards associated with other state-action pairs. The agent is assumed to know the transition probabilities. The state of the art result for this setting is a no-regret algorithm. In this paper we propose a new learning algorithm and, assuming that stationary policies mix uniformly fast, we show that after T time steps, the expected regret of the new algorithm is O T 2/3 (ln T )1/3 , giving the ﬁrst rigorously proved regret bound for the problem. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 hu Abstract We consider online learning in ﬁnite stochastic Markovian environments where in each time step a new reward function is chosen by an oblivious adversary. [sent-8, score-0.486]

2 The goal of the learning agent is to compete with the best stationary policy in terms of the total reward received. [sent-9, score-1.015]

3 In each time step the agent observes the current state and the reward associated with the last transition, however, the agent does not observe the rewards associated with other state-action pairs. [sent-10, score-1.133]

4 The agent is assumed to know the transition probabilities. [sent-11, score-0.366]

5 In this paper we propose a new learning algorithm and, assuming that stationary policies mix uniformly fast, we show that after T time steps, the expected regret of the new algorithm is O T 2/3 (ln T )1/3 , giving the ﬁrst rigorously proved regret bound for the problem. [sent-13, score-1.017]

6 The formal problem deﬁnition is as follows: An agent navigates in a ﬁnite stochastic environment by selecting actions based on the states and rewards experienced previously. [sent-15, score-0.449]

7 At each time instant the agent observes the reward associated with the last transition and the current state, that is, at time t + 1 the agent observes rt (xt , at ), where xt is the state visited at time t and at is the action chosen. [sent-16, score-1.948]

8 The agent does not observe the rewards associated with other transitions, that is, the agent ˆ faces a bandit situation. [sent-17, score-0.868]

9 The goal of the agent is to maximize its total expected reward RT in T steps. [sent-18, score-0.668]

10 As opposed to the standard MDP setting, the reward function at each time step may be different. [sent-19, score-0.35]

11 The only assumption about this sequence of reward functions rt is that they are chosen ahead of time, independently of how the agent acts. [sent-20, score-1.011]

12 Assuming that the stationary distributions underlying stationary policies exist, are unique and they are uniformly bounded away from zero and 1 that these policies mix uniformly fast, our main result shows that the total expected regret of our algorithm in T time steps is O T 2/3 (ln T )1/3 . [sent-24, score-1.152]

13 (2005, 2009) is that they assume that the reward function is fully observed (i. [sent-29, score-0.293]

14 , in each time step the learning agent observes the whole reward function rt ), whereas we consider the bandit setting. [sent-31, score-1.3]

15 The main result in these works is a bound on the total expected regret, which scales with the square root of the number of time steps under mixing assumptions identical to our assumptions. [sent-32, score-0.285]

16 (2009) who proposed new algorithms and proved a bound on the expected regret of order O T 3/4+ε for arbitrary ε ∈ (0, 1/3). [sent-34, score-0.39]

17 The requirement that the full reward function must be given to the agent at every time step signiﬁcantly limits their applicability. [sent-41, score-0.672]

18 There are only three papers that we know of where the bandit situation was considered. [sent-42, score-0.204]

19 (2010) gave O T regret bounds for a special bandit setting when the agent interacts with a loop-free episodic environment. [sent-46, score-0.74]

20 Another closely related work is due to Yu and Mannor (2009a,b) who considered the problem of online learning in MDPs where the transition probabilities may also change arbitrarily after each transition. [sent-50, score-0.168]

21 2 Problem deﬁnition Formally, a ﬁnite Markov Decision Process (MDP) M is deﬁned by a ﬁnite state space X , a ﬁnite action set A, a transition probability kernel P : X × A × X → [0, 1], and a reward function r : X × A → [0, 1]. [sent-57, score-0.485]

22 }, knowing the state xt ∈ X , an agent acting in the MDP M chooses an action at ∈ A(xt ) to be executed based on (xt , r(at−1 , xt−1 ), at−1 , xt−1 , . [sent-61, score-0.672]

23 As a result of executing the chosen action the process moves to state xt+1 ∈ X with probability P (xt+1 |xt , at ) and the agent receives reward r(xt , at ). [sent-66, score-0.74]

24 In the so-called average-reward problem, the goal of the agent is to maximize the average reward received over time. [sent-67, score-0.593]

25 1 Online learning in MDPs In this paper we consider the online version of MDPs when the reward function is allowed to change arbitrarily. [sent-70, score-0.369]

26 That is, instead of a single reward function r, a sequence of reward functions {rt } is given. [sent-71, score-0.586]

27 This sequence is assumed to be ﬁxed ahead of time, and, for simplicity, we assume that rt (x, a) ∈ [0, 1] for all (x, a) ∈ X × A and t ∈ {1, 2, . [sent-72, score-0.418]

28 2 The learning agent is assumed to know the transition probabilities P , but is not given the sequence {rt }. [sent-78, score-0.366]

29 The protocol of interaction with the environment is unchanged: At time step t the agent receives xt and then selects an action at which is sent to the environment. [sent-79, score-0.714]

30 In response, the reward rt (xt , at ) and the next state xt+1 are communicated to the agent. [sent-80, score-0.736]

31 The goal of the learning agent is to maximize its expected total reward T ˆ RT = E rt (xt , at ) . [sent-82, score-1.053]

32 t=1 An equivalent goal is to minimize the regret, that is, to minimize the difference between the expected total reward received by the best algorithm within some reference class and the expected total reward of the learning algorithm. [sent-83, score-0.773]

33 2 A stationary stochastic policy, π, (or, in short: a policy) is a mapping π : A × X → [0, 1], where π(a|x) ≡ π(a, x) is the probability of taking action a in state x. [sent-89, score-0.297]

34 We say that a policy π is followed in an MDP if the action at time t is drawn from π, independently of previous states and actions given the current state xt : at ∼ π(·|xt ). [sent-90, score-0.675]

35 The expected total reward while following a policy π is deﬁned as T π RT = E rt (xt , at ) . [sent-91, score-0.977]

36 t=1 Here {(xt , at )} denotes the trajectory that results from following policy π from x1 ∼ P0 . [sent-92, score-0.256]

37 The expected regret (or expected relative loss) of the learning agent relative to the class of policies (in short, the regret) is deﬁned as π ˆ ˆ LT = sup RT − RT , π where the supremum is taken over all (stochastic stationary) policies. [sent-93, score-0.781]

38 Note that the optimal policy is chosen in hindsight, depending acausally on the reward function. [sent-94, score-0.517]

39 If the regret of an agent grows sublinearly with T then we can say that in the long run it acts as well as the best (stochastic stationary) policy (i. [sent-95, score-0.783]

40 , the average expected regret of the agent is asymptotically equal to that of the best policy). [sent-97, score-0.581]

41 3 Assumptions In this section we list the assumptions that we make throughout the paper about the transition probability kernel (hence, these assumptions will not be mentioned in the subsequent results). [sent-98, score-0.158]

42 Hence, for a distribution µ, µP π is the distribution over X that results from using policy π for one step from µ (i. [sent-107, score-0.253]

43 Remember that the stationary distribution of a policy π is a distribution µ which satisﬁes µP π = µ. [sent-110, score-0.359]

44 Assumption A1 Every policy π has a well-deﬁned unique stationary distribution µπ . [sent-111, score-0.359]

45 Assumption A2 The stationary distributions are uniformly bounded away from zero: inf π,x µπ (x) ≥ β for some β > 0. [sent-112, score-0.232]

46 2 This is a reasonable reference class because for a ﬁxed reward function one can always ﬁnd a member of it which maximizes the average reward per time step, see Puterman (1994). [sent-114, score-0.651]

47 4 Learning in online MDPs under bandit feedback In this section we shall ﬁrst introduce some additional, standard MDP deﬁnitions, which we will be used later. [sent-118, score-0.302]

48 1 Preliminaries Fix an arbitrary policy π and t ≥ 1. [sent-123, score-0.247]

49 Deﬁne, ρπ , the average reward per stage corresponding to π, P and t rt by 1 S→∞ S S ρπ = lim t E[rt (xs , as )] . [sent-125, score-0.678]

50 s=0 An alternative expression for ρπ is ρπ = x µπ (x) a π(a|x)rt (x, a), where µπ is the stationary t t π π distribution underlying π. [sent-126, score-0.159]

51 Let qt be the action-value function of π, P and rt and vt be the corresponding state-value function. [sent-127, score-0.959]

52 These can be uniquely deﬁned as the solutions of the following Bellman equations: π qt (x, a) = rt (x, a) − ρπ + t π P (x |x, a)vt (x ), π vt (x) = π π(a|x)qt (x, a). [sent-128, score-0.959]

53 a x Now, consider the trajectory {(xt , at )} underlying a learning agent, where x1 is randomly chosen from P0 , and deﬁne ut = ( x1 , a1 , r1 (x1 , a1 ), x2 , a2 , r2 (x2 , a2 ), . [sent-129, score-0.189]

54 , xt , at , rt (xt , at ) ) and πt (a|x) = P[at = a|ut−1 , xt = x]. [sent-132, score-0.877]

55 That is, πt denotes the policy followed by the agent at time step t (which is computed based on past information and is therefore random). [sent-133, score-0.605]

56 We will use the following notation: π qt = qt t , π vt = vt t , ρt = ρπt . [sent-134, score-1.148]

57 t Note that qt , vt satisfy the Bellman equations underlying πt , P and rt . [sent-135, score-1.008]

58 For reasons to be made clear later in the paper, we shall need the state distribution at time step t given that we start from the state-action pair (x, a) at time t − N , conditioned on the policies used between time steps t − N and t: def µN (x ) = P [xt = x | xt−N = x, at−N = a, πt−N +1 , . [sent-136, score-0.351]

59 Since in our case the full reward function rt is not observed, the agent uses an estimate of it. [sent-146, score-1.0]

60 The main difﬁculty is to come up with an unbiased estimate of rt with a controlled variance. [sent-147, score-0.431]

61 Here we propose to use the following estimate: ˆt (x, a) = r rt (x,a) πt (a|x)µN (x|xt−N ,at−N ) t if (x, a) = (xt , at ) 0 otherwise, 4 (1) ˆ ˆ ˆ where t ≥ N + 1. [sent-148, score-0.385]

62 Deﬁne qt , vt and ρ as the solution to the Bellman equations underlying the average reward MDP deﬁned by (P, πt , ˆt ): r ˆ ˆ qt (x, a) = ˆt (x, a) − ρt + r P (x |x, a)ˆ t (x ), v ˆ vt (x) = πt (a|x)ˆ t (x, a) , q a x (2) µπt (x)πt (a|x)ˆt (x, a) . [sent-149, score-1.49]

63 , πt−N ∈ σ(ut−N ) and µN can be computed using t µN = ex P a P πt−N +1 · · · P πt−1 , t,x,a (5) a where P is the transition probability matrix when in every state action a is used and ex is the unit row vector corresponding to x (and we assumed that X = {1, . [sent-156, score-0.238]

64 Moreover, a simple but tedious calculation shows that (3) and (4) ensure the conditional unbiasedness of our estimates, that is, E [ ˆt (x, a)| ut−N ] = rt (x, a). [sent-160, score-0.385]

65 r (6) It then follows that ˆ E[ρt |ut−N ] = ρt , and, hence, by the uniqueness of the solutions of the Bellman equations, we have, for all (x, a) ∈ X × A, E[ˆ t (x, a)|ut−N ] = qt (x, a) q and E[ˆ t (x)|ut−N ] = vt (x). [sent-161, score-0.574]

66 v (8) The bandit algorithm that we propose is shown as Algorithm 1. [sent-163, score-0.204]

67 (2009) in that a bandit algorithm is used in each state which together determine the policy to be used. [sent-165, score-0.486]

68 These bandit algorithms are fed with estimates of action-values for the current policy and the ˆ current reward. [sent-166, score-0.468]

69 In our case these action-value estimates are qt deﬁned earlier, which are based on the reward estimates ˆt . [sent-167, score-0.695]

70 A major difference is that the policy computed based on the most recent actionr value estimates is used only N steps later. [sent-168, score-0.289]

71 Its price is that we need to store N policies (or weights, leading to the policies), thus, the memory needed by our algorithm scales with N |A||X |. [sent-170, score-0.18]

72 In addition to the need of dealing with the t ˆ delay, we also need to deal with the fact that in our case qt and qt can be both negative, which must be taken into account in the proper tuning of the algorithm’s parameters. [sent-173, score-0.644]

73 Let N = τ ln T , η = T −2/3 · (ln |A|)2/3 · γ = T −1/3 · (2τ + 4)−2/3 · 4τ + 8 (2τ + 4)τ |A| ln T + (3τ + 1)2 β −1/3 2 ln |A| (2τ + 4)τ |A| ln T + (3τ + 1)2 β 5 , 1/3 . [sent-177, score-0.644]

74 Algorithm 1 Algorithm for the online bandit MDP. [sent-178, score-0.28]

75 Draw an action at randomly, according to the policy πt (·|xt ). [sent-186, score-0.292]

76 t ˆ (b) Construct estimates ˆt using (1) and compute qt using (2). [sent-191, score-0.362]

77 Then the regret can be bounded as ˆ LT ≤ 3 T 2/3 · 1/3 (4τ + 8) ln |A| (2τ + 4)τ |A| ln T + (3τ + 1)2 β + O T 1/3 . [sent-193, score-0.591]

78 It is interesting to note that, similarly to the regret bound of Even-Dar et al. [sent-194, score-0.364]

79 (2009), the main term of the regret bound does not directly depend on the size of the state space, but it depends on it only through β and the mixing time τ , deﬁned in Assumptions A2 and A3, respectively; however, we also need to note that β > 1/|X |. [sent-195, score-0.433]

80 (2002), to give an algorithm with an O The proof of the theorem is similar to the proof of a similar bound done for the full-information case π ˆ by Even-Dar et al. [sent-198, score-0.204]

81 Clearly, it sufﬁces to bound RT − RT for an arbitrary ﬁx policy π. [sent-200, score-0.305]

82 For any policy π and any T T π RT − t=1 ρπ ≤ 2(τ + 1). [sent-206, score-0.224]

83 For any policy π and for all T large enough, we have T E [ρπ − ρt ] t t=1 ≤ (4τ + 10)N + ln |A| + (2τ + 4) T η γ+ 2η |A| N (1/γ + 4τ + 6) + (e − 2)(2τ + 4) β . [sent-210, score-0.385]

84 1 General tools First, we show that if the policies that we follow up to time step t change slowly, µN is “close” to t µπt : Lemma 2. [sent-218, score-0.212]

85 t,x,a max x,a x In the next two lemmas we compute the rate of change of the policies produced by Exp3 and show that for a large enough value of N , µN can be uniformly bounded form below by β/2. [sent-221, score-0.269]

86 max x (11) a The previous results yield the following result that show that by choosing the parameters appropriately, the policies will change slowly and µN will be uniformly bounded away from zero. [sent-226, score-0.286]

87 Assume that c(3τ + 1)2 < β/2, and let N ≥ τ ln 4 β − 2c(3τ + 1)2 . [sent-229, score-0.161]

88 , 2N , which can be easily seen since the policies do not change in this period. [sent-234, score-0.155]

89 , 2009) For any policy π and t ≥ 1, ρπ − ρt = t µπ (x)π(a|x) [qt (x, a) − vt (x)] . [sent-243, score-0.476]

90 x,a T T For every x, a deﬁne QT (x, a) = t=N +1 qt (x, a) and VT (x) = t=N +1 vt (x). [sent-244, score-0.574]

91 Assume that γ ∈ (0, 1), c(3τ + 1)2 < β/2, N ≥ τ ln 4 β−2c(3τ +1)2 ,0<η≤ β 2(1/γ +2τ +3) , and T > N hold. [sent-248, score-0.161]

92 Then, for all (x, a) ∈ X × A, E [QT (x, a) − VT (x)] ≤ (4τ + 8)N + ln |A| + (2τ + 4) T η γ+ 2η |A| N (1/γ + 4τ + 6) + (e − 2)(2τ + 4) β 7 . [sent-249, score-0.161]

93 (2002) concerning the regret bound of Exp3, although some details are more subtle in our case: our estimates have different properties than the ones considered in the original proof, and we also have to deal with the N -step delay. [sent-252, score-0.375]

94 Let T −N +1 T −N +1 ˆN VT (x) = πt+N −1 (a|x)ˆ t (x, a) and q t=N +1 ˆ QN (x, b) = T a ˆ qt (x, b). [sent-253, score-0.322]

96 (2002), we can show that 4 ln |A| ˆN ˆ VT (x) ≥ (1 − γ)QN (x, b) − − (τ + 2) η(e − 2) T η β Next, since the policies satisfy maxx using (8) and (13), that a T −N +1 |ˆ t (x, a)| . [sent-257, score-0.365]

97 ˆN Now, taking the expectation of both sides of (14) and using the bound on E VT (x) we get E [VT (x)] ≥ (1 − γ)E QN (x, b) − T ln |A| 4 − (τ + 2) η(e − 2) η β T −N +1 E [|ˆ t (x, a)|] q t=N +1 a − 2(τ + 2) N (c T |A| + 1), ˆ where we used that E QN (x, b) = E QN (x, b) by (8). [sent-259, score-0.219]

98 Since qt (x, b) ≤ 2(τ + 2), T T E QN (x, b) ≤ E [QT (x, b)] + 2(τ + 2) N. [sent-260, score-0.322]

99 Under the conditions of the proposition, combining Lemmas 5-6 yields T E [ρπ − ρt ] t t=1 µπ (x)π(a|x) E [QT (x, a) − VT (x)] ≤ 2N + x,a ≤ (4τ + 10)N + ln |A| + (2τ + 4) T η γ+ 2η |A| N (1/γ + 4τ + 6) + (e − 2)(2τ + 4) β , proving Proposition 1. [sent-263, score-0.184]

100 Online learning in Markov decision processes with arbitrarily changing rewards and transitions. [sent-316, score-0.168]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('rt', 0.385), ('qt', 0.322), ('agent', 0.3), ('reward', 0.293), ('vt', 0.252), ('xt', 0.246), ('regret', 0.236), ('policy', 0.224), ('bandit', 0.204), ('ln', 0.161), ('policies', 0.155), ('stationary', 0.135), ('ut', 0.133), ('mdp', 0.101), ('neu', 0.083), ('qn', 0.08), ('puterman', 0.078), ('online', 0.076), ('yu', 0.073), ('mdps', 0.073), ('auer', 0.07), ('mannor', 0.07), ('et', 0.07), ('action', 0.068), ('hungary', 0.068), ('transition', 0.066), ('rewards', 0.064), ('lemma', 0.062), ('observes', 0.061), ('proposition', 0.061), ('state', 0.058), ('bound', 0.058), ('bellman', 0.054), ('maxx', 0.049), ('decision', 0.047), ('assumptions', 0.046), ('mta', 0.045), ('sztaki', 0.045), ('expected', 0.045), ('lt', 0.042), ('rgy', 0.041), ('hungarian', 0.041), ('lemmas', 0.041), ('concerning', 0.041), ('estimates', 0.04), ('markov', 0.04), ('uniformly', 0.04), ('proof', 0.038), ('reference', 0.037), ('wt', 0.037), ('andr', 0.037), ('antos', 0.037), ('mansour', 0.037), ('stochastic', 0.036), ('slowly', 0.034), ('bounded', 0.033), ('compete', 0.033), ('ahead', 0.033), ('trajectory', 0.032), ('mixing', 0.032), ('processes', 0.031), ('delay', 0.03), ('alberta', 0.03), ('total', 0.03), ('gy', 0.03), ('rigorously', 0.03), ('szepesv', 0.029), ('step', 0.029), ('proved', 0.028), ('time', 0.028), ('actions', 0.027), ('xs', 0.027), ('visited', 0.026), ('mix', 0.026), ('arbitrarily', 0.026), ('sure', 0.026), ('kakade', 0.026), ('steps', 0.025), ('equations', 0.025), ('price', 0.025), ('unbiased', 0.025), ('followed', 0.024), ('environments', 0.024), ('underlying', 0.024), ('nitions', 0.024), ('away', 0.024), ('arbitrary', 0.023), ('proving', 0.023), ('ex', 0.023), ('nished', 0.023), ('shimkin', 0.023), ('sublinearly', 0.023), ('budapest', 0.023), ('gale', 0.023), ('instants', 0.023), ('full', 0.022), ('feedback', 0.022), ('environment', 0.022), ('receives', 0.021), ('main', 0.021)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.9999997 196 nips-2010-Online Markov Decision Processes under Bandit Feedback

Author: Gergely Neu, Andras Antos, András György, Csaba Szepesvári

2 0.33130792 229 nips-2010-Reward Design via Online Gradient Ascent

Author: Jonathan Sorg, Richard L. Lewis, Satinder P. Singh

Abstract: Recent work has demonstrated that when artiﬁcial agents are limited in their ability to achieve their goals, the agent designer can beneﬁt by making the agent’s goals different from the designer’s. This gives rise to the optimization problem of designing the artiﬁcial agent’s goals—in the RL framework, designing the agent’s reward function. Existing attempts at solving this optimal reward problem do not leverage experience gained online during the agent’s lifetime nor do they take advantage of knowledge about the agent’s structure. In this work, we develop a gradient ascent approach with formal convergence guarantees for approximately solving the optimal reward problem online during an agent’s lifetime. We show that our method generalizes a standard policy gradient approach, and we demonstrate its ability to improve reward functions in agents with various forms of limitations. 1 The Optimal Reward Problem In this work, we consider the scenario of an agent designer building an autonomous agent. The designer has his or her own goals which must be translated into goals for the autonomous agent. We represent goals using the Reinforcement Learning (RL) formalism of the reward function. This leads to the optimal reward problem of designing the agent’s reward function so as to maximize the objective reward received by the agent designer. Typically, the designer assigns his or her own reward to the agent. However, there is ample work which demonstrates the beneﬁt of assigning reward which does not match the designer’s. For example, work on reward shaping [11] has shown how to modify rewards to accelerate learning without altering the optimal policy, and PAC-MDP methods [5, 20] including approximate Bayesian methods [7, 19] add bonuses to the objective reward to achieve optimism under uncertainty. These approaches explicitly or implicitly assume that the asymptotic behavior of the agent should be the same as that which would occur using the objective reward function. These methods do not explicitly consider the optimal reward problem; however, they do show improved performance through reward modiﬁcation. In our recent work that does explicitly consider the optimal reward problem [18], we analyzed an explicit hypothesis about the beneﬁt of reward design—that it helps mitigate the performance loss caused by computational constraints (bounds) on agent architectures. We considered various types of agent limitations—limits on planning depth, failure to account for partial observability, and other erroneous modeling assumptions—and demonstrated the beneﬁts of good reward functions in each case empirically. Crucially, in bounded agents, the optimal reward function often leads to behavior that is different from the asymptotic behavior achieved with the objective reward function. In this work, we develop an algorithm, Policy Gradient for Reward Design (PGRD), for improving reward functions for a family of bounded agents that behave according to repeated local (from the current state) model-based planning. We show that this algorithm is capable of improving the reward functions in agents with computational limitations necessitating small bounds on the depth of planning, and also from the use of an inaccurate model (which may be inaccurate due to computationally-motivated approximations). PGRD has few parameters, improves the reward 1 function online during an agent’s lifetime, takes advantage of knowledge about the agent’s structure (through the gradient computation), and is linear in the number of reward function parameters. Notation. Formally, we consider discrete-time partially-observable environments with a ﬁnite number of hidden states s ∈ S, actions a ∈ A, and observations o ∈ O; these ﬁnite set assumptions are useful for our theorems, but our algorithm can handle inﬁnite sets in practice. Its dynamics are governed by a state-transition function P (s |s, a) that deﬁnes a distribution over next-states s conditioned on current state s and action a, and an observation function Ω(o|s) that deﬁnes a distribution over observations o conditioned on current state s. The agent designer’s goals are speciﬁed via the objective reward function RO . At each time step, the designer receives reward RO (st ) ∈ [0, 1] based on the current state st of the environment, where the subscript denotes time. The designer’s objective return is the expected mean objective reward N 1 obtained over an inﬁnite horizon, i.e., limN →∞ E N t=0 RO (st ) . In the standard view of RL, the agent uses the same reward function as the designer to align the interests of the agent and the designer. Here we allow for a separate agent reward function R(· ). An agent’s reward function can in general be deﬁned in terms of the history of actions and observations, but is often more pragmatically deﬁned in terms of some abstraction of history. We deﬁne the agent’s reward function precisely in Section 2. Optimal Reward Problem. An RL agent attempts to act so as to maximize its own cumulative reward, or return. Crucially, as a result, the sequence of environment-states {st }∞ is affected by t=0 the choice of reward function; therefore, the agent designer’s return is affected as well. The optimal reward problem arises from the fact that while the objective reward function is ﬁxed as part of the problem description, the reward function is a choice to be made by the designer. We capture this choice abstractly by letting the reward be parameterized by some vector of parameters θ chosen from space of parameters Θ. Each θ ∈ Θ speciﬁes a reward function R(· ; θ) which in turn produces a distribution over environment state sequences via whatever RL method the agent uses. The expected N 1 return obtained by the designer for choice θ is U(θ) = limN →∞ E N t=0 RO (st ) R(·; θ) . The optimal reward parameters are given by the solution to the optimal reward problem [16, 17, 18]: θ∗ = arg max U(θ) = arg max lim E θ∈Θ θ∈Θ N →∞ 1 N N RO (st ) R(·; θ) . (1) t=0 Our previous research on solving the optimal reward problem has focused primarily on the properties of the optimal reward function and its correspondence to the agent architecture and the environment [16, 17, 18]. This work has used inefﬁcient exhaustive search methods for ﬁnding good approximations to θ∗ (though there is recent work on using genetic algorithms to do this [6, 9, 12]). Our primary contribution in this paper is a new convergent online stochastic gradient method for ﬁnding approximately optimal reward functions. To our knowledge, this is the ﬁrst algorithm that improves reward functions in an online setting—during a single agent’s lifetime. In Section 2, we present the PGRD algorithm, prove its convergence, and relate it to OLPOMDP [2], a policy gradient algorithm. In Section 3, we present experiments demonstrating PGRD’s ability to approximately solve the optimal reward problem online. 2 PGRD: Policy Gradient for Reward Design PGRD builds on the following insight: the agent’s planning algorithm procedurally converts the reward function into behavior; thus, the reward function can be viewed as a speciﬁc parameterization of the agent’s policy. Using this insight, PGRD updates the reward parameters by estimating the gradient of the objective return with respect to the reward parameters, θ U(θ), from experience, using standard policy gradient techniques. In fact, we show that PGRD can be viewed as an (independently interesting) generalization of the policy gradient method OLPOMDP [2]. Speciﬁcally, we show that OLPOMDP is special case of PGRD when the planning depth d is zero. In this section, we ﬁrst present the family of local planning agents for which PGRD improves the reward function. Next, we develop PGRD and prove its convergence. Finally, we show that PGRD generalizes OLPOMDP and discuss how adding planning to OLPOMDP affects the space of policies available to the optimization method. 2 1 2 3 4 5 Input: T , θ0 , {αt }∞ , β, γ t=0 o0 , i0 = initializeStart(); for t = 0, 1, 2, 3, . . . do ∀a Qt (a; θt ) = plan(it , ot , T, R(it , ·, ·; θt ), d,γ); at ∼ µ(a|it ; Qt ); rt+1 , ot+1 = takeAction(at ); µ(a |i ;Q ) 6 7 8 9 t zt+1 = βzt + θt t |itt ;Qt ) t ; µ(a θt+1 = θt + αt (rt+1 zt+1 − λθt ) ; it+1 = updateInternalState(it , at , ot+1 ); end Figure 1: PGRD (Policy Gradient for Reward Design) Algorithm A Family of Limited Agents with Internal State. Given a Markov model T deﬁned over the observation space O and action space A, denote T (o |o, a) the probability of next observation o given that the agent takes action a after observing o. Our agents use the model T to plan. We do not assume that the model T is an accurate model of the environment. The use of an incorrect model is one type of agent limitation we examine in our experiments. In general, agents can use non-Markov models deﬁned in terms of the history of observations and actions; we leave this for future work. The agent maintains an internal state feature vector it that is updated at each time step using it+1 = updateInternalState(it , at , ot+1 ). The internal state allows the agent to use reward functions T that depend on the agent’s history. We consider rewards of the form R(it , o, a; θt ) = θt φ(it , o, a), where θt is the reward parameter vector at time t, and φ(it , o, a) is a vector of features based on internal state it , planning state o, and action a. Note that if φ is a vector of binary indicator features, this representation allows for arbitrary reward functions and thus the representation is completely general. Many existing methods use reward functions that depend on history. Reward functions based on empirical counts of observations, as in PAC-MDP approaches [5, 20], provide some examples; see [14, 15, 13] for others. We present a concrete example in our empirical section. At each time step t, the agent’s planning algorithm, plan, performs depth-d planning using the model T and reward function R(it , o, a; θt ) with current internal state it and reward parameters θt . Speciﬁcally, the agent computes a d-step Q-value function Qd (it , ot , a; θt ) ∀a ∈ A, where Qd (it , o, a; θt ) = R(it , o, a; θt ) + γ o ∈O T (o |o, a) maxb∈A Qd−1 (it , o , b; θt ) and Q0 (it , o, a; θt ) = R(it , o, a; θt ). We emphasize that the internal state it and reward parameters θt are held invariant while planning. Note that the d-step Q-values are only computed for the current observation ot , in effect by building a depth-d tree rooted at ot . In the d = 0 special case, the planning procedure completely ignores the model T and returns Q0 (it , ot , a; θt ) = R(it , ot , a; θt ). Regardless of the value of d, we treat the end result of planning as providing a scoring function Qt (a; θt ) where the dependence on d, it and ot is dropped from the notation. To allow for gradient calculations, our agents act according to the τ Qt (a;θt ) def Boltzmann (soft-max) stochastic policy parameterized by Q: µ(a|it ; Qt ) = e eτ Qt (b;θt ) , where τ b is a temperature parameter that determines how stochastically the agent selects the action with the highest score. When the planning depth d is small due to computational limitations, the agent cannot account for events beyond the planning depth. We examine this limitation in our experiments. Gradient Ascent. To develop a gradient algorithm for improving the reward function, we need to compute the gradient of the objective return with respect to θ: θ U(θ). The main insight is to break the gradient calculation into the calculation of two gradients. The ﬁrst is the gradient of the objective return with respect to the policy µ, and the second is the gradient of the policy with respect to the reward function parameters θ. The ﬁrst gradient is exactly what is computed in standard policy gradient approaches [2]. The second gradient is challenging because the transformation from reward parameters to policy involves a model-based planning procedure. We draw from the work of Neu and Szepesv´ ri [10] which shows that this gradient computation resembles planning itself. We a develop PGRD, presented in Figure 1, explicitly as a generalization of OLPOMDP, a policy gradient algorithm developed by Bartlett and Baxter [2], because of its foundational simplicity relative to other policy-gradient algorithms such as those based on actor-critic methods (e.g., [4]). Notably, the reward parameters are the only parameters being learned in PGRD. 3 PGRD follows the form of OLPOMDP (Algorithm 1 in Bartlett and Baxter [2]) but generalizes it in three places. In Figure 1 line 3, the agent plans to compute the policy, rather than storing the policy directly. In line 6, the gradient of the policy with respect to the parameters accounts for the planning procedure. In line 8, the agent maintains a general notion of internal state that allows for richer parameterization of policies than typically considered (similar to Aberdeen and Baxter [1]). The algorithm takes as parameters a sequence of learning rates {αk }, a decaying-average parameter β, and regularization parameter λ > 0 which keeps the the reward parameters θ bounded throughout learning. Given a sequence of calculations of the gradient of the policy with respect to the parameters, θt µ(at |it ; Qt ), the remainder of the algorithm climbs the gradient of objective return θ U(θ) using OLPOMDP machinery. In the next subsection, we discuss how to compute θt µ(at |it ; Qt ). Computing the Gradient of the Policy with respect to Reward. For the Boltzmann distribution, the gradient of the policy with respect to the reward parameters is given by the equation θt µ(a|it ; Qt ) = τ · µ(a|Qt )[ θt Qt (a|it ; θt ) − θt Qt (b; θt )], where τ is the Boltzmann b∈A temperature (see [10]). Thus, computing θt µ(a|it ; Qt ) reduces to computing θt Qt (a; θt ). The value of Qt depends on the reward parameters θt , the model, and the planning depth. However, as we present below, the process of computing the gradient closely resembles the process of planning itself, and the two computations can be interleaved. Theorem 1 presented below is an adaptation of Proposition 4 from Neu and Szepesv´ ri [10]. It presents the gradient computation for depth-d a planning as well as for inﬁnite-depth discounted planning. We assume that the gradient of the reward function with respect to the parameters is bounded: supθ,o,i,a θ R(i, o, a, θ) < ∞. The proof of the theorem follows directly from Proposition 4 of Neu and Szepesv´ ri [10]. a Theorem 1. Except on a set of measure zero, for any depth d, the gradient θ Qd (o, a; θ) exists and is given by the recursion (where we have dropped the dependence on i for simplicity) d θ Q (o, a; θ) = θ R(o, a; θ) π d−1 (b|o ) T (o |o, a) +γ o ∈O d−1 (o θQ , b; θ), (2) b∈A where θ Q0 (o, a; θ) = θ R(o, a; θ) and π d (a|o) ∈ arg maxa Qd (o, a; θ) is any policy that is greedy with respect to Qd . The result also holds for θ Q∗ (o, a; θ) = θ limd→∞ Qd (o, a; θ). The Q-function will not be differentiable when there are multiple optimal policies. This is reﬂected in the arbitrary choice of π in the gradient calculation. However, it was shown by Neu and Szepesv´ ri [10] that even for values of θ which are not differentiable, the above computation produces a a valid calculation of a subgradient; we discuss this below in our proof of convergence of PGRD. Convergence of PGRD (Figure 1). Given a particular ﬁxed reward function R(·; θ), transition model T , and planning depth, there is a corresponding ﬁxed randomized policy µ(a|i; θ)—where we have explicitly represented the reward’s dependence on the internal state vector i in the policy parameterization and dropped Q from the notation as it is redundant given that everything else is ﬁxed. Denote the agent’s internal-state update as a (usually deterministic) distribution ψ(i |i, a, o). Given a ﬁxed reward parameter vector θ, the joint environment-state–internal-state transitions can be modeled as a Markov chain with a |S||I| × |S||I| transition matrix M (θ) whose entries are given by M s,i , s ,i (θ) = p( s , i | s, i ; θ) = o,a ψ(i |i, a, o)Ω(o|s )P (s |s, a)µ(a|i; θ). We make the following assumptions about the agent and the environment: Assumption 1. The transition matrix M (θ) of the joint environment-state–internal-state Markov chain has a unique stationary distribution π(θ) = [πs1 ,i1 (θ), πs2 ,i2 (θ), . . . , πs|S| ,i|I| (θ)] satisfying the balance equations π(θ)M (θ) = π(θ), for all θ ∈ Θ. Assumption 2. During its execution, PGRD (Figure 1) does not reach a value of it , and θt at which µ(at |it , Qt ) is not differentiable with respect to θt . It follows from Assumption 1 that the objective return, U(θ), is independent of the start state. The original OLPOMDP convergence proof [2] has a similar condition that only considers environment states. Intuitively, this condition allows PGRD to handle history-dependence of a reward function in the same manner that it handles partial observability in an environment. Assumption 2 accounts for the fact that a planning algorithm may not be fully differentiable everywhere. However, Theorem 1 showed that inﬁnite and bounded-depth planning is differentiable almost everywhere (in a measure theoretic sense). Furthermore, this assumption is perhaps stronger than necessary, as stochastic approximation algorithms, which provide the theory upon which OLPOMDP is based, have been shown to converge using subgradients [8]. 4 In order to state the convergence theorem, we must deﬁne the approximate gradient which OLPOMDP def T calculates. Let the approximate gradient estimate be β U(θ) = limT →∞ t=1 rt zt for a ﬁxed θ and θ PGRD parameter β, where zt (in Figure 1) represents a time-decaying average of the θt µ(at |it , Qt ) calculations. It was shown by Bartlett and Baxter [2] that β U(θ) is close to the true value θ U(θ) θ for large values of β. Theorem 2 proves that PGRD converges to a stable equilibrium point based on this approximate gradient measure. This equilibrium point will typically correspond to some local optimum in the return function U(θ). Given our development and assumptions, the theorem is a straightforward extension of Theorem 6 from Bartlett and Baxter [2] (proof omitted). ∞ Theorem 2. Given β ∈ [0, 1), λ > 0, and a sequence of step sizes αt satisfying t=0 αt = ∞ and ∞ 2 t=0 (αt ) < ∞, PGRD produces a sequence of reward parameters θt such that θt → L as t → ∞ a.s., where L is the set of stable equilibrium points of the differential equation ∂θ = β U(θ) − λθ. θ ∂t PGRD generalizes OLPOMDP. As stated above, OLPOMDP, when it uses a Boltzmann distribution in its policy representation (a common case), is a special case of PGRD when the planning depth is zero. First, notice that in the case of depth-0 planning, Q0 (i, o, a; θ) = R(i, o, a, θ), regardless of the transition model and reward parameterization. We can also see from Theorem 1 that 0 θ Q (i, o, a; θ) = θ R(i, o, a; θ). Because R(i, o, a; θ) can be parameterized arbitrarily, PGRD can be conﬁgured to match standard OLPOMDP with any policy parameterization that also computes a score function for the Boltzmann distribution. In our experiments, we demonstrate that choosing a planning depth d > 0 can be beneﬁcial over using OLPOMDP (d = 0). In the remainder of this section, we show theoretically that choosing d > 0 does not hurt in the sense that it does not reduce the space of policies available to the policy gradient method. Speciﬁcally, we show that when using an expressive enough reward parameterization, PGRD’s space of policies is not restricted relative to OLPOMDP’s space of policies. We prove the result for inﬁnite planning, but the extension to depth-limited planning is straightforward. Theorem 3. There exists a reward parameterization such that, for an arbitrary transition model T , the space of policies representable by PGRD with inﬁnite planning is identical to the space of policies representable by PGRD with depth 0 planning. Proof. Ignoring internal state for now (holding it constant), let C(o, a) be an arbitrary reward function used by PGRD with depth 0 planning. Let R(o, a; θ) be a reward function for PGRD with inﬁnite (d = ∞) planning. The depth-∞ agent uses the planning result Q∗ (o, a; θ) to act, while the depth-0 agent uses the function C(o, a) to act. Therefore, it sufﬁces to show that one can always choose θ such that the planning solution Q∗ (o, a; θ) equals C(o, a). For all o ∈ O, a ∈ A, set R(o, a; θ) = C(o, a) − γ o T (o |o, a) maxa C(o , a ). Substituting Q∗ for C, this is the Bellman optimality equation [22] for inﬁnite-horizon planning. Setting R(o, a; θ) as above is possible if it is parameterized by a table with an entry for each observation–action pair. Theorem 3 also shows that the effect of an arbitrarily poor model can be overcome with a good choice of reward function. This is because a Boltzmann distribution can, allowing for an arbitrary scoring function C, represent any policy. We demonstrate this ability of PGRD in our experiments. 3 Experiments The primary objective of our experiments is to demonstrate that PGRD is able to use experience online to improve the reward function parameters, thereby improving the agent’s obtained objective return. Speciﬁcally, we compare the objective return achieved by PGRD to the objective return achieved by PGRD with the reward adaptation turned off. In both cases, the reward function is initialized to the objective reward function. A secondary objective is to demonstrate that when a good model is available, adding the ability to plan—even for small depths—improves performance relative to the baseline algorithm of OLPOMDP (or equivalently PGRD with depth d = 0). Foraging Domain for Experiments 1 to 3: The foraging environment illustrated in Figure 2(a) is a 3 × 3 grid world with 3 dead-end corridors (rows) separated by impassable walls. The agent (bird) has four available actions corresponding to each cardinal direction. Movement in the intended direction fails with probability 0.1, resulting in movement in a random direction. If the resulting direction is 5 Objective Return 0.15 D=6, α=0 & D=6, α=5×10 −5 D=4, α=2×10 −4 D=0, α=5×10 −4 0.1 0.05 0 D=4, α=0 D=0, α=0 1000 2000 3000 4000 5000 Time Steps C) Objective Return B) A) 0.15 D=6, α=0 & D=6, α=5×10 −5 D=3, α=3×10 −3 D=1, α=3×10 −4 0.1 D=3, α=0 0.05 D=0, α=0.01 & D=1, α=0 0 1000 2000 3000 4000 5000 D=0, α=0 Time Steps Figure 2: A) Foraging Domain, B) Performance of PGRD with observation-action reward features, C) Performance of PGRD with recency reward features blocked by a wall or the boundary, the action results in no movement. There is a food source (worm) located in one of the three right-most locations at the end of each corridor. The agent has an eat action, which consumes the worm when the agent is at the worm’s location. After the agent consumes the worm, a new worm appears randomly in one of the other two potential worm locations. Objective Reward for the Foraging Domain: The designer’s goal is to maximize the average number of worms eaten per time step. Thus, the objective reward function RO provides a reward of 1.0 when the agent eats a worm, and a reward of 0 otherwise. The objective return is deﬁned as in Equation (1). Experimental Methodology: We tested PGRD for depth-limited planning agents of depths 0–6. Recall that PGRD for the agent with planning depth 0 is the OLPOMDP algorithm. For each depth, we jointly optimized over the PGRD algorithm parameters, α and β (we use a ﬁxed α throughout learning). We tested values for α on an approximate logarithmic scale in the range (10−6 , 10−2 ) as well as the special value of α = 0, which corresponds to an agent that does not adapt its reward function. We tested β values in the set 0, 0.4, 0.7, 0.9, 0.95, 0.99. Following common practice [3], we set the λ parameter to 0. We explicitly bound the reward parameters and capped the reward function output both to the range [−1, 1]. We used a Boltzmann temperature parameter of τ = 100 and planning discount factor γ = 0.95. Because we initialized θ so that the initial reward function was the objective reward function, PGRD with α = 0 was equivalent to a standard depth-limited planning agent. Experiment 1: A fully observable environment with a correct model learned online. In this experiment, we improve the reward function in an agent whose only limitation is planning depth, using (1) a general reward parameterization based on the current observation and (2) a more compact reward parameterization which also depends on the history of observations. Observation: The agent observes the full state, which is given by the pair o = (l, w), where l is the agent’s location and w is the worm’s location. Learning a Correct Model: Although the theorem of convergence of PGRD relies on the agent having a ﬁxed model, the algorithm itself is readily applied to the case of learning a model online. In this experiment, the agent’s model T is learned online based on empirical transition probabilities between observations (recall this is a fully observable environment). Let no,a,o be the number of times that o was reached after taking action a after observing o. The agent models the probability of seeing o as no,a,o T (o |o, a) = . n o o,a,o Reward Parameterizations: Recall that R(i, o, a; θ) = θT φ(i, o, a), for some φ(i, o, a). (1) In the observation-action parameterization, φ(i, o, a) is a binary feature vector with one binary feature for each observation-action pair—internal state is ignored. This is effectively a table representation over all reward functions indexed by (o, a). As shown in Theorem 3, the observation-action feature representation is capable of producing arbitrary policies over the observations. In large problems, such a parameterization would not be feasible. (2) The recency parameterization is a more compact representation which uses features that rely on the history of observations. The feature vector is φ(i, o, a) = [RO (o, a), 1, φcl (l, i), φcl,a (l, a, i)], where RO (o, a) is the objective reward function deﬁned as above. The feature φcl (l) = 1 − 1/c(l, i), where c(l, i) is the number of time steps since the agent has visited location l, as represented in the agent’s internal state i. Its value is normalized to the range [0, 1) and is high when the agent has not been to location l recently. The feature φcl,a (l, a, i) = 1 − 1/c(l, a, i) is similarly deﬁned with respect to the time since the agent has taken action a in location l. Features based on recency counts encourage persistent exploration [21, 18]. 6 Results & Discussion: Figure 2(b) and Figure 2(c) present results for agents that use the observationaction parameterization and the recency parameterization of the reward function respectively. The horizontal axis is the number of time steps of experience. The vertical axis is the objective return, i.e., the average objective reward per time step. Each curve is an average over 130 trials. The values of d and the associated optimal algorithm parameters for each curve are noted in the ﬁgures. First, note that with d = 6, the agent is unbounded, because food is never more than 6 steps away. Therefore, the agent does not beneﬁt from adapting the reward function parameters (given that we initialize to the objective reward function). Indeed, the d = 6, α = 0 agent performs as well as the best reward-optimizing agent. The performance for d = 6 improves with experience because the model improves with experience (and thus from the curves it is seen that the model gets quite accurate in about 1500 time steps). The largest objective return obtained for d = 6 is also the best objective return that can be obtained for any value of d. Several results can be observed in both Figures 2(b) and (c). 1) Each curve that uses α > 0 (solid lines) improves with experience. This is a demonstration of our primary contribution, that PGRD is able to effectively improve the reward function with experience. That the improvement over time is not just due to model learning is seen in the fact that for each value of d < 6 the curve for α > 0 (solid-line) which adapts the reward parameters does signiﬁcantly better than the corresponding curve for α = 0 (dashed-line); the α = 0 agents still learn the model. 2) For both α = 0 and α > 0 agents, the objective return obtained by agents with equivalent amounts of experience increases monotonically as d is increased (though to maintain readability we only show selected values of d in each ﬁgure). This demonstrates our secondary contribution, that the ability to plan in PGRD signiﬁcantly improves performance over standard OLPOMDP (PGRD with d = 0). There are also some interesting differences between the results for the two different reward function parameterizations. With the observation-action parameterization, we noted that there always exists a setting of θ for all d that will yield optimal objective return. This is seen in Figure 2(b) in that all solid-line curves approach optimal objective return. In contrast, the more compact recency reward parameterization does not afford this guarantee and indeed for small values of d (< 3), the solid-line curves in Figure 2(c) converge to less than optimal objective return. Notably, OLPOMDP (d = 0) does not perform well with this feature set. On the other hand, for planning depths 3 ≤ d < 6, the PGRD agents with the recency parameterization achieve optimal objective return faster than the corresponding PGRD agent with the observation-action parameterization. Finally, we note that this experiment validates our claim that PGRD can improve reward functions that depend on history. Experiment 2: A fully observable environment and poor given model. Our theoretical analysis showed that PGRD with an incorrect model and the observation–action reward parameterization should (modulo local maxima issues) do just as well asymptotically as it would with a correct model. Here we illustrate this theoretical result empirically on the same foraging domain and objective reward function used in Experiment 1. We also test our hypothesis that a poor model should slow down the rate of learning relative to a correct model. Poor Model: We gave the agents a ﬁxed incorrect model of the foraging environment that assumes there are no internal walls separating the 3 corridors. Reward Parameterization: We used the observation–action reward parameterization. With a poor model it is no longer interesting to initialize θ so that the initial reward function is the objective reward function because even for d = 6 such an agent would do poorly. Furthermore, we found that this initialization leads to excessively bad exploration and therefore poor learning of how to modify the reward. Thus, we initialize θ to uniform random values near 0, in the range (−10−3 , 10−3 ). Results: Figure 3(a) plots the objective return as a function of number of steps of experience. Each curve is an average over 36 trials. As hypothesized, the bad model slows learning by a factor of more than 10 (notice the difference in the x-axis scales from those in Figure 2). Here, deeper planning results in slower learning and indeed the d = 0 agent that does not use the model at all learns the fastest. However, also as hypothesized, because they used the expressive observation–action parameterization, agents of all planning depths mitigate the damage caused by the poor model and eventually converge to the optimal objective return. Experiment 3: Partially observable foraging world. Here we evaluate PGRD’s ability to learn in a partially observable version of the foraging domain. In addition, the agents learn a model under the erroneous (and computationally convenient) assumption that the domain is fully observable. 7 0.1 −4 D = 0, α = 2 ×10 D = 2, α = 3 ×10 −5 −5 D = 6, α = 2 ×10 0.05 D = 0&2&6, α = 0 0 1 2 3 Time Steps 4 5 x 10 4 0.06 D = 6, α = 7 ×10 D = 2, α = 7 ×10 −4 0.04 D = 1, α = 7 ×10 −4 D = 0, α = 5 ×10 −4 D = 0, α = 0 D = 1&2&6, α = 0 0.02 0 C) −4 1000 2000 3000 4000 5000 Time Steps Objective Return B) 0.08 0.15 Objective Return Objective Return A) 2.5 2 x 10 −3 D=6, α=3×10 −6 D=0, α=1×10 −5 1.5 D=0&6, α=0 1 0.5 1 2 3 Time Steps 4 5 x 10 4 Figure 3: A) Performance of PGRD with a poor model, B) Performance of PGRD in a partially observable world with recency reward features, C) Performance of PGRD in Acrobot Partial Observation: Instead of viewing the location of the worm at all times, the agent can now only see the worm when it is colocated with it: its observation is o = (l, f ), where f indicates whether the agent is colocated with the food. Learning an Incorrect Model: The model is learned just as in Experiment 1. Because of the erroneous full observability assumption, the model will hallucinate about worms at all the corridor ends based on the empirical frequency of having encountered them there. Reward Parameterization: We used the recency parameterization; due to the partial observability, agents with the observation–action feature set perform poorly in this environment. The parameters θ are initialized such that the initial reward function equals the objective reward function. Results & Discussion: Figure 3(b) plots the mean of 260 trials. As seen in the solid-line curves, PGRD improves the objective return at all depths (only a small amount for d = 0 and signiﬁcantly more for d > 0). In fact, agents which don’t adapt the reward are hurt by planning (relative to d = 0). This experiment demonstrates that the combination of planning and reward improvement can be beneﬁcial even when the model is erroneous. Because of the partial observability, optimal behavior in this environment achieves less objective return than in Experiment 1. Experiment 4: Acrobot. In this experiment we test PGRD in the Acrobot environment [22], a common benchmark task in the RL literature and one that has previously been used in the testing of policy gradient approaches [23]. This experiment demonstrates PGRD in an environment in which an agent must be limited due to the size of the state space and further demonstrates that adding model-based planning to policy gradient approaches can improve performance. Domain: The version of Acrobot we use is as speciﬁed by Sutton and Barto [22]. It is a two-link robot arm in which the position of one shoulder-joint is ﬁxed and the agent’s control is limited to 3 actions which apply torque to the elbow-joint. Observation: The fully-observable state space is 4 dimensional, with two joint angles ψ1 and ψ2 , and ˙ ˙ two joint velocities ψ1 and ψ2 . Objective Reward: The designer receives an objective reward of 1.0 when the tip is one arm’s length above the ﬁxed shoulder-joint, after which the bot is reset to its initial resting position. Model: We provide the agent with a perfect model of the environment. Because the environment is continuous, value iteration is intractable, and computational limitations prevent planning deep enough to compute the optimal action in any state. The feature vector contains 13 entries. One feature corresponds to the objective reward signal. For each action, there are 5 features corresponding to each of the state features plus an additional feature representing the height of the tip: φ(i, o, a) = ˙ ˙ [RO (o), {ψ1 (o), ψ2 (o), ψ1 (o), ψ2 (o), h(o)}a ]. The height feature has been used in previous work as an alternative deﬁnition of objective reward [23]. Results & Discussion: We plot the mean of 80 trials in Figure 3(c). Agents that use the ﬁxed (α = 0) objective reward function with bounded-depth planning perform according to the bottom two curves. Allowing PGRD and OLPOMDP to adapt the parameters θ leads to improved objective return, as seen in the top two curves in Figure 3(c). Finally, the PGRD d = 6 agent outperforms the standard OLPOMDP agent (PGRD with d = 0), further demonstrating that PGRD outperforms OLPOMDP. Overall Conclusion: We developed PGRD, a new method for approximately solving the optimal reward problem in bounded planning agents that can be applied in an online setting. We showed that PGRD is a generalization of OLPOMDP and demonstrated that it both improves reward functions in limited agents and outperforms the model-free OLPOMDP approach. 8 References [1] Douglas Aberdeen and Jonathan Baxter. Scalable Internal-State Policy-Gradient Methods for POMDPs. Proceedings of the Nineteenth International Conference on Machine Learning, 2002. [2] Peter L. Bartlett and Jonathan Baxter. Stochastic optimization of controlled partially observable Markov decision processes. In Proceedings of the 39th IEEE Conference on Decision and Control, 2000. [3] Jonathan Baxter, Peter L. Bartlett, and Lex Weaver. Experiments with Inﬁnite-Horizon, Policy-Gradient Estimation, 2001. [4] Shalabh Bhatnagar, Richard S. Sutton, M Ghavamzadeh, and Mark Lee. Natural actor-critic algorithms. Automatica, 2009. [5] Ronen I. Brafman and Moshe Tennenholtz. R-MAX - A General Polynomial Time Algorithm for NearOptimal Reinforcement Learning. Journal of Machine Learning Research, 3:213–231, 2001. [6] S. Elfwing, Eiji Uchibe, K. Doya, and H. I. Christensen. Co-evolution of Shaping Rewards and MetaParameters in Reinforcement Learning. Adaptive Behavior, 16(6):400–412, 2008. [7] J. Zico Kolter and Andrew Y. Ng. Near-Bayesian exploration in polynomial time. In Proceedings of the 26th International Conference on Machine Learning, pages 513–520, 2009. [8] Harold J. Kushner and G. George Yin. Stochastic Approximation and Recursive Algorithms and Applications. Springer, 2nd edition, 2010. [9] Cetin Mericli, Tekin Mericli, and H. Levent Akin. A Reward Function Generation Method Using Genetic ¸ ¸ ¸ Algorithms : A Robot Soccer Case Study (Extended Abstract). In Proc. of the 9th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2010), number 2, pages 1513–1514, 2010. [10] Gergely Neu and Csaba Szepesv´ ri. Apprenticeship learning using inverse reinforcement learning and a gradient methods. In Proceedings of the 23rd Conference on Uncertainty in Artiﬁcial Intelligence, pages 295–302, 2007. [11] Andrew Y. Ng, Stuart J. Russell, and D. Harada. Policy invariance under reward transformations: Theory and application to reward shaping. In Proceedings of the 16th International Conference on Machine Learning, pages 278–287, 1999. [12] Scott Niekum, Andrew G. Barto, and Lee Spector. Genetic Programming for Reward Function Search. IEEE Transactions on Autonomous Mental Development, 2(2):83–90, 2010. [13] Pierre-Yves Oudeyer, Frederic Kaplan, and Verena V. Hafner. Intrinsic Motivation Systems for Autonomous Mental Development. IEEE Transactions on Evolutionary Computation, 11(2):265–286, April 2007. [14] J¨ rgen Schmidhuber. Curious model-building control systems. In IEEE International Joint Conference on u Neural Networks, pages 1458–1463, 1991. [15] Satinder Singh, Andrew G. Barto, and Nuttapong Chentanez. Intrinsically Motivated Reinforcement Learning. In Proceedings of Advances in Neural Information Processing Systems 17 (NIPS), pages 1281–1288, 2005. [16] Satinder Singh, Richard L. Lewis, and Andrew G. Barto. Where Do Rewards Come From? In Proceedings of the Annual Conference of the Cognitive Science Society, pages 2601–2606, 2009. [17] Satinder Singh, Richard L. Lewis, Andrew G. Barto, and Jonathan Sorg. Intrinsically Motivated Reinforcement Learning: An Evolutionary Perspective. IEEE Transations on Autonomous Mental Development, 2(2):70–82, 2010. [18] Jonathan Sorg, Satinder Singh, and Richard L. Lewis. Internal Rewards Mitigate Agent Boundedness. In Proceedings of the 27th International Conference on Machine Learning, 2010. [19] Jonathan Sorg, Satinder Singh, and Richard L. Lewis. Variance-Based Rewards for Approximate Bayesian Reinforcement Learning. In Proceedings of the 26th Conference on Uncertainty in Artiﬁcial Intelligence, 2010. [20] Alexander L. Strehl and Michael L. Littman. An analysis of model-based Interval Estimation for Markov Decision Processes. Journal of Computer and System Sciences, 74(8):1309–1331, 2008. [21] Richard S. Sutton. Integrated Architectures for Learning, Planning, and Reacting Based on Approximating Dynamic Programming. In The Seventh International Conference on Machine Learning, pages 216–224. 1990. [22] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, 1998. [23] Lex Weaver and Nigel Tao. The Optimal Reward Baseline for Gradient-Based Reinforcement Learning. In Proceedings of the 17th Conference on Uncertainty in Artiﬁcial Intelligence, pages 538–545. 2001. 9

3 0.27088594 203 nips-2010-Parametric Bandits: The Generalized Linear Case

Author: Sarah Filippi, Olivier Cappe, Aurélien Garivier, Csaba Szepesvári

Abstract: We consider structured multi-armed bandit problems based on the Generalized Linear Model (GLM) framework of statistics. For these bandits, we propose a new algorithm, called GLM-UCB. We derive ﬁnite time, high probability bounds on the regret of the algorithm, extending previous analyses developed for the linear bandits to the non-linear case. The analysis highlights a key difﬁculty in generalizing linear bandit algorithms to the non-linear case, which is solved in GLM-UCB by focusing on the reward space rather than on the parameter space. Moreover, as the actual effectiveness of current parameterized bandit algorithms is often poor in practice, we provide a tuning method based on asymptotic arguments, which leads to signiﬁcantly better practical performance. We present two numerical experiments on real-world data that illustrate the potential of the GLM-UCB approach. Keywords: multi-armed bandit, parametric bandits, generalized linear models, UCB, regret minimization. 1

4 0.26481473 152 nips-2010-Learning from Logged Implicit Exploration Data

Author: Alex Strehl, John Langford, Lihong Li, Sham M. Kakade

Abstract: We provide a sound and consistent foundation for the use of nonrandom exploration data in “contextual bandit” or “partially labeled” settings where only the value of a chosen action is learned. The primary challenge in a variety of settings is that the exploration policy, in which “ofﬂine” data is logged, is not explicitly known. Prior solutions here require either control of the actions during the learning process, recorded random exploration, or actions chosen obliviously in a repeated manner. The techniques reported here lift these restrictions, allowing the learning of a policy for choosing actions given features from historical data where no randomization occurred or was logged. We empirically verify our solution on two reasonably sized sets of real-world data obtained from Yahoo!.

5 0.26362532 222 nips-2010-Random Walk Approach to Regret Minimization

Author: Hariharan Narayanan, Alexander Rakhlin

Abstract: We propose a computationally efﬁcient random walk on a convex body which rapidly mixes to a time-varying Gibbs distribution. In the setting of online convex optimization and repeated games, the algorithm yields low regret and presents a novel efﬁcient method for implementing mixture forecasting strategies. 1

6 0.26071793 192 nips-2010-Online Classification with Specificity Constraints

7 0.25026563 4 nips-2010-A Computational Decision Theory for Interactive Assistants

8 0.25006801 193 nips-2010-Online Learning: Random Averages, Combinatorial Parameters, and Learnability

9 0.24672708 184 nips-2010-Nonparametric Bayesian Policy Priors for Reinforcement Learning

10 0.24051146 14 nips-2010-A Reduction from Apprenticeship Learning to Classification

11 0.22057343 179 nips-2010-Natural Policy Gradient Methods with Parameter-based Exploration for Control Tasks

12 0.21919382 189 nips-2010-On a Connection between Importance Sampling and the Likelihood Ratio Policy Gradient

13 0.20751224 183 nips-2010-Non-Stochastic Bandit Slate Problems

14 0.20479396 130 nips-2010-Interval Estimation for Reinforcement-Learning Algorithms in Continuous-State Domains

15 0.20272702 134 nips-2010-LSTD with Random Projections

16 0.20239128 208 nips-2010-Policy gradients in linearly-solvable MDPs

17 0.19474012 43 nips-2010-Bootstrapping Apprenticeship Learning

18 0.19260314 11 nips-2010-A POMDP Extension with Belief-dependent Rewards

19 0.18984991 201 nips-2010-PAC-Bayesian Model Selection for Reinforcement Learning

20 0.18843877 93 nips-2010-Feature Construction for Inverse Reinforcement Learning

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, 0.27), (1, -0.487), (2, 0.044), (3, 0.001), (4, 0.035), (5, 0.078), (6, -0.103), (7, -0.03), (8, -0.092), (9, 0.341), (10, 0.033), (11, 0.087), (12, -0.015), (13, -0.03), (14, 0.013), (15, 0.02), (16, -0.147), (17, -0.039), (18, 0.081), (19, 0.021), (20, 0.033), (21, -0.003), (22, -0.061), (23, 0.039), (24, -0.071), (25, 0.053), (26, 0.032), (27, -0.088), (28, 0.021), (29, -0.028), (30, -0.02), (31, -0.061), (32, -0.088), (33, 0.045), (34, -0.04), (35, -0.083), (36, 0.037), (37, -0.035), (38, -0.066), (39, 0.039), (40, -0.008), (41, 0.054), (42, -0.045), (43, -0.053), (44, 0.03), (45, -0.02), (46, 0.003), (47, -0.018), (48, 0.022), (49, 0.008)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97749865 196 nips-2010-Online Markov Decision Processes under Bandit Feedback

Author: Gergely Neu, Andras Antos, András György, Csaba Szepesvári

2 0.79602903 4 nips-2010-A Computational Decision Theory for Interactive Assistants

Author: Alan Fern, Prasad Tadepalli

Abstract: We study several classes of interactive assistants from the points of view of decision theory and computational complexity. We ﬁrst introduce a class of POMDPs called hidden-goal MDPs (HGMDPs), which formalize the problem of interactively assisting an agent whose goal is hidden and whose actions are observable. In spite of its restricted nature, we show that optimal action selection in ﬁnite horizon HGMDPs is PSPACE-complete even in domains with deterministic dynamics. We then introduce a more restricted model called helper action MDPs (HAMDPs), where the assistant’s action is accepted by the agent when it is helpful, and can be easily ignored by the agent otherwise. We show classes of HAMDPs that are complete for PSPACE and NP along with a polynomial time class. Furthermore, we show that for general HAMDPs a simple myopic policy achieves a regret, compared to an omniscient assistant, that is bounded by the entropy of the initial goal distribution. A variation of this policy is shown to achieve worst-case regret that is logarithmic in the number of goals for any goal distribution. 1

3 0.76727092 229 nips-2010-Reward Design via Online Gradient Ascent

Author: Jonathan Sorg, Richard L. Lewis, Satinder P. Singh

4 0.76133382 183 nips-2010-Non-Stochastic Bandit Slate Problems

Author: Satyen Kale, Lev Reyzin, Robert E. Schapire

Abstract: We consider bandit problems, motivated by applications in online advertising and news story selection, in which the learner must repeatedly select a slate, that is, a subset of size s from K possible actions, and then receives rewards for just the selected actions. The goal is to minimize the regret with respect to total reward of the best slate computed in hindsight. We consider unordered and ordered versions √ of the problem, and give efﬁcient algorithms which have regret O( T ), where the constant depends on the speciﬁc nature of the problem. We also consider versions of the problem where we have access to a number of policies which make recom√ mendations for slates in every round, and give algorithms with O( T ) regret for competing with the best such policy as well. We make use of the technique of relative entropy projections combined with the usual multiplicative weight update algorithm to obtain our algorithms. 1

5 0.72495133 203 nips-2010-Parametric Bandits: The Generalized Linear Case

Author: Sarah Filippi, Olivier Cappe, Aurélien Garivier, Csaba Szepesvári

6 0.65130591 11 nips-2010-A POMDP Extension with Belief-dependent Rewards

7 0.64750183 130 nips-2010-Interval Estimation for Reinforcement-Learning Algorithms in Continuous-State Domains

8 0.64088535 201 nips-2010-PAC-Bayesian Model Selection for Reinforcement Learning

9 0.60111469 192 nips-2010-Online Classification with Specificity Constraints

10 0.57942349 222 nips-2010-Random Walk Approach to Regret Minimization

11 0.56459922 43 nips-2010-Bootstrapping Apprenticeship Learning

12 0.56360435 152 nips-2010-Learning from Logged Implicit Exploration Data

13 0.55300087 168 nips-2010-Monte-Carlo Planning in Large POMDPs

14 0.54596108 14 nips-2010-A Reduction from Apprenticeship Learning to Classification

15 0.54307508 93 nips-2010-Feature Construction for Inverse Reinforcement Learning

16 0.5417403 184 nips-2010-Nonparametric Bayesian Policy Priors for Reinforcement Learning

17 0.52431452 50 nips-2010-Constructing Skill Trees for Reinforcement Learning Agents from Demonstration Trajectories

18 0.52040213 179 nips-2010-Natural Policy Gradient Methods with Parameter-based Exploration for Control Tasks

19 0.51591831 37 nips-2010-Basis Construction from Power Series Expansions of Value Functions

20 0.51088011 193 nips-2010-Online Learning: Random Averages, Combinatorial Parameters, and Learnability

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(13, 0.107), (27, 0.062), (30, 0.049), (35, 0.022), (45, 0.239), (50, 0.038), (52, 0.031), (53, 0.026), (60, 0.093), (77, 0.052), (78, 0.014), (80, 0.127), (90, 0.045)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.91822124 196 nips-2010-Online Markov Decision Processes under Bandit Feedback

Author: Gergely Neu, Andras Antos, András György, Csaba Szepesvári

2 0.88943911 70 nips-2010-Efficient Optimization for Discriminative Latent Class Models

Author: Armand Joulin, Jean Ponce, Francis R. Bach

Abstract: Dimensionality reduction is commonly used in the setting of multi-label supervised classiﬁcation to control the learning capacity and to provide a meaningful representation of the data. We introduce a simple forward probabilistic model which is a multinomial extension of reduced rank regression, and show that this model provides a probabilistic interpretation of discriminative clustering methods with added beneﬁts in terms of number of hyperparameters and optimization. While the expectation-maximization (EM) algorithm is commonly used to learn these probabilistic models, it usually leads to local maxima because it relies on a non-convex cost function. To avoid this problem, we introduce a local approximation of this cost function, which in turn leads to a quadratic non-convex optimization problem over a product of simplices. In order to maximize quadratic functions, we propose an efﬁcient algorithm based on convex relaxations and lowrank representations of the data, capable of handling large-scale problems. Experiments on text document classiﬁcation show that the new model outperforms other supervised dimensionality reduction methods, while simulations on unsupervised clustering show that our probabilistic formulation has better properties than existing discriminative clustering methods. 1

3 0.88296944 261 nips-2010-Supervised Clustering

Author: Pranjal Awasthi, Reza B. Zadeh

Abstract: Despite the ubiquity of clustering as a tool in unsupervised learning, there is not yet a consensus on a formal theory, and the vast majority of work in this direction has focused on unsupervised clustering. We study a recently proposed framework for supervised clustering where there is access to a teacher. We give an improved generic algorithm to cluster any concept class in that model. Our algorithm is query-efﬁcient in the sense that it involves only a small amount of interaction with the teacher. We also present and study two natural generalizations of the model. The model assumes that the teacher response to the algorithm is perfect. We eliminate this limitation by proposing a noisy model and give an algorithm for clustering the class of intervals in this noisy model. We also propose a dynamic model where the teacher sees a random subset of the points. Finally, for datasets satisfying a spectrum of weak to strong properties, we give query bounds, and show that a class of clustering functions containing Single-Linkage will ﬁnd the target clustering under the strongest property.

4 0.88205993 265 nips-2010-The LASSO risk: asymptotic results and real world examples

Author: Mohsen Bayati, José Pereira, Andrea Montanari

Abstract: We consider the problem of learning a coefﬁcient vector x0 ∈ RN from noisy linear observation y = Ax0 + w ∈ Rn . In many contexts (ranging from model selection to image processing) it is desirable to construct a sparse estimator x. In this case, a popular approach consists in solving an ℓ1 -penalized least squares problem known as the LASSO or Basis Pursuit DeNoising (BPDN). For sequences of matrices A of increasing dimensions, with independent gaussian entries, we prove that the normalized risk of the LASSO converges to a limit, and we obtain an explicit expression for this limit. Our result is the ﬁrst rigorous derivation of an explicit formula for the asymptotic mean square error of the LASSO for random instances. The proof technique is based on the analysis of AMP, a recently developed efﬁcient algorithm, that is inspired from graphical models ideas. Through simulations on real data matrices (gene expression data and hospital medical records) we observe that these results can be relevant in a broad array of practical applications.

5 0.88046587 239 nips-2010-Sidestepping Intractable Inference with Structured Ensemble Cascades

Author: David Weiss, Benjamin Sapp, Ben Taskar

Abstract: For many structured prediction problems, complex models often require adopting approximate inference techniques such as variational methods or sampling, which generally provide no satisfactory accuracy guarantees. In this work, we propose sidestepping intractable inference altogether by learning ensembles of tractable sub-models as part of a structured prediction cascade. We focus in particular on problems with high-treewidth and large state-spaces, which occur in many computer vision tasks. Unlike other variational methods, our ensembles do not enforce agreement between sub-models, but ﬁlter the space of possible outputs by simply adding and thresholding the max-marginals of each constituent model. Our framework jointly estimates parameters for all models in the ensemble for each level of the cascade by minimizing a novel, convex loss function, yet requires only a linear increase in computation over learning or inference in a single tractable sub-model. We provide a generalization bound on the ﬁltering loss of the ensemble as a theoretical justiﬁcation of our approach, and we evaluate our method on both synthetic data and the task of estimating articulated human pose from challenging videos. We ﬁnd that our approach signiﬁcantly outperforms loopy belief propagation on the synthetic data and a state-of-the-art model on the pose estimation/tracking problem. 1

6 0.87953448 138 nips-2010-Large Margin Multi-Task Metric Learning

7 0.87913424 92 nips-2010-Fast global convergence rates of gradient methods for high-dimensional statistical recovery

8 0.87748712 7 nips-2010-A Family of Penalty Functions for Structured Sparsity

9 0.87578374 210 nips-2010-Practical Large-Scale Optimization for Max-norm Regularization

10 0.87547636 30 nips-2010-An Inverse Power Method for Nonlinear Eigenproblems with Applications in 1-Spectral Clustering and Sparse PCA

11 0.87546998 63 nips-2010-Distributed Dual Averaging In Networks

12 0.87511635 117 nips-2010-Identifying graph-structured activation patterns in networks

13 0.87461394 62 nips-2010-Discriminative Clustering by Regularized Information Maximization

14 0.8744877 31 nips-2010-An analysis on negative curvature induced by singularity in multi-layer neural-network learning

15 0.87276453 287 nips-2010-Worst-Case Linear Discriminant Analysis

16 0.8718949 87 nips-2010-Extended Bayesian Information Criteria for Gaussian Graphical Models

17 0.87171984 163 nips-2010-Lower Bounds on Rate of Convergence of Cutting Plane Methods

18 0.87157035 12 nips-2010-A Primal-Dual Algorithm for Group Sparse Regularization with Overlapping Groups

19 0.87152106 275 nips-2010-Transduction with Matrix Completion: Three Birds with One Stone

20 0.87064064 273 nips-2010-Towards Property-Based Classification of Clustering Paradigms