یک اتوماتای تصادفی بصورت پنج‌تایی تعریف می‌شود که تعداد اقدامهای اتوماتا، تعداد اقدامهای اتوماتا، مجموعه اقدامهای اتوماتا، مجموعه ورودیهای اتوماتا، تابع تولید وضعیت جدید، تابع خروجی که وضعیت فعلی را به خروجی بعدی نگاشت می‌کند و مجموعه وضعیتهای داخلی اتوماتا در لحظه n، می‌باشند.

مجموعه شامل خروجیهای (اقدامهای) اتوماتا است که اتوماتا در هر گام یک اقدام از r اقدام این مجموعه را برای اِعمال بر محیط انتخاب می‌نماید. مجموعه ورودی‌ها () ورودیهای اتوماتا را مشخص می‌کند. توابع F و G وضعیت فعلی ورودی را به خروجی بعدی (اقدام بعدی) اتوماتا نگاشت می‌کنند. اگر نگاشتهای F و G قطعی باشند، اتوماتا یک اتوماتای قطعی[۱] نامیده می‌شود. در حالتیکه نگاشتهای F و G تصادفی باشند، اتوماتا یک اتوماتای تصادفی نامیده می‌شود.

اتوماتای یادگیر به دو گروه اتوماتای با ساختار ثابت[۲] و اتوماتای با ساختار متغیر[۳] تقسیم بندی می‌گردند. در اتوماتای تصادفی با ساختار ثابت احتمال اقدامهای اتوماتا ثابت هستند. درحالیکه در اتوماتای تصادفی با ساختار متغیر احتمالات اقدامهای اتوماتا در هر تکرار بِروز می‌شوند. در اتوماتای یادگیر با ساختار متغیر، تغییر احتمالهای اقدامها بر اساس الگوریتم یادگیری انجام می‌شود. همچنین در اتوماتای یادگیر با ساختار متغیر، وضعیت داخلی اتوماتا توسط احتمالات اقدامهای اتوماتا بازنمایی می‌شوند. در واقع اتوماتا بصورت یک state-output automata در نظر گرفته می‌شود که خروجی آن معادل با وضعیت داخلی آن می‌باشد. وضعیت داخلی اتوماتا در لحظه n را با بردار احتمال اقدامهای اتوماتا P(n) که در زیر آمده است، نشان داده می‌شود.

 
بطوریکه  
(‏۲‑۱)

در آغاز فعالیت اتوماتا، احتمال اقدامهای آن با هم برابر و مساوی می‌باشند. (که r تعداد اقدامهای اتوماتا می‌باشد.)

[۱] Deterministic Automata

[۲] Fixed Structure Automata

[۳] Variable Structure Automata