What Do We Care About in Bandits with Noncompliance? BRACE: Bandits with Recommendations, Abstention, and Certified Effects

이 논문은 비준수 (noncompliance) 가 있는 밴딧 문제에서 추천과 실제 치료 간 불일치를 해결하기 위해 BRACE 알고리즘을 제안하며, 이는 다양한 학습 목표 (추천 복지 대 치료 학습) 를 동시에 고려하고 약한 식별성 하에서도 안전하고 유효한 불확실성 추정을 가능하게 합니다.

핵심

이 논문은 **"지시 (추천) 와 실제 행동이 다를 때, 우리는 무엇을 배워야 할까?"**라는 아주 실용적이고 중요한 질문을 던집니다.

기존의 인공지능 학습 (밴딧 알고리즘) 은 "내가 추천한 것이 곧 실행된다"고 가정했습니다. 하지만 현실은 다릅니다. 의사가 약을 처방해도 환자가 먹지 않거나, 알고리즘이 상품을 추천해도 사용자가 무시할 수 있죠.

이 논문은 이런 '불이행 (Noncompliance)' 상황에서 우리가 무엇을 목표로 삼아야 하는지, 그리고 어떻게 안전하게 배워야 하는지 새로운 방법을 제시합니다.

---

🍎 핵심 비유: "요리사 (AI) 와 손님 (현실)"

이 논문의 내용을 요리사와 손님의 관계로 비유해 볼까요?

1. 기존의 문제 (과거의 방식):

   • **요리사 (AI)**가 "오늘은 스테이크를 드세요"라고 추천합니다.
   • **손님 (현실)**은 그 말을 듣고 무조건 스테이크를 먹습니다.
   • 여기서 요리사는 "스테이크가 맛있었나?"만 확인하면 됩니다. 추천과 행동이 같으니까요.

2. 새로운 문제 (이 논문의 상황):

   • **요리사 (AI)**가 "스테이크를 드세요"라고 추천합니다.
   • 하지만 손님은 "아니야, 나는 오늘 생선 먹고 싶어"라고 말하며 생선을 주문합니다. (이게 바로 '불이행'입니다.)
   • 여기서 중요한 질문이 생깁니다: "우리는 무엇을 배워야 할까?"

🎯 세 가지 다른 목표 (우리는 무엇을 원할까?)

이 논문은 이 상황에서 세 가지 완전히 다른 목표를 제시합니다. 이 세 가지는 서로 충돌할 수 있습니다.

1. 목표 A: 지금의 만족도 극대화 (REC - 추천 복지)

   • 질문: "지금 이 식당 시스템 (추천 + 손님의 선택) 안에서, 손님이 가장 행복하게 먹을 수 있는 추천은 무엇일까?"
   • 비유: 손님이 생선을 좋아한다는 걸 알고 있다면, 요리사는 "생선"을 추천해야 합니다. 비록 요리사가 원래 스테이크를 원했더라도요. 현재 시스템이 돌아가는 방식에 맞춰 최적의 결과를 내는 것이 목표입니다.

2. 목표 B: 미래의 완벽한 치료법 찾기 (TRT - 구조적 치료)

   • 질문: "만약 내가 손님의 입맛을 완전히 통제할 수 있다면 (손님이 무조건 내 말을 듣는다면), 어떤 음식이 가장 건강하고 맛있을까?"
   • 비유: 손님의 사적인 취향 (비밀 신호) 을 무시하고, 순수하게 음식 자체의 영양과 맛을 기준으로 "최고의 음식"을 찾아내는 것입니다. 이는 미래에 시스템을 완전히 바꿀 때 (예: 병원에서 환자가 무조건 의사의 처방을 따르는 경우) 유용한 지식입니다.

3. 목표 C: 확실한 증거 (INF - 과학적 추론)

   • 질문: "우리가 배운 결과가 정말로 맞을까? 아니면 운이 좋았을 뿐일까?"
   • 비유: "이 음식이 정말 최고일까? 아니면 그냥 오늘 운이 좋았을 뿐일까?"를 통계적으로 100% 확신할 수 있는 증거를 남기는 것입니다.

🔥 이 논문의 핵심 통찰:
과거에는 A 와 B 가 같다고 생각했습니다. (추천 = 행동). 하지만 현실에서는 A(현재 추천 시스템) 가 B(미래 직접 통제) 보다 훨씬 더 좋은 결과를 낼 수도 있습니다.

• 예시: 손님이 "비밀 신호" (개인적인 취향) 를 가지고 있다면, 요리사는 그 신호를 읽어내어 추천하는 것이 (목표 A) 손님의 만족도를 100% 높일 수 있습니다. 하지만 요리사가 그 신호를 모른 채 '최고의 음식'을 직접 시키려 하면 (목표 B), 손님은 불만족할 수 있습니다.

🛡️ 해결책: BRACE (안전한 나침반)

저자는 이 복잡한 상황에서 실수하지 않고 안전하게 배울 수 있는 BRACE라는 새로운 알고리즘을 제안합니다.

• 안전 장치 (Certification):
  • 만약 데이터가 너무 부족하거나, 추천과 행동 사이의 관계가 너무 불분명하면 (약한 식별), BRACE 는 **"지금은 모른다"**라고 정직하게 말합니다. (이를 '거부 (Abstention)'라고 합니다.)
  • 마치 미끄러운 얼음 위를 걷다가 미끄러질 것 같으면, "지금은 걷지 말고 서 있어라"라고 말하는 것과 같습니다.
• 이중 목표:
  • 현재 시스템이 중요하다면 목표 A를 쫓고, 미래 시스템을 설계해야 한다면 목표 B를 쫓습니다.
  • 중요한 건, 무엇을 목표로 할지 먼저 정하고 알고리즘을 실행해야 한다는 것입니다.

📊 실험 결과: 무엇을 배웠을까?

이 논문은 다양한 시나리오로 실험을 했습니다.

1. 쉬운 문제: 데이터가 명확하면 기존 방법도 잘 작동합니다.
2. 어려운 문제 (약한 데이터): 데이터가 불분명할 때, 기존 방법들은 "무작정 추측"해서 큰 실수를 저지릅니다. 하지만 BRACE 는 "모르겠다"고 말하며 멈춥니다. 이것이 안전입니다.
3. 목표의 충돌: 때로는 "현재 추천 시스템"이 "미래 직접 통제"보다 더 좋은 결과를 줍니다. 이럴 때 무조건 미래의 이상적인 목표를 쫓는 것은 실수일 수 있습니다.

💡 결론: 우리는 무엇을 배워야 할까?

이 논문은 우리에게 **"무조건 '최고의 치료법'을 찾으려 하지 마라"**라고 말합니다.

• 만약 당신이 현재의 시스템 (의사 - 환자 관계, 알고리즘 - 사용자 관계) 을 개선하고 싶다면, **실제 일어나는 행동 (추천 + 선택)**을 최적화해야 합니다.
• 만약 당신이 미래의 시스템을 완전히 바꿀 계획이라면, 그때는 순수한 치료 효과를 배워야 합니다.

한 줄 요약:

"추천과 행동이 다를 때는, 무엇을 목표로 할지 (현재의 만족 vs 미래의 이상) 먼저 정해야 하며, 데이터가 불확실할 때는 정직하게 멈추는 것이 가장 똑똑한 학습입니다."

이 논문은 인공지능이 현실의 복잡한 인간 행동과 맞닥뜨렸을 때, 단순히 '정답'을 찾는 것이 아니라 **'어떤 질문을 던져야 할지'**를 먼저 고민하게 해줍니다.

기술 요약

이 논문은 비준수 (Noncompliance) 가 있는 컨텍스트 밴딧 (Contextual Bandits) 문제를 다루며, 학습자가 내리는 권장 (Recommendation) 과 실제로 시행된 치료 (Treatment) 가 분리되는 상황에서 최적의 학습 목표를 어떻게 설정해야 하는지에 대한 근본적인 질문을 제기합니다.

저자 Nicolás Della Penna 는 제안된 알고리즘 BRACE를 통해 이 문제를 해결하고, 다양한 학습 목표 (현재의 운영적 효용 vs 미래의 구조적 치료 규칙) 간의 상충 관계를 정량화합니다.

다음은 이 논문의 기술적 요약입니다.

---

1. 문제 정의: 비준수와 목표의 분할 (Objective Choice)

전통적인 밴딧 모델에서는 학습자의 행동 (Action) 이 곧 치료 (Treatment) 로 간주됩니다. 그러나 의료, 플랫폼 추천 등 많은 실제 응용 분야에서는 학습자가 권장 (Z) 만 할 수 있고, 환자가 이를 따르거나 (Compliance) 거부하거나, 하위 의사결정자 (의사 등) 가 이를 수정하여 실제 치료 (X) 가 결정되는 경우가 많습니다.

이러한 비준수 (Noncompliance) 상황에서는 학습 목표가 모호해질 수 있으며, 논문은 이를 세 가지 명확한 목표로 구분합니다.

1. REC (Operational Recommendation Welfare): 현재 추천 채널을 통해 실현되는 효용을 최대화하는 것. (현재 시스템 내에서의 최적화)
2. TRT (Structural Treatment Welfare): 미래에 직접적인 치료 통제 (Direct Control) 가 가능해졌을 때 적용할 최적의 치료 규칙을 학습하는 것. (구조적 인과 효과 학습)
3. INF (Scientific Inference): 적응적 샘플링 하에서 선택된 목표에 대한 유효한 불확실성 구간 (Confidence Sequence) 을 제공하는 것.

핵심 통찰:

• 직접 통제 (Direct Control) 환경에서는 REC 와 TRT 가 일치하지만, 비준수 환경에서는 두 목표가 완전히 다를 수 있습니다.
• 특히, 하위 의사결정자가 학습자가 알 수 없는 개인 정보 (Private Information) 를 활용하여 치료를 수정할 경우, 학습자가 도달할 수 있는 가장 좋은 추천 정책 (REC) 이 어떤 직접 치료 정책 (TRT) 보다도 높은 효용을 낼 수 있습니다 (Proposition 3.2).
• 따라서 알고리즘을 설계하기 전에 어떤 목표 (REC vs TRT) 를 우선시할지를 명확히 해야 합니다.

2. 제안 방법론: BRACE 알고리즘

논문은 유한한 컨텍스트 (Finite-Context) 환경에서 작동하는 BRACE (Bandits with Recommendations, Abstention, and Certified Effects) 알고리즘을 제안합니다.

주요 특징:

• 파라미터 프리 (Parameter-free): 학습률이나 탐색 파라미터를 조정할 필요가 없습니다.
• 위상 배가 (Phase Doubling): $t_r = 2^r$ 시점까지 균일 탐색 (Uniform Exploration) 을 수행합니다.
• 행렬 인증 (Matrix Certification): 구조적 치료 (TRT) 를 추론하기 위해 필요한 IV(Instrumental Variable) 역행렬 계산 시, 추정된 준수 행렬 (Compliance Matrix) $\hat{P}(w)$가 역행렬 계산에 안정적일 때만 (Certified) 역행렬을 수행합니다.
  • 인증되지 않은 경우 (불안정한 IV), 추정을 중단하거나 (Abstention) 전체 범위 $[0, 1]$의 신뢰 구간을 반환하여 안전성을 보장합니다.
• 목표별 구간 (Objective-specific Intervals):
  • REC 목표: 관찰된 결과 (Intent-to-Treat) 를 기반으로 직접 구간을 계산합니다.
  • TRT/INF 목표: 인증된 경우에만 IV 역행렬을 사용하여 구조적 평균 ($\mu$) 을 추정합니다.

알고리즘 흐름:

1. 각 위상 (Phase) 에서 모든 권장 사항을 균일하게 샘플링합니다.
2. 경험적 준수 행렬 $\hat{P}$와 결과 평균 $\hat{g}$를 계산합니다.
3. 인증 조건 ($\|\hat{P}^{-1}\|_\infty \cdot \text{오차} \leq 0.5$) 을 확인합니다.
   • 조건 만족: 역행렬을 통해 $\hat{\mu}$를 계산하고 정책 간격을 좁힙니다.
   • 조건 불만족: 구조적 추정을 중단하고 불확실성을 유지합니다.
4. 최적 정책이 명확하게 분리 (Strict Separation) 되면 학습을 중단하고 해당 정책을 배포합니다.

3. 주요 이론적 기여 및 결과

1. 목표 선택의 형식화: REC 와 TRT 가 일치하는 직접 통제 regime 과, REC 가 TRT 를 엄격하게 우월할 수 있는 매개 (Mediated) regime 을 수학적으로 구분했습니다.
2. 동시 유효성 (Simultaneous Validity): 유한 컨텍스트 환경에서 BRACE 는 다음을 동시에 보장합니다.
   • 정책 가치 유효성 (Policy-value validity): 선택된 목표 (REC 또는 TRT) 에 대한 신뢰 구간이 항상 유효합니다.
   • 고정 간격 식별 (Fixed-gap identification): 최적 정책과 두 번째로 좋은 정책 간의 간격 ($\Delta$) 이 양수일 때, BRACE 는 최적 정책을 식별하고 학습을 중단합니다.
3. 샘플 복잡도:
   • REC 목표: $O(K / (\nu_{min} \Delta_{rec}^2))$
   • TRT 목표: $O(L^2 K / (\nu_{min} \Delta_{str}^2))$ (여기서 $L$은 준수 행렬 역행렬의 노름으로, IV 의 강도를 나타냅니다. 약한 IV 일수록 더 많은 샘플이 필요합니다.)
4. 풍부한 컨텍스트 (Rich Contexts) 를 위한 시뮬파라메트릭 로드맵:
   • 연속적인 컨텍스트를 위해 직교 점수 (Orthogonal Score) 를 유도했습니다.
   • 이 점수의 편향 (Bias) 이 준수 모델 오차와 결과 모델 오차의 곱으로 분해됨을 보여, 약한 식별 (Weak Identification) 하에서도 안정적인 추론을 위해 역행렬 안정화가 필수적임을 강조했습니다.

4. 실험 결과 (Empirical Study)

유한 컨텍스트 환경에서 설계된 11 가지 시나리오를 통해 BRACE 를 검증했습니다.

• 직접 통제 vs 매개 환경: 직접 통제 환경에서는 REC 와 TRT 가 일치하지만, 개인 정보나 워크플로우 재설계가 필요한 환경에서는 두 목표가 상충됨을 확인했습니다.
• 약한 식별 (Weak Identification) 에 대한 안전성:
  • 약한 IV 환경에서 기존 방법론 (Unsafe baselines) 은 잘못된 추정을 하고 실패하는 반면, BRACE 는 거부 (Abstention) 하거나 넓은 신뢰 구간을 제공하여 위험을 회피합니다.
  • 이는 안전성이 단순히 후회 (Regret) 로만 측정되는 것이 아님을 보여줍니다.
• 동질성 위반 (Homogeneity Failure): IV 가 가정하는 동질성 조건이 깨질 때, TRT(구조적 치료) 의 점 추정값은 신뢰할 수 없게 되지만, REC(현재 추천) 는 여전히 유효하고 학습 가능합니다.
• 추가 도구 변수 (Rectangular Overidentification): 추천 옵션이 치료 옵션보다 많을 경우 (직사각형 IV), 구조적 불확실성이 줄어들어 BRACE 가 추정을 중단하지 않고 올바른 정책을 배포할 수 있음을 확인했습니다.

5. 의의 및 결론

이 논문은 비준수가 있는 밴딧 문제에서 "피드백 모델"뿐만 아니라 "학습 목표" 자체가 설계의 핵심임을 강조합니다.

• 실무적 함의: 현재 시스템의 효율성을 높이는 것 (REC) 과 미래의 치료 규칙을 찾는 것 (TRT) 은 서로 다른 목표이며, 상황에 따라 REC 를 우선시하는 것이 더 합리적일 수 있습니다.
• 안전한 학습: BRACE 는 불확실성이 큰 경우 (약한 IV, 동질성 위반) 에 무리한 추정을 하지 않고 "거부"하거나 "불확실성"을 명시함으로써, 임상 시험이나 고위험 의사결정 환경에서 안전성을 보장합니다.
• 목표 지향적 설계: 알고리즘을 선택하기 전에 "우리가 무엇을 원하는가 (현재의 추천 효율성 vs 미래의 치료 규칙)"를 명확히 해야 하며, BRACE 는 이러한 목표에 따라 유연하게 작동하는 파라미터 프리 솔루션을 제공합니다.

결론적으로, 이 연구는 비준수 환경에서의 적응적 실험을 단순한 "최적화" 문제가 아닌, 배포 regimes(현재 vs 미래) 와 이해관계자 (현재 환자 vs 미래 환자) 의 관점을 고려한 목표 선택의 문제로 재정의했습니다.