Supabase RLS policy issue

I am trying to get or create some data in Supabase. I am using Python(>= 3.9) Fast API and vercel for deployment. The issue is:

{
    "error": "Failed to get history: {'code': '42501', 'details': None, 'hint': None, 'message': 'new row violates row-level security policy for table \"chat_history\"'}"
}

When a single user is trying to access the DB is fine, but when multiple users try to access the DB at the same time it returns an error like this to every other user except one. I have tried changing RLS policies, read many documentations but the issue remains the same.

My table schemas and RLS policies:

CREATE TABLE chat_history (
  chat_id UUID PRIMARY KEY DEFAULT uuid_generate_v4(),
  user_id UUID NOT NULL REFERENCES auth.users(id) ON DELETE CASCADE,
  messages JSONB NOT NULL DEFAULT '[]',
  updated_at TIMESTAMP WITH TIME ZONE DEFAULT CURRENT_TIMESTAMP
);

CREATE INDEX idx_chat_history_user_id ON chat_history(user_id);


CREATE POLICY "Users can view their own chat history"
ON public.chat_history
FOR SELECT
TO authenticated
USING (
  user_id = auth.uid()
);


CREATE POLICY "Users can insert their own chat history"
ON public.chat_history
FOR INSERT
TO authenticated
WITH CHECK (
  user_id = auth.uid()
);


CREATE POLICY "Users can update their own chat history"
ON public.chat_history
FOR UPDATE
TO authenticated
USING (
  user_id = auth.uid()
)
WITH CHECK (
  user_id = auth.uid()
);


CREATE POLICY "Users can delete their own chat history"
ON public.chat_history
FOR DELETE
TO authenticated
USING (
  user_id = auth.uid()
);

Python function:

async def _get_or_create_chat_record(self, user_id: str):
    """Get or create a chat history record for the user"""
    # Check if a chat record already exists
    try:
        response = supabase.table("chat_history").select("*").eq("user_id", user_id).execute()
        logger.info(f"Checking chat history for user {user_id}: {response}")
        if response.data and len(response.data) > 0:
            # Chat record exists, return it
            return response.data[0]
        else:
            # Create new chat record
            insert_response = supabase.table("chat_history").insert({
                "user_id": user_id,
                "messages": []  # Empty array of messages
            }).execute()
            
            if not insert_response.data:
                logger.error(f"Failed to create chat history record: {insert_response}")
                raise Exception("Failed to create chat history record")
            
            logger.info(f"Insert response {insert_response.data[0]} for user {user_id}")
            return insert_response.data[0]
    except Exception as e:
        logger.error(f"Error getting or creating chat record for user {user_id}: {str(e)}")
        raise


async def get_user_supabase(request: Request):
    """
    Dependency to extract and validate Supabase Auth user from Authorization header.
    """
    auth_header = request.headers.get("Authorization")
    if not auth_header or not auth_header.startswith("Bearer "):
        raise HTTPException(status_code=401, detail="Missing or invalid Authorization header")
    access_token = auth_header.split(" ")[1]
    try:
        user_response = supabase.auth.get_user(jwt=access_token)
        if not user_response or not user_response.user:
            raise HTTPException(status_code=401, detail="Invalid or expired token")
        return {
            "supabase": supabase,
            "user": user_response.user
        }
    except Exception as e:
        raise HTTPException(status_code=401, detail=f"Authentication error: {str(e)}")

I am passing the supabase client through Apis like this:

@app.post("/chat", response_model=ChatResponse)
async def chat(request: ChatRequest, supabase_client = Depends(get_user_supabase)):

PS: I have also tried with turning off RLS, then also it works fine!

If needed more info please let me know!