Are you using any apps that force stop other apps?
(Greenify or anything like it?)
Force stopping an app often can turn Accessibility off.
That is because for Accessibility to work, those apps have to constantly run.
If the app is stopped, then the Accessibility for that app has to be denied.
And if your device is a low memory device, then it may need to turn off apps to make room for other apps to run.
Also, if you have too many apps using Accessibility, it can slow the device down to a crawl, making it more likely for apps to be shut down.
I have found that you can run one or two apps per GB of RAM (at least on my cheap devices) without noticing it too much, but you can really tell if you exceed that.
Android can and will turn apps off if more memory needs to be allotted to other apps in the foreground.
If apps are installed onto an SD card, this can also cause problems.