Mediator-Based Reward Design in Online Contextual Bandit

Motivation

• Known: 강화학습에서 동일한 optimal policy를 유도하는 여러 reward function이 존재할 수 있으며, 잘 설계된 reward는 학습 효율을 크게 향상시킬 수 있다는 것이 알려져 있다. 또한 causal DAG 기반 도메인 지식을 RL 알고리즘 설계에 활용하는 연구와 mediator 기반 surrogate index를 이용해 average treatment effect를 추정하는 causal inference 연구(Athey et al., 2019)가 존재한다.
• Gap: 기존의 mediator 기반 surrogate index 연구는 오프라인/배치 설정에서 surrogate outcome을 추정하거나 off-policy optimization에 활용하는 데 그쳤으며, online contextual bandit 환경에서 surrogate reward를 적응적으로 학습하고 이를 임의의 bandit oracle과 결합해 regret 개선을 이론적으로 보장하는 프레임워크는 부재했다.
• Why: 모바일 헬스나 광고와 같이 reward가 매우 노이즈가 많은 인간 행동으로부터 정의되는 응용 분야에서, 전문가의 causal DAG 지식을 활용해 학습 신호의 분산을 줄이면 online decision-making 알고리즘의 표본 효율성과 regret 성능을 실질적으로 개선할 수 있어 중요하다.
• Approach: action과 reward 사이의 mediator 변수를 이용한 causal DAG를 바탕으로 surrogate reward를 정의하고, 이를 online ridge regression으로 적응적으로 추정하는 reward-design agent를 설계하여 adversarial bandit oracle과 결합, LinUCB류 알고리즘 대비 개선된 regret bound를 이론적으로 증명하고 시뮬레이션으로 검증한다.

Achievement

Figure 4. Synthetic-data comparison of R-LinExp3, R-LinUCB, and LinExp3 relative to LinUCB. Error bars represent standar

1. Surrogate reward의 unbiasedness와 분산 감소 증명: surrogacy assumption(Rt ⊥ At | Mt, St) 하에서 mediator 기반 surrogate reward ˜Rt = E[Rt|Mt,St]가 원래 reward와 동일한 기대값을 가지면서 분산이 약하거나 강하게 감소함을 Proposition 1로 증명하였다.
2. 모듈형 online reward-design agent 제안: 어떤 online bandit oracle과도 결합 가능한 형태로 online ridge regression 기반 reward-design agent(Algorithm 1)를 설계하여 reward 설계와 decision-making을 분리하였다.
3. Adversarial oracle을 활용한 regret bound 개선: reward 학습으로 인한 non-stationarity 문제를 해결하기 위해 variance-adaptive adversarial bandit oracle(R-LinExp3 등)을 도입하고, surrogacy 가정이 정확히 성립하거나 약하게 위반되는 경우 모두에서 LinUCB류 stochastic linear contextual bandit 대비 더 타이트한 regret bound를 이론적으로 증명하였다.
4. 시뮬레이션을 통한 실증적 검증: synthetic 데이터와 HeartSteps V1 실제 모바일 헬스 데이터셋을 이용한 시뮬레이션 연구를 통해 R-LinExp3, R-LinUCB가 LinExp3 대비 성능 개선을 보임을 확인하였다.

How

Figure 4. Synthetic-data comparison of R-LinExp3, R-LinUCB, and LinExp3 relative to LinUCB. Error bars represent standar

• 문제 설정: state St, action At, mediator Mt, reward Rt로 구성된 contextual bandit에서 causal DAG(Figure 2)를 통해 mediator가 action과 reward 사이의 모든 causal pathway를 포착하는 surrogacy assumption을 정의.
• 선형 작업 모델: Rt = θ_At⊤St + θS⊤St + θM⊤Mt + ϵt, Mt = Γ_At St + ωt 형태의 linear working model을 가정하여 surrogacy 위반 정도(θ_At)를 명시적으로 포함.
• Online reward learning: 매 시점마다 online ridge regression(Eq. 2)으로 θS, θM을 추정하여 surrogate reward ˜Rt = ˆθS⊤St + ˆθM⊤Mt를 구성(Algorithm 1).
• Adversarial bandit oracle 결합: reward의 non-stationarity를 다루기 위해 variance-adaptive adversarial regret guarantee(Assumption 2)를 만족하는 oracle(R-LinExp3)을 사용.
• Regret 분석: bounded coefficient 가정(Assumption 3) 하에서 surrogacy 성립/위반 시나리오별로 regret bound를 도출하고 LinUCB-style 알고리즘과 비교.
• 실험 검증: synthetic 데이터 및 HeartSteps V1 데이터셋으로 R-LinExp3, R-LinUCB, LinExp3의 성능을 비교(Figure 4, 5).

Originality

• 인과추론 분야에서 offline 설정에 국한되었던 mediator 기반 surrogate index 개념을 online contextual bandit 학습 문제로 확장한 점이 독창적이다.
• reward 설계와 decision-making(bandit oracle)을 명시적으로 분리하는 모듈형 프레임워크를 제시하여 임의의 online bandit 알고리즘과 결합 가능하게 설계한 점이 새롭다.
• surrogate reward 학습으로 인해 발생하는 reward non-stationarity 문제를 adversarial bandit oracle로 해결하는 접근이 독특하며, surrogacy assumption이 정확히 성립하지 않는 경우에도 horizon이 짧으면 이점이 있음을 이론적으로 규명한 점이 실용적으로 의미 있다.

Limitation & Further Study

• 선형 reward/mediator generating process(Eq. 1)에 의존하고 있어, 비선형 관계나 고차원 mediator 구조로의 확장이 필요하다.
• 전문가가 제공하는 causal DAG가 정확하다는 가정(causal sufficiency 포함)에 강하게 의존하는데, 실제 응용에서는 DAG misspecification 위험이 있어 이에 대한 robustness 분석이 부족하다.
• 시뮬레이션 검증이 HeartSteps V1이라는 단일 실제 데이터셋과 synthetic 데이터에 국한되어 있어, 더 다양한 도메인(광고 등)에서의 실증적 검증이 추가로 필요하다.
• surrogacy 위반 정도(θ_At)와 horizon T 간의 trade-off에 대한 구체적 가이드라인(실제 상황에서 언제 이 방법을 적용해야 하는지)이 제한적으로만 제시되어 있다.

Evaluation

총평: causal mediator 지식을 online contextual bandit의 reward 설계에 체계적으로 통합한 참신하고 이론적으로 탄탄한 연구로, 모바일 헬스와 같이 노이즈 많은 reward 환경에서 실질적 개선 가능성을 보여준다. 다만 선형 모델 가정과 DAG 정확성에 대한 의존도가 높아 향후 비선형 확장 및 misspecification에 대한 강건성 연구가 뒷받침될 필요가 있다.