arXiv:2412.00798

Combinatorial Rising Bandit

Seockbean Song, Youngsik Yoon, Siwei Wang, Wei Chen, Jungseul Ok

제출 2024-12-01

원문 초록

Combinatorial online learning is a fundamental task to decide the optimal combination of base arms in sequential interactions with systems providing uncertain rewards, which is applicable to diverse domains such as robotics, social advertising, network routing and recommendation systems. In real-world scenarios, we often observe rising rewards, where the selection of a base arm not only provides an instantaneous reward but also contributes to the enhancement of future rewards, {\it e.g.}, robots enhancing proficiency through practice and social influence strengthening in the history of successful recommendations. To address this, we introduce the problem of combinatorial rising bandit to minimize policy regret and propose a provably efficient algorithm, called Combinatorial Rising Upper Confidence Bound (CRUCB), of which regret upper bound is close to a regret lower bound. To the best of our knowledge, previous studies do not provide a sub-linear regret lower bound, making it impossible to assess the efficiency of their algorithms. However, we provide the sub-linear regret lower bound for combinatorial rising bandit and show that CRUCB is provably efficient by showing that the regret upper bound is close to the regret lower bound. In addition, we empirically demonstrate the effectiveness and superiority of CRUCB not only in synthetic environments but also in realistic applications of deep reinforcement learning.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.11607v2cs.AI공통 태그 Deep Reinforcement Learning

학습된 불확실성은 언제 신뢰할 수 있는가? 분포적 강화학습에 대한 감사

When Can Learned Uncertainty Be Trusted? An Audit of Distributional Reinforcement Learning

많은 학습된 예측 모델은 불확실성을 확률분포로 표현하며, 플래너와 정책은 이 분포를 이용해 위험을 판단한다. 그러나 모델이 분포를 출력한다는 사실만으로는 그 분포가 의사결정과 관련된 환경의 불확실성을 포착하는지 알 수 없다. 본 연구는 이 문제를 분포적 강화학습에서 다루며, 여기서 학습된 반환 분포 P_{\theta}(Z | s,a)는 스냅샷-재시작 몬테카를로로 추정한 환경 기반 분포 P_env(Z | s,a)와 직접 비교될 수 있다. 우리의 감사는 먼저 상위 두 행동 간의 초과 Wasserstein 격차(1차 확률 지배가 위배되는 질량과 같음)를 이용하여 위험 민감 사용자가 근거로 삼을 주장들을 선별한다. 이후 각 주장은 순열 귀무분포, 부트스트랩 반박, FDR 통제를 사용하여 실제 정답과 대조하여 검증된다. MinAtar에서 QR-DQN, C51, IQN(33회 실행) 전반에 걸쳐, 가장 강하게 주장된 위험 상충 관계의 40-95%가 95% 신뢰도로 반박되었고, 그 배치는 정답을 모르는 배치와 통계적으로 구별되지 않았으며, 확인될 수 있는 것은 거의 없었다. 사전 학습된 전체 Atari QR-DQN에서도 유사한 양상이 나타났다. 크기를 아는 양성 대조군에서는 동일한 감사가 실제 주장의 96-100%를 확인하여(상관 0.89-0.92), 실제 위험이 존재할 때 이를 탐지할 수 있다. 가장 많이 표시된 상태에서 학습된 CVaR 조언에 따라 행동하면 그 결과는 유익한 경우부터 우연보다 유의하게 나쁜 경우까지 다양했다. 앙상블, 위험 민감 학습, 재보정은 문제를 해결하지 못하며, 재보정 실험은 학습된 분산이 실제 위험에 관해 쓸 만한 정보를 갖지 않음을 시사한다. 이러한 결과에 따라, 학습된 세계 모델의 추정을 포함한 불확실성 추정은 그것이 사용되는 의사결정 지점에서 실현된 결과와 대조하여 검증되어야 한다고 제안한다.

arXiv:2610.02545v2cs.LG공통 태그 Deep Reinforcement Learning

보상 인플레이션: 강화학습을 위한 건강한 자극

Reward Inflation: A Healthy Stimulus for Reinforcement Learning

보상은 강화 학습(RL)의 주된 학습 신호이다. 그러나 보상의 크기는 보통 학습 내내 고정되는 반면, 그 시간적 조절은 아직 충분히 탐구되지 않았다. 본 논문은 학습이 진행되는 동안 보상을 점진적으로 스케일링하는 보상 인플레이션(reward inflation)을 제안하고, 이것이 RL에 건강한 자극으로 작용할 수 있음을 보인다. 이론적으로 보상 인플레이션은 정책 갱신 중 최근 전이에 더 큰 가중을 두는 암묵적 최신성 가중을 유도하여 더 빠른 적응을 가능하게 한다. 또한 보상 인플레이션이 정책이 포화될 때 그래디언트 신호를 유지함으로써 휴면 뉴런의 출현을 억제함을 보이며, 이는 가소성 보존에 기여할 가능성을 시사한다. ALE 게임과 MuJoCo 과제에 대한 실험 결과는 이러한 발견을 뒷받침하며, 적절한 수준의 보상 인플레이션이 광범위한 과제에 이롭다는 것을 보여 준다. 마지막으로 인플레이션 수준을 즉석에서 조정하는 적응형 변형인 Fed를 도입하며, 이것이 고정된 인플레이션보다 자주 성능을 향상시킨다는 것을 확인한다. 소스 코드는 https://github.com/northadventure/RewardInflation 에서 이용할 수 있다.

arXiv:2607.14393v3cs.RO공통 태그 Deep Reinforcement Learning

로봇 행동을 위한 fNIRS 기반 오프라인 강화학습 접근법

An offline approach to fNIRS-guided reinforcement learning for robot behavior

인간 참여형 강화학습은 로봇 행동을 사용자 선호에 맞게 학습, 미세조정, 정렬하는 데 널리 쓰이는 접근법이 되었다. 본 논문은 기능적 근적외선 분광법(fNIRS)을 통한 뇌 신호를 이용하여 시뮬레이션에서 로봇 학습을 조절하는 것의 실현 가능성을 탐구한다. 수동적(관찰적) 상호작용 과제와 능동적(시연적) 상호작용 과제로 학습된 에이전트를 비교하고, 대체보다 매개변수 증강에 초점을 맞추어 신경 신호로 RL 알고리즘을 강화하는 여러 방법을 시험한다. 또한 모델의 세분성과 잡음이 에이전트 학습에 미치는 영향을 조사한다. 결과는 이 프레임워크가 효과적임을 보여 준다. 신경 신호는 궤적 우선순위와 상태-행동 q-타깃을 증강할 때 학습을 개선한다. 아울러 이 프레임워크는 오프라인 데이터로부터 성공적으로 학습하므로, 실시간 BCI 설정이 비현실적이거나 제한된 데이터만 이용 가능한 환경에 실용적인 대안을 제공한다.

arXiv:2607.09993v2cs.GT공통 태그 Deep Reinforcement Learning

베이지안 내쉬를 넘어서: 비대칭 정보 하의 적대적 팀 게임을 위한 미니맥스-후회 균형 학습

Beyond Bayesian Nash: Learning Minimax-Regret Equilibria for Adversarial Team Games under Asymmetric Information

적대적 경로 탐색, 목표 탐색, 그래프 상의 도달 가능성 게임과 같이 비대칭 정보가 존재하는 적대적 팀 게임(ATG)은 숨겨진 목표 깃발과 같은 은닉된 상대 유형과 기만에 강건한 전략을 요구한다. 비대칭 정보 하에서 기만은 전지적 상대가 자연(Nature)과 공모하여 관찰된 유형에 따라 행동을 조정할 수 있도록 유형 분포를 전략적으로 이동시키는 것으로 간주된다. 베이지안 내시 균형(BNE)과 같은 기존의 위험 중립 해 개념은 분포 이동에 민감하며, 분포적으로 강건한 접근법은 미리 정해진 모호성 집합 내에서만 보장을 제공한다. 이러한 한계를 해결하기 위해 본 연구는 미니맥스 후회 추론의 분포 비의존적 강건성과 명목 유형 분포의 확률적 정보를 결합한 새로운 균형 개념인 확률적 강건 미니맥스 후회 균형(PR-MRE)을 도입한다. PR-MRE는 유형 공간의 고신뢰도 부분집합에 대해 최악의 경우 후회를 최소화하여, 확률 질량의 전략적 재분배에 대한 보호를 제공하면서 완전히 분포 비의존적인 접근법의 보수성을 피한다. 유한 정규형 베이지안 게임에서 근사 PR-MRE 계산을 강건 쌍선형 계획법으로 정식화할 수 있음을 보이고, 계산 가능한 반정부호 완화를 유도한다. 이어서 이 완화를 강건 이중 오라클 프레임워크 내의 새로운 메타 솔버인 PRMRE-PSRO로 적응시켜, 심층 강화학습 최선 응답을 통해 근사 PR-MRE 전략을 집단 기반으로 학습할 수 있게 한다. 그래프 구조의 적대적 팀 게임에서의 실험은 PR-MRE가 위험 중립 베이지안 내시 균형 해에 비해 숨겨진 유형 전반에서 최악의 경우 성능이 크게 향상된 전략을 발견하며, 그 결과 전략적 분포 이동 하에서 더 강건한 행동을 보임을 입증한다.

arXiv:2607.13686v2cs.LG공통 태그 Recommendation Systems

일반 함수 근사 하에서의 최적·효율적 문맥적 조합 세미-밴딧

Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation

본 논문은 맥락적 조합 세미밴딧(CCSB) 문제를 연구한다. 이 문제에서 학습자는 매 라운드마다 맥락을 관측하고, 기본 팔들의 부분집합으로 이루어진 조합 행동을 선택하며, 선택된 각 팔의 보상을 받는다. 목표는 시간에 따른 누적 보상을 최대화하는 것이다. 기존의 많은 연구가 선형 보상 함수 근사를 갖는 CCSB 문제에 초점을 맞춘 반면, 일반 보상 함수 근사를 갖는 CCSB 문제에 대한 효율적인 알고리즘 설계는 제한적이다. 본 연구에서는 학습자가 참 보상 함수를 포함하는 보상 함수 클래스 $\mathcal{F}$에 접근할 수 있는 실현 가능(realizable) 설정을 연구하고 $\mathrm{SquareCB{.}Comb}$ 알고리즘을 제안한다. $\mathrm{SquareCB{.}Comb}$가 $O(\sqrt{m A T \log |\mathcal{F}|})$의 미니맥스 최적 후회 한계를 달성함을 증명한다. 여기서 $A$는 팔의 수, $m$은 조합 행동에 포함되는 팔의 최대 개수, $T$는 시간 지평이다. 또한 맥락이 주어졌을 때 모든 팔의 보상을 효율적으로 예측할 수 있는 온라인 회귀 오라클이 있고, 조합 행동 집합이 효율적인 선형 최적화 또는 팔에 대한 임의의 목표 주변 확률이 주어졌을 때의 효율적인 샘플링 중 하나를 허용하면 $\mathrm{SquareCB{.}Comb}$는 계산적으로 효율적이다. 웹페이지 추천과 맥락적 최단 경로 문제에서 알고리즘의 효과를 실험적으로 검증한다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.