Transcription of Reinforcement Learning - Lecture 1: Introduction
1 Reinforcement LearningLecture 1: IntroductionAlexandre Proutiere, Sadegh Talebi, Jungseul OkKTH, The Royal Institute of TechnologyLecture 1: Outline1. Generic models for sequential decision making2. Overview and schedule of the course2 Lecture 1: models for sequential decision making2. Overview and schedule of the course3 Sequential Decision a sequential action selection / control policymaximising rewards4 Sequential Decision MakingProblem definition1. System dynamics2. Set of available policies available information or feedback to thedecision maker3. Reward structure5 Applications6 Sequential Decision few examples: Linear:st+1=Ast+Bat Deterministic and stationary:st+1=F(st,at) Markovian:P(st+1=s |ht,st=s,at=a) =pt(s |s,a)where s pt(s |s,a) = 1; homogenous ifpt(s |s,a) =p(s |s,a)7 Sequential Decision MakingInformation - Set of few examples: Markov Decision Process (MDP)- Fully observable state and reward- Known reward distribution and transition probabilities-atfunction of(s0,a0,r0.)
2 ,st 1,at 1,rt 1,st)8 Sequential Decision MakingInformation - Set of few examples: Partially Observable Markov Decision Process (POMDP)- Partially observable state: we knowztwith knownP[st=s|zt]- Observed rewards- Known reward distribution and transition probabilities-atfunction of(z0,a0,r0,..,zt 1,at 1,rt 1,zt)9 Sequential Decision MakingInformation - Set of few examples: Reinforcement Learning - Observable state and reward- Unknown reward distribution- Unknown transition probabilities-atfunction of(s0,a0,r0,..,st 1,at 1,rt 1,st)10 Sequential Decision MakingInformation - Set of few examples: Adversarial problems- Observable state and reward- Arbitrary and time-varying reward function and state transitions-atfunction of(s0,a0,r0.
3 ,st 1,at 1,rt 1,st)11 Sequential Decision few examples: Finite horizon:max E[ Tt=0rt(a t,s t)] Infinite horizon discounted:max E[ t=0 trt(a t,s t)] Infinite horizon average:max lim infT 1TE[ Tt=0rt(a t,s t)]12 Problem classification13 Selling an itemYou need to sell your house, and receive offers sequentially. Rejecting anoffer has a cost of 10 kSEK. What is the rejection/acceptance policymaximising your profit? are with known distributionReinforcement Learning .(Bandit optimisation) Offers are withunknown distributionAdversarial sequence of offers is arbitrary14 Lecture 1: Outline1. Generic models for sequential decision and schedule of the course15 Reinforcement learningLearning optimal sequential behaviour / control from interacting with theenvironmentUnknownstate dynamicsand reward function:s t+1=Ft(s t,a t)rt( , )16 Reinforcement learningLearning optimal sequential behaviour / control from interacting with theenvironment[.]
4 ]By the time we learn to liveIt s already too lateOur hearts cry in unison at night[..]Louis Aragon17 Reinforcement Learning : Applications Making a robot walk Portfolio optimisation Playing games better thanhumans Helicopter stuntmanoeuvres Optimal communicationprotocols in radio networks Display ads Search engines ..181. Bandit OptimisationState dynamics:s t+1=Ft(s t,a t) Interact with an or adversarial environment The reward is independent of the state and is the only feedback:- environment:rt(a,s) =rt(a)random variable with mean a- adversarial environment:rt(a,s) =rt(a)is arbitrary!192. Markov Decision Process (MDP)State dynamics:s t+1=Ft(s t,a t) History att:h t= (s 1,a 1.)
5 ,s t 1,a t 1,s t) Markovian environment:P[s t+1=s |h t,s t=s,a t=a] =p(s |s,a) Stationary deterministic rewards (for simplicity):rt(a,s) =r(a,s)20 What is to be learnt and optimised? Bandit optimisation: the average rewards of actions are unknownInformation available at timetunder :a 1,r1(a 1),..,a t 1,rt 1(a t 1) MDP: The state dynamicsp( |s,a)and the reward functionr(a,s)are unknownInformation available at timetunder :s 1,a 1,r1(a 1,s 1),..,s t 1,a t 1,rt 1(a t 1,s t 1),s t Objective: maximise the cumulative rewardT t=1E[rt(a t,s t)]or t=1 tE[rt(a t,s t)]21 Regret Difference between the cumulative reward of an Oracle policy andthat of agent Regret quantifies the price to pay for Learning !
6 Exploration vs. exploitation trade-off: we need to probe all actionsto play the best later ..221. Bandit OptimisationFirst application:Clinical trial, Thompson 1933- A set of possible actions at each step- Unknown sequence of rewards for each action- Bandit feedback: only rewards of chosen actions are observed- Goal: maximise the cumulative reward (up to stepT)Two examples:a. Finite number of actions, stochastic rewardsb. Continuous actions, concave adversarial rewards23a. Stochastic bandits Robbins 1952 Finite set of actionsA (Unknown) rewards of actiona A:(rt(a),t 0) BernoulliwithE[rt(a)] = a Optimal actiona? arg maxa a Online policy : select actiona tat timetdepending ona 1,r1(a 1).
7 ,a t 1,rt 1(a t 1) Regret up to timeT:R (T) =T a? Tt=1 a t24a. Stochastic banditsFundamental performance limits:(Lai-Robbins1985)For anyreasonable :lim infTR (T)log(T) a6=a? a? aKL( , a?)whereKL(a,b) =alog(ab) + (1 a) log(1 a1 b)(KL divergence)Algorithms:(i) -greedy: linear regret(ii) t-greedy: logarithmic regret ( t= 1/t)(iii) Upper Confidence Bound algorithm:ba(t) = a(t) + 2 log(t)na(t) (t): empirical reward ofaup totna(t): nb of timesaplayed up tot25b. Adversarial Convex BanditsAt the beginning of each year, Volvo has to select a vectorx(in a convexset) representing the relative efforts in producing various models (S60,V70, V90.)
8 The reward is an arbitrarily varying and unknownconcave function ofx. How to maximise reward over say 50 years?26b. Adversarial Convex BanditsAt the beginning of each year, Volvo has to select a vectorx(in a convexset) representing the relative efforts in producing various models (S60,V70, V90,..). The reward is an arbitrarily varying and unknownconcave function ofx. How to maximise reward over say 50 years?27b. Adversarial Convex BanditsAt the beginning of each year, Volvo has to select a vectorx(in a convexset) representing the relative efforts in producing various models (S60,V70, V90,..). The reward is an arbitrarily varying and unknownconcave function ofx.
9 How to maximise reward over say 50 years?28b. Adversarial Convex BanditsAt the beginning of each year, Volvo has to select a vectorx(in a convexset) representing the relative efforts in producing various models (S60,V70, V90,..). The reward is an arbitrarily varying and unknownconcave function ofx. How to maximise reward over say 50 years?29b. Adversarial Convex BanditsAt the beginning of each year, Volvo has to select a vectorx(in a convexset) representing the relative efforts in producing various models (S60,V70, V90,..). The reward is an arbitrarily varying and unknownconcave function ofx. How to maximise reward over say 50 years?
10 30b. Adversarial Convex BanditsAt the beginning of each year, Volvo has to select a vectorx(in a convexset) representing the relative efforts in producing various models (S60,V70, V90,..). The reward is an arbitrarily varying and unknownconcave function ofx. How to maximise reward over say 50 years?31b. Adversarial Convex Bandits Continuous set of actionsA= [0,1] (Unknown) Arbitrary but concave rewards of actionx A:rt(x) Online policy : select actionx tat timetdepending onx 1,r1(x 1),..,x t 1,rt 1(x t 1) Regret up to timeT: (defined the best empirical action up totimeT)R (T) = maxx [0,1]T t=1rt(x) T t=1rt(x t)Can we do something smart at all?
