Shannon Game

In this note I want to start to explore one of my notions of compositionality of Lewis games with another game. In my thinking currently consider at least three senses for compositionality

1. Learning a MARL skill in a way that agents can repurpose it across new tasks and setting.

2. Learning a domain specific signaling system that serves the needs of a game framing a lewis signaling game. Serves here means:

   • marl \arg max(Returns \mid \text{given expected actions of other agents})
   • population dynamics \arg max(Progeny \mid \text{given expected actions of other agents})

3. Learning a structured complex signaling of systems with features more like NLP and less like a bijection.

   1. Learn semantics by break down the state into some structure and express the full state using some aggregation of the parts.
      • e.g. do it using a structured signal, e.g. a template with slots for signals
        • NOT X; AND X,Y; OR X,Y
        • X-big, X-big-er, X-big-est, X-small, X-small-er, X-small-est
        • X-1, X-2, X-3, X-4, X-5, X-6, X-7, X-8, X-9, X-10 for inflections of action-X
        • X-1, X-2, X-3, X-4, X-5, X-6, X-7, X-8, X-9, X-10 for inflections of noun-Y
   2. Capability to generalize learned semantics to new states
      • map a state to a prefix category and a suffix disambiguation
      • the prefix can be a signal in partial equilibrium solution of the lewis signaling game.
      • the might be reuse of an existing signal or a new signal.
   3. ability to use categories
   4. ability to learn

4. using a hieracial model also seems to be an option.

The stating point:

One can represent a communication protocol as a decision tree.

So in the abstraction one way that a emergent communications might arise is using three modules:

1. Lewis signaling games to model different coordination tasks like

   1. the alphabet and or basic signals
   2. a lexicon built on the alphabet
   3. a grammar to support composition of lexemes into sentences that can express complex states.
   4. coordinating of decision rules
      • the sender get a decision trees that map states to a string in the alphabet this is called an encoder.
      • receiver get a decision tree that maps the string to a state space, this is called a decoder The encoder-decoder might just serialize the state or it might do arbitrary complex transformations that include a compression, error detection and correction and even analysis of the agents environment required to pick the best action. However at this point we want a minimal that is restricted to serialization and deserialization, compression using a prefix code and perhaps error detection and correction.
   5. coordinating grammar rules. We may also need a grammar to support parsing of complex signals. In a simple case we might be processing mathematical expression and need to ensure that the formulas are well formed. In more complex scenarios we may need enforce selectional restrictions and subcategorization frames. In the MVP I imagine a simple rule that allows nested clauses.
   6. one idea for using lewis games to coordinate the decision rules if it can enumerate all possible trees and let agents pick one. Other more complex scenarios are possible too.

2. a Shannon game to model the communication of information between agents in which they learn a shared communication protocol with using error detection and correction capabilities.

3. a Chomsky game to model development of a shared grammar for complex signals.

   • A trivial version is to use concatenation of signals to form new signals.
   • A more powerful version is to use an ordered vector of signals. Using a simple prefix code this allows creation of a powerful morphology.
     
   • Probably the minimalist option though is to use a rule that allows nested clauses. If the tree allows recursion we get what Humboldt called the infinite use of finite means.
   • Just having a recursive rule though might over-generate and we might require additional means to restrict the grammar by way of selectional restrictions¹ and subcategorization frames ².

¹ restrict sematic roles

² might restrict phrase elements to morphological categories in the lexicon with suitable features.

Shannon Game

Sharon games are about emergence of randomized communication protocols.

A randomized communication protocol is a probability distribution over the set of possible deterministic communication protocols.

We can model any deterministic communication protocol as a pair of decision rees, one for the sender and one for the receiver. The sender’s decision tree maps each possible message to a signal, and the receiver’s decision tree maps each possible signal to a message.

Messages that the sender can send.

The sender samples a message from this distribution and sends it to the receiver. The receiver then uses a decoding function to map the received message back to the original signal. The goal of the game is for the sender and receiver to coordinate on a communication protocol that maximizes their payoff, which is typically based on the accuracy of message transmission and reception.

It is a protocol that uses randomness to encode and decode messages.

This randomness can be used to introduce redundancy in the message, which can help in error detection and correction.

import numpy as np

class CommunicationAgent:
    def __init__(self, num_strategies):
        self.num_strategies = num_strategies
        self.q_table = np.zeros((num_strategies, num_strategies))
        self.learning_rate = 0.1
        self.discount_factor = 0.9
        self.epsilon = 0.1
    
    def choose_strategy(self):
        if np.random.rand() < self.epsilon:
            return np.random.randint(self.num_strategies)
        else:
            return np.argmax(self.q_table.sum(axis=1))
    
    def update_q_values(self, sender_strategy, receiver_strategy, reward):
        max_future_q = np.max(self.q_table[receiver_strategy])
        current_q = self.q_table[sender_strategy, receiver_strategy]
        new_q = current_q + self.learning_rate * (reward + self.discount_factor * max_future_q - current_q)
        self.q_table[sender_strategy, receiver_strategy] = new_q

# Simulation parameters
num_strategies = 8
num_iterations = 10000

# Initialize agents
alice = CommunicationAgent(num_strategies)
bob = CommunicationAgent(num_strategies)

for _ in range(num_iterations):
    sender_strategy = alice.choose_strategy()
    receiver_strategy = bob.choose_strategy()
    
    # Simulate message transmission and reception with noise
    # This is a placeholder for actual encoding/decoding logic
    success = np.random.rand() < 0.8  # Assume 80% chance of success
    
    reward = 1 if success else -1
    alice.update_q_values(sender_strategy, receiver_strategy, reward)
    bob.update_q_values(receiver_strategy, sender_strategy, reward)

print("Alice's Q-Table:\n", alice.q_table)
print("Bob's Q-Table:\n", bob.q_table)

Alice's Q-Table:
 [[6.57110843 6.74229554 6.75218428 6.58476516 6.6848205  6.7093983
  6.65008078 6.85391505]
 [6.8660244  0.         1.40420282 0.74270819 0.69404036 0.69767502
  1.19950973 0.        ]
 [7.02875006 0.         0.66128705 0.45256661 0.5241919  0.43066909
  1.07486849 2.28458366]
 [7.18824707 0.69284123 1.12411616 0.81127392 0.59840725 0.
  1.55334449 1.05933599]
 [7.07328025 0.35036568 1.5662752  1.26638392 0.70470059 1.60990736
  0.68431892 0.73594177]
 [6.31933938 1.35639438 0.68592077 1.25143991 0.         1.66828428
  0.         1.57758044]
 [7.05048089 0.72162504 0.         1.29972342 0.42303469 1.47976873
  1.81638255 2.33582802]
 [7.05669624 0.         0.         0.71246496 0.         0.92205622
  0.         0.91764269]]
Bob's Q-Table:
 [[6.71421358 6.690117   6.87592953 6.97507006 6.92728373 6.27757436
  6.5388233  7.03710432]
 [7.07439452 0.         0.         0.70657058 0.40879261 1.35840522
  0.69534906 0.        ]
 [6.98936669 1.43411508 0.64487398 1.12651883 1.61549536 0.6951973
  0.         0.        ]
 [6.75377482 0.72120663 0.40917227 0.75347396 1.27587634 1.16513229
  1.26582918 0.73771071]
 [6.73222825 0.69242388 0.46264077 0.52866576 0.72249045 0.
  0.46555849 0.        ]
 [7.09826895 0.69833847 0.40843843 0.         1.54200331 1.6311776
  1.60490629 0.88698387]
 [6.85769686 1.17148428 1.05206849 1.44657543 0.70956796 0.
  1.8999549  0.        ]
 [7.04865988 0.         2.25780613 0.97199582 0.73102373 1.44430025
  2.2120178  0.77298064]]

This example illustrates a basic game-theoretic approach where the sender and receiver iteratively learn better strategies for encoding and decoding messages over a noisy channel. The reinforcement learning framework allows both parties to adapt and improve their protocols, enhancing the reliability of communication over time. This model can be extended and refined to include more sophisticated encoding/decoding techniques and more complex noise models.

from mesa import Agent, Model
from mesa.time import RandomActivation
from mesa.datacollection import DataCollector
import numpy as np

def hamming_distance(a, b):
    return np.sum(a != b) / len(a)

class Sender(Agent):
    def __init__(self, unique_id, model):
        super().__init__(unique_id, model)
        self.protocol = self.random_protocol()
    
    def random_protocol(self):
        # Define a random protocol for encoding (Identity function for now)
        return lambda msg: msg  
    
    def step(self):
        self.model.original_message = np.random.randint(0, 2, self.model.message_length)  # Generate a binary message
        encoded_message = self.protocol(self.model.original_message)
        self.model.sent_message = encoded_message

class Receiver(Agent):
    def __init__(self, unique_id, model):
        super().__init__(unique_id, model)
        self.protocol = self.random_protocol()
    
    def random_protocol(self):
        # Define a random protocol for decoding (Identity function for now)
        return lambda msg: msg  
    
    def step(self):
        if self.model.sent_message is None:
            return  # **Avoid processing before sender has sent a message**
        
        # Convert to NumPy array to ensure bitwise operations work
        noisy_message = np.array(self.model.sent_message) ^ np.random.binomial(1, self.model.error_rate, self.model.message_length)
        recovered_message = self.protocol(noisy_message)
        self.model.recovered_message = recovered_message
        self.evaluate_performance()
    
    def evaluate_performance(self):
        original_message = self.model.original_message
        recovered_message = self.model.recovered_message
        distance = hamming_distance(original_message, recovered_message)
        self.model.payoff += self.model.recovery_payoff(distance)
        self.model.payoff += self.model.length_payoff(len(recovered_message))
        self.model.payoff += self.model.early_recovery_payoff(self.model.current_step)

class NoisyChannelModel(Model):
    def __init__(self, message_length=10, error_rate=0.1, max_steps=100):
        self.message_length = message_length
        self.error_rate = error_rate
        self.current_step = 0
        self.max_steps = max_steps
        self.payoff = 0
        self.running = True  # Fix: Initialize running status
        
        self.schedule = RandomActivation(self)
        
        self.original_message = np.random.randint(0, 2, self.message_length)  # Initialize first message
        self.sent_message = None
        self.recovered_message = None
        
        sender = Sender(1, self)
        receiver = Receiver(2, self)
        self.schedule.add(sender)
        self.schedule.add(receiver)
        
        self.datacollector = DataCollector(
            model_reporters={"Payoff": "payoff"}
        )
    
    def recovery_payoff(self, distance):
        return 1 - distance
    
    def length_payoff(self, length):
        return 1 / length if length > 0 else 0  # Avoid division by zero
    
    def early_recovery_payoff(self, step):
        return (self.max_steps - step) / self.max_steps
    
    def step(self):
        self.current_step += 1
        self.schedule.step()
        self.datacollector.collect(self)
        if self.current_step >= self.max_steps:
            self.running = False  # Stop the simulation

# Run the model
model = NoisyChannelModel()
while model.running:
    model.step()

# Retrieve results
results = model.datacollector.get_model_vars_dataframe()
print(results)

    Payoff
0     1.99
1     3.77
2     5.64
3     7.60
4     9.55
..     ...
95  145.84
96  146.97
97  147.99
98  149.10
99  150.00

[100 rows x 1 columns]

/home/oren/work/blog/.venv/lib/python3.10/site-packages/mesa/agent.py:52: FutureWarning:

The Mesa Model class was not initialized. In the future, you need to explicitly initialize the Model by calling super().__init__() on initialization.

so this is a variant that uses a noisy channel model to simulate the transmission of messages between a sender and receiver. The agents have protocols for encoding and decoding messages, and the model tracks the performance of the communication system based on the accuracy of message recovery, message length, and early recovery. This example demonstrates how to model and analyze the performance of communication systems in the presence of noise and other challenges.

What we don’t have is a way to pick different protocols or to improve them over time.

I would break this down into a few steps: 1. identify the environmental factors that would encourage the agents to evolve diverse and efficient transmission protocols. a. noisy channels b. limited bandwidth c. limited computational resources d. time constraints e. risks of predation.

2. allow agents randomly generate candidate protocols and evaluate their performance.

def random_protocol():
    # Define a random protocol for encoding/decoding
    return lambda msg: np.random.randint(0, 2, len(msg))

# which  would be used as follows

class Sender(Agent):
    def __init__(self, unique_id, model):
        super().__init__(unique_id, model)
        self.protocol = random_protocol()
    
    def step(self):
        message = np.random.randint(0, 2, self.model.message_length)
        encoded_message = self.protocol(message)
        self.model.sent_message = encoded_message

This could be done by introducing reinforcement learning techniques to allow the agents to adapt and learn better encoding/decoding strategies based on feedback from the environment. This would enable the agents to optimize their protocols for improved communication performance in noisy channels.