Therefore, applying RL algorithms with high sample complexity to real-world tasks is difficult, where trial-and-error can be extremely expensive.

→ RL알고리즘을 high sample complexity에 적용하는 게 어렵다.

Therefore, a major focus of recent deep RL (DRL) research has been on enhancing sample efficiency [5]. Model-based RL (MBRL) is one of the most important research directions that have the potential to make RL algorithms significantly more sample efficient [6].

→ 따라서, sample을 efficient하게 하려면 model-based RL이 필요

→ 수천 번의 가상 상호작용을 빠르게 수행

MDP는 ⟨S, A, M, R, γ⟩로 이루어진다.

S : state space A : action space γ : discount factor for future rewards M : S ×A →S - state transition dynamics R : S ×A - reward function

그래서, "모델을 학습한다"의 의미는, M과 R을 recover한다는 뜻. 이미 많은 경우에 reward function은 이미 define되어있으니까, 사실상, 주요 목표는 state transition dynamics인 M을 학습하는 게 주요 목표겠지!

이렇게 하면 샘플 복잡도가 줄어들고, 모델에서 생성된 시뮬레이션 데이터를 통해 학습을 하게 되는 것. 이때, 이 시뮬레이션 데이터를 활용해서 policy를 학습하게 되는 것이다!

Recent studies from both theoretical [14] and empirical [6, 8] perspectives demonstrate that, given a sufficiently accurate model, it is intuitive that MBRL yields higher sample efficiency than MFRL. -> 일단 accurate한 모델이 있다면, MBRLd은 sample efficiency가 더 높다 MFRL보다는...

그리고 이 Model-based RL이 2가지로 나뉠 수 있다.

• blackbox model rollout for trajectory sampling
• whitebox model for gradient propagation

게다가, Model-based와 다른 애들이 합쳐진 걸 또 배울 것이다. (OffRL, multi-agent RL 등등)

2 Model Learning

We assume that some historical data is available for learning. Usually, the historical data can be in the form of trajectories {τ1, τ2, . . . , τk }, and each trajectory is a sequence of state-action-reward pairs

M : (st, at) -> (st+1) R : (st, at) -> rt

2.1 Model Learning in tabular setting

단순히 Tabular setting이라고 한다면, (s,a)를 집어넣었을때, ex) (s,a,s1):3번 (s,a,s2): 4번 (s,a,s3):5번 (s,a)를 넣었을때, s1이 나올 확률은? = 3/(3+4+5)가 되는 거지,

Notice that $$ \hat{M}, \hat{R} $$ are an unbiased estimation of the true transition $$ M^* R^* $$ respectively, and thus converge to them as the samples approach infinity. -> 결국 추정치지만 나중에는 infinity로 수렴

A key limitation of the analysis is the assumption of the tabular setting, where models are not able to generalize across states. -> 근데, 이 Tabular setting의 중요한 점은, 상태들 간의 일반화를 하지 못한다 : 상태가 매우 적고 고정되어 있는 경우에는 잘 작동 but 상태 공간이 커지거나 복잡해지면 효율적X => 상태 간의 연결 관계나 패턴을 파악하지 못한다

예를 들어서, 상태 간 일반화가 이루어지지 않기 때문에 상태 A와 상태 C가 유사하다고 해도, 이를 따로 다룰 수밖에 없음. $$ P(s ′ ∣A,a)≈P(s ′ ∣C,a)

for some s ′ ∈S $$

$$ Q(A,a)=R(A,a)+γ \underset{a ′}

max ​
Q(s ′ ,a ′ ) $$ $$ Q ( C , a ) = R ( C , a ) + γ \underset{a ′} max

Q ( s ′ , a ′ )

$$ 이런식으로 일반화가 될 수 있다.! 근데 Tabular setting에서는, 독립적으로 값이 계산이 되는거지.

2.2 Model Learning via prediction loss

linear model들로 이제 approximation을 한다. $$ M_θ(approximation) 와 M^∗(real) $$

2.2.1 Prediction model loss

1) the stationary state-action distribution induced by πD and M ∗ 로부터 뽑은 (s,a)를 approximation에 넣은 다음에 나오는 state 2) M*(.|(s,a))로부터 뽑은 s' 을 가지고 MSE를 구하는 거다.

• 근데 이렇게 되면 어떤 문제가 생긴다?

=> 바로 특정 하나의 s'로 전이가 된다. $$ M(s'|(s,a)) $$ 얘가 무조건 s'으로 되는가? ㄴㄴ 그럼 이것도 확률분포가 되는거.

그래서 단순히, s'으로 나오는 게 아니니까 MSE를 쓰지 말고 KL divergence를 활용해보자고요~! (분포와 분포사이의 척도를 재는 KL divergence)

근데, 이때, M_θ가 보통 가우시안으로 정의가 되기 때문에 결국에는, 저 식으로 된다. 그래서 어떤 supervised learning이라도 사용될 수 있는 이유임.

2.2.2 Model Properties

수학적으로는, 시간이 지날수록 오차가 2차적으로 더 커진다. 그러니 실제환경이랑 매우 일치해야한다.

2.2.3 Model Variants

<단계별 모델>

• 기존의 전통적인 모델 : 한 번에 하나의 상태를 예측 : 이 모델은 예측한 상태를 다시 입력으로 사용하는 구조 => 누적 오차(compounding error) 발생 가능

• 단계별 모델(multistep model) : 한 번에 여러 단계를 예측 : "가짜" 상태를 입력으로 사용하지 않으니까 => 오차가 누적되지 않음.

<역방향 전이 모델>

• 기존 모델 s_t와 a_t를 입력으로 받아서 s_t+1예측하기

• 역방향 전이 모델 s_t+1과 a_t를 입력으로 받아서 s_t예측하기

2.3 Model Learning with reduced error

2.3.1 Model learning with Lipschitz continuity constraint

: 일단 아까 compounding error(계속해서 누적되는 error)가 생기니까, 그걸 없애줘야겠지? 활용한 것 1 : Lipschitz continuity constraint

활용한 것 2 : Wasserstein 거리 == 두 확률분포 P와 Q 사이의 "최소한의 이동 비용" 개념

(이때, Π (P, Q) denotes the set of all joint distributions γ(x, y)) ( γ에서 x만 봤을 때 나오는 분포가 P, γ에서 y만 봤을 때 나오는 분포가 Q 이렇게 생각하면 될듯.

그래서, a state distribution ρ over the state space S 를 고려해봤을 때, state transition dynamics를 이렇게 정의할 수 있다 : 근데, 중요한 건 그러면 n-step error가 있을 때 upperbound가 뭐니 뭥미 이거잖아?

2.3.2 Model learning by distribution matching

The prediction loss employed in Theorems 1 and 2 minimizes the model error on each point of the state-action data. While the prediction loss minimization can be straightforwardly solved by supervised learning, the long-term effect of transitions is hard to capture, resulting in the horizon-squared com- pounding error issue. => "이 한 번의 예측"만 잘하면 되는 게 아님! => n-step 시뮬레이션이 중요 => 그러니,** match the distributions between the real trajectories and the trajectories rolled out in the learned model.** ! ! ! ! ! => 매칭을 시키자.

Model-based로 만들어낸 데이터랑 기존 데이터상의 분포 mismatch가 일어날 거 아니니! 그래서, phi(E) 즉, expert data로부터 온 (s,a)를 활용해서 log(D(s,a)) + phi(phi) 즉, 에이전트 만든 data로부터 온 (s,a)를 활용해서 만든 log(1-D(s,a))를 maximize해야한다.

제곱수의 합

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

접근 방법

1. 일단 dp[i] 정의 = i를 제곱수의 합으로 표현할 때의 최소 항 개수
2. min_count를 만든다

코드

N = int(input())
dp = [0] * (N+1)

for i in range(1,N+1):
    min_count = i 
    j = 1 
    while j*j <= i : 
        dp[i] = min(min_count,dp[i-j*j]+1]
        j += 1 
    dp[i] = min_count

print(dp[N])

(선택사항) 오류 해결

원래는 이걸 min_count를 i로 할 생각을 못했ㅇ듬…

뭔가 나한테는 아직 dp가 무조건 피보나치같은 애들로 생각이 되나봄.

→ DP는 피보나치처럼 단순한 연속 관계일 때도 있지만 / 모든 가능한 선택지들을 확인하면서 최소값(또는 최대값)을 고르는 문제

예시를 들어보자면, 로봇 협업 학습 (예: 물류창고, 공장 로봇들) 문제: 서로 다른 환경에 있는 로봇들(예: 로봇 팔, 드론 등)이 유사한 작업을 하지만 환경이나 하드웨어가 조금씩 다름. FRL 활용: 각 로봇은 자기가 있는 현장에서 로컬 강화 학습 수행. 정책만 공유 → 새로운 로봇이 빠르게 적응 가능 (few-shot transfer). 데이터는 유출되지 않으므로 보안 문제 없음. ! ! ! !

• federated RL? = clients가 그들의 locally하게 train된 모델들을 share해서 client가 collaborative하게 학습하는 것이다. => privacy up + communication resource down

  
  
  

• federated RL과 online RL? sequential interaction을 통해서 환경에 대해 배우고 + 연합학습 Policy를 배우는.

• 얘는

• federated RL과 offline RL?

=> 각 클라이언트는 환경과 직접 상호작용하지 못함( 다른 조건에서 수집된 데이터만 가지고 있음) => 그런데 이 데이터를 공유하지 않고도 전체적으로 가장 좋은 action policy를 어떻게 배울 수 있을까?

• Offline RL알고리즘의 예시 CQL , TD3-BC : actor-critic learning approach = 각 클라이언트에 이미 존재하는 데이터셋만을 활용해서 actor-critic 학습을 수행하는 방식
  
  

• offline RL을 바로 fedearted learning에 적용했을 때의 문제점 많은 클라이언트들이 각각 작은 데이터셋만 보유하고 있음 -> 클라이언트마다 품질이 제각각인 정책(policy) 집합!이 생긴다. => 이런 상태에서, 이런 상태에서, 단순히 FedAvg 같은 일반적인 federated learning을 통해 이 policy들과 critic들을 평균 내듯이 통합하면,안됨.
  
  

• offline RL을 federated learning에 적용했을 때 고려해야할 점

(i) Ensemble heterogeneity 클라이언트의 데이터셋이 서로 달라서, 만들어진 정책들 또한 성능이 제각각. 단순히 평균X 이 정책 집합이 가진 집단적인 지혜(collective wisdom)를 잘 반영하는 방식이 필요하다.

(ii) Pessimistic value-computation (비관적인 가치 계산) Offline RL은, 데이터에서 잘 나타나지 않은 행동에 대해 분포 이동(distribution shift)을 피하려고 낮은 가치를 부여하는 pessimistic 접근. -> 하지만 federated learning에서는 오히려, 이 policy 집합이 제공하는 가장 높은 가치(high-value actions)를 적극적으로 추출하려는 야심 있는 접근이 필요하다.

(iii) Data heterogeneity (데이터 이질성) 다른 federated learning과 마찬가지로, 클라이언트마다 다른 데이터로 여러 번 로컬 학습을 한 뒤 다 합치는 방식은 bias된 모델을 만들 위험이 있다. -> 따라서, 로컬 정책이 너무 멀리 벗어나지 않도록 규제(regularize)하는 것이 필요하다.

• 해결책 [FEDORA]

문제 1 : Ensemble Heterogeneity

문제: 클라이언트의 데이터가 제각각이라 학습된 정책의 품질이 서로 다름. 단순 평균(FedAvg)을 하면 전체 성능이 악화될 수 있음. 해결: → 각 클라이언트의 정책을 평가하여 가중치를 다르게 주는 방식으로 결합함. → 엔트로피 정규화를 통해 과도한 쏠림 없이 ensemble wisdom를 추출.

문제 2 : Pessimistic Value Computation

문제: Offline RL은 훈련 데이터에 적게 나온 행동에 대해 낮은 가치를 부여함. 이로 인해 연합 시 높은 가치의 행동을 놓칠 수 있음. 해결: → 낙관적 평가(optimism) 원칙을 도입해, 연합 critic과 로컬 critic이 가장 높은 값을 추출하도록 유도. → policy가 적극적으로 high-value 행동을 하도록 훈련

문제 3 : (Data Heterogeneity

문제: 클라이언트마다 데이터 분포가 달라, 연합 전에 local 모델들이 너무 달라질 수 있음. 해결: → 클라이언트의 정책을 연합된 정책과 로컬 데이터 기준으로 정규화(regularization) → 이는 편향된 학습 경향(drift)을 줄이고 안정성을 향상

문제 4: 낮은 품질 데이터의 영향력 (Irrelevant or Low-Quality Data)

문제: 어떤 클라이언트는 매우 질 낮은 policy을 만들어, 전체 연합 정책에 악영향을 줄 수 있음. 해결: → policy의 품질을 추정하여, 품질이 낮은 경우 해당 클라이언트의 영향력을 점차 줄임 → 즉, 무의미한 데이터는 자연스럽게 영향력이 감소

• FEDORA 실험 EDORA on a variety of MuJoCo environments and real-world datasets FEDORA’s excellent performance via real-world experiments on a TurtleBot robot

수식 관련된건 (2)탄에 올리도록 하겠습니다!

(요기 이 simulation based 부분은 아직 구현을 하지 못했고 강의를 끝까지는 못 들어성 다음 부분으로 넘겨보겠습니당...!)

그리고 저번까지는 계속해서 그냥 ppt에 나와있는 기본코드를 구현하는 것에 그쳤는데, 여기 나와있는 그 미로 탐험이 개인적으로 재미있어보이더라구요??

그래서 구현을 한번 해보았습니당ㅎㅎㅎ

import numpy as np
import matplotlib.pyplot as plt
import time
import argparse

# 미로 크기 설정 (6x9 미로)
maze = np.array([
    [0, 0, 0, 0, 0, 0, 0, 1, 0],  # 벽 (1)
    [0, 0, 1, 0, 0, 0, 0, 1, 0],  # 길 (0)
    [0, 0, 1, 0, 0, 0, 0, 1, 0],
    [0, 0, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0]
])

start = (2, 0)
goal = (0, 8)

actions = ['up', 'down', 'left', 'right']
action_map = {0: 'up', 1: 'down', 2: 'left', 3: 'right'}

# 미로 출력 함수
def plot_maze(maze, agent_position, ax=None, agent_plot=None,title=None):
    if ax is None or agent_plot is None:
        fig, ax = plt.subplots(figsize=(6, 6))
        ax.imshow(maze, cmap='binary')
        ax.scatter(goal[1], goal[0], c='green', s=100, marker='x')
        agent_plot = ax.scatter(agent_position[1], agent_position[0], c='red', s=100, marker='*')
        ax.set_xticks(np.arange(-0.5, maze.shape[1], 1), minor=True)
        ax.set_yticks(np.arange(-0.5, maze.shape[0], 1), minor=True)
        ax.grid(which='minor', color='black', linestyle='-', linewidth=2)
        plt.ion()
        plt.show()
        return ax, agent_plot
    agent_plot.set_offsets([agent_position[1], agent_position[0]])
    if title:
        ax.set_title(title, fontsize=14)

    plt.draw()
    plt.pause(0.01)

    return ax, agent_plot

# 에이전트 이동 함수
def move_agent(agent_position, direction):
    x, y = agent_position
    if direction == 'up' and x > 0 and maze[x-1, y] != 1:
        return (x-1, y)
    elif direction == 'down' and x < maze.shape[0] - 1 and maze[x+1, y] != 1:
        return (x+1, y)
    elif direction == 'left' and y > 0 and maze[x, y-1] != 1:
        return (x, y-1)
    elif direction == 'right' and y < maze.shape[1] - 1 and maze[x, y+1] != 1:
        return (x, y+1)
    return agent_position

# 상태 인덱스 변환
def state_index(state):
    return state[0] * maze.shape[1] + state[1]

# Q-테이블 및 모델 초기화
num_states = maze.shape[0] * maze.shape[1]
num_actions = len(actions)
Q = np.zeros((num_states, num_actions))
Model = {}

# ε-greedy 정책
def epsilon_greedy_policy(Q, state, epsilon):
    if np.random.rand() < epsilon:
        return np.random.choice(num_actions)
    return np.argmax(Q[state])

# Dyna-Q 알고리즘
def DynaQ(planning_step, num_episodes, alpha=0.1, gamma=0.9, epsilon=0.1):
    global Q, Model

    ax, agent_plot = plot_maze(maze, start) #일단 maze만들고

    for episode in range(num_episodes):
        state = start
        state_idx = state_index(state) #idx를 통해 table을 만들어야하니.
        num_step = 1

        while state != goal:
            action = epsilon_greedy_policy(Q, state_idx, epsilon)
            next_state = move_agent(state, action_map[action])
            next_state_idx = state_index(next_state)
            reward = 1 if next_state == goal else -0.01 #reward는 goal에 도착할때만!

            # Q 업데이트
            Q[state_idx, action] += alpha * (reward + gamma * np.max(Q[next_state_idx]) - Q[state_idx, action]) #Q-learning에서 봤듯이.

            # 환경 모델 업데이트
            Model[(state_idx, action)] = (next_state_idx, reward) #next랑 reward

            # Planning 단계
            for _ in range(planning_step):
                sampled_state_idx, sampled_action = list(Model.keys())[np.random.randint(len(Model))] #요거 어케할지 몰라서 지피티참고
                sampled_next_state_idx, sampled_reward = Model[(sampled_state_idx, sampled_action)] #next랑 reward저장되어잇는고임
                Q[sampled_state_idx, sampled_action] += alpha * (sampled_reward + gamma * np.max(Q[sampled_next_state_idx]) - Q[sampled_state_idx, sampled_action])

            state = next_state
            state_idx = next_state_idx
            planning_title = f"episode {episode + 1}, step {num_step}"
            ax, agent_plot = plot_maze(maze, state, ax, agent_plot,planning_title)
            num_step += 1

        print(f"Episode {episode + 1} completed with {num_step} steps!")

    return Q

# 메인 함수
def main():
    parser = argparse.ArgumentParser(description="Simple maze with Dyna-Q")
    parser.add_argument("--planning_step", type=int, default=5, help="Number of planning steps")
    parser.add_argument("--num_episodes", type=int, default=10, help="Number of training episodes")
    args = parser.parse_args()

    global Q, Model
    Q = np.zeros((num_states, num_actions))  # Q-테이블 초기화
    Model = {}  # 환경 모델 초기화

    final_Q = DynaQ(args.planning_step, args.num_episodes)

    print("\nFinal Q-table:")
    print(final_Q)

if __name__ == "__main__":
    main()

이전과는 다른 점은, Model[(state_idx,action)]이 추가 되었다는 것인데요.

여기서 Model은 정말 다양한 모델을 쓸 수 있지만 일단 ppt에서 Model에도 table lookup도 있다고 해서 일단은 table lookup방식으로 해보았습니다! ! ! !

이런식으로 점점 수렴하는 것을 알 수 있습니다!!!

#### 1.  Monte Carlo Control Policy #### 
#==============================================================================

import numpy as np

num_states = 5
num_actions = 2
num_episodes = 5000

theta = np.random.randn(num_states, num_actions)  # 각 상태에서 행동별 가중치
#원래 사실 theta를 어떻게 initialize 해야하는지 감이 안잡혔었음.

# Softmax 정책 함수
def softmax_policy(state, theta):
    preferences = theta[state]  # 해당 상태의 행동별 가중치 가져오기
    exp_values = np.exp(preferences - np.max(preferences))  # 안정적인 softmax
    return exp_values / np.sum(exp_values)

# 확률에 따라 행동 선택
def choose_action(state, theta):
    probs = softmax_policy(state, theta)
    return np.random.choice(num_actions, p=probs)


# 한 번의 에피소드를 실행하면서 데이터를 모으는 코드 (Monte Carlo)
def run_episode(theta, max_steps=10):
    episode = []
    state = np.random.randint(0, num_states)  # 랜덤한 초기 상태

    for _ in range(max_steps):  # max_steps 이후 종료
        action = choose_action(state, theta)
        next_state = np.random.randint(0, num_states)
        reward = np.random.randn()

        episode.append((state, action, reward))
        state = next_state

    return episode

alpha = 0.01  # 학습률
gamma = 0.9   # 감가율 (할인율)

# GLIE Monte Carlo Control 학습
for episode_num in range(1, num_episodes + 1):
    episode = run_episode(theta) 

    G = 0  # 리턴값 초기화

    for state, action, reward in reversed(episode):
        G = reward + gamma * G  # 할인된 보상 계산
        probs = softmax_policy(state, theta)

        grad = np.zeros_like(theta[state])
        #gradient를 저장하는 저장소! 
        grad[action] = 1 - probs[action]  # log 확률의 gradient가 이렇게 계산이 되고 
        #여기서 헷갈렸던 건, 선택한 행동 선택한 행동 a에 대해서만 기울기를 계산
        theta[state] += alpha * grad * G  # 정책 파라미터 업데이트
        #alpha * log gradient * G 이렇게 되는 것임. 

# 학습된 파라미터 출력
print("Theta:")
print(theta)



#### 2.  Action Value Actor Critic #### 
#==============================================================================

import numpy as np

num_states = 5
num_actions = 2
num_episodes = 5000

theta = np.random.randn(num_states, num_actions)  # 각 상태에서 행동별 가중치
#원래 사실 theta를 어떻게 initialize 해야하는지 감이 안잡혔었음.
w = np.zeros(num_states * num_actions)  # VFA에서 사용할 가중치 초기화

# Softmax 정책 함수
def softmax_policy(state, theta):
    preferences = theta[state]  # 해당 상태의 행동별 가중치 가져오기
    exp_values = np.exp(preferences - np.max(preferences))  # 안정적인 softmax
    return exp_values / np.sum(exp_values)

# 확률에 따라 행동 선택
def choose_action(state, theta):
    probs = softmax_policy(state, theta)
    return np.random.choice(num_actions, p=probs)
    #행동 선택 

# 한 번의 에피소드를 실행하면서 데이터를 모으는 코드 (Monte Carlo) : 이건 필요 x .왜냐면 매스텝마다 update하니까. 
#def run_episode(theta, max_steps=10):


alpha = 0.01  # 학습률
gamma = 0.9   # 감가율 (할인율)



def feature_vector(state,action,num_states,num_actions):
    vec = np.zeros(num_states * num_actions)
    vec[state * num_actions + action] = 1  
    return vec

def VFA(state, action, w):
    return np.dot(w, feature_vector(state, action, num_states, num_actions))  # 가중치와 특징 벡터의 내적



for episode_num in range(1, num_episodes + 1):
    state = np.random.randint(0, num_states)  # 초기 상태
    action = choose_action(state, theta) #action 고르고 

    #여기서 state,action,reard in reversed(episode)할 필요가 없는 게, 이건 매번 update다.
    for _ in range(10):  # 최대 10 스텝
        reward = np.random.randn()  # 보상 샘플링
        next_state = np.random.randint(0, num_states)  # 환경에서 다음 상태 샘플링
        next_action = choose_action(next_state, theta)  # 정책에 따라 다음 행동 선택

        delta = reward + gamma * VFA(next_state, next_action, w) - VFA(state, action, w)  # TD error


        # 크리틱 업데이트 (w 업데이트)
        w += alpha * delta * feature_vector(state, action, num_states, num_actions)

        # 액터 업데이트 (theta 업데이트)
        probs = softmax_policy(state, theta)
        grad = np.zeros_like(theta[state])
        grad[action] = 1 - probs[action]
        theta[state] += alpha * grad * delta

        # 다음 스텝으로 이동
        state, action = next_state, next_action        

# 학습된 파라미터 출력
print("Theta:")
print(theta)

6강에 있는 내용들 그대로 이해하기 쉽게 조금만 바꿔서 해보았습니다!!!!!

5강에서 한번 개념 제대로 잡으니까, 그냥 지식 업데이트만 하면 되는 느낌이더라구용!!! 혹시 질문이 있다면,,,댓글을 남겨주세요!!

"""
THis is a code for Model Free Control in RL. 
"""

# ###1. Monte Carlo Value Function Approximation ###
# #==============================================================================
import numpy as np

num_states = 5    # 상태 개수
num_actions = 2   # 행동 개수
num_episodes = 5000  

# 가중치 초기화 (VFA용)
w = np.zeros(num_states)  # feature vector의 크기만큼 가중치 생성

# ε-greedy policy [만약, 저 epsilon이 고정이라면 그냥 exploration만 계속하게 됨]
def epsilon_greedy_policy(w, state, epsilon):
    # 행동에 대한 VFA 값 계산
    action_values = [VFA(state, w) for _ in range(num_actions)] #수정 

    # 가장 높은 VFA 값을 가지는 행동 선택
    best_action = np.argmax(action_values)

    # ε-greedy 정책
    policy = np.full(num_actions, epsilon / num_actions)   # 모든 행동에 대해 ε/m 확률 부여
    policy[best_action] += 1 - epsilon # 가장 좋은 행동에는 1 - ε 추가 확률 

    return np.random.choice(np.arange(num_actions), p=policy)

# 한 번의 에피소드를 실행하면서 데이터를 모으는 코드 (Monte Carlo)
def run_episode(epsilon, max_steps=10):
    episode = []  
    state = np.random.randint(0, num_states)  # 랜덤한 초기 상태

    while True:
        action = epsilon_greedy_policy(w, state, epsilon) #epsilon_greedy_policy로 탐색과정! 
        next_state = np.random.randint(0, num_states)  #
        reward = np.random.randn()

        episode.append((state, action, reward)) 
        state = next_state

        if len(episode) >= max_steps:  # 최대 10번 이동 후 종료
            break
    return episode

def feature_vector(state, num_states):
    vec = np.zeros(num_states)
    vec[state] = 1  
    return vec

def VFA(state, w):
    return np.dot(w, feature_vector(state, num_states))  # 상태에 대한 가중치 적용

# GLIE Monte Carlo Control 학습
for episode_num in range(1, num_episodes+1):
    epsilon = 1 / episode_num # episode를 점점 늘려갈 때마다 epsilon값이 줄어든다. 
    episode = run_episode(epsilon) #매번 epsilon greedy policy로 탐색을 해서 episode를 만들어낸다. 

    G = 0  # 매번 그냥 0에서부터 시작. 그 에피소드에서는 G=0인 것임.
    visited = set()  # 첫 방문 판별용

    for state, action, reward in reversed(episode):
        G = reward + 0.9 * G  # 감가율  = 0.9 

        if (state, action) not in visited:  # 첫 방문인지 확인 
            visited.add((state, action)) 
            state_vec = feature_vector(state,num_states) # 상태 벡터 생성
            alpha = 1 / (episode_num + 1)

            w += alpha * (G - VFA(state, w)) * state_vec  # w 업데이트
            #Q[state, action] += alpha * (G - Q[state, action])여기서는 이걸 할 필요가 없음. 단순히 w만 업데이트 하면 됨. 

print("W:")
print(w)


#==============================================================================

#### 2.SARSA ####
w = np.zeros(num_states * num_actions) # feature vector의 크기만큼 가중치 생성
def epsilon_greedy_policy(w, state, epsilon):
    # 행동에 대한 VFA 값 계산
    action_values = [VFA(state, w) for _ in range(num_actions)]

    # 가장 높은 VFA 값을 가지는 행동 선택
    best_action = np.argmax(action_values)

    # ε-greedy 정책
    policy = np.full(num_actions, epsilon / num_actions)   # 모든 행동에 대해 ε/m 확률 부여
    policy[best_action] += 1 - epsilon # 가장 좋은 행동에는 1 - ε 추가 확률 

    return np.random.choice(np.arange(num_actions), p=policy)
def run_episode_next(epsilon, max_steps=10):
    episode = []  
    state = np.random.randint(0, num_states)  # 랜덤한 초기 상태
    action = epsilon_greedy_policy(w, state, epsilon)  # 초기 행동 선택

    while True:
        next_state = np.random.randint(0, num_states)  # 임의의 환경 이동
        reward = np.random.randn()
        next_action = epsilon_greedy_policy(w, next_state, epsilon) # 다음 행동 선택

        episode.append((state, action, reward, next_state, next_action)) 

        state, action = next_state, next_action  # SARSA는 (s, a, r, s', a') 방식으로 진행!

        if len(episode) >= max_steps:  # 최대 10번 이동 후 종료
            break
    return episode   


def feature_vector(state,action,num_states,num_actions):
    vec = np.zeros(num_states * num_actions)
    vec[state * num_actions + action] = 1  
    return vec

def VFA(state, action, w):
    return np.dot(w, feature_vector(state, action, num_states, num_actions))  # state-action에 대한 가중치 적용

for episode_num in range(1, num_episodes+1):
    epsilon = 1 / episode_num # episode를 점점 늘려갈 때마다 epsilon값이 줄어든다. 
    episode = run_episode_next(epsilon)  

    visited = set()  # 첫 방문 판별용

    for state, action, reward, next_state, next_action in reversed(episode):
        if (state, action) not in visited:  
            visited.add((state, action)) 
            state_action_vec = feature_vector(state, action, num_states,num_actions) # 상태 벡터 생성

            alpha = 1 / (episode_num + 1)

            w += alpha * (reward + 0.9 * VFA(next_state, next_action, w) - VFA(state, action, w)) * state_action_vec

print("학습된 가중치 벡터 w:")
print(w)


#### 3.n-step SARSA ####
n_step = 3  
alpha = 0.1

for episode_num in range(1, num_episodes + 1):
    epsilon = 1 / episode_num  # Exploration 감소
    episode = run_episode_next(epsilon)  # 에피소드 진행

    for t in range(len(episode)):  # 각 time step에 대해 반복
        G = 0  # n-step return 초기화

        # 1. n-step 동안 보상 계산
        for i in range(n_step):  # n-step동안 보상 계산
            if t + i < len(episode):
                G += (0.9 ** i) * episode[t + i][2]  # 보상 추가 n-step 동안 보상 계산 : 이거는 건들 수 없고, 건들 필요가 없음. 

        # 2. n-step 후의 Q 값 추가 여기서 건든다.
        if t + n_step < len(episode):
            G += (0.9 ** n_step) * VFA(episode[t + n_step][3], episode[t + n_step][4], w)

        # 3. Q 업데이트
        state, action = episode[t][:2]  # 현재 상태, 행동
        state_action_vec = feature_vector(state, action, num_states, num_actions)  # 상태-행동 벡터 생성
        w += alpha * (G - VFA(state, action, w)) * state_action_vec  # 가중치 업데이트

print("학습된 가중치 벡터 w:")
print(w)


#### 4.backward SARSA ####

alpha = 0.1  # 학습률
gamma = 0.9  # 할인율
lmbda = 0.8  # Eligibility Trace 감쇠율

for episode_num in range(1, num_episodes + 1):
    #원래는
    E = np.zeros((num_states, num_actions)) 
    #Q = np.zeros((num_states, num_actions)) 
    w = np.zeros(num_states * num_actions)  
    epsilon = 1 / episode_num  # Exploration 감소
    episode = run_episode_next(epsilon)

    for state, action, reward, next_state, next_action in reversed(episode):
        d = reward + gamma * VFA(next_state, next_action, w) - VFA(state, action, w)#d = reward + 0.9 * Q[next_state,next_action] - Q[state,action]

        E[state,action] = E[state,action] + 1 #일단 방문했으니까 +1 증가시킴
        #흠 여기까지는 그래도 어느정도 이해가 가는데,밑에는 잘 몰라서
        for s in range(num_states):
            for a in range(num_actions):
                w += alpha * d * E[s, a]  # Q 업데이트
                E[s, a] *= gamma * lmbda  #(시간이 지나면서 감소)
            """
            1. 기본 SARSA와의 비교 
            Q[state, action] += alpha * (reward + 0.9 * Q[next_state, next_action] - Q[state,action])  
            => 이게 기본 SARSA알고리즘
            => Q[state, action] += alpha * (d) 인 것임.  
            따라서, E[s,a]를 단순히 곱하면
            Q[state, action] += alpha * (d) * E[s,a]임 


            2. 왜 여기서 num_states와 num_actions에 대해 다 계산하니? 
            Q 값을 업데이트할 때는 현재 상태뿐만 아니라 과거에 방문했던 상태들도 보상의 영향을 받음 
            이걸 처리하기 위해 모든 상태-행동 쌍에 대해 Eligibility Trace를 곱해서 업데이트
            """
print(w)

#### 5. Q-Learning ####
def greedy_policy_val_weight(Q,state,action): #state가 주어질 때 best action을 선택해서 값을 찾는 greedy
    #return np.max(VFA(state,action,w)) #현실적으로 greedy가 안될 거 같다? 이부분이? 
    return np.max([VFA(state, action, w) for action in range(num_actions)])

    #ver2. 정리 버전 - 37p : Q(S,A) ←Q(S,A) + α R + γ maxa′Q(S′,a′)−Q(S,A)
for episode_num in range(1, num_episodes+1):
    epsilon = 1 / episode_num # episode를 점점 늘려갈 때마다 epsilon값이 줄어든다. 
    #behaviro policy ( 내가 관찰한 policy )
    episode = run_episode_next(epsilon) 

    visited = set()  # 첫 방문 판별용

    for state, action, reward, next_state, next_action in reversed(episode): 
        if (state, action) not in visited:  
            visited.add((state, action))  

            N[state, action] += 1  # 방문 횟수 증가
            alpha = 1 / N[state, action]  # 학습률 감소 (GLIE 조건)

            # target policy에서의 action 추출? 
            # 어떻게 target policy를 특정하지? 일단 greedy라고 나와있으니, greedy하게 episode를 뽑아보자. 
            #next_val = greedy_policy_val(Q, next_state)
            next_val =greedy_policy_val_weight(state,action,w) #이게 맞는건가?

            w += alpha * (reward + 0.9 * next_val - VFA(state, action, w)) * feature_vector(state, action, num_states, num_actions)
            #여기서 매우 중요한 건, 똑같이 저렇게 reversed(episode)를 했다고 하더라도, 저 위에서는 G를 썼지만, 여기서는 그때의 그 reward만을 써서 update를 한다는 것
print("w")
print(w)
'''
Q-learning에서는, 그 다음에 최적의 행동을 선택할 때, 
가장 그 이후의 최적의 행동이어야 하는데 과연 이걸 어떻게 weight로 표현할 수 있을까?

(이전에는 단순히 Q[state]의 max를 뽑았는데?)
=> 일단 state가 고정되어 있으니까, 너무 걱정하지 말고 그 state에 해당하는 action을 뽑아서 그 action에 대한 가중치를 뽑아보자.
'''
### 6. DQN ###
w = np.zeros(num_states * num_actions)  # 가중치 벡터
w_minus = np.copy(w)

def get_mini_batch(episode, batch_size):
      """ 주어진 episode에서 미니 배치를 샘플링하는 함수 """
    # 무작위로 미니 배치 샘플링 (배치 사이즈 만큼)
    mini_batch = random.sample(episode, batch_size)
    return mini_batch

for episode_num in range(1, num_episodes+1):
    epsilon = 1 / episode_num # episode를 점점 늘려갈 때마다 epsilon값이 줄어든다. 
    #behavior policy ( 내가 관찰한 policy )
    episode = run_episode_next(epsilon) #e-greedy로 episode를 뽑아낸다.

    visited = set()  # 첫 방문 판별용

    #매번 뽑는 게 아니라, random mini-batch를 뽑는다 
    batch_size = 4 
    mini_batch = get_mini_batch(episode, batch_size)

    for state, action, reward, next_state, next_action in mini_batch: 
        if (state, action) not in visited:  
            visited.add((state, action))  

            N[state, action] += 1  # 방문 횟수 증가
            alpha = 1 / N[state, action]  # 학습률 감소 (GLIE 조건)

            # target policy에서의 action 추출? 
            # 어떻게 target policy를 특정하지? 일단 greedy라고 나와있으니, greedy하게 episode를 뽑아보자. 
            #next_val = greedy_policy_val(Q, next_state)
            next_val = VFA(next_state, next_action, w_minus) #왜냐면, 저기 식에서 w_minus를 쓰니까
            w += alpha * (reward + 0.9 * next_val - VFA(state, action, w)) * feature_vector(state, action, num_states, num_actions)

    if episode_num % 10 == 0:  # 예: 10 에피소드마다 동기화
        w_minus = np.copy(w)

print("w")
print(w)

밑에꺼는, GPT한테 argparse써서 좀 예쁘게 보일 수 있도록 맡겨보았습니당

import numpy as np
import random
import torch
import torch.nn as nn
import torch.optim as optim
from collections import deque

# 하이퍼파라미터 설정
num_episodes = 1000
epsilon_start = 1.0
epsilon_end = 0.1
epsilon_decay = 0.995
gamma = 0.99  # 할인율
batch_size = 32
learning_rate = 0.0001
update_target_every = 10  # 타겟 네트워크 업데이트 주기

# 환경 설정 (예시로 OpenAI Gym 환경을 사용)
import gym
env = gym.make('CartPole-v1')

# Q 네트워크 정의
class QNetwork(nn.Module):
    def __init__(self, state_dim, action_dim):
        super(QNetwork, self).__init__()
        self.fc1 = nn.Linear(state_dim, 64) 
        self.fc2 = nn.Linear(64, 64)
        self.fc3 = nn.Linear(64, action_dim)

    def forward(self, x):
        x = torch.relu(self.fc1(x))
        x = torch.relu(self.fc2(x))
        return self.fc3(x)

# Q 네트워크와 타겟 네트워크 초기화
state_dim = env.observation_space.shape[0]
action_dim = env.action_space.n
q_network = QNetwork(state_dim, action_dim)
target_network = QNetwork(state_dim, action_dim)
target_network.load_state_dict(q_network.state_dict())  # 타겟 네트워크 초기화
target_network.eval()  # 타겟 네트워크는 평가 모드

# 옵티마이저
optimizer = optim.Adam(q_network.parameters(), lr=learning_rate)

# 경험 리플레이 버퍼
memory = deque(maxlen=10000)

# epsilon-greedy 정책
def epsilon_greedy(state, epsilon):
    if random.random() < epsilon:
        return env.action_space.sample()  # 랜덤 행동
    else:
        state_tensor = torch.FloatTensor(state).unsqueeze(0)
        q_values = q_network(state_tensor)  # Q값 예측
        return torch.argmax(q_values).item()  # 가장 큰 Q값을 가지는 행동 선택

# 경험 리플레이에서 미니 배치 샘플링
def get_mini_batch(batch_size):
    batch = random.sample(memory, batch_size)
    states, actions, rewards, next_states, dones = zip(*batch)
    return torch.FloatTensor(states), torch.LongTensor(actions), torch.FloatTensor(rewards), torch.FloatTensor(next_states), torch.BoolTensor(dones)

# 학습 루프
epsilon = epsilon_start
for episode in range(num_episodes):
    state = env.reset()
    total_reward = 0
    done = False

    while not done:
        action = epsilon_greedy(state, epsilon)
        next_state, reward, done, _ = env.step(action)
        memory.append((state, action, reward, next_state, done))  # 경험 리플레이 버퍼에 저장

        state = next_state
        total_reward += reward

        # 미니 배치로 학습
        if len(memory) > batch_size:
            states, actions, rewards, next_states, dones = get_mini_batch(batch_size)

            # 현재 Q 네트워크에서 Q값 계산
            q_values = q_network(states) #feature vector뽑기 + w내적이 다 여기에 포함된 과정임. 
            q_value = q_values.gather(1, actions.unsqueeze(1))  # 현재 행동에 대한 Q값

            # 타겟 네트워크에서 Q값 계산
            next_q_values = target_network(next_states)
            next_q_value = next_q_values.max(1)[0]  # 가장 큰 Q값

            # 타겟 Q값 계산
            target = rewards + gamma * next_q_value * (~dones)

            # 손실 함수 계산
            loss = nn.MSELoss()(q_value.squeeze(), target)

            # 역전파
            optimizer.zero_grad()
            loss.backward()
            optimizer.step()

    # epsilon 값 감소
    epsilon = max(epsilon_end, epsilon * epsilon_decay)

    # 주기적으로 타겟 네트워크 업데이트
    if episode % update_target_every == 0:
        target_network.load_state_dict(q_network.state_dict())

    print(f"Episode {episode+1}/{num_episodes}, Total Reward: {total_reward}")

print("학습 완료!")

하나하나 다 저 David RL보고 구현한거라서! 오류가 있을 수도 있으니(?) 주의해주세요ㅎㅎ

결국 중요한 건, 어떻게 저렇게 0.9뒤에 곱해지는 애들이 어떻게 달라지는지이다.

지피티를 진짜 검토할 때만 쓰고 혼자 이렇게 구현했다는 것이 매우 뿌듯><하다

Q-learning과 다른 learning의 차이?

#### 5. Q-Learning ####

def greedy_policy_action(Q, state): #state만 주어질 때 best action을 찾는 greedy
    return np.argmax(Q[state])

    #ver1. 정석 버전 PPT 35p : Q(St ,At ) ←Q(St ,At ) + α Rt+1 + γQ(St+1,A′)−Q(St ,At ) 이 식 그대로 
for episode_num in range(1, num_episodes+1):
    epsilon = 1 / episode_num # episode를 점점 늘려갈 때마다 epsilon값이 줄어든다. 
    #behaviro policy ( 내가 관찰한 policy )
    episode = run_episode_next(epsilon) 

    visited = set()  # 첫 방문 판별용

    for state, action, reward, next_state, next_action in reversed(episode): 
        if (state, action) not in visited:  
            visited.add((state, action))  

            N[state, action] += 1  # 방문 횟수 증가
            alpha = 1 / N[state, action]  # 학습률 감소 (GLIE 조건)

            # target policy에서의 action 추출? 
            # 어떻게 target policy를 특정하지? 일단 greedy라고 나와있으니, greedy하게 episode를 뽑아보자. 
            next_action_target = greedy_policy_action(Q, next_state)  # 목표 정책의 행동 선택

            Q[state, action] += alpha * (reward + 0.9 * Q[next_state, next_action_target] - Q[state, action])

print("학습된 Q 테이블:")
print(Q)

def greedy_policy_val(Q, state): #state가 주어질 때 best action을 선택해서 값을 찾는 greedy
    return np.max(Q[state])

    #ver2. 정리 버전 PPT 37p : Q(S,A) ←Q(S,A) + α R + γ maxa′Q(S′,a′)−Q(S,A)
for episode_num in range(1, num_episodes+1):
    epsilon = 1 / episode_num # episode를 점점 늘려갈 때마다 epsilon값이 줄어든다. 
    #behaviro policy ( 내가 관찰한 policy )
    episode = run_episode_next(epsilon) 

    visited = set()  # 첫 방문 판별용

    for state, action, reward, next_state, next_action in reversed(episode): 
        if (state, action) not in visited:  
            visited.add((state, action))  

            N[state, action] += 1  # 방문 횟수 증가
            alpha = 1 / N[state, action]  # 학습률 감소 (GLIE 조건)

            # target policy에서의 action 추출? 
            # 어떻게 target policy를 특정하지? 일단 greedy라고 나와있으니, greedy하게 episode를 뽑아보자. 
            next_val = greedy_policy_val(Q, next_state)  # 최대 Q 값 사용

            Q[state, action] += alpha * (reward + 0.9 * next_val - Q[state, action])
            #여기서 매우 중요한 건, 똑같이 저렇게 reversed(episode)를 했다고 하더라도, 저 위에서는 G를 썼지만, 여기서는 그때의 그 reward만을 써서 update를 한다는 것
print("학습된 Q 테이블:")
print(Q)

#### 2.SARSA ####
for episode_num in range(1, num_episodes+1):
    epsilon = 1 / episode_num # episode를 점점 늘려갈 때마다 epsilon값이 줄어든다. 
    episode = run_episode_next(epsilon)  

    visited = set()  # 첫 방문 판별용

    for state, action, reward, next_state, next_action in reversed(episode):
        if (state, action) not in visited:  
            visited.add((state, action))  

            N[state, action] += 1  # 방문 횟수 증가
            alpha = 1 / N[state, action]  # 학습률 감소 (GLIE 조건)

            Q[state, action] += alpha * (reward + 0.9 * Q[next_state, next_action] - Q[state, action])
            #여기서 매우 중요한 건, 똑같이 저렇게 reversed(episode)를 했다고 하더라도, 저 위에서는 G를 썼지만, 여기서는 그때의 그 reward만을 써서 update를 한다는 것
print("학습된 Q 테이블:")
print(Q)

• SARSA vs Q-Learning
  • next_state, next_action은 어디서?
    • next_state : 둘다 기존의 policy(behavior policy)에서 뽑는다.
    • next_action :
      • SARSA : from behavior policy (run_episode_next 함수 활용)
      • Q-Learning : from target policy (greedy_policy_action 함수 or greedy_policy_val)

            <br>
            ⇒ 그렇다면, 언제 greedy_policy_action을? 언제 greedy_policy_val을?
            <br>
            <br>
            greedy_policy_action : 
            <br>
            최적의 행동(next action)을 직접 선택
            <br>
            `argmax(Q[state])`를 사용해 가장 높은 Q 값을 가진 행동 선택
            <br>
            <br>
            greedy_policy_val : 

            특정 상태에서 최대 Q 값을 가져오기 위해 사용

            `max(Q[state])`를 사용해 가능한 행동 중 최대 Q 값 반환

epsilon_greedy_policy vs greedy_policy

def epsilon_greedy_policy(Q, state, epsilon):
    m = len(Q[state])
    best_action = np.argmax(Q[state])  # Q 값이 가장 높은 행동 선택

    policy = np.full(m, epsilon / m)   # 모든 행동에 대해 ε/m 확률 부여
    policy[best_action] += 1 - epsilon # 가장 좋은 행동에는 1 - ε 추가 확률

    return np.random.choice(np.arange(m), p=policy)
    # 완전히 랜덤이 아니라, 특정 확률 분포를 따르는 랜덤 선택을 하기 위해서. 


def greedy_policy_action(Q, state): #state만 주어질 때 best action을 찾는 greedy
    return np.argmax(Q[state])


def greedy_policy_val(Q, state): #state가 주어질 때 best action을 선택해서 값을 찾는 greedy
    return np.max(Q[state])

• epsilon_greedy_policy vs greedy_policy

  • e_greedy : 탐색(exploration)까지 고려해야 할 때 -> ⇒ 다시 살펴보니, 애초에 ‘탐색’임. (함수 이름을 epsilon_greedy_policy_exp)이렇게 했어야하나…ㅎㅎ → 그래서 저기에 np.random.choice를 넣어두는 것임.

  • greedy_policy : 가장 좋은 행동, 좋은 값만 선택할 때

    → 그래서 저기에 np.random.choice가 없는 것

반성

0. 처음부터 0층을 채움
1. 층을 순회할 때 : 1층~max_k층까지 채워야 함. (1,max_k+1)이 맞음.
2. 호수를 순회할 때 : 1호~max까지 채워야 함. 그래서 (0,max)가 맞음.

T = int(input())

for _ in range(T):  
    k = int(input())
    n = int(input())
    people = [x for x in range(1, n+1)]  
    for _ in range(k):
        for i in range(1, n): 
            people[i] += people[i-1] 
    print(people[n-1])

# 잘못된 풀이

# T = int(input())
# d = [[0]*14 for i in range(0,14)] #14 x 14 matrix
# d[0] = [i for i in range(1,15)] #0층은 1부터 14까지 사람이 산다. d[0][0] = 0층 1호에 사는 사람 수 d[0][1] = 0층 2호에 사는 사람 수
# k_n = [(int(input()), int(input())) for _ in range(T)]
# max_k = max(k_n, key=lambda x: x[0])[0]  # 층 최대값
# max_n = max(k_n, key=lambda x: x[1])[1] 

# for a in range(1,max_k+1): #층(이미 1층부터는 채워져있으니까)
#   for b in range(0,max_n):#호수
#     if b == 0:
#             d[a][b] = d[a - 1][b]  # 1호는 바로 아래층의 사람 수와 같음
#         else:
#             d[a][b] = d[a][b - 1] + d[a - 1][b]  # 점화식 적용

# for (k,n) in k_n:
#   print(d[k][n-1])

🚀 핵심 차이점

1. 공간 복잡도 차이 네 풀이: d라는 2차원 리스트(14x14) 를 만들어서 저장함. (메모리 사용 큼) 정답 풀이: 1차원 리스트(people) 만 사용하여 메모리 절약함. 👉 교훈: 꼭 필요한 데이터만 저장하자! 2차원 배열 없이, 필요한 부분만 업데이트하는 방식을 연습

2. 점화식 적용 방식 네 풀이는 d[k][n] = d[k][n-1] + d[k-1][n]을 2차원 배열에 직접 적용. 정답 풀이는 people[i] += people[i-1]를 사용해 1차원 리스트에서 값을 누적. 👉 교훈: 배열을 줄이는 테크닉 배우기

people[i] += people[i-1] 방식처럼, 계산에 필요한 최소한의 변수만 업데이트하는 방식 고민해 보기.

3. 미리 저장 vs 실시간 계산 네 풀이는 최대 층수, 최대 호수를 미리 계산해서 d를 전부 채움. 정답 풀이는 각 테스트 케이스마다 바로 계산. 👉 교훈: 미리 계산할 필요가 없으면, 즉시 계산하는 방법 고려

모든 경우를 미리 계산하지 않고, 각 케이스에 맞춰 필요한 연산만 수행하는 방식이 더 효율적,..

문제
3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

접근 방법

1. 3 X N의 경우 나눠보기

   1. 3 x 0

      = 1 (근데 여기서 0이라고 할뻔 했다)

   2. 3 x 1

      = x

   3. 3 x 2

      = 3

   4. 3 x 3

      = x

   5. 3 x 4

      = 3 x 3 + 2 (중간에 연결이 되는 경우

   6. 3 x 5

      = x

   7. 3 x 6 ( 이 부분을 떠올리기 힘들었음)

      = 3×(N-2) 크기의 벽을 채운 후, 3×2 크기의 새로운 공간을 추가하는 방법 + 3×(N-4) 크기의 벽을 채운 후, 특수한 모양의 블록(새로운 모양)으로 채우는 방법 + 3×(N-6) 크기의 벽을 채운 후, 특수한 모양의 블록(새로운 모양)으로 채우는 방법

코드

N = int(input())

# dp 테이블 초기화
d = [0] * (N + 1)
d[0] = 1  # 3×0 크기의 벽을 채우는 경우는 1가지 (아무것도 놓지 않는 경우)

if N >= 2:
    d[2] = 3  # 3×2 크기의 벽을 채우는 경우는 3가지

# 짝수 크기만 계산
for i in range(4, N + 1, 2):
    d[i] = d[i - 2] * 3  # 기본적인 경우

    # 특수한 경우를 하나씩 직접 추가
    if i >= 4:
        d[i] += d[i - 4] * 2
    if i >= 6:
        d[i] += d[i - 6] * 2
    if i >= 8:
        d[i] += d[i - 8] * 2
    if i >= 10:
        d[i] += d[i - 10] * 2
    if i >= 12:
        d[i] += d[i - 12] * 2

print(d[N])

(선택사항) 오류 해결

💡 순서는 왜 고려하지 않아도 될까?

우리가 d[N]을 구할 때, d[N-2], d[N-4], d[N-6] 등을 활용하는 방식이 중복을 자동으로 포함

(1) 타일을 채우는 방식이 "순차적"으로 진행

우리는 항상 왼쪽부터 오른쪽으로 타일을 채운다고 가정

예를 들어, d[N]을 구할 때는 항상 3×(N-2)까지 채워진 상태에서 새로운 3×2 블록을 추가하는 방식을 고려.

✔ d[N-2]를 먼저 계산 → 이미 3×(N-2)까지는 채워진 상태

✔ 그 상태에서 3×2 블록을 추가하면 d[N-2] * 3

✔ 3×(N-4)까지 채워진 후 특수한 타일을 추가하는 경우도 자동으로 포함

즉, 순서를 고민할 필요 없이 이전 결과를 그대로 가져오면서 새로운 블록을 추가하는 방식이라 중복 계산이 없고, 순서도 자연스럽게 포함

(2) 특수한 경우는 항상 2가지 방향이 존재

우리가 특수한 경우를 d[N-4] * 2처럼 곱하기 2를 하는 이유도 순서와 관련

예를 들어, 3×4 크기의 특수 블록이 있다면

이 블록을 전체 3×N 크기의 벽에서 사용할 때,

1️⃣ 왼쪽에 놓을 수도 있고,

2️⃣ 오른쪽에 놓을 수도 있음

✔ 그래서 * 2를…

✔ 이렇게 하면 자연스럽게 모든 배치 순서가 자동으로… 포함

저번거는 다 그냥 노트필기에 해버려서ㅠ올릴 게 못된다...

저번주 스터디에 스터디원분이 구현을 하셔서 오신걸 보고! 깜짝~놀라버려성 나도 한번 구현을 해봐야겠다고 생각했다! ! ! ! ! ! !

그분이 공부하신 방법대로 한번 따라해봤다. (1) PPT를 곱씹어 보기 (2) 코드를 구현해보기

나도 근데 그런 타입(?)인 거 같다!!!

원래 Q-learning도 구현하려고 했으나,,, 시간관계상 일단

"""
THis is a code for Model Free Control in RL. 
"""

#### 1. GLIE Monte Carlo Control #### 
#==============================================================================
import numpy as np

num_states = 5    # 상태 개수
num_actions = 2   # 행동 개수
num_episodes = 5000  

# Q-테이블 초기화 (모든 Q(s,a)를 0으로 시작) 
# Q(s,a) ==  E[ Gt | St= s , At = a]
Q = np.zeros((num_states, num_actions)) 

# 각 상태에서 방문 횟수 저장
N = np.zeros((num_states, num_actions))

# ε-greedy policy [만약, 저 epsilon이 고정이라면 그냥 exploration만 계속하게 됨]
def epsilon_greedy_policy(Q, state, epsilon):
    m = len(Q[state])
    best_action = np.argmax(Q[state])  # Q 값이 가장 높은 행동 선택

    policy = np.full(m, epsilon / m)   # 모든 행동에 대해 ε/m 확률 부여
    policy[best_action] += 1 - epsilon # 가장 좋은 행동에는 1 - ε 추가 확률

    return np.random.choice(np.arange(m), p=policy)

# 한 번의 에피소드를 실행하면서 데이터를 모으는 코드 (Monte Carlo)
def run_episode(epsilon, max_steps=10):
    episode = []  
    state = np.random.randint(0, num_states)  # 랜덤한 초기 상태

    while True:
        action = epsilon_greedy_policy(Q, state, epsilon) #epsilon_greedy_policy로 탐색과정! 
        next_state = np.random.randint(0, num_states)  #
        reward = np.random.randn()

        episode.append((state, action, reward)) 
        state = next_state

        if len(episode) >= max_steps:  # 최대 10번 이동 후 종료
            break
    return episode



# GLIE Monte Carlo Control 학습
for episode_num in range(1, num_episodes+1):
    epsilon = 1 / episode_num # episode를 점점 늘려갈 때마다 epsilon값이 줄어든다. 
    episode = run_episode(epsilon) #매번 epsilon greedy policy로 탐색을 해서 episode를 만들어낸다. 

    G = 0  # 매번 그냥 0에서부터 시작. 그 에피소드에서는 G=0인 것임.
    visited = set()  # 첫 방문 판별용

    for state, action, reward in reversed(episode):
        G = reward + 0.9 * G  # 감가율  = 0.9 

        if (state, action) not in visited:  # 첫 방문인지 확인 
            visited.add((state, action)) 
            N[state, action] += 1  # 특정 state, 특정 action에 대해 방문 횟수 증가
            alpha = 1 / N[state, action]  # GLIE 조건: α → 0 (학습율 감소)
            Q[state, action] += alpha * (G - Q[state, action])  # Q(s,a) 업데이트


print("학습된 Q 테이블:")
print(Q)




#==============================================================================

#### 2.SARSA ####
def run_episode_next(epsilon, max_steps=10):
    episode = []  
    state = np.random.randint(0, num_states)  # 랜덤한 초기 상태
    action = epsilon_greedy_policy(Q, state, epsilon)  # 초기 행동 선택

    while True:
        next_state = np.random.randint(0, num_states)  # 임의의 환경 이동
        reward = np.random.randn()
        next_action = epsilon_greedy_policy(Q, next_state, epsilon) # 다음 행동 선택

        episode.append((state, action, reward, next_state, next_action)) 

        state, action = next_state, next_action  # SARSA는 (s, a, r, s', a') 방식으로 진행!

        if len(episode) >= max_steps:  # 최대 10번 이동 후 종료
            break
    return episode   


for episode_num in range(1, num_episodes+1):
    epsilon = 1 / episode_num # episode를 점점 늘려갈 때마다 epsilon값이 줄어든다. 
    episode = run_episode_next(epsilon)  

    visited = set()  # 첫 방문 판별용

    for state, action, reward, next_state, next_action in reversed(episode):
        if (state, action) not in visited:  
            visited.add((state, action))  

            N[state, action] += 1  # 방문 횟수 증가
            alpha = 1 / N[state, action]  # 학습률 감소 (GLIE 조건)

            Q[state, action] += alpha * (reward + 0.9 * Q[next_state, next_action] - Q[state, action])
            #여기서 매우 중요한 건, 똑같이 저렇게 reversed(episode)를 했다고 하더라도, 저 위에서는 G를 썼지만, 여기서는 그때의 그 reward만을 써서 update를 한다는 것
print("학습된 Q 테이블:")
print(Q)


#### 3.n-step SARSA ####

n_step = 3  
alpha = 0.1
for episode_num in range(1, num_episodes + 1):
    epsilon = 1 / episode_num  # Exploration 감소
    episode = run_episode_next(epsilon)  

    for t in range(len(episode)):  # 각 time step에 대해 반복
        G = 0  # n-step return 초기화

        # 1. n-step 동안 보상 계산
        for i in range(n_step): #3번 step이라고 하면 3번 반복해야함.
            if t + i < len(episode):
                G += (0.9 ** i) * episode[t + i][2]  # 이건 보상!!!! 

        # 2. n-step 후의 Q 값 추가
        if t + n_step < len(episode):
            G += (0.9 ** n_step) * Q[episode[t + n_step][3], episode[t + n_step][4]]

        # 3. Q 업데이트
        state, action = episode[t][:2]  # 현재 상태, 행동
        Q[state, action] += alpha * (G - Q[state, action])  
print("학습된 Q 테이블:")
print(Q)



#### 4.backward SARSA ####

alpha = 0.1  # 학습률
gamma = 0.9  # 할인율
lmbda = 0.8  # Eligibility Trace 감쇠율

for episode_num in range(1, num_episodes + 1):
    E = np.zeros((num_states, num_actions))
    Q = np.zeros((num_states, num_actions))
    epsilon = 1 / episode_num  # Exploration 감소
    episode = run_episode_next(epsilon)

    for state, action, reward, next_state, next_action in reversed(episode):
        d = reward + 0.9 * Q[next_state,next_action] - Q[state,action]

        E[state,action] = E[state,action] + 1 #일단 방문했으니까 +1 증가시킴
        #흠 여기까지는 그래도 괜찮은데, 밑의 걸 떠올리는 게 힘들었음. 
        for s in range(num_states):
            for a in range(num_actions):
                Q[s, a] += alpha * d * E[s, a]  # Q 업데이트
                E[s, a] *= gamma * lmbda  #(시간이 지나면서 감소)
            """
            1. 기본 SARSA와의 비교 
            Q[state, action] += alpha * (reward + 0.9 * Q[next_state, next_action] - Q[state,action])  
            => 이게 기본 SARSA알고리즘
            => Q[state, action] += alpha * (d) 인 것임.  
            따라서, E[s,a]를 단순히 곱하면
            Q[state, action] += alpha * (d) * E[s,a]임 


            2. 왜 여기서 num_states와 num_actions에 대해 다 계산하니? 
            Q 값을 업데이트할 때는 현재 상태뿐만 아니라 과거에 방문했던 상태들도 보상의 영향을 받음 
            이걸 처리하기 위해 모든 상태-행동 쌍에 대해 Eligibility Trace를 곱해서 업데이트!!!!! 
            """

시간은 많이 걸렸긴한데, 근데 구현해보니까 뭐가 뭔지 알것같긴하다. 그래서 너무 즐겁다~

혁펜하임님의 다양한 영상들을 보면서 공부해온 저였습니다. 사실 비전공자이다보니, 학교에서 선형대수학 강의나 딥러닝 강의를 들을 때마다 많이 힘들었(?)었는데요...ㅋㅋㅋ 그럴 때마다 혁펜하임님의 도움을 상당히 많이 받았습니다.

특히 인공지능수학을 공부할 때 배웠던 convex optimizaiton이나, 선형대수학이나, 딥러닝이나 상당히 많은 도움을 받았었습니다ㅎㅎ

바로 'Easy!딥러닝'입니다. 사실 AI가 정말 핫해진지 한 2년?정도 된 거 같은데요, 이제는 사람들이 그냥 '갖다 쓰기만 하면 되는 거 아니야?'하는 생각이 들 정도로 정말 쉬운 방법들로 코드 몇줄만 돌리면 딥러닝을 할 수 있는 시대가 되었습니다.

그 간극은 바로 '1.수학 지식+ 2.코딩 능력 + 3.모델 공부'로 해결되죠. 1,3번을 위한 바로 첫번째 스텝이 바로 'Easy!딥러닝' 책인 것 같습니다

저는 일단 역전파에 관련해서 리뷰해보겠습니다! 일단 딥러닝은 매 iteration마다 실제값과 훈련된값의 차이인 loss를 계산합니다(loss는 계산하는 방식마다 다 다릅니다). 그 loss를 궁극적으로 계산하는 이유는 뭘까요?

바로 그 loss를 이용해서 파라미터를 바꿔줘야 하기 때문입니다. 그 파라미터를 바꿔주는 거의 정석적인 방법이 바로 역전파입니다.

학교에서 backpropagation에 대해 배울 때, Chain rule을 활용해서 복잡하게 배웠던 기억이 있는데 이 책에서는 그림과 함께 상세하게 역전파의 기본 개념을 알려주더군요! 들,나의 개념으로 제시를 하는데 들어가고 나가고 이래서 들,나 인거 같습니다ㅋㅋ Activation function 통과 전을 들! Activation function 통과 후를 나!

일단 w2를 바꿔야 하니까, w2가 어떻게 L에 들어가는지 보면, w2-> 들2 -> 나2-> L 의 과정인데요

그 과정처럼 chain rule을 써서 L에 대한 w2미분을 쓸 수 있습니다

생각해보니 들 나 이렇게 쓰는게 진짜 편하네요 나/들 이 액티베이션 함수가 뭐인지에 따라서 실제 식은 다 달라지겠지만, 이해하는 데에는 훨 좋은!! 것 같습니다

그리고 나서 똑같이 chain rule을 써서 L에 대한 w1미분을 구할 수 있습니다 w1-> 들1 -> 나1-> 들2 -> 나2-> L 과정이 길다보니 당연히 Chain rule으로 구할 때도 좀 더 길겠죠?? 하지만 중요한건 모든 경로를 고려해줘야한다는 점! 그래서 사실상

w1-> 들1 -> 나1-> 들2 -> 나2-> L w1-> 들1 -> 나1-> 들‘2 -> 나’2-> L

이렇게 다양한 경로로 L에 영향을 미칠 수 있으니…! 노드의 개수에 맞춰서 모든 경로를 고려해야합니다~

근데 여기서 잘 생각해보면 가로로 노드가 많아질수록 액티베이션 미분이 점점 많아집니다! 처음에 w2를 L에 대해 미분한다고 치면, = 액티베이션 미분 x L에 대한 나2의 미분 w1을 L에 대해 미분한다고 치면, = 액티베이션 미분 x 웨이트 미분 x 액티베이션 미분 x L에 대한 나2의 미분

점점 액티베이션 미분 x 웨이트 미분이 계속 추가될 거 같다는 느낌이 들지 않으신가요!! 즉, 책에서 말하는 액웨!가 계속 추가된다는 말입니다. 이게 바로 다양한 activation function이 등장한 이유고, L에 대한 파라미터의 미분값들이 소실되지 않도록 ReLU같은 activation function이 등장한 이유입니다!

왜냐면 ReLU는 진짜 신기하게도 그냥 0보다 작으면 0이고 0보다 크면 그냥 y=x거든요 0보다 클때 미분하면(액티베이션 미분)이 1이니까 그래도 곱할때마다 값이 적어질 확률은 없겠죠???

그래서 이 책에서는 vanishing gradient를 액웨를 여러번 곱하게 되는 것의 문제로 규정하였고, 특히 여기서 ‘액’의 중요성을 알게 했습니다! (Activation function 잘 골라야 합니다…ㅋㅋ)

뭔가 액웨가 계속해서 곱해지는 게 어쩔 수 없는 back propagation의 본질적인 현상이고, 그래서 ’액‘을 잘 선택해야하는…점을 정말 잘 알려주신 것 같습니다!!!

저도 액웨로 배웠으면…좀 더 backpropagation이해가 빠르지 않았을까 하는 생각이…ㅋㅋㅋ 어찌되었든 이런 상세한 설명과 액웨가 들어있는 혁펜하임의 easy! 딥러닝 강추합니다!!!><

그리고 심지어 혁펜하임 강의도 있어서 이해하기도 정말 easy할거같네요!!!! 추천추천~

몬테카를로! Temporal Difference!

몬테카를로 : 세보는 거! 아 이렇네~~ policy를 따라서 계속 해보고, return들을 평균 내보는 것!

처음 방문한 것만 쳐주는 게 first-visit MC! => 방문한 모든 타임스텝을 고려하는 게 아니라 각 상태를 에피소드에서 처음 방문했을 때만 업데이트하는 방식

에피소드 경로: S1 → S2 → S3 → S2 → S4 (종료) 보상: 0 → 1 → -1 → 2 → 3 First-Visit MC는 S2를 두 번째 방문했을 때(보상 2)를 무시하고, 첫 방문 시점(보상 1)만 반영. Every-Visit MC는 S2에서 두 번 방문한 모든 보상을 업데이트함.

일단 왜 counter가 필요한지...? 이렇게 측정을 해야하기 때문에 필요한 것!

1. Increment Counter (방문 횟수 증가) 특정 상태 S가 방문될 때마다 그 상태의 방문 횟수를 증가시키는 과정. 즉, 해당 상태가 몇 번 방문되었는지 기록하는 변수.

2. Increment Total Return (총 보상 업데이트) 상태 S를 방문했을 때, 해당 에피소드에서 얻은 총 보상(return)을 업데이트하는 과정. 이 값을 누적해서 평균을 계산하면 상태 가치 V(S) 를 추정할 수 있음.

아직도 왜 몬테카를로여야하는지? ✅ 몬테카를로 방법이 RL에서 하는 일

1. 에피소드(게임 한 판)를 여러 번 실행
2. 각 상태에서 받는 총 보상(return)을 기록
3. 여러 번 실행한 결과를 평균 내서 상태 가치 V(S) 를 추정

Blackjack Example action1 stick - 카드 받기 stop! action2 twist - 카드 받기 reward는 규칙에 따라... -> 이게 뭐지 x=1부터 x=k까지의 평균

• prediction 인풋 : MDP와 Policy output : value function !

• control 인풋 : MDP output : optimal value function과 optimal policy

=> 결국, 핵심은 맨 위에 있는 하얀색 값을 얻기 위해서는 4개의 하얀색 값을 활용하면 된다! 이얘기! => 맨 위의 하얀색 = sigma (흰->검 이 될 확률 x (검은색에서의 보상 + sigma(검->흰이 될 확률 x 흰에서의 보상)) => 맨 위의 하얀색 =

여기서의 핵심은 이 검은색! 이 정확하다는 것! => 이 정확한 검은색을 통해서 계속 계속 들어갈 수 있다!

여기서의 policy는 random policy. 동서남북으로 갈 수 있음!

• k = 0 흰에서의 보상은 0
• k = 1 흰에서의 보상은 -1

1. 좌상단 & 우하단 제외 $v_{1}(s)$ = $ 1/4 \times (-1 + 0) + 1/4 \times (-1 + 0 ) + 1/4 \times (-1 + 0 ) + 1/4 \times (-1 + 0) = -1$

   맨 위의 하얀색 = sigma (흰->검 이 될 확률 x (검은색에서의 보상 + sigma(검->흰이 될 확률 x 흰에서의 보상)) => -1 = sigma ( 1/4 x (-1 + 0 ))

2. 좌상단 & 우하단 $v_{1}(s)$ = $ 1/4 \times (-1 + 0) + 1/4 \times (-1 + 0 ) + 1/4 \times (-1 + 0 ) + 1/4 \times (-1 + 0) = -1$

   policy는 계속해서 1/4인데 동일한데 그럼 계산이 어떻게 되는 거지?

• k = 2

1. -1.7

$v_{2}(s)$ = $ 1/4 \times (-1 + 1 \times -1) + 1/4 \times (-1 + 1 \times -1) + 1/4 \times (-1 + 1 \times -1 ) + 1/4 \times (-1 + 0) $

2. -2.0

$v_{2}(s)$ = $ 1/4 \times (-1 + 1 \times -1) + 1/4 \times (-1 + 1 \times -1) + 1/4 \times (-1 + 1 \times -1 ) + 1/4 \times (-1 + 1 \times -1) $

-> greedy하게 움지이기만 해도 best policy를 찾을 수 있다. -> 그니까, k=2를 예시로 들자면, v(s)= -1.7인 경우엔 0으로 가는 게 가장 greedy한 선택이고, -2.0인 경우에는 -1.7으로 가는 게 greedy한 거겠지?

무한하게 가지 않더라도. 어쨌뜬 optimal policy를 도달했다.

여기에서의 optimal policy란? 일단 policy의 정의 자체가 $Phi(a|s)$ = $P[A_t = a| S_t = s]$ 이기 때문에 , 무조건 내가 어떤 state에 있던 간에 나는 best policy를 안다! 이것보다는, 특정 state에 있을 때 내가 어떻게 선택해야지 가장 좋을지를 안다! 이런 느낌~

Policy Iteration

Policy Iteration은 evaluate(평가) : value function 을 찾고 improve (그 value function에 대해 greedy하게 움직이는 policy를 찾는)

계속해서 결국 star에 도달하기 위한 여정!

improve하면 이전 Policy보다 더 좋다!

일찍 끝내면 안되니?

Value Iteration

value iteration은

: 팡요랩에서도 이해를 못했다고 한다? : 그냥 policy가 과연 s에서 optimal state를 얻을 수 있을까? 그렇다면 어떤 조건이 무조건 필요한 걸까? -> s'이 s로부터 도달 가능할 때, -> policy를 통해 s'으로부터 optimal value를 얻을 수 있다.

https://arxiv.org/pdf/2501.17273

Abstract

• 연구 목적: LLM이 인간의 의견을 변화시키는 능력을 측정하고, 다양한 설득 전략(personalization, 조작된 통계 등)이 미치는 영향을 평가

• 연구 방법: 인간 참가자(n = 33)가 LLM이 생성한 주장과 토론을 진행하며, 의견 변화 여부를 측정합니다. 토론 전후의 의견 일치를 비교하여 설득력을 정량적으로 분석합니다. 설득 전략을 세 가지로 구분하여 효과를 비교합니다. 개인화된 설득(Personalized arguments): 참가자의 성격 및 인구통계 정보를 반영한 맞춤형 주장 조작된 통계(Fabricated statistics): 허구의 통계를 활용한 주장 혼합 전략(Mixed strategy): 개인화된 주장과 조작된 통계를 함께 사용하는 접근 방식

-> 연구의 방향성과 이게 가장 일치하는듯?!

1 Introduction

1. GPT-4o-mini의 설득력은 인간이 작성한 정적인(static) 주장과 비슷한 수준을 보임. 하지만 토론 중 실시간으로 대응하는 경우, LLM은 인간이 작성한 정적 주장보다 훨씬 높은 설득력을 가짐.

2. 혼합 전략(Mixed strategy)이 가장 강력한 설득력을 보임. 혼합 전략을 사용할 경우, 참가자가 자신의 입장을 바꿀 확률은 51%.

3. 반면, 인간이 작성한 정적 주장만을 읽었을 때 입장을 바꿀 확률은 32%에 불과함. 간단한 프롬프트 엔지니어링과 구조화된 답변(scaffolding) 방식이 LLM의 설득력을 강화함. 즉, 단순한 설득 전략보다 맞춤형 접근 방식을 사용할 때 효과가 크게 향상됨.

2 Background and Related Work

Information Operations(InfoOps)

InfoOps는 상대의 의사결정을 방해하거나 조작하기 위해 정보를 수집하고 활용하는 전략, 주로 국가 지원 행위자(state-sponsored actors)가 수행한다. 기존 : 봇(bot)을 활용하여 가짜 뉴스를 퍼뜨리거나 여론을 조작하는 방식이 일반적 현재 : LLM이 등장하면서 더 정교하고 개인 맞춤형 설득이 가능

최근 OpenAI 보고서에 따르면 LLM이 허위 정보 캠페인에 사용된 사례가 있으며, 이는 빙산의 일각일 가능성이 높다!!!! 그러니, 충분히 다룰만한 문제이다.

Accessibility and general capabilities

GPT-4는 인간보다 논리적이고 일관된 방식으로 토론을 진행할 수 있으며, 때로는 인간보다 더 설득력이 높다고 평가

Microtargeting

특히, 개인 맞춤형 메시지(마이크로타겟팅, microtargeting) 기법을 적용하면 설득력이 더욱 강화된다. 사용자의 소셜미디어 데이터를 분석하여 나이, 성별, 정치적 성향, 성격 특성을 추정할 수 있음. 연구 결과, LLM이 상대의 인구통계 정보를 알고 있을 때 설득력이 약 80% 증가한 사례가 있음. 그러나 일부 연구에서는 마이크로타겟팅이 LLM의 설득력에 큰 영향을 주지 않는다고 주장하며, 논란이 존재한다.

Threat Actors

threat actor들이 해를 끼칠 수 있는 그런 상황 !

In such a scenario, the threat actor would have full control of the prompts, and would leverage research findings to make the arguments as persuasive as possible to their counterpart.

근데 그렇게 threat actor들이 어떤 전략을 사용할 것이냐면,

1. 능력 강화 기법 적용 – 예를 들어, 멀티에이전트 구조(multi-agent scaffolding)를 활용하여 LLM의 성능을 향상시키는 것.
2. 가장 효과적인 설득 전략 활용 – 지식과 논리를 극대화하여 설득 효과를 극대화하는 것.
3. 사용자 관련 정보 제공 – LLM에 사용자의 인구통계 정보 및 성격 프로필을 입력하여 개인 맞춤형 설득을 수행하는 것.

3 Methodology

• personal data collection demographic의 내용 : age, gender, profession, education level, and country they’ve spent most time in. We theorized that knowing a participant’s profession and the country they’ve spent most time would have a greater impact on a user’s views.

여기서 그러면 어떤 trait를 썼나?? OCEAN (openness, conscientiousness, extraversion, agreeableness, neurotic) traits

• 토론 구조 3단계로 나누어 논의 길이를 조절하고 반박 및 반론을 포함하도록 설계.
• 의견 측정 리커트 척도를 사용해 참가자의 의견 변화를 평가. 사전 의견 서술을 요구해 보다 신중한 답변을 유도.
• 토론 방식 참가자는 자신의 기존 의견을 지지하는 입장에서 시작하도록 설정해, LLM이 실제로 의견을 변화시킬 수 있는지를 검증.
• 주제 선정 정치적 논쟁보다는 온라인 콘텐츠 규제, AI 사용 윤리 등 비교적 유연한 주제를 선택하여 참가자의 의견 변화 가능성을 높임.

Prescription drug importation should be allowed to in- crease access and lower costs. Genetic modification of unborn babies is unethical and dangerous. Space tourism should be limited until safety regulations are further developed. AI must be transparent and explainable in order to be widely accepted. Internet access should be considered a basic human right.

3.1

• model선택 GPT-4o-mini를 선택한 이유: 접근성이 높고 비용이 저렴하여 대규모 온라인 설득 캠페인에 적합. LLM의 역할: 사용자의 기존 의견을 바탕으로 200단어 이내로 설득력 있는 답변을 생성하도록 설정.

• 토론 유형 (Debate Types) Simple: 기본적인 설득형 프롬프트 사용. Stats: 통계 및 출처를 활용해 설득하도록 유도(허위 통계 생성 가능). Personalized: 사용자의 인구통계 및 성격 정보를 반영해 맞춤형 설득 전략 사용. Mixed: 다중 에이전트 시스템을 사용해 개인화된 접근 + 통계 기반 설득 결합.

• 비교 실험 (Static Arguments) LLM과 인간의 설득력을 비교하기 위해, GPT-4o-mini와 인간이 각각 찬반 입장의 글을 작성. 기존 데이터셋( [14] )이 불완전하여 Prolific에서 추가 수집 후 품질 필터링 진행. 최종적으로 GPT-4o-mini에도 동일한 주제에 대해 찬반 논거를 생성하게 함. 이 실험을 통해 LLM 기반 설득 방식의 효과와 최적의 전략을 비교 분석했다.

3.2 Experimental Design

• 실험 설계 및 참가자 모집 실험을 위한 웹사이트를 구축하고, Prolific 플랫폼에서 참가자 모집. 총 33명이 참여했으며, 평균 참여 시간은 1시간 45분. 참가자들은 기본 인구통계 정보(연령, 성별, 직업, 교육 수준, 거주 국가)와 TIPI 성격 테스트(10개 항목) 수행. AI 생성 콘텐츠 금지 등의 실험 지침 제공 후, 이해도 테스트(퀴즈) 진행.

• 실험 절차 참가자는 6가지 인터랙션 유형(simple, stats, personalized, mixed, arg-hum, arg-llm)을 무작위 순서로 경험. 각 인터랙션은 29개 주제 중 하나에 대한 토론 또는 논증을 포함.

• 실험 단계

1.주제 제시: 참가자는 주제 문장을 보고 초기 의견을 짧게 작성. 2. Likert 척도 평가: 1(강하게 반대)7(강하게 찬성)으로 의견 표시. 3. 토론(해당 시): 참가자는 자신의 의견을 지지하는 입장에서 소개(Introduction) 작성. LLM의 응답이 표시됨. 이후 반박(Rebuttal) 및 결론(Conclusion) 단계 진행. 최소 50단어 이상 작성 필수. 4. 논증(해당 시): LLM 또는 인간이 작성한 논증을 읽고 평가. 5. 최종 의견 제출: 참가자는 주제에 대한 최종 의견(12문장) 작성. Likert 척도로 다시 평가.

• 품질 관리 자동화된 검토 시스템을 사용해 응답 시간, 비활동 시간, 붙여넣기 이벤트 등을 점검. GPT-4o-mini를 활용해 응답이 영어로 작성되었는지, 논리적인지 확인. 자동 검토에서 문제가 발견된 경우, 연구진이 직접 검토. 의심되지 않은 응답도 일부 무작위 샘플링하여 수동 검토.

4 Results

연구에서는 인간 참여자를 모집하여 6가지 유형의 상호작용(단순형, 통계형, 개인화형, 혼합형, 인간 작성 논증, LLM 작성 논증)을 통해 설득력을 측정했다.

• 실험 방법

Prolific 플랫폼을 이용해 33명의 참여자를 모집하여 평균 1시간 45분 동안 실험을 진행함. 참여자들은 먼저 기본 인구통계 정보를 제공하고 TIPI 테스트로 성격을 자가 평가함. AI 생성 콘텐츠 금지 등의 실험 지침을 확인하고 이해도 검사를 수행함. 이후 6가지 유형의 상호작용을 무작위 순서로 경험함. 각 토론 또는 논증 후, Likert 척도로 의견 변화를 기록함.

• 설득력 평가 지표

Likert Δ: 참여자의 의견 변화 정도(LLM이 의도한 방향으로 변화한 크기). P(+change): 의도한 방향으로 의견이 변화할 확률.

• 결과 요약

혼합형(mixed)이 가장 높은 설득력을 보였음 (Likert Δ = 1.146, P(+change) = 51%). 개인화형(personalized)은 가장 낮은 설득력을 보였으며, 단순형(simple)보다도 효과가 떨어짐. 통계형(stats)은 단순형보다 약간 높은 성능을 보였으나 유의미한 차이는 없음. 인간 논증(arg-hum)이 LLM 논증(arg-llm)보다 Likert Δ가 높았지만, P(+change)는 LLM 논증이 더 높았음. 특정 참여자(15%)가 의견 변화를 거부하는 경향이 있었으며, 중립적 입장을 가진 참여자가 부정적 Likert Δ를 보일 확률이 높았음.

• 한계점

표본 크기가 작음(n=33, m=198) 자기 보고식(opinion self-report)이 노이즈를 포함할 가능성이 높음 통계적 유의성이 낮은 경우가 많음.

https://arxiv.org/pdf/2408.15879 일단 acl논문이다.

Abstract

일단 LLM이 다양한 분야에 쓰이고 있다. (credit card, Insurance 등등. 이때 insurance policy나 investment plan을 선택하도록 돕는다.)

We present a sophisticated multi-agent framework wherein a consortium of agents operate in collaborative manner.

1 Introduction

현재, 다양한 assistive agent들이 많이 쓰이고 있다. (보험, 여행 설계 등등)

하지만,

문제 : conducting a successful conversation that can motivate the user to take a preferred action requires more than human- like responses.

해결방법 :

1. 유저의 무드를 계속해서 분석할 수 있어야 함.
2. 유저의 저항을 분석할 수 있어야 함.
3. 아이디어에 대한 유저의 경향성을 파악할 수 있어야 함.

결국엔, 문제가 이것임. 그렇다면 어떻게 구현했을까?

1.1 Persuasion

• persuasion의 정의 : 특정한 agenda에 관해 그들의 belief를 induce하는 것!

• persuasion의 예시 : 소비자의 선택을 독려하거나, 정치적인 캠페인을 독려하거나.

• persuasion의 구성요소 1) user-directed : persuader <> target audience 간의 direct 상호작용! -> 논문에선 여기에 좀 더 초점! 2) vicarious message : 직접적인 고려 없이 indirect 상호작용!

1.2 Resistance to Perusasion

• resistance의 정의 : 그들의 행동,태도,믿음 등에 영향을 끼치는 행위들에 withstand하는 것!

• resistance의 technique

1. prior attitude 불러일으키기
2. selective exposure
3. biased processing
4. counter-arguing

: 근데 하지만 이러한 메커니즘은 아직 덜 발달됨.

2 Related Work

Carlos et al. [4]

Simon et.al [2] analyses the ability of LLMs to emulate persuasion dynamics and achieve opinion change in another LLM agent with a persona.

이전 연구의 특징 : moral language와 lexical complexity로 했었음.

2.1 Our Contributions

일단 persuasion을 위한 framework 만들기 => 계속해서 user의 감정 + 저항 방법 + 사회적인 노출에 대해 분석!

3 Setup

일단, chat application에서는 4개의 different agnet를 설정했다. Conversation agent, Advisor agent, Moderator and retrieval agent. 대화 시스템은 여러 에이전트로 구성된다.

Sales Agent: 최종 응답을 결정하는 핵심 에이전트 Advisor Agent & Retrieval Agent: Sales Agent에 정보를 제공 Analyzer Agent: 사용자의 감정 및 저항 전략을 분석 Strategist Agent: 전문가의 규칙이나 LLM을 활용해 설득 전략을 생성 Fact Checker: 최종 응답의 정확성을 검증

-> 결국 이렇게 다양한 에이전트가 협력해서!

3.1 Sales Agents

은행 에이전트: 신용카드를 추천하고 프리미엄 카드 가입을 유도 보험 에이전트: 사용자의 의문을 해소하고 적절한 보험 상품을 추천 투자 상담 에이전트: 전통 vs. 현대적 투자 방식의 차이점을 설명하고 투자 유도 사용자가 관심을 보이면 관련 URL을 제공하며, 구매 여부가 설득 성공 여부의 주요 지표로 측정된다.

3.2 User Agents

LLM을 활용해 25가지 서로 다른 인격(Persona)을 생성 인구통계, 재정, 교육 수준 등을 달리해 다양성을 확보 무작위 감정 및 동기를 부여해 저항 패턴을 변화 주제별 기억 시스템(Belief System)을 보유해 반복된 대화에서도 변화된 반응을 보임

3.3 Evaluation Metrics

3.3 평가 지표 (Evaluation Metrics) 설득 효과는 다음 세 가지 지표를 통해 측정된다.

• 설문 조사 (Surveys) 사용자 관점에서 제품, 혜택, 브랜드, 구매 관심도의 변화를 측정 대화 전후 정량적 질문이 포함된 설문을 진행하여 변화량을 분석

• 행동 지표 (Action-based Metric) 사용자가 선택한 구매 결정 옵션을 분석 선택지: 구매, 웹사이트 방문, 추가 정보 요청, 구매하지 않음 사용자가 구매 결정을 내리면 해당 도구를 호출하여 기록

• 언어 분석 (Language Analysis) 대화를 제3자의 관점에서 분석하여 설득력을 평가 LLM을 활용해 사전 정의된 평가 기준을 적용하여 측정

세 가지 지표의 가중 평균을 통해 최종 설득력 점수를 산출 행동 지표(Action)가 가장 높은 가중치를 가지며, 그다음 설문 조사(Survey), 마지막으로 언어 분석(Language Analysis)이 반영됨

4 Experiment

총 300개의 대화를 생성하였으며, 이는 25명의 사용자 에이전트와 3명의 판매 에이전트 간에 이루어졌다. 사용자 에이전트의 감정과 원인은 무작위로 설정되었으며, 비교 벤치마크로 75개의 중립 감정 대화(3×25)도 수행되었다.

• 각 세션의 구성 요소:

사전 설문조사: 사용자의 기존 신념을 측정 최대 20턴의 대화: 사용자와 판매 에이전트 간의 대화 사후 설문조사: 사용자의 신념 변화 측정 사용자 지식베이스 업데이트: 대화 후 사용자의 신념 시스템을 반영

• 모델 사용 및 대화 종료 조건 사용자 에이전트: GPT-4o (제한 초과 시 GPT-4로 대체) 판매 에이전트: GPT-4o-mini 및 GPT-3.5-turbo 기타 지원 에이전트: GPT-4o-mini 구매 결정은 사용자 에이전트가 함수 호출을 통해 수행

• 세션 종료 조건:

20턴을 초과하지 않는 대화 사용자가 구매 결정을 내린 경우

• 구매 결정 옵션: Buy: 성공적인 설득 Visit Site, Need More Details: 부분적 성공 (구매 의향 유발) No Buy: 설득 실패 (하지만 사후 설문에서 긍정적인 인식 변화 가능)

• 결과 분석 및 후속 조치 설문조사 반복: 세션 종료 후, 사용자에게 동일한 질문을 포함한 사후 설문 실시 지식베이스 업데이트: 사용자 신념 시스템 진화 반영 (후속 대화에 영향) LLM 분석: 전체 대화를 평가하여 판매 에이전트의 설득력 및 사용자 인식 변화 점수화 6턴 이하의 대화는 설득력 측정에서 제외되지만, 감정이 설득에 미치는 영향 연구에는 포함됨

현재 상황 : 많은 llm연구들이 진행되고 있다.

문제 : 여기서의 assumption은 LLM에 의해 처리된 정보들이 honest하고, deception이 없다는 것을 가정

 실제 예시 )

 **예시 1**. **deception** 구별 불가

 **예시 2**. 악의적인 가치들에 관련된 **위험 구분 불가** 

→ significant loss

해결책 : identify and counteract deceptive inputs를 하는 게 필요!!!

그렇다면, 여기서 쓰인 시나리오는?

→ realistic linguistic tasks with misinformation

인간은 그럼 이런 시나리오에 어떤 식으로 반응하는데?

→ recursive thinking, perspective-taking

따라서 우리는 ReCon을 제시한다!

2 Related Work

• Thought methods of LLMs
• Game Playing in Deceptive Environments

3 Background

3.1 Brief introduction

Avalon

= competitive한 setting에서, deception과 misinformation을 simulate할 수 있도록 만들어 놓은 보드게임!

= good vs evil

• Good Team

= 멀린 , 퍼시벌

(근데 심지어 논문에 이렇게 나와있다)

(This game is about a battle between good and evil, where the good team, featuring Merlin, Percival, and two Loyal Servants of Arthur, aims to complete quests.)

• evil side

= 모르가나, 암살자

( In contrast, the evil side, with Morgana and Assassin, seeks to fail these quests.)

• 구체적인 아발론 관련 설명

  

BigTom

= LLM의 ToM cabability를 알아보기 위해 만든 벤치마크!

( llm이 잘못된 정보 찾고, 그 잘못된 정보들을 가지고 navigate하는 시나리오 포함)

ex ) 잘못된 처음의 아래 믿음이 self-misinformation으로 연결

Noor believes a pitcher contains oat milk but it has already been replaced with almond milk by his coworker

3.2 Challenges in Deceptive Environments

그렇다면, 도대체 저 avalon game이란 환경에서, 어떤 게 문제인데? 어떤 게 문제여서 해결을 해야하는건데?

1. Misled by malicious content

   = ‘깜빡 속기!’

   Arthur’s loyal servant (a good player) <> Assassin(an evil player)

   1. Assassin

      제안 : replacing a good player with an evil one ( 한번 바꿔보자! )

      ( 속셈 : evil한 거를 위해서! )

   2. Arthur

      CoT를 통해서 답했을 때 : 그럼! evail player를 불러들이자~~ ( 속음 )

      ReCon을 통해서 답했을 때 : 근데, 되게 조심해야해! ( 안 속음 )

2. Exposing private information

   = 비밀 정보 누설 !

   1. 상황

      새로 뭔가 팀을 꾸려야 하는 상황

   2. Merlin

      CoT를 통해서 답했을 때 : 그럼! 나,Merlin,은~ ( 비밀 정보 누설 )

      ReCon을 통해서 답했을 때 : 그냥 뭐 걱정되니까 다시한번 바꿔보자 ( 비밀 정보 누설 X )

3. Hidden thought deception

   = 생각을 말 안함

   1. 상황

      player 4가 assassin인 거를 Morgana만 아는 상황!

   2. Morgana

      CoT를 통해서 답했을 때 : 뭐 미션 성공안했으니까~player 4를 제외하는 게 좋아 ( 생각 말 안함 )

      ReCon을 통해서 답했을 때 : 나는 evil을 좋아하니까~player 4를 제외하는 게 좋아 ( 생각 말 함 )

⇒ 결국 안 속고 + 비밀 정보 누설 안하고 + 생각 말 하는 애여야 해!

4 Recursive Contemplation

3.2에 있는 challengs를 해결하기 위해서,

과연 어떤 것들이 좋을까?

4.1 Formulation Contemplation

해결할 문제 : Exposing private information & Hidden thought deception

해결책 : 1) 안에서 contemplate 한 다음 → 2) 밖으로 the spoken content 내뱉기!

⇒ [First-order Perspective Transition]

• First-order의 의미는?

= ‘infer what others might be thinking from its own perspective’

= 내 관점에서 다른 사람들이 어떻게 생각할지!

• 구체적인 실현 방법

= deduce the roles of fellow players!

1 ) 다른 사람들의 역할 추측하기 2 ) 다른 사람의 상태와 할 말 추측하기 3 ) contemplation 하기

• 수학적으로 풀어내보기

1 ) 안에서 contemplate 한 다음

플레이어 숫자 :

일때,

K번째 player는 first thinks about the current game situation and the roles of fellow players, following the principle of first-order perspective transition:

Tk = k의생각!

H = 기존의 대화 로그

Rk = player k의 role

Gk = role assumption ( 다른 사람들에 대한 )

G’k = 업데이트된 role assumption

IRk = role-specific한 비밀 정보

P뭐시기뭐시기 = 다 프롬프트 ! ! ! ! !

2) 밖으로 the spoken content 내뱉기!

Sk = k의 내뱉는 말!

4.2 Refinement Contemplation

근데 4.1에서 했음에도 불구하고, 실수가 있었다고 한다.

해결할 문제 : Exposing private information…

해결책 : 1) 안에서 contemplate 한 다음 → 2) 안에서 contemplate 한 다음 → 3) 밖으로 the spoken content 내뱉기!

⇒ [Second-Order Perspective Transition]

• Second-Order의 의미는?

= ‘putting oneself in someone else’s shoes’

= 다른 사람의 관점에서 다른 사람들이 어떻게 생각할지!

• 구체적으로 보자면,

  “If I verbalize my initial version Sk of spoken content, how would the other roles, from both good and evil sides, respectively perceive my speech?”

• 구체적인 실현 방법

  

  Ok = 다른 역할의 심리 상태에 대한 분석

  

  최종적으로 대화 로그에 포함된다!

5 Experimental Evaluations

5.1 Experimental Results on Avalon

5.1.1 End-to-End Evaluations

일단, 한번 마피아를 잘 뽑았나! 한번 볼게! 원래는 이제 하도 애들이 잘 속이니까(거짓말을 잘 하니까), 사실 마피아를 잡는! 그런 확률이 현저~하게 떨어지지만, 이 기법을 적용해서 투명하게 게임을 해보면 어떨까?

🔹 실험 개요

• 아발론 게임 여러번 하게 함.
• ReCon을 Chain-of-Thought(CoT)에 적용하여 평가함.
  • 좋은 편(선한 편) 테스트: CoT를 나쁜 편(악한 편)으로 설정해 비교.
  • 나쁜 편(악한 편) 테스트: ReCon을 좋은 편(선한 편)으로 설정해 비교.
• 비교 대상:
  • 기본 프롬프팅(vanilla prompting)
  • Chain-of-Thought (CoT)
  • Tree-of-Thoughts (ToT)
• 모델: ChatGPT, Claude, LLaMA-2 (LLaMA-2는 응답 형식이 맞지 않아 실패).

🔹 실험 결과 요약

1. ReCon이 기존 방법(CoT, ToT)보다 성능이 좋음.
2. ReCon의 다양한 설계 요소(예: formulation conotemplation, refinement)가 효과적.
   • 선한 편에서는 관점 전환(first/second-order perspective transitions)이 성능 향상에 크게 기여.
   • 악한 편에서는 정교화 기법(refinement contemplation)이 더 중요한 역할을 함.
3. ReCon의 모든 기법을 조합했을 때 성능이 가장 높음.

5.1.2 Multi-Dimensional Evaluation

🔹 ReCon 성능 비교 실험

ReCon과 그 변형(ablated variants), 그리고 기본 모델인 CoT를 비교하여 ReCon의 설계 효과를 평가

📌 비교 기준 (6가지 평가 지표)

1. Concealment (CCL) – 비밀 유지 능력 (불필요한 정보 노출 방지)
2. Logic (LG) – 논리적인 게임 분석 능력
3. Contribution (CTR) – 팀 성공에 기여하는 발언 여부
4. Persuasiveness (PRS) – 다른 플레이어를 설득하는 능력
5. Information (INF) – 유용한 정보를 제공하는 정도
6. Creativity (CRT) – 독창적인 전략과 관점

📌 실험 방법

• ChatGPT로 20번의 Avalon 게임을 진행하여 데이터 수집
• 각 프롬프트에 대해 4가지 방식의 응답 생성
  1. ReCon
  2. ReCon (2단계인 refinement 없음)
  3. ReCon (1단계인 formulation 없음)
  4. 기본 CoT
• 총 2300개 이상의 응답 생성
• GPT-4를 이용하여 각 응답을 6가지 기준으로 비교

🔹 실험 결과

1. Figure 4(a): ReCon이 모든 기준에서 CoT보다 성능이 뛰어남
2. Figure 4(b), (c): 2단계 refinement contemplation와 1단계 formulation contemplation 기법이 성능 향상에 큰 도움을 줌
3. 예외:
   • PRS(설득력) 점수는 기대보다 낮음
   • 이유: 1단계 formulation contemplation 으로 인해 더 간결한 표현을 사용했기 때문
   • 예를 들어, 감정적인 표현(“우리는 반드시 승리할 것이다! 단결하자!”)이 줄어듦

🔹 First-Order & Second-Order Perspective Transitions 분석

👉 핵심 내용:

ReCon에서 1차 및 2차 관점 전환을 제거하면 모든 평가 지표에서 성능이 감소함.

📌 세부 분석

1. Figure 4(d), (e):
   • 1차 및 2차 관점 전환을 제거하면 모든 평가 지표에서 성능 저하 발생
2. Figure 4(f), (g):
   • refinement 또는 formulation 고려 없이 1차·2차 관점 전환을 제거하면 대부분의 지표가 하락
   • 예외적으로 CCL(비밀 유지 능력)은 향상됨
   • 하지만 이는 관점 전환과 정교화/공식화 기법을 함께 사용해야 비밀 유지가 더 효과적임을 시사

5.1.3 Reliability of Automatic Evaluation

그러면, GPT-4를 평가할 때 썼으니까 안좋은 거 아니야?!!! 잘못평가했으면 어떡해~!

🔹 연구 방법

• GPT-4의 자동 평가 결과(Figure 4)를 인간 주석(annotations)과 비교하여 신뢰성을 평가
• 무작위 샘플 216개 대화 선정, 인간 평가자들이 합의 수준에 따라 분류
  • “완전 합의” (Full Agreement)
  • “대부분 합의” (Majority Agreement)
  • “대부분 불일치” (Majority Disagreement)
  • “완전 불일치” (Full Disagreement)
• 주석 팀: Avalon 게임에 익숙한 12명의 평가자 (남성 8명, 여성 4명)

🔹 결과 (Figure 5)

• 합의 비율: 73.15%
• 불일치 비율: 26.85%
• 통계적 검증 (§H.3 참고)에서도 신뢰도 높음

🔎 결론: GPT-4의 자동 평가는 신뢰할 만한 결과를 제공함.

5.2 Experimental Results on BigTom

목표: ReCon이 Avalon 게임 외 다른 인지적 과제에도 확장 가능한지 검증

왜냐면, avalon 게임에만 적용되면 소용이 없잖니~

🔹 BigTom이란?

• BigTom (Gandhi et al., 2023): LLM의 심리 이론(ToM, Theory of Mind) 능력을 평가하는 사회적 추론 벤치마크

• 특징: false belief 관련 사례 포함 → 오정보(misinformation) 탐지와 연관

  

🔹 5.2.1 기본 모델과 비교 (Comparison with Baselines)

• 비교 대상:

  • 일반 LLMs (Vanilla LLMs)
  • CoT (Chain-of-Thought)
  • ToT (Tree-of-Thought)
  • ReCon

• 실험 방법:

  • Vanilla LLM & CoT → Gandhi et al. (2023) 방식 사용
  • ToT → Yao et al. (2023) 방식 적용 (2-depth tree, 각 플랜 5회 평가)

• 결과 (Table 1):

  

  • ReCon이 거의 모든 테스트에서 최고 성능
  • 특히 초기 신념(Initial Beliefs) 관련 문제에서 우수, 거짓 정보 대응력 향상

✅ 결론: ReCon은 거짓 신념(misinformation) 탐지 및 대응에서 효과적!

📌 5.2.2 ReCon의 확장 가능성 (Scaling Trend of ReCon)

• Figure 6 분석:
  • LLaMA-Chat의 매개변수 수(parameter count) 증가 → ReCon 성능도 꾸준히 향상
  • 같은 모델 크기에서 ReCon > CoT, ToT
  • 🚀 결론: ReCon은 더 큰 모델에서도 확장 가능, 차세대 LLM과도 호환 가능

6. Conclusion

• Limitations

📌 ReCon의 일반화 가능성과 한계

1. ReCon이 모든 LLM에서 효과적인가?

• 불확실성: ReCon이 모든 종류의 LLM 성능을 향상시킬지는 확실하지 않음.
• 광범위한 테스트: 연구에서는 GPT-3.5, GPT-4, Claude-2, LLaMA-7b-chat, LLaMA-13b-chat 등 다양한 LLM을 평가.
• 핵심 관찰: 다양한 LLM에서 ReCon이 성능 향상을 보여줌 → 현재 LLM에 대해 일관된 효과를 가질 가능성.
• 미래 전망:
  • ReCon의 인지 전략(재귀적 사고, 관점 전환)은 인간 지능과 유사.
  • LLM이 인간 수준의 지능에 도달하더라도, ReCon의 접근법은 여전히 유효할 가능성이 높음.
  • 잠재적 약점: 만약 미래의 LLM이 생성 능력이 부족해진다면, ReCon의 효과가 감소할 수도 있음.

✅ 결론: ReCon의 전략은 LLM이 발전하더라도 지속적으로 유용할 가능성이 높음, 다만 생성 능력이 약화될 경우 효과가 감소할 수도 있음.

2. ReCon이 모든 속임수 환경에서 효과적인가?

• 불확실성: ReCon이 모든 종류의 기만(속임수) 및 허위 정보 환경에서 효과적일까?
• 두 가지 대표적인 테스트 환경:
  1. Avalon 게임 – 복잡한 속임수 및 이론적 사고(ToM) 필요, 그러나 정답(ground-truth)이 없음.
  2. BigTom 벤치마크 – 단순한 허위 정보 및 ToM, 하지만 정답이 존재하고 다양한 추론 과제가 포함됨.
• 실험 결과:
  • ReCon은 두 환경에서 모두 우수한 성능을 보임.
  • 다양한 기만 및 허위 정보 환경에 대해 일반화 가능성이 있음.

✅ 결론: ReCon은 허위 정보 탐지에 유망하지만, 실제 환경에서 추가적인 테스트가 필요함.

3. ReCon이 사전 학습 없이도 효과적인가?

• 우려 사항: ReCon의 성능이 LLM의 본래 능력에 의존한다면, 추가적인 미세 조정(fine-tuning)이 필요할까?
• 잠재적 이점: 추가적인 데이터로 미세 조정을 하면 ReCon의 성능이 더욱 향상될 가능성.
• 인지적 접근법의 강점:
  • LLM이 본래 가지고 있는 능력을 항상 최적으로 활용하지는 않음 → 인지적 방법이 이를 극대화하는 역할.
  • CoT(Chain-of-Thought) 및 ToT(Tree-of-Thought)와 유사하게, LLM의 추론 능력을 최대한 활용하도록 유도.
  • 장점: 추가적인 훈련 데이터 없이도 작동 가능 → 보다 광범위한 응용 가능성 제공.

✅ 결론: 추가적인 학습이 ReCon의 성능을 높일 수 있지만, 추가 데이터 없이도 LLM의 내재적 능력을 효과적으로 활용하는 것이 ReCon의 핵심 강점.

📌 최종 정리

✅ ReCon은 다양한 LLM에서 성능을 향상시키며, AI가 발전하더라도 유효할 가능성이 높음.

✅ 실제 환경에서 추가적인 검증이 필요함.

✅ fine-tuning이 도움이 될 수 있지만, ReCon은 추가 학습 없이도 LLM의 잠재력을 극대화할 수 있음.

*Markov Process -> MarKov Reward Process -> Markov Decision Process * 이렇게 확장이 된다.

일단 MarKoV 특성 예전의 것들은 현재랑 관계가 없다. state만 필요할 뿐, 이전 history는 필요가 없다.

• State Transition Matrix

s에서 s'으로 갈 확률을 Pss'라고 하는데,

그것들을 이제 저렇게 matrix로 모아 놓은 게 P라고 생각하면 됨. n x n

1. markov process

: 상태들이 n개가 있고 discrete하게 state를 옮겨다니는! _state는 stochastially 움직이는 ! _ S = state들의 집합 P = 전이 확률 matrix

random process : 샘플링을 할 수 있다.

여기서 state는 7개! state의 전이 확률이 화살표...! 오오 여기서, sampling을 해볼 수가 있음.

episode란? 처음부터 시작해서 final까지 가는 것!

시작이 C1이라 하면, 그 뒤에 C2,C3

2. markov reward process

= markov chain + rewards 하지만 action은 없다.

아까는 S,P였는데 R,r이 필요 R은 reward function r은 discount factor

R에 있는 수는? 그냥 뭐 예시다.

이거는 action이 없기 때문에 확률적으로 그냥 그 확률을 따라가서 reward를 주는 거다. 그래서 action이 결부될 일이 없음.

강화학습은 이 return을 maximize하는 것이 핵심이다. 경로동안 받는 보상들의 총합!!! 감마가 1 : 멀리 보는 거 = 미래의 보상도 현재 보상만큼 중요시 ! 감마가 0 : 단기

Horizon = 얼마나 많은 state만큼 진행이 되는건지!

discount 왜 해?

1. 수학적으로 편리해서

state value function은, reward의 총 기댓값

• reward signal 정답이 알려주는 사람 없이, 에이전트가 리워드 신호만 받으면서 좋은 방법론을 찾아가는 것 ! ! ! ! supervisor가 없이 ! ! ! == 자기주도학습 잘 하는 학생 reward : 니가 알아서 해!

• feedback is delayed supervised learning에서는 지연 학습 이런 게 없지만...

• time really matters supervised learning 에서는 independent & identically distributed. 하지만, 강화학습은 sequential ... 오.

• agent's action affect the subsequent data it receives 아 순간적으로 학습하는 건가?

reward는 숫자 scalar 하나 !! ! 하지만, 여기서는 cumulative reward...라는 것! (현재말고 전체를 봐서)

그러면, 굳이 스칼라로 치환해서 안되는 그런 문제들은??...(ex.벡터) => 뭔가 조작을 해야하겠군.

(예시)

하 한번 결정 잘 하면 안되고, 지속적으로 결정을 잘해야함. greedy하게 하면 안되고 long-term을 언제나 생각해야함.

llm agent, 주식 포트폴리오 알고리즘이 저 뇌

state : history에 함수를 씌운 것 = f : 과거 자체를 다 볼 수는 함수 = f : 과거 중 하나만 보는 함수 = 즉, history의 어떤 부분에 가중치를 둘 지 생각할 수 있는 것임.

얘는 그럼 실시간으로 학습하는 거네? llm한테 프롬프트를 그냥 주입하는 것은 inference였고, 전혀 llm의 internal state에 영향이 없었는데 얘는 inference + learing을 동시에 하다보니 internal state를 바꿀 수 있음.

llm chat history vs RL에서의 history 1 시점에서의 Agent A의 message+ 1 시점에서의 Agent B의 message + 2 시점에서의 Agent A의 message = chat history : 단순히 inference 때의 prompt의 일부로 들어감 O,R,A = H = RL history : learning에 사용

• environment state

environment의 state는 뭔데? == obv + reward + action 을 관찰한 후 , 다음 obv값은? == f (Ht) == f (obv + reward + action ) [근데 여기 f가 history를 가지고 environment의 state를 알아내는 함수인거지] -> 다음 enviornment를 예측하기 위해 필요한 feature들 + 그 feature의 값들! -> 내부에서 돌아가고 있는 것들@!!! !! ! !

• agent state

agnet의 state는 뭔데? == obv + reward + action 을 관찰한 후 , 다음 obv값은? == f (Ht) == f (obv + reward + action ) [근데 여기 f가 history를 가지고 agent에게 필요한 정보들을 알아내는 함수인거지] ex) 삼성전자에서 주식할 때 필요한 것들(ex. 블룸버그 뉴스, 어제 매도량, 어제 매수량 등등) -> 학습할 때 중요하게 생각하는 feature를 추출 + 그 feature의 값들!

여기서 information state가 등장. 저거라면 markov인거

우리는 이제 쥐... agent의 state를 어떻게 정하느냐에 따라서 달라지는 것.

MDP

agent state != environment state

agent state : public한 정보들로만 구성됨 environment state : public + private들로 구성 ( 모든 애들 다 ! )

RL agent의 구성 요소

state를 넣으면 action을 뽑아내는! 오 신기

• deterministic policy : 하나의 액션만 !
• stochastic policy : 각 action별 확률을 뱉음

state를 넣으면 value을 뽑아내는! 어떤 Poclicy 파이를 따라갔을 때 예상되는 기댓값인 것임.

감마 : 2000년대의 돈 != 2010년대의 돈 state를 넣으면 환경에 대한 예측값을 뽑아내는 !

1. reward 예측
2. 그다음 state 예측 (모델이 이걸 예측을 한 것이다)
   예시  policy : 선택 화살표  처음에는 아예 검은색 맵인 것임.

Categorizing RL agents

LEARNING AND PLANNING

강화학습은 두개를 합친 것 learning : env를 모르는 것. 환경에 그냥 던져진 것. 걔의 policy를 개선시켜가는 게 learning planning : env를 앎. reward가 어떻게 되는지 알고 transistion이 어떻게 되는지 앎 . (이게 몬테카를로...)

prediction은 value function을 잘 만드는 것 control은 best policy를 찾는 것!

아우 재밌다!

LLM은 엄청난 발전을 했다.

하지만 customize하는 방법이 좋음(하나만 다 할 수는 없으니...) -> persona setting! ( LLM-driven human behavior simulation can facilitate insightful exchanges (e.g. “You are a pro-choice devout Christian. Why do you support abortion?”)

하지만, persona-assinged LLM은 unintended한 side-effect를 찾기가 어렵다.

이걸 위해서 19 diverse personas 를 만들어서, 24 reasoning datasets spanning multiple subject domains에 테스트 해봤다.

충격적이게도, For ChatGPT-3.53, 80% of our personas demonstrated bias, i.e., had a drop in performance on at least one dataset. Additionally, the magnitude of this bias is also significant—we observed a rel- ative drop of 70% in accuracy on certain datasets and an average drop of 35% across datasets for some personas.

인종별로, 종교별로 차이도 있었다. we observe the model bias resulting in disparate performance, e.g. Jewish persona performs better on STEM datasets, Atheist persona performs better than Christians on Sciences, and Obama Supporter persona outperforms Trump Sup- porter on ethics

2. Methodology & Setup

• assigning a persona

일단 chatgpt같은 llm은 2가지의 프롬프트가 있다. (1) system prompt (2) user prompt

시스템프롬프트에서, persona instruction을 따르라고 언급하고, user prompt에서 user에 관한 정보를 넣었다.

• personas & datasets in the study

24개의 dataset을 썼다...! ! ! ! (math reasoning, programming, physics, maths, medicine ...)

• model & evaluation chatgpt3.5를 대상으로.

3 Findings

3.1 Persona elicits bias in reasoning

24개의 데이터셋에 대해 accuracy를 측정한건데, 각각의 persona마다 이렇게 다르게 나왔다.

3.2 Extent of the Bias

이건 이제 significant한 drop이 있는 경우를 체크한 것이다. (ex.phys.disabled의 경우 baseline인 human persona보다 현저하게 drop이 있는 경우가 23개고, asian인 경우 baseline인 human persona보다 현저하게 drop이 있는 경우가 21개다)

4 Analysis

1. 고정관념에 의한 응답 거부 모델은 특정 페르소나(예: "신체 장애인", "종교인", "트럼프 지지자")에 대해 그들이 어떤 작업을 할 수 없다고 잘못 생각하고, 질문에 답하지 않거나 거부하는 경우가 많음.

예를 들어, 신체 장애인을 묘사하는 모델이 "수학 계산을 할 수 없다"고 답할 수 있습니다. 이런 방식의 거부는 고정관념에 근거한 잘못된 추정에서...

fig 8은 각 페르소나에 대한 오류 비율을 보여줍니다. 특히 신체 장애인이나 종교적인 페르소나는 응답 거부(abstentions)로 인한 오류 비율이 크다는 것을 나타냅니다. 예를 들어, 신체 장애인 페르소나에서는 58%가 "응답 거부"로 인한 오류

2. 고정관념에 의한 추론 오류: 응답 거부를 넘어, 모델이 특정 페르소나에 대해 잘못된 추론을 할 수 있음.

단순히 응답을 거부하는 것이 아니라, 특정 페르소나 때문에 응답이 이상하게 나올 수도 있단 의미. 예를 들어, 신체 장애인이나 종교인 페르소나가 같은 질문에 대해 다르게 응답할 수 있는데, 이 차이는 모델의 고정관념에 의한 것 예를 들어, "오바마 지지자"와 "트럼프 지지자" 페르소나가 같은 수학 문제를 풀 때 정확도가 39% 차이가 나는 경우가 있었음. = 모델은 단순히 "응답 거부"하는 것만이 아니라, 잘못된 고정관념을 바탕으로 응답을 왜곡하거나 불균형적인 정확도 차이를 보입니다. 이 미묘한 편향은 "응답 거부"보다 발견하기 어렵기 때문에 더 문제 ! ! ! ! !