组合多变量多臂土匪及其在情景强化学习等领域的应用-李帅.pdf

1、Shuai Li(https:/shuaili8.github.io/)Shanghai Jiao Tong UniversityThis work is published at ICML 2024Oct 13,2024https:/arxiv.org/abs/2406.01386Driving questionCan combinatorial MAB handle decision-making systems with states?What is the relationship between RL and combinatorial MAB?Main technical resu

2、lt Episodic RL is an instance of CMAB Plug-in CMAB algorithms/analysis that achievesnear-optimal regret Integrating RL structure achieves minimax optimal regretConnectionPlug-in SolutionMinimax OptimalBackground of multi-armed bandit(MAB)and combinatorial MAB(CMAB)Episodic RL and its connection with

3、 CMABCMAB view of solving episodic RLBackground of multi-armed bandit(MAB)and combinatorial MAB(CMAB)Episodic RL and its connection with CMABCMAB view of solving episodic RLmax().():reward/utility for decision :m candidate decisionsDrivingRecSysLLM selectionObjective:maximize expected total rewards

4、=1 An agent and arms Each arm has a reward distribution with unknown mean In each round =1,2,:The agent selects an arm Observes reward Items,products,route,CTR,preference,delay,Click,purchase,time,minimize regret Reg =1arm 1arm 2=2=argmax()Optimism in the face of uncertainty(OFU)Explore based on the

5、 best possible values(i.e.,optimistic estimates)associated with the arm!A common framework based on upper confidence bound(UCB)estimation+uncertainty levelIdea:always try the best arm,where best includes exploration andexploitationIn round:Compute UCB index for each arm:UCB,=+log():empirical average

6、 reward of arm ():number of times has been observed up to time Select the arm with the highest UCB indexUCB,=+log()Exploitation:is the average reward.Higher leads to higher UCB index.Exploration:log()decreases as we havemore observations.Fewer leads tohigher UCB index.Reg(T)=0log or logGap=()()max()