한국어 초록
평균 기반 알고리즘(mean-based algorithm)은 평균 보상이 낮은 행동에 낮은 확률을 할당하는 온라인 학습 알고리즘이다. 최근 연구에 따르면 이러한 알고리즘은 경제 게임에서 내시 균형(Nash equilibria)의 근사치 역할을 하는 순차적 비지배(serially undominated) 행동으로 수렴한다. 그러나 실증적 연구들은 평균 기반 알고리즘이 밴딧 피드백(bandit feedback) 환경에서 기존 무후회(no-regret) 대안들보다 더 느리게 수렴함을 보여준다. 본 연구는 미지의 기간(unknown horizon)과 밴딧 피드백 환경에서 평균 기반 알고리즘을 조사한다. 이 설정에서 우리는 알고리즘 정의 수열 $γ_t$에 대한 최초의 하한(lower bound)을 제시하여 이러한 알고리즘의 학습 속도에 대한 근본적인 한계를 규명한다. 다중 팔 밴딧(multi-armed bandit) 문제에서 이 결과는 임의의 알고리즘이 낮은 보상의 행동을 안정적으로 식별하는 동시에 이러한 지식에 따라 행동할 수 있는 속도를 제한한다. 또한 우리는 두 가지 평균 기반 알고리즘을 제안한다. 하나는 $ε$-greedy를 일반화한 것이고, 다른 하나는 평균 기반 Exp3를 미지의 기간으로 확장한 것이다. 실험을 통해 평균 기반 알고리즘이 다소 느리기는 하지만 다른 밴딧 피드백 알고리즘과 경쟁력 있는 성능을 보일 수 있음을 확인했다. 나아가 후회(regret)와의 관계를 추가로 연구한다. $γ_t$의 선택에 따라 무후회 알고리즘과의 교집합은 자명하지 않으며(non-trivial), 일부 알고리즘은 평균 기반이면서 동시에 무후회임을 보인다.
원문 초록
Mean-based algorithms are online learning algorithms that assign low probability to actions with low average rewards. Recent research shows that they converge to serially undominated actions, which serve as approximations to Nash equilibria in economic games. However, empirical studies indicate that mean-based algorithms converge more slowly in bandit-feedback settings than established no-regret alternatives. This work investigates mean-based algorithms under unknown horizons and bandit feedback. In this setting, we provide the first lower bound on the algorithm-defining sequence $γ_t$, establishing a fundamental limit on the learning speed of such algorithms. In multi-armed bandit problems, this result constrains the rate at which any algorithm can reliably identify low-reward actions while acting according to this knowledge. We also propose two mean-based algorithms: one generalizes $ε$-greedy, and the other extends mean-based Exp3 to unknown horizons. Our experiments show that mean-based algorithms, although slightly slower, can perform competitively with other bandit-feedback algorithms. We further study the relationship to regret. Depending on the choice of $γ_t$, the intersection with no-regret algorithms is non-trivial, and we show that some algorithms are both mean-based and no-regret.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
TreeLoRA: 계층적 그래디언트 유사도 트리 기반 층별 LoRA를 활용한 효율적 지속 학습
TreeLoRA: Efficient Continual Learning via Layer-Wise LoRAs Guided by a Hierarchical Gradient-Similarity Tree
많은 실세계 응용에서는 데이터를 스트리밍 환경에서 수집하며, 학습 태스크가 순차적으로 등장한다. 이는 모델을 온라인으로 갱신하는 지속 학습(CL)을 필요로 하며, 새로운 태스크에 적응하면서 과거 지식을 보존하여 치명적 망각을 방지한다. 최근 대규모 사전학습 모델(LPM)의 성장과 함께, 상당한 계산 요구와 증가하는 매개변수 규모로 인해 CL에서 효율성이 점점 더 중요해졌다. 본 논문에서는 TreeLoRA(K-D Tree of Low-Rank Adapters)를 제안한다. 이는 계층적 그래디언트 유사도를 활용하여 층별 어댑터를 구성하고, 특히 LPM을 위한 효율적인 CL을 가능하게 하는 새로운 접근법이다. 태스크 유사도 추정의 계산 부담을 줄이기 위해, 밴딧(bandit) 기법을 사용하여 하한 신뢰 구간(lower confidence bounds)에 기반한 알고리즘을 개발하고 태스크 구조를 효율적으로 탐색한다. 또한 희소 그래디언트 업데이트를 사용하여 매개변수 최적화를 촉진하고, 이 접근법을 LPM에 더 적합하게 만든다. 접근법의 근거를 정당화하는 이론적 분석을 제공하며, 비전 트랜스포머(ViT)와 대규모 언어 모델(LLM) 모두에 대한 실험을 통해 비전 및 자연어 처리(NLP) 태스크를 포함한 다양한 도메인에서 본 접근법의 효과와 효율성을 입증한다.
Adaptive Action Duration with Contextual Bandits for Deep Reinforcement Learning in Dynamic Environments
From Theory to Practice with RAVEN-UCB: Addressing Non-Stationarity in Multi-Armed Bandits through Variance Adaptation
VirnyFlow: A Design Space for Responsible Model Development
Test-Time Scaling of Diffusion Models via Noise Trajectory Search
Human in the Loop Adaptive Optimization for Improved Time Series Forecasting
토론
이 논문과 연결된 포럼 글이 아직 없습니다.