Sign In

Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs

μž‘μ„±μž
  • Haebom
μΉ΄ν…Œκ³ λ¦¬
Empty

μ €μž

Pierre Boudart (SIERRA), Pierre Gaillard (Thoth), Alessandro Rudi (PSL, DI-ENS, Inria)

πŸ’‘ κ°œμš”

λ³Έ μ—°κ΅¬λŠ” λ‹€ν•­ λ‘œμ§€μŠ€ν‹±(MNL) λͺ¨λΈλ‘œ μ „ν™˜ ν™•λ₯ μ„ λͺ¨λΈλ§ν•˜λŠ” μ—ν”Όμ†Œλ“œν˜• 마λ₯΄μ½”ν”„ κ²°μ • κ³Όμ •(MDP)μ—μ„œμ˜ κ°•ν™”ν•™μŠ΅ 문제λ₯Ό λ‹€λ£Ήλ‹ˆλ‹€. κΈ°μ‘΄ MNL ν˜Όν•© MDP μ•Œκ³ λ¦¬μ¦˜μ˜ $\tilde{O}(dH^2\sqrt{T})$의 ν›„νšŒ(regret) λ³΅μž‘λ„λ₯Ό, 졜적 κ°€μΉ˜ ν•¨μˆ˜μ˜ 뢄산을 λ°˜μ˜ν•˜λŠ” 문제 의쑴 μƒμˆ˜ $\bar\sigmaT$λ₯Ό λ„μž…ν•˜μ—¬ $\tilde{O}(dH^2\bar\sigmaT\sqrt{T})$둜 κ°œμ„ ν•œ μƒˆλ‘œμš΄ μ•Œκ³ λ¦¬μ¦˜μ„ μ œμ•ˆν•©λ‹ˆλ‹€. μ΄λŠ” μ΅œμ•…μ˜ 경우 κΈ°μ‘΄ λ³΅μž‘λ„λ₯Ό νšŒλ³΅ν•˜λ©΄μ„œλ„ κ΅¬μ‘°ν™”λœ MDPμ—μ„œλŠ” 더 λ‚˜μ€ μ„±λŠ₯을 보이며, KL μ œμ•½μ΄ μžˆλŠ” 강건 MDP의 경우 μˆ˜ν‰(horizon) μ˜μ‘΄μ„±μ„ $H$λ°° μ€„μ΄λŠ” 효과λ₯Ό κ°€μ Έμ˜΅λ‹ˆλ‹€.

πŸ”‘ μ‹œμ‚¬μ  및 ν•œκ³„

β€’
MNL ν˜Όν•© MDPμ—μ„œ ν›„νšŒ λ³΅μž‘λ„λ₯Ό μ΅œμ ν™”ν•˜κΈ° μœ„ν•΄ 문제의 ꡬ쑰적 νŠΉμ„±(졜적 κ°€μΉ˜ ν•¨μˆ˜μ˜ λΆ„μ‚°)을 λ°˜μ˜ν•˜λŠ” μƒˆλ‘œμš΄ 이둠적 도ꡬ($\bar\sigmaT$)λ₯Ό μ„±κ³΅μ μœΌλ‘œ λ„μž…ν–ˆμŠ΅λ‹ˆλ‹€.
β€’
μ œμ•ˆλœ μ•Œκ³ λ¦¬μ¦˜μ€ μ΅œμ•…μ˜ 경우 κΈ°μ‘΄ 연ꡬ와 λ™λ“±ν•œ μ„±λŠ₯을 λ³΄μ΄λ©΄μ„œλ„, νŠΉμ • ꡬ쑰λ₯Ό 가진 MDPμ—μ„œλŠ” 이둠적으둜 더 μš°μˆ˜ν•œ μ„±λŠ₯을 보μž₯ν•˜λ©°, μ΄λŠ” μ‹€μ œ μ‘μš©μ—μ„œ μ€‘μš”ν•œ 의미λ₯Ό κ°€μ§‘λ‹ˆλ‹€.
β€’
λ³Έ μ—°κ΅¬λŠ” MNL ν˜Όν•© MDP에 λŒ€ν•œ ν›„νšŒ λ³΅μž‘μ„±μ„ 졜초둜 μ™„μ „νžˆ 규λͺ…ν•˜λ©°, Minimax μ΅œμ μ„±μ„ λ‹¬μ„±ν–ˆμŒμ„ λ³΄μ˜€μŠ΅λ‹ˆλ‹€.
β€’
ν–₯ν›„ μ—°κ΅¬μ—μ„œλŠ” μ œμ•ˆλœ μ•Œκ³ λ¦¬μ¦˜μ˜ μ‹€μ œ κ΅¬ν˜„ 및 λ‹€μ–‘ν•œ μ‹€μ œ MDP λ¬Έμ œμ— λŒ€ν•œ 적용 κ°€λŠ₯성을 νƒμƒ‰ν•˜κ³ , $\bar\sigmaT$λ₯Ό 효율적으둜 μΆ”μ •ν•˜λŠ” λ°©μ•ˆμ„ λͺ¨μƒ‰ν•  수 μžˆμŠ΅λ‹ˆλ‹€.
πŸ‘
Made with Slashpage